Higher-order components in hypergraphs

[https://arxiv.org/pdf/2208.05718.pdf]

Introduction

pair-wise vs. higher-order , 오랜만에 들고온 주제죠. Relation 은 1:1 , 1:N 으로 보는게 좋을지에 대한 논의는 끝이 없는것 같습니다. 특정 상황에 따라 모두 장단이 뚜렷하기에 목적성을 가지고 어떤 그래프 형태가 좋을지에 대해 끊임없이 고민한다면 좋은 그래프가 탄생하는 맥락과 비슷해보입니다. 본 논문은 HOC (Higher-order component)가 dynamics of the hypergraph에 어떻게 영향을 끼치는지 연구한 결과를 보여줍니다. 과연 group-wise 한 component 가 contagion dynamics 에 영향을 끼칠까요?

preliminary

Higher-order graph vs. hypergraph

In summary, a hypergraph is a generalization of a graph where an edge can connect any number of vertices, whereas a higher-order graph extends this concept further by allowing higher-order relationships involving more than two vertices, represented by simplices. Both structures provide more expressive ways to model complex relationships, but higher-order graphs offer a more versatile and powerful representation.

summary

영향이 끼치는지 검증해보기 위해 2가지 아이디어가 들어갑니다. 1. original(real-world) 를 higher-order graph 형태로 샘플링한 그래프 2. Higher-order graph component(HOC) 와 subgroup(higher-order) 관계 여부 체킹 이 두가지 과정으로부터 결국 preassigned vs. random subgraph 에서 결과가 어떻게 다르며, Higher-order graph 에 higher order component 와 연결관계가 있을시에 , SIR 모델 결과는 어떻게 다를까?  라는 점을 실험합니다.

결론적으로 차이가 있다고 합니다. ginat HOC가 존재할 때, 발병이 발생하는 매개변수 공간은 훨씬 더 크며, 이는 '’’HOC 가 존재하지 않을때보다 발병할 확률 즉 , SIR 의 susceptible 가 크다고 합니다. the system is more prone to outbreaks than that without HOC. ’’’

insight

군중심리로만 여겨졌던 부분이 정량화되어 연구된 결과라고 생각합니다. 개인이 속해있는 커뮤니티의 갯수가 정말 많이 늘어나고 있는 적절한 시기에 나온 베이스라인과 같은 논문이라고 판단되기에 imporvement for room 빈방이 굉장히 많아 보이는 주제라고 생각되네요.

Kùzu 0.0.3 Release

[https://kuzudb.com/blog/kuzu-0.0.3-release.html]

[https://github.com/kuzudb/kuzu/blob/9cd03095612e012396cd2297d2bae301f1ddab54/tools/python_api/src_py/torch_geometric_feature_store.py#L14]

잘합니다. 정말 잘합니다. 데이터베이스계 신흥강자로 RDB 에 duckDB가 있다면 GDB에는 kuzudb가 있다 라고 말할 수 있을정도로 트렌디하며, 기본에 충실한 오픈소스입니다. 현재 scalable ML with DB 라는 콘셉이 machine learning industry 에 불고 있습니다. 약간의 TMI 를 더하자면 nvidia 의 cugraph 에서도 마찬가지로 graph-all-in-one with GPU 콘셉으로 저장,분석,예측을 구현한 뒤 공격적인 마케팅을 펼치고 있습니다.

다시 돌아와서, 예전에 한 번 언급드렸었죠. Large graph data 을 유연하게 저장 및 불러오기를 할 수 있게끔 torch_geometric 에서 backend low-level function을 제공했었습니다. 본 아티클의 주요 쟁점은 kuzudb에서 앞서 언급한 backend 기능 graphstore,featurestore 을 활용해서 자신들의 db에 torch_geometric backend 를 접목한 결과라고 보시면 되겠습니다.

단순하게 접목은 누구나 다 할 수 있습니다. 하지만 kuzudb 는 ‘buffer manager’ ,’data type’, ‘query optimizer’ 등 요소들을 통해 저장 조회 불러오기 등의 성능을 향상시킵니다. 이 모든 기반에는 핵심 기술인 ‘factorization’이 존재하는데요. 간단하게 말해서 (a)-[b]→(c) 과 같은 조회 상황에서 발생하는 카테시안 곱을 최적화하게끔 테이블을 분해하여 scanning time 을 줄이는 기능이라고 보시면 되겠습니다.

model dominant 가 확정시 되어지고 있는 추세에서 이제는 data 를 어떻게 핸들링할 수 있는지 몇 tb , pb 를 다룰수 있는지에 대한 역량이 중요시되어지고 있는 가운데 더더욱 각광받을 기술이 본 포스팅에 나와있는것과 같이 data를 잘 다루는 기술이지 않을까 싶네요.

DGL v1.1.0 release

https://github.com/dmlc/dgl/releases/tag/1.1.0

한동안 잠잠했던 DGL 이 1.1.0 release 했습니다. 주요 내용은 다음과 같습니다.

• Sparse API improvement
• Datasets for evaluating graph transformers and graph learning under heterophily
• Modules and utilities, including Cugraph convolution modules and SubgraphX
• Graph transformer deprecation
• Performance improvement

특히 주목해서 보시면 좋을 부분은 Sparse 입니다. 그래프에서 Sparse matrix handling 은 엊그제 AI expo Kaist 기술교류회에서 발표를 할 정도로 굉장히 중요한 부분이라고 할 수 있습니다. DGL에서 그 중요한 부분을 굉장히 간단하게 구현할 수 있게 제공해두었으니 꼭 한 번 경험해보시는걸 추천드립니다.

jax vs pytorch.

original post ; twitter @zhu_zhaocheng

code ; https://colab.research.google.com/drive/1CBcPN-PdRsWpBMCjJkdDVClLq_tvf9Rg?usp=sharing#scrollTo=WfMOP-H32Wmk

과연 TPU 가 GPU 보다 우월할까요? 원작자분의 허락을 받아 재밌는 내용을 공유드립니다. OOM에 대해 많은 스트레스가 있으셨던 분들이 보면 좋을 자료입니다. large graph 를 prediction 하는 상황에서 JAX , JIT(just in time) , pytorch 등의 framework 에서는 어떤 결과를 보일지에 대해 간단히 실험해보았네요.

Message passing on homogeneous graphs

Without JIT, JAX is 8.7% slower than PyTorch.

With JIT, JAX is 9.6% faster than PyTorch. JAX automatically fuses the operations to reduce memory.

torch.compile is 49.2% faster than torch.jit.script.

Based on T4 GPU available in Colab.

Profile on regular-sized inputs.

• JAX: 33.3ms
• JAX + JIT: 17.8ms
• PyTorch: 30.4ms
• PyTorch + JIT: 29.1ms
• PyTorch + compile: 19.5ms
• PyTorch Scatter: 28.7ms
• PyTorch sparse tensor: 44.4ms

Profile on large inputs.

• JAX: OOM
• JAX + JIT: 541ms
• PyTorch: OOM
• PyTorch + JIT: OOM
• PyTorch + compile: OOM
• PyTorch Scatter: OOM
• PyTorch sparse tensor: 817ms

코랩으로 간단 명료하게 잘 정리가 되어있으니, 시간 되실때 한 번 왜 TPU가 유리할까, 본인의 ML infra 와 비교해보며 무엇이 최적의 수단일까 라는 고민을 필두로 실행해보시는걸 추천드립니다.

[graphinterview]

일전에 언급드린 maxime 과의 인터뷰를 홈페이지에 포스팅해놓았습니다. 알찬내용 한가득이니 꼭 한 번 보시는걸 추천드립니다 :)

Next interview , Machine learning engineer Sumit Kumar @META

많은 기대 부탁드립니다.