Hypergraph Link Prediction via Hyperedge Copying

Xie He, Philip S. Chodrow, Peter J. Mucha · 2025

Read Hypergraph Link Prediction via Hyperedge Copying by Xie He, Philip S. Chodrow, Peter J. Mucha (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-02386.txt.

Introduction

Xie He, Philip Chodrow, and Peter Mucha model how group links form over time in this 2025 paper. A hypergraph links sets of nodes at once, not just pairs, and real ones keep growing. Their model builds new group links by copying older ones with some noise.

The copying model reproduces several patterns seen in real hypergraphs, and the authors derive how node degrees, group sizes, and overlaps should look under it. They also show which real patterns the model misses. A fast fitting method learns the model from data with millions of nodes and links. On a link prediction test, a version with just eleven settings rivaled large neural networks.

Catalog record

CREATORXie He, Philip S. Chodrow, Peter J. Mucha
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE88 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-02386

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Hypergraph Link Prediction via Hyperedge Copying Thanks: X.H. is a research scientist at Microsoft Research. Thanks: P.S.C. is an assistant professor of computer science at Middlebury College. Thanks: P.J.M. is the Jack Byrne Distinguished Professor of Mathematics at Dartmouth College. Xie He, Philip S. Chodrow, Peter J. Mucha Abstract . We propose a generative model of temporally-evolving hypergraphs in which hyperedges form via noisy copying of previous hyperedges. Our proposed model reproduces several stylized facts from many empirical hypergraphs, is learnable from data, and defines a likelihood over a complete hypergraph rather than ego-based or other sub-hypergraphs. Analyzing our model, we derive descriptions of node degree, edge size, and edge intersection size distributions in terms of the model parameters. We also show several features of empirical hypergraphs which are and are not successfully captured by our model. We provide a scalable stochastic expectation maximization algorithm with which we can fit our model to hypergraph data sets with millions of nodes and edges. Finally, we assess our model on a hypergraph link prediction task, finding that an instantiation of our model with just 11 parameters can achieve competitive predictive performance with large neural networks. Introduction Many complex systems are composed of simple components participating in multi-way interactions. Such systems — often called higher-order networks [ 10 ] to distinguish them from networks composed of only pairwise interactions — have received much attention in recent years. Higher-order networks preserve richer structural information about a system and therefore admit a broader array of measures, dynamics, and algorithms than their pairwise counterparts [ 7 , 6 , 13 ] . Higher-order networks are frequently represented as either hypergraphs or simplicial complexes [ 3 ] . Whether a given system demands a higher-order representation, and which one to choose, are subtle modeling questions [ 42 ] driven by both the data analysis techniques to be used and the structure of the data itself. Hypergraphs are among the most flexible data structures for representing higher-order networks. In hypergraphs, each multi-way interaction is represented by an edge consisting of a set of nodes of arbitrary finite size. While simplicial complex representations require that every subset of every edge is also present in the data, hypergraphs require no such stipulation. Empirically, many hypergraphs come close to satisfying this subset inclusion criterion, but many others do not [ 23 ] . While many hypergraph data sets include only the memberships of nodes in edges, other data sets may include node attributes [ 4 ] , directedness or generalized node-edge roles [ 18 , 15 ] , and temporal information about the arrival or duration of interactions [ 27 , 33 ] . The latter case is often described under the heading of temporal hypergraphs , and is our modeling focus in this paper. Some examples of systems naturally represented by temporal hypergraphs include group socializing, email communication, and scholarly collaboration [ 34 , 38 , 12 ] . A common aim in modeling temporal hypergraphs is link prediction, first popularized for dyadic graphs [ 28 ] : given observations of the hypergraph up to a specified time, we aim to predict which possible new edges are likely to form in the future. The link prediction problem in hypergraphs has a wide range of applications: in collaboration networks, predicting future collaborations among multiple entities can aid in resource allocation and project planning [ 47 ] ; in biological systems, forecasting interactions among a set of molecules can contribute to drug discovery and understanding molecular processes [ 41 ] ; in logistics and supply chain management, predicting future connections in a hypergraph can optimize the flow of goods and resources [ 40 ] . The problem of link prediction in hypergraphs was popularized by Benson et al. [ 8 ] and has since received treatment from a wide range of approaches [ 29 , 46 ] , with techniques including linear discriminative models [ 8 ] , neural discriminative models [ 44 ] , statistical generative models [ 37 ] , and mechanistic generative models [ 9 , 2 , 20 , 19 ] . We take a mechanistic approach to the modeling of temporal hypergraphs. Our modeling framework is motivated by a simple, fundamental difference between hypergraphs and dyadic graphs. In dyadic graphs, all edges contain two nodes (ignoring self-loops). Any pair of edges can therefore intersect on zero, one, or two nodes. The number of two-edge motifs [ 31 ] in undirected graphs (in which self-loops are disallowed but multiedges are allowed) is therefore three. In contrast, in hypergraphs, an edge of size i may intersect with another edge of size j on a set of any size k\leq\min\{i,j\} . The number of possible two-edge motifs in a hypergraph [ 26 , 30 ] with maximum edge-size \bar{k} is therefore O(\bar{k}^{3}) , since the sizes of two edges, as well as the size of the intersection can all be distinguished. A wide range of intersection behavior is observed in empirical hypergraph data [ 25 ] , at rates much higher than explained by simple null models [ 14 ] . Several generative models have been proposed which produce large hypergraph edge intersections [ 24 ] . The model of Lee, Choe, and Shin [ 25 ] reproduces several empirical intersection patterns in a hypergraph with specified edge-size and node degree distributions. Because these features of the data are specified in advance, the model is statistically generative but does not model mechanistic evolution in growing hypergraphs. The Correlated Repeated Unions (CRU) model of Benson, Kumar, and Tomkins [ 9 ] is an explicitly mechanistic and temporal hypergraph model: arriving edges are formed as unions of noisy copies of previous edges. Copy models have a rich history in network science, serving, for example, as an early alternative to preferential attachment as a mechanistic explanation for heavy tails in the degree sequences of dyadic graphs [ 21 , 39 , 43 , 35 ] . The CRU model is designed to generate hypergraphs in which the same subsets of nodes appear in multiple edges. This model, however, is designed for subsampled hypergraphs which may be viewed as single “sequences of sets.” Applying the model to a full hypergraph dataset requires the researcher to subsample the data into one or more such sequences; this limits the model’s ability to describe hypergraphs in which seemingly disparate sequences may merge, and also prevents the researcher from evaluating a model likelihood on the complete data. Roh et al. [ 36 ] details the degree distribution and edge-size distribution for a model of growing hypergraphs with preferential linking in which the evolution of the hypergraph is based entirely on adding new nodes to current edges and nodes. Our proposed model is perhaps most similar to the hypergraph preferential attachment models proposed by Avin et al. [ 2 ] and Giroire et al. [ 20 ] involve several types of updates to the hypergraph, such as isolated vertex addition and multiple types of edge addition. In each timestep, one of these actions is selected and performed. In contrast, our model involves a single, multipart update step. Our proposed Hyperedge Copy Model (HCM) employs a simple edge-copying growth mechanism.

Read the complete text