26년 3월 4주차 그래프 오마카세

Graphs are maximally expressive for higher-order interactions

Graphs are maximally expressive for higher-order interactions

We demonstrate that graph-based models are fully capable of representing higher-order interactions, and have a long history of being used for precisely this purpose. This stands in contrast to a common claim in the recent literature on “higher-order networks” that graph-based representations are fundamentally limited to “pairwise” interactions, requiring hypergraph formulations to capture richer dependencies. We clarify this issue by emphasizing two frequently overlooked facts. First, graph-based models are not restricted to pairwise interactions, as they naturally accommodate interactions that depend simultaneously on multiple adjacent nodes. Second, hypergraph formulations are strict special cases of more general graph-based representations, as they impose additional constraints on the allowable interactions between adjacent elements rather than expanding the space of possibilities. We show that key phenomenology commonly attributed to hypergraphs -- such as abrupt transitions -- can, in general, be recovered exactly using graph models, even locally tree-like ones, and thus do not constitute a class of phenomena that is inherently contingent on hypergraphs models. Finally, we argue that the broad relevance of hypergraphs for applications that is sometimes claimed in the literature is not supported by evidence. Instead it is likely grounded in misconceptions that network models cannot accommodate multibody interactions or that certain phenomena can only be captured with hypergraphs. We argue that clearly distinguishing between multivariate interactions, parametrized by graphs, and the functions that define them enables a more unified and flexible foundation for modeling interacting systems.

arXiv.orgTiago P. Peixoto

• 그래프 연구를 하다 보면 최근 몇 년 사이 하이퍼그래프(Hypergraph)라는 단어를 점점 더 자주 마주치게 됩니다. 그리고 이 흐름에는 대체로 비슷한 주장이 따라붙습니다.

• 이 주장은 현재 네트워크 과학 분야에서 거의 정설처럼 받아들여지고 있고, 그 위에 동기화, 전염병 확산, 생태계 안정성 분석 등 다양한 연구가 쌓여 있습니다.
• 이번 주 소개할 논문은 이 전제 자체에 정면으로 이의를 제기합니다. 해당 논문에서 던지는 저자들의 메시지는 명료합니다. 그래프는 처음부터 고차 상호작용을 표현할 수 있었고, 오히려 하이퍼그래프가 그래프의 특수한 경우에 불과하다.
• 물리학, 복잡계 과학, 그래프 이론을 넘나드는 탄탄한 논거를 갖춘 이 포지션 페이퍼는, 유행하는 프레임워크를 당연히 여기기 전에 한 번쯤 멈춰 서게 만드는 논문입니다. 현재 하이퍼그래프 기반 모델을 사용하거나 검토 중인 분, GNN 아키텍처 선택 시 그래프 vs. 하이퍼그래프 표현력 문제를 고민해본 분, 혹은 가지고 있는 데이터에 하이퍼그래프를 써야 하는지 의문이 드셔본 분들이라면 읽어보시는 것을 추천드립니다.
• 해당 논문을 깊게 이해하는 데 도움될 수 있는 자료들도 같이 첨부해드리니 참고해보시면 좋을 것 같습니다.

Complex Contagions and the Weakness of Long Ties on JSTOR

Damon Centola, Michael Macy, Complex Contagions and the Weakness of Long Ties, American Journal of Sociology, Vol. 113, No. 3 (November 2007), pp. 702-734

The University of Chicago Press

Network reconstruction and community detection from dynamics

We present a scalable nonparametric Bayesian method to perform network reconstruction from observed functional behavior that at the same time infers the communities present in the network. We show that the joint reconstruction with community detection has a synergistic effect, where the edge correlations used to inform the existence of communities are also inherently used to improve the accuracy of the reconstruction which, in turn, can better inform the uncovering of communities. We illustrate the use of our method with observations arising from epidemic models and the Ising model, both on synthetic and empirical networks, as well as on data containing only functional information.

arXiv.orgTiago P. Peixoto

Hypergraph reconstruction from network data - Communications Physics

Higher-order interactions intervene in a large variety of networked phenomena, from shared interests known to influence the creation of social ties, to co-location shaping networks embedded in space, like power grids. This work introduces a Bayesian framework to infer higher-order interactions hidden in network data.

NatureJean-Gabriel Young

• Higher-Order Network(HON) 관련 연구자료에서 반복되는 주장의 출발점은 이렇습니다. "그래프의 엣지는 두 노드 사이의 독립적인 상호작용을 나타내므로, 그 함수는 결국 쌍별 항의 합으로 분해된다."
• 저자들은 이 해석이 근본적으로 잘못되었다고 지적하며, 그래프는 처음부터 쌍별 상호작용만 하는 구조가 아니라는 사실을 주장 강조합니다.
  • 그래프는 누구와 상호작용하는지 그 도메인을 정의할 뿐, 어떻게 상호작용하는지를 강제하지 않습니다. 한 노드의 이웃 집합이 결정되면, 그 위에 정의되는 함수는 이웃 전체를 동시에, 비선형적으로 고려하는 임의의 다변수 함수가 될 수 있습니다.
  • Kauffman의 Random boolen 네트워크부터 complex contagion, bootstrap(k-core) 퍼콜레이션까지, 수십 년간 그래프 기반 모델들은 이미 고차 상호작용을 당연하게 다루어 왔습니다. 즉, 그래프 = 쌍별관계 이라는 등식은 이전의 사실과도 맞지 않습니다.
• 하이퍼그래프는 하이퍼엣지라는 추가 구조를 도입함으로써, 사실상 노드 함수의 형태에 제약을 추가합니다. 하이퍼엣지가 존재한다는 것은, 노드 각각의 함수에 동일한 결합 함수가 대칭적으로 등장해야 한다는 조건을 의미합니다. 그 결과, 하이퍼그래프가 표현할 수 있는 상호작용의 공간은, 아무 제약 없이 다변수 함수를 정의할 수 있는 일반 그래프 기반 모델보다 좁습니다.
  • 따라서 하이퍼그래프 모델로 관찰 가능한 모든 현상은 반드시 그래프 기반 모델로도 관찰 가능하며, 그 역은 일반적으로 성립하지 않습니다. 자연스럽게 "하이퍼그래프는 그래프의 일반화가 아니라 특수화된 케이스"라는 핵심 주장을 나타냅니다.
• 설명 내용을 가볍게 정리해보면, 하이퍼그래프가 표현할 수 있는 상호작용의 공간은 아무 제약 없이 다변수 함수를 정의할 수 있는 일반 그래프 기반 모델보다 좁으며, 하이퍼그래프 모델로 관찰 가능한 모든 현상은, 반드시 그래프 기반 모델로도 관찰 가능하며 그 역은 일반적으로 성립하지 않습니다.
• 더 나아가, 저자들은 멀티레이어 네트워크가 하이퍼그래프를 완전히 포함하면서도 더 일반적인 구조임을 보입니다. (표현력의 포함 관계: 일반 그래프 기반 모델 ⊇ 멀티레이어 네트워크 ⊇ 하이퍼그래프) 즉, hyperedge의 존재로 인한 구조적인 복잡도와 상호작용 함수의 복잡도는 독립된 개념입니다. 쉽게 말하면, 복잡한 상호작용을 표현하기 위해 복잡한 구조가 반드시 필요하지는 않음을 암시합니다.

• HON 연구에서 하이퍼그래프의 우월성을 뒷받침하는 주요 근거로 자주 등장하는 세 가지 현상(Abrupt synchronization, Simplicial contagion model, 그리고 Ecosystem stability analysis)이 있습니다. 저자들은 이 각각의 사례를 검토하며, 공통된 문제점을 찾아냅니다.
• 이 연구들의 분석이 주로 평균장(mean-field) 근사에 기반하고 있는데, 바로 이 평균장 방정식이 하이퍼그래프 구조 자체를 사실상 무시한다는 것입니다.
  • 평균장 근사에서 하이퍼엣지의 인접 텐서를 앙상블 평균으로 치환하면, 결과적으로 얻어지는 방정식은 하이퍼그래프가 아닌 클리크 구조조차 없는 locally tree-like 그래프와 동일합니다. 즉, 하이퍼그래프를 써서 분석했지만 그 분석이 실제로 보여주는 것은 하이퍼그래프가 필요하지 않다는 사실인 셈입니다.
• Bootstrap 퍼콜레이션, 상호의존 퍼콜레이션과 같이 그래프에서 이미 잘 알려진 갑작스러운 전이 현상과 비교해보면, 이른바 하이퍼그래프에서만 나타나는 현상들은 사실 Cooperative Multivariate Interaction이 만들어내는 것이며, 하이퍼엣지라는 구조는 그 메커니즘에 관여하지 않습니다.

• 저자들은 하이퍼그래프의 필요성을 주장하는 경험적 근거들을 네 가지 유형으로 분류하고, 이들의 취약성을 지적합니다.
  • Toy model의 존재 : 특정 현상을 재현하는 하이퍼그래프 모델이 있다는 것은, 그 현상을 설명하는 데 하이퍼그래프가 필수라는 증거가 되지 않습니다. 대안적인 그래프 기반 모델과의 체계적 비교 없이는 의미 있는 주장이 될 수 없습니다.
  • 이분 그래프(bipartite graph)의 재해석 : 공동저자 네트워크처럼 이분 그래프로 분석되던 데이터를 하이퍼그래프로 "재해석"하는 것은 수학적으로 동치인 표현 방식을 바꾸는 것에 불과합니다.
  • 그래프 데이터에서 하이퍼그래프 추출 : 클리크를 하이퍼엣지로 직접 대응시키는 휴리스틱 방법은 역문제의 비식별성 문제로 인해 원칙적 근거가 없습니다.
  • 시계열 데이터로부터의 추론 : 상관관계 기반 방법은 직접 상호작용과 간접 상호작용을 구분하지 못하는 구조적 한계가 있으며, 복잡도 패널티를 고려한 모델 선택이 수행된 사례도 없습니다.
• 즉, 하이퍼그래프를 쓸 수 있다는 것과 하이퍼그래프를 써야 한다는 것은 전혀 다른 주장입니다. 대부분의 연구에서는 그 전자를 보여줄 뿐, 후자를 뒷받침하는 근거는 거의 없습니다.

• 이 논문이 전달하는 핵심은 한 문장으로 압축됩니다.

• 물론 저자들은 하이퍼그래프가 쓸모없다고 말하는 것이 아닙니다. 통계물리학, 위상 데이터 분석, 신호 처리 등 하이퍼그래프가 유용하게 활용되는 맥락은 분명히 존재합니다. 이 논문이 비판하는 것은 하이퍼그래프 자체가 아니라, 그래프는 쌍별 상호작용만 다룰 수 있다는 잘못된 전제 위에 세워진 주장들입니다.
• 저를 포함해서 많은 연구자분들이 그래프 연구를 하면서 "내 데이터를 단순 dyadic한 그래프보다 좀 더 더 복잡한 구조로서 표현할 필요가 있지 않을까?" 라는 고민이 자연스럽게 드실 수 있을 겁니다. 하지만 이 논문은 그 직전에 한 가지 질문을 먼저 던질 것을 권합니다.
  • 지금 내가 쓰는 그래프 위에서 정의하는 함수가 정말 표현하고 싶은 것을 표현하고 있는가?
• 구조를 바꾸기 전에 함수를 다시 바라보는 것. 이 논문 또한, 앞서 오마카세를 통해 공유해온 핵심 인사이트들과 같은 결에서, 새로운 해답이 반드시 새로운 구조에서만 나오는 것은 아니라는 점을 보여줍니다.

[Contact Info]

Gmail: jhbae1184@akane.waseda.jp

Twitter (X): @jhbae1184

LinkedIn