2025 | GEON LEE*, Kim Jaechul Graduate School of AI, KAIST, South Korea FANCHEN BU*, School of Electrical Engineering, KAIST, South Korea TINA ELIASI-RAD, Khoury College of Computer Sciences, Northeastern University, USA KIJUNG SHIN, Kim Jaechul Graduate School of AI, KAIST, South Korea
This survey provides a comprehensive overview of hypergraph mining, covering patterns, tools, and generators. Hypergraphs, which are a generalization of graphs, are used to model higher-order interactions in real-world systems, such as collaboration networks, protein interactions, and item co-purchases. The mathematical complexity of hypergraphs offers both opportunities and challenges for mining, which aims to discover and understand recurring structural properties (patterns) in these networks.
The survey categorizes tools used for hypergraph mining into three main types: null models, structural elements, and structural quantities. Null models, such as the configuration model and the random filling model, are used to generate random hypergraphs for comparison with real-world data. Structural elements include substructures like triangles, higher-order network motifs, and hypergraph motifs, which help in understanding the underlying structures. Structural quantities are numerical tools that measure specific aspects of hypergraphs, such as group degrees, hypercoreness, distances, centrality scores, and transitivity.
The survey also discusses hypergraph generators, which produce synthetic hypergraphs that mimic real-world patterns. These generators are valuable for validating the understanding of real-world patterns and for simulating and evaluating hypergraph algorithms.
The structural patterns in real-world hypergraphs are categorized into static and dynamic patterns, and node-level, hyperedge-level, subhypergraph-level, and hypergraph-level patterns. Static patterns describe the characteristics of static hypergraphs or individual snapshots of temporal hypergraphs, while dynamic patterns describe the evolution over time. Node-level patterns focus on individual nodes, hyperedge-level patterns on hyperedges, subhypergraph-level patterns on specific combinations of nodes and hyperedges, and hypergraph-level patterns on the entire hypergraph.
The survey provides a detailed taxonomy for each category and discusses the practical applications of these tools and patterns. It also highlights the importance of hypergraph mining in various fields, including recommendation systems, computer vision, natural language processing, social network analysis, financial analysis, bioinformatics, and circuit design.This survey provides a comprehensive overview of hypergraph mining, covering patterns, tools, and generators. Hypergraphs, which are a generalization of graphs, are used to model higher-order interactions in real-world systems, such as collaboration networks, protein interactions, and item co-purchases. The mathematical complexity of hypergraphs offers both opportunities and challenges for mining, which aims to discover and understand recurring structural properties (patterns) in these networks.
The survey categorizes tools used for hypergraph mining into three main types: null models, structural elements, and structural quantities. Null models, such as the configuration model and the random filling model, are used to generate random hypergraphs for comparison with real-world data. Structural elements include substructures like triangles, higher-order network motifs, and hypergraph motifs, which help in understanding the underlying structures. Structural quantities are numerical tools that measure specific aspects of hypergraphs, such as group degrees, hypercoreness, distances, centrality scores, and transitivity.
The survey also discusses hypergraph generators, which produce synthetic hypergraphs that mimic real-world patterns. These generators are valuable for validating the understanding of real-world patterns and for simulating and evaluating hypergraph algorithms.
The structural patterns in real-world hypergraphs are categorized into static and dynamic patterns, and node-level, hyperedge-level, subhypergraph-level, and hypergraph-level patterns. Static patterns describe the characteristics of static hypergraphs or individual snapshots of temporal hypergraphs, while dynamic patterns describe the evolution over time. Node-level patterns focus on individual nodes, hyperedge-level patterns on hyperedges, subhypergraph-level patterns on specific combinations of nodes and hyperedges, and hypergraph-level patterns on the entire hypergraph.
The survey provides a detailed taxonomy for each category and discusses the practical applications of these tools and patterns. It also highlights the importance of hypergraph mining in various fields, including recommendation systems, computer vision, natural language processing, social network analysis, financial analysis, bioinformatics, and circuit design.