Simplicial closure and higher-order link prediction

By Austin R. Benson, Rediet Abebe, Michael T. Schaub, Ali Jadbabaie, Jon M. Kleinberg. Proceedings of the National Academy of Sciences of the United States of America, 2018

619 citations recorded by the source corpus.

Significance Networks provide a powerful abstraction for complex systems throughout the sciences by representing the underlying set of pairwise interactions, but much of the structure within these systems involves interactions that take place among more than two nodes at once. While these higher-order interactions are ubiquitous, an evaluation of the basic properties and organizational principles in such systems is missing. Here we study 19 datasets from biology, medicine, social networks, and the web and characterize how higher-order structure emerges and differs between domains. We then propose a general framework for evaluating higher-order data models based on link prediction, a task in which we seek to predict future interactions from a system’s structure and past history. 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 difference from traditional pairwise link prediction, with a greater role for local rather than long-range information in predicting the appearance of new interactions.

Subfields: Molecular Biology, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/b4394dca98b2482bf763d4e6099f89364ec8f8ff

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Molecular Biology

In Statistical and Nonlinear Physics

Citations in the corpus

Inductive Representation Learning in Temporal Networks via Causal Anonymous Walks (2021, background): “…and meaningful motifs/patterns of temporal networks; CAW-N may also be generalized to predict high-order structures ( e.g. , triangles) that correspond to some function units of temporal networks from different domains (Benson et al., 2016; 2018; Zitnik et al., 2019). feedback on the abstract.”
Dynamics on higher-order networks: a review (2022, background): “[19], which investigates datasets from different disciplines ranging from various social networks to biology and demonstrates a variety of characteristics of the higherorder structures emerging therein, is particularly noteworthy.”
Networks beyond pairwise interactions: structure and dynamics (2020, background): “VII A), to predict higher-order interactions in streaming data [116], and to study polymers [263].”
What are higher-order networks? (2021, background): “In particular, there has been work on generalizing the idea of triadic closure in networks—the tendency of two nodes to connect, if they have a mutual neighbor—to higher-order networks [26,227].”
Hodge Laplacians on graphs (2015, background): “” Unlike physical problems arising from areas such as continuum mechanics or electromagnetics, where the differentiable Hodge–de Rham theory has been applied with great efficacy for both modeling and computations [1, 2, 27, 40, 47, 58, 59], those arising from data analytic applications are likely to”
Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning (2020, background): “This task belongs to the more general class of higher-order network motif prediction tasks [49,50] and has recently attracted much signiﬁcance to [51–55].”
Random Walks on Simplicial Complexes and the normalized Hodge Laplacian (2018, methodology): “This practice has been used when, for example, the elements of \scrS are sets of authors on scientific publications [103] or sets of tags annotating questions on Stack Overflow [10].”