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 (3)

• Hierarchical structure and the prediction of missing links in networks
• Evaluating Overfit and Underfit in Models of Network Community Structure
• When Hashes Met Wedges: A Distributed Algorithm for Finding High Similarity Vectors

Cited by in corpus (123)

• 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
• A framework for second order eigenvector centralities and clustering coefficients
• Hyperlink communities in higher-order networks
• 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
• Multiplex measures for higher-order networks
• Hypercore Decomposition for Non-Fragile Hyperedges: Concepts, Algorithms, Observations, and Applications
• STruD: Truss Decomposition of Simplicial Complexes
• 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
• The structural evolution of temporal hypergraphs through the lens of hyper-cores
• How Transitive Are Real-World Group Interactions? -- Measurement and Reproduction
• 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
• Limit theorems for the cubic mean-field Ising model
• Beyond Pairwise Interactions: Unveiling the Role of Higher-Order Interactions via Stepwise Reduction
• FreSCo: Mining Frequent Patterns in Simplicial Complexes
• Motif-Based Spectral Clustering of Weighted Directed Networks
• Exploring Cohesive Subgraphs in Hypergraphs: The (k,g)-core Approach
• Core-periphery Models for Hypergraphs
• Clustering coefficients for networks with higher order interactions
• A novel similarity measure for mining missing links in long-path networks
• Fixation dynamics on 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
• Event Graphs: Advances and Applications of Second-Order Time-Unfolded Temporal Network Models
• Network interpolation
• Community Detection Using Revised Medoid-Shift Based on KNN
• Understanding and Predicting Links in Graphs: A Persistent Homology Perspective
• Unsupervised Joint $k$-node Graph Representations with Compositional Energy-Based Models
• The inverse problem beyond two-body interaction: the cubic mean-field Ising model
• Higher-order shortest paths in hypergraphs
• Link Prediction via controlling the leading eigenvector
• Community detection in hypergraphs through hyperedge percolation
• Clustering Coefficient Reflecting Pairwise Relationships within Hyperedges
• Higher-order null models as a lens for social systems
• Understanding Higher-order Structures in Evolving Graphs: A Simplicial Complex based Kernel Estimation Approach
• How Do Hyperedges Overlap in Real-World Hypergraphs? -- Patterns, Measures, and Generators
• Combinatorial Properties for a Class of Simplicial Complexes Extended from Pseudo-fractal Scale-free Web
• Simplex Closing Probabilities in Directed Graphs
• Sampling nodes and hyperedges via random walks on large hypergraphs
• Connected components in networks with higher-order interactions
• Modeling and Analysis of Tagging Networks in Stack Exchange Communities
• Uplifting edges in higher order networks: spectral centralities for non-uniform hypergraphs
• Spreader events and the limitations of projected networks for capturing dynamics on multipartite networks
• Heuristics for Link Prediction in Multiplex Networks
• Evolution of Real-world Hypergraphs: Patterns and Models without Oracles
• Edge corona product as an approach to modeling complex simplical networks
• Mean Field Analysis of Hypergraph Contagion Model
• Optimal Edge Weight Perturbations to Attack Shortest Paths
• Dynamical systems defined on simplicial complexes: symmetries, conjugacies, and invariant subspaces
• 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
• Representing Higher-Order Networks with Spectral Moments
• A nonlinear diffusion method for semi-supervised learning on hypergraphs
• Topological measures in weighted hypergraphs
• 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