Simplicial Closure and higher-order link prediction

Abstract

Networks provide a powerful formalism for modeling complex systems by using a model of pairwise interactions. But much of the structure within these systems involves interactions that take place among more than two nodes at once; for example, communication within a group rather than person-to person, collaboration among a team rather than a pair of coauthors, or biological interaction between a set of molecules rather than just two. Such higher-order interactions are ubiquitous, but their empirical study has received limited attention, and little is known about possible organizational principles of such structures. Here we study the temporal evolution of 19 datasets with explicit accounting for higher-order interactions. We show that there is a rich variety of structure in our datasets but datasets from the same system types have consistent patterns of higher-order structure. Furthermore, we find that tie strength and edge density are competing positive indicators of higher-order organization, and these trends are consistent across interactions involving differing numbers of nodes. To systematically further the study of theories for such higher-order structures, we propose higher-order link prediction as a benchmark problem to assess models and algorithms that predict higher-order structure. We find a fundamental differences from traditional pairwise link prediction, with a greater role for local rather than long-range information in predicting the appearance of new interactions.

References in corpus (22)

• Scikit-learn: Machine Learning in Python
• Statistical mechanics of complex networks
• The structure and function of complex networks
• Multilayer Networks
• Link Prediction in Complex Networks: A Survey
• Hierarchical structure and the prediction of missing links in networks
• Evolution of the social network of scientific collaborations
• Clustering and preferential attachment in growing networks
• Graph Embedding Techniques, Applications, and Performance: A Survey
• Higher-order organization of complex networks
• High-resolution measurements of face-to-face contact patterns in a primary school
• Contact patterns in a high school: a comparison between data collected using wearable sensors, contact diaries and friendship surveys
• Motifs in Temporal Networks
• Memory in network flows and its effects on spreading dynamics and community detection
• Representing higher-order dependencies in networks
• A network analysis of committees in the United States House of Representatives
• Evaluating Overfit and Underfit in Models of Network Community Structure
• Simplicial complexes: spectrum, homology and random walks
• New approaches to model and study social networks
• Cross-validation estimate of the number of clusters in a network
• Diamond Sampling for Approximate Maximum All-pairs Dot-product (MAD) Search
• When Hashes Met Wedges: A Distributed Algorithm for Finding High Similarity Vectors

Cited by in corpus (124)

• Networks beyond pairwise interactions: structure and dynamics
• Dynamics on higher-order networks: A review
• What are higher-order networks?
• Explosive higher-order Kuramoto dynamics on simplicial complexes
• Higher-order interactions shape collective dynamics differently in hypergraphs and simplicial complexes
• Social contagion models on hypergraphs
• Topological Signal Processing over Simplicial Complexes
• Random walks on hypergraphs
• Random Walks on Simplicial Complexes and the normalized Hodge 1-Laplacian
• The effect of heterogeneity on hypergraph contagion models
• Abrupt phase transition of epidemic spreading in simplicial complexes
• Higher-order motif analysis in hypergraphs
• Signal Processing on Higher-Order Networks: Livin' on the Edge ... and Beyond
• Progresses and Challenges in Link Prediction
• Inference of hyperedges and overlapping communities in hypergraphs
• Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning
• An adaptive voter model on simplicial complexes
• Beyond the clustering coefficient: A topological analysis of node neighbourhoods in complex networks
• Gender inequality and self-publication patterns among scientific editors
• The temporal dynamics of group interactions in higher-order social networks
• Hypergraph Motifs: Concepts, Algorithms, and Discoveries
• Community Detection in Large Hypergraphs
• Group interactions modulate critical mass dynamics in social convention
• Unified treatment of synchronization patterns in generalized networks with higher-order, multilayer, and temporal interactions
• How Much and When Do We Need Higher-order Information in Hypergraphs? A Case Study on Hyperedge Prediction
• Experimental analyses on 2-hop-based and 3-hop-based link prediction algorithms
• Inductive Representation Learning in Temporal Networks via Causal Anonymous Walks
• Clustering in graphs and hypergraphs with categorical edge labels
• Structural Patterns and Generative Models of Real-world Hypergraphs
• A Survey on Hyperlink Prediction
• Vector Centrality in Hypergraphs
• Flow Smoothing and Denoising: Graph Signal Processing in the Edge-Space
• D-dimensional oscillators in simplicial structures: odd and even dimensions display different synchronization scenarios
• Hyperedge overlap drives explosive collective behaviors in systems with higher-order interactions
• Epidemics on Hypergraphs: Spectral Thresholds for Extinction
• Consensus on simplicial complexes, or: The nonlinear simplicial Laplacian
• Higher-Order Components Dictate Higher-Order Contagion Dynamics in Hypergraphs
• Effective epidemic containment strategy in hypergraphs
• Hypergraphx: a library for higher-order network analysis
• Predicting Biomedical Interactions with Higher-Order Graph Convolutional Networks
• The simpliciality of higher-order networks
• Disentangling homophily, community structure and triadic closure in networks
• Simplicial degree in complex networks. Applications of Topological Data Analysis to Network Science
• Reconstructing networks
• Hypergraph reconstruction from dynamics
• HGWaveNet: A Hyperbolic Graph Neural Network for Temporal Link Prediction
• DYMOND: DYnamic MOtif-NoDes Network Generative Model
• Randomizing hypergraphs preserving degree correlation and local clustering
• Discriminating abilities of threshold-free evaluation metrics in link prediction
• The maximum capability of a topological feature in link prediction
• Centrality anomalies in complex networks as a result of model over-simplification
• Predicting hyperlinks via hypernetwork loop structure
• Dynamical robustness of network of oscillators
• Exact and sampling methods for mining higher-order motifs in large hypergraphs
• Simplex2Vec embeddings for community detection in simplicial complexes
• Investigating and Modeling the Dynamics of Long Ties
• Hyperlink communities in higher-order networks
• A framework for second order eigenvector centralities and clustering coefficients
• Higher-Order Networks Representation and Learning: A Survey
• Classification of Edge-dependent Labels of Nodes in Hypergraphs
• Nonlinear bias toward complex contagion in uncertain transmission settings
• A framework to generate hypergraphs with community structure
• STruD: Truss Decomposition of Simplicial Complexes
• Multiplex measures for higher-order networks
• Hypercore Decomposition for Non-Fragile Hyperedges: Concepts, Algorithms, Observations, and Applications
• A Hybrid Similarity-Aware Graph Neural Network with Transformer for Node Classification
• Higher-order link prediction via local information
• Edge-based Local Push for Personalized PageRank
• How Transitive Are Real-World Group Interactions? -- Measurement and Reproduction
• The structural evolution of temporal hypergraphs through the lens of hyper-cores
• SUREL+: Moving from Walks to Sets for Scalable Subgraph-based Graph Representation Learning
• Filtering higher-order datasets
• Principled Hyperedge Prediction with Structural Spectral Features and Neural Networks
• Enhancing Hyperedge Prediction with Context-Aware Self-Supervised Learning
• FreSCo: Mining Frequent Patterns in Simplicial Complexes
• Beyond Pairwise Interactions: Unveiling the Role of Higher-Order Interactions via Stepwise Reduction
• Limit theorems for the cubic mean-field Ising model
• Motif-Based Spectral Clustering of Weighted Directed Networks
• Exploring Cohesive Subgraphs in Hypergraphs: The (k,g)-core Approach
• A novel similarity measure for mining missing links in long-path networks
• Fixation dynamics on hypergraphs
• Clustering coefficients for networks with higher order interactions
• Core-periphery Models for Hypergraphs
• Local Hypergraph Clustering using Capacity Releasing Diffusion
• Interplay between Topology and Edge Weights in Real-World Graphs: Concepts, Patterns, and an Algorithm
• A simple bipartite graph projection model for clustering in networks
• Quantifying the structural stability of simplicial homology
• Community Detection Using Revised Medoid-Shift Based on KNN
• Network interpolation
• Understanding and Predicting Links in Graphs: A Persistent Homology Perspective
• Event Graphs: Advances and Applications of Second-Order Time-Unfolded Temporal Network Models
• Unsupervised Joint $k$-node Graph Representations with Compositional Energy-Based Models
• Higher-order shortest paths in hypergraphs
• Community detection in hypergraphs through hyperedge percolation
• Clustering Coefficient Reflecting Pairwise Relationships within Hyperedges
• Link Prediction via controlling the leading eigenvector
• Higher-order null models as a lens for social systems
• The inverse problem beyond two-body interaction: the cubic mean-field Ising model
• How Do Hyperedges Overlap in Real-World Hypergraphs? -- Patterns, Measures, and Generators
• Simplex Closing Probabilities in Directed Graphs
• Understanding Higher-order Structures in Evolving Graphs: A Simplicial Complex based Kernel Estimation Approach
• Combinatorial Properties for a Class of Simplicial Complexes Extended from Pseudo-fractal Scale-free Web
• Heuristics for Link Prediction in Multiplex Networks
• Uplifting edges in higher order networks: spectral centralities for non-uniform hypergraphs
• Sampling nodes and hyperedges via random walks on large hypergraphs
• Connected components in networks with higher-order interactions
• Spreader events and the limitations of projected networks for capturing dynamics on multipartite networks
• Evolution of Real-world Hypergraphs: Patterns and Models without Oracles
• Edge corona product as an approach to modeling complex simplical networks
• Modeling and Analysis of Tagging Networks in Stack Exchange Communities
• Mean Field Analysis of Hypergraph Contagion Model
• Optimal Edge Weight Perturbations to Attack Shortest Paths
• Representing Higher-Order Networks with Spectral Moments
• A nonlinear diffusion method for semi-supervised learning on hypergraphs
• Consensus dynamics on temporal hypergraphs
• Learning Short-Term and Long-Term Patterns of High-Order Dynamics in Real-World Networks
• HyperCI: A Higher Order Collective Influence Measure for Hypernetwork Dismantling
• Topological measures in weighted hypergraphs
• Dynamical systems defined on simplicial complexes: symmetries, conjugacies, and invariant subspaces
• Node similarity distribution of complex networks and its application in link prediction
• SPAN: Subgraph Prediction Attention Network for Dynamic Graphs
• Higher-Order Relations Skew Link Prediction in Graphs
• Love tHy Neighbour: Remeasuring Local Structural Node Similarity in Hypergraph-Derived Networks
• The CAT SET on the MAT: Cross Attention for Set Matching in Bipartite Hypergraphs