Hypergraph Projection and Reconstruction

Title: Hypergraph Projection and Reconstruction

Abstract: Hypergraphs generalize the concept of graphs by extending edges from node pairs to node sets of arbitrary sizes. In this talk, we discuss the implications of using a graph, instead of a hypergraph, to represent real-world interconnected systems that contain relationships of higher order by nature. Such a modeling choice typically involves a projection (clique expansion) process that maps the original hypergraph onto a graph, and is common in graph-based analysis. While hypergraph projection can potentially lead to loss of higher-order relations, there exist limited studies on the consequences of doing so, as well as possible remedies. 

We will introduce two things that fill this research gap: (1) we develop an analysis based on graph and set theory, showing two ubiquitous patterns of hyperedges at the root of structural information loss in all hypergraph projections; we also quantify the combinatorial impossibility in recovering the lost higher-order structures, assuming no additional information being available; (2) we still seek to recover the lost higher-order structures in hypergraph projection, by relaxing the problem into a learning-based setting. Under this setting, we introduce a learning-based hypergraph reconstruction method based on a key statistic of hyperedge distributions that we identified. Our reconstruction method is evaluated on real-world datasets and exhibits consistently good performance. We also demonstrate benefits of the reconstructed hypergraphs via real-world use cases.

The talk is based on joint work with Jon Kleinberg, published at ICLR 2024.

Bio: Yanbang Wang is a fourth-year Ph.D. candidate in Computer Science at Cornell University, advised by Prof. Jon Kleinberg.  He is broadly interested in network science, graph learning, and their societal impacts. His research goal is to develop more accurate, data-compatible, and socially responsible learning algorithms for large-scale, interconnected social and information systems.