Mining of Real-world Hypergraphs:
Patterns, Tools, and Generators

Geon Lee

Kim Jaechul Graduate School of AI
KAIST
Seoul, South Korea

Jaemin Yoo

Heinz College
Carnegie Mellon University
Pittsburgh, PA, USA

Kijung Shin

Kim Jaechul Graduate School of AI
KAIST
Seoul, South Korea

[New] Check out our survey on hypergraph mining (https://dl.acm.org/doi/10.1145/3719002)

[New] Check out our tutorial on hypergraph neural networks (https://sites.google.com/view/hnn-tutorial)

Summary

Group interactions are prevalent in various complex systems (e.g., collaborations of researchers and group discussions on online Q\&A sites), and they are commonly modeled as hypergraphs. Hyperedges, which compose a hypergraph, are non-empty subsets of any number of nodes, and thus each hyperedge naturally represents a group interaction among entities. The higher-order nature of hypergraphs brings about unique structural properties that have not been considered in ordinary pairwise graphs.

In this tutorial, we offer a comprehensive overview of a new research topic called hypergraph mining. Specifically, we first present recently revealed structural properties of real-world hypergraphs, including (a) static and dynamic patterns, (b) global and local patterns, and (c) connectivity and overlapping patterns. Together with the patterns, we describe advanced data mining tools used for their discovery. Lastly, we introduce simple yet realistic hypergraph generative models that provide an explanation of the structural properties.

Target audience: This tutorial is targeted at anyone interested in graph mining, social network analysis, or network science from researchers to practitioners from the industry.

Prerequisites: Basic knowledge of linear algebra and probability theory will be helpful. The tutorial will cover the necessary preliminaries and provide an intuitive overview of recent studies on the topic.

Videos

Full Tutorial (3 hours) [YouTube Link]

Teaser (20 minutes) [YouTube Link]

Slides

Part I. Introduction
[ DOWNLOAD | DROPBOX ]

Group interactions in the real-world
Power of hypergraph modeling
Data repositories and open-source software for hypergraph mining

Part II. Static Structural Patterns
[ DOWNLOAD | DROPBOX ]

Basic (node-level, hyperedge-level, and hypergraph-level) patterns
Advanced (sub-hypergraph-level) patterns
Data mining tools for static structure analysis

Part III. Dynamic Structural Patterns
[ DOWNLOAD | DROPBOX ]

Basic (node-level, hyperedge-level, and hypergraph-level) patterns
Advanced (sub-hypergraph-level) patterns
Data mining tools for dynamic structure analysis

Part IV. Generative Models
[ DOWNLOAD | DROPBOX ]

Generative models of full and sub hypergraphs
Generative models of static and dynamic hypergraphs

Presenters

Geon Lee is a Ph.D. student at the Kim Jaechul Graduate School of AI at KAIST. He received his B.S. degree in Computer Science and Engineering from Sungkyunkwan University in 2019. His research interests include graph mining and its applications, and especially, his studies of hypergraphs have appeared in major data mining venues, including VLDB, WWW, and ICDM. More details can be found at https://geonlee0325.github.io.

Jaemin Yoo is a postdoctoral research fellow in the Heinz College of Information Systems and Public Policy at Carnegie Mellon University. He received his Ph.D. and B.S. in Computer Science and Engineering from Seoul National University. His research interests include probabilistic mining and machine learning on graphs, and his work has been published in major venues including WWW, KDD, and NeurIPS. He is a recipient of the Google PhD Fellowship and the Qualcomm Innovation Fellowship. More details can be found at https://jaeminyoo.github.io.

Kijung Shin is an Ewon Endowed Assistant Professor (jointly affiliated) in the Kim Jaechul Graduate School of AI and the School of Electrical Engineering at KAIST. He received his Ph.D. from the Computer Science Department at Carnegie Mellon University in 2019. He has published more than 50 referred articles in major data mining venues, including KDD, WWW, and ICDM, and he won the best research paper award at KDD 2016. His research interests span a wide range of topics on graph mining, with a focus on scalable algorithm design and empirical analysis of real-world hypergraphs. More details can be found at https://kijungs.github.io/.

Important References and Software

Austin R Benson, Rediet Abebe, Michael T Schaub, Ali Jadbabaie, and Jon Kleinberg. Simplicial closure and higher-order link prediction. PNAS, 115(48):E11221–E11230, 2018 [LINK] [CODE]
Austin R Benson, Ravi Kumar, and Andrew Tomkins. Sequences of sets. In KDD, 2018 [LINK] [CODE]
Fanchen Bu, Geon Lee, and Kijung Shin. Hypercore Decomposition for Non-Fragile Hyperedges: Concepts, Algorithms, Observations, and Applications, Data Mining and Knowledge Discovery 37:2389–2437, 2023 [PDF] [CODE]
Giulia Cencetti, Federico Battiston, Bruno Lepri, and M ́arton Karsai. Temporal properties of higher-order interactions in social networks. Scientific reports, 11(1):1–10, 2021 [LINK]
Philip S Chodrow. Configuration models of random hypergraphs. Journal of Complex Networks, 8(3):cnaa018, 2020 [PDF]
Minyoung Choe, Jaemin Yoo, Geon Lee, Woonsung Baek, U Kang, and Kijung Shin. MiDaS: Representative sampling from real-world hypergraphs. In WWW, 2022 [PDF] [CODE]
Hyunjin Choo and Kijung Shin. On the persistence of higher-order interactions in real-world hypergraphs. In SDM, 2022 [PDF] [CODE]
Cazamere Comrie and Jon Kleinberg. Hypergraph ego-networks and their temporal evolution. In ICDM, 2021 [PDF] [CODE]
Manh Tuan Do, Se-eun Yoon, Bryan Hooi, and Kijung Shin. Structural patterns and generative models of real-world hypergraphs. In KDD, 2020 [PDF] [CODE]
Luca Gallo, Lucas Lacasa, Vito Latora, and Federico Battiston. Higher-order correlations reveal complex memory in temporal hypergraphs. arXiv preprint arXiv:2303.09316, 2023 [PDF]
Sunwoo Kim, Fanchen Bu, Minyoung Choe, Jaemin Yoo, and Kijung Shin. How Transitive Are Real-World Group Interactions? - Measurement and Reproduction. In KDD, 2023 [PDF] [CODE]
Sunwoo Kim, Minyoung Choe, Jaemin Yoo, and Kijung Shin. Reciprocity in Directed Hypergraphs: Measures, Findings, and Generators. In ICDM, 2022 [PDF] [CODE]
Jihoon Ko, Yunbum Kook, and Kijung Shin. Growth Patterns and Models of Real-world Hypergraphs. Knowledge and Information Systems, 64(11), 2883-2920, 2022 [PDF] [CODE]
Yunbum Kook, Jihoon Ko, and Kijung Shin. Evolution of real-world hypergraphs: Patterns and models without oracles. In ICDM, 2020 [PDF] [CODE]
Geon Lee, Fanchen Bu, Tina Eliassi-Rad, Kijung Shin. A Survey on Hypergraph Mining: Patterns, Tools, and Generators. arXiv preprint arXiv:2401.08878, 2024. [PDF]
Geon Lee, Minyoung Choe, and Kijung Shin. How do hyperedges overlap in real-world hypergraphs? - patterns, measures, and generators. In WWW, 2021 [PDF] [CODE]
Geon Lee, Jihoon Ko, and Kijung Shin. Hypergraph motifs: concepts, algorithms, and discoveries. PVLDB, 13(12):2256–2269, 2020 [PDF] [CODE]
Geon Lee and Kijung Shin. Temporal Hypergraph Motifs. Knowledge and Information Systems, 65(4):1549-1586, 2023 [PDF] [CODE]
Geon Lee and Kijung Shin. THyMe+: Temporal hypergraph motifs and fast algorithms for exact counting. In ICDM, 2021 [PDF] [CODE]
Timothy LaRock and Renaud Lambiotte. Encapsulation Structure and Dynamics in Hypergraphs. arXiv preprint arXiv:2307.04613, 2023. [PDF] [CODE]
Quintino Francesco Lotito, Federico Musciotto, Alberto Montresor, and Federico Battiston. Higher-order motif analysis in hypergraphs. Communications Physics, 5(1):1–8, 2022 [LINK] [CODE]
Leo Torres, Ann S. Blevins, Danielle Bassett, and Tina Eliassi-Rad. The why, how, and when of representations for complex systems. SIAM Review 63(3):435-485, 2021 [PDF]

Datasets

Dr. Austin Benson's hypergraph datasets: https://www.cs.cornell.edu/~arb/data/
Mr. Sunwoo Kim's large-scale hypergraph datasets: https://github.com/kswoo97/pcl
Mr. Sunwoo Kim's directed hypergraph datasets: https://github.com/kswoo97/hyprec

Page updated

Google Sites

Report abuse

Mining of Real-world Hypergraphs: Patterns, Tools, and Generators