PaperlayerView exact revision on arXiv

Source-linked AI summary

Simplicial Closure and higher-order link prediction

Austin R. Benson, Rediet Abebe, Michael T. Schaub, Ali Jadbabaie, Jon Kleinberg

arXiv:1802.06916v2cs.SIcond-mat.stat-mechmath.ATphysics.soc-phstat.ML

TL;DR

Pairwise network models overlook group interactions whose organizational principles remain insufficiently studied. The paper analyzes temporal higher-order structure in 19 datasets and introduces higher-order link prediction, finding domain-consistent structure, competing positive indicators of closure, and a stronger role for local information than in traditional pairwise prediction.

  • Problem

    Higher-order interactions are widespread, but their empirical organization is poorly understood because network data and analysis commonly represent relationships only pairwise.

  • Method

    The paper studies temporal group interactions across 19 datasets and evaluates future simplicial closure through higher-order link prediction.

  • Results

    Tie strength and edge density are competing positive indicators of higher-order organization, while local measures effectively predict closure and differ from traditional link prediction’s emphasis on long paths.

  • Takeaways & Limitations

    Higher-order structure varies across domains, shows consistent patterns within system types, and requires prediction methods that account for local group-level evolution.

  • Takeaways & Limitations

    Closure probabilities were measured at one point in time for each dataset, and some datasets contain only a slice of the underlying network dynamics.

Abstract

from arXiv · show

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.

1 INTRODUCTION

Higher-order group interactions are common but poorly characterized because standard network data and graph models reduce systems to pairwise links. This paper studies temporal higher-order structure across 19 datasets and introduces higher-order link prediction to evaluate how such interactions emerge.

  • Motivation: Higher-order interactions occur in settings such as coauthorship and email, but conventional graph representations do not capture group-based structure.Existing formalisms include set systems, hypergraphs, simplicial complexes, and bipartite affiliation graphs.
  • Research gap: Limited data collection and computational challenges have left the organizational principles of real-world higher-order structures largely unknown.The paper asks whether higher-order properties distinguish dataset types or are universal across datasets.
  • Approach: The study analyzes the structure and temporal evolution of 19 higher-order datasets from varied domains.The datasets contain timestamped group interactions, with multiple simplices sometimes appearing at the same time.
  • Findings: Three-way interaction features reveal distinct patterns across domains that are unavailable from the networks’ graph structure alone.This provides an initial basis for rigorous cross-domain analysis of higher-order topological interactions.
  • Simplicial closure: Simplicial closure extends triadic-closure theory by studying how node groups evolve until they coappear in a higher-order structure.Strong prior interactions between subsets of a group increase the likelihood of a simplicial closure event.
  • Benchmark: Higher-order link prediction forecasts future higher-order interactions from existing data as an evaluation framework for models of emerging higher-order structure.The framework is designed to support systematic comparison of theories and algorithms.

2 STRUCTURAL ANALYSIS OF HIGHER-ORDER NETWORKS

The paper represents higher-order interactions as timestamped simplices and analyzes open versus closed triangles, revealing diverse but domain-consistent structural patterns. Local higher-order features, especially open-triangle prevalence alongside degree or density, distinguish system domains.

  • Dataset representation: Each dataset is a collection of timestamped sets of nodes, called simplices, preserving group interactions rather than decomposing them into pairwise links.A k-node simplex contains k nodes participating in a shared interaction at a given timestamp.
  • Higher-order features: The projected graph connects node pairs that co-appear in simplices, while a clique is closed when all nodes co-appear in one simplex and open when only its pairs co-appear.Open and closed triangles cannot be distinguished by the weighted projected graph alone.
  • Higher-order features: Restricting analysis to 3-node simplices yields a near-linear relationship between open-triangle fraction and log average degree, with R2 = 0.85 versus R2 = 0.38 for the comparison model.The reported relationship demonstrates substantial structural diversity even under a restricted simplex size.
  • Higher-order features: Small simplices of at most four nodes are most common, but datasets span distinct combinations of edge density and open-triangle fraction.Observed landscapes include low- and high-density systems with small, medium, or large fractions of open triangles.
  • System-domain discrimination: The results indicate that higher-order statistics help identify local organizational mechanisms, while their values vary across contexts but remain relatively stable within a system domain.Average degree tends to be more valuable than edge density for local organizational mechanisms.

3 TEMPORAL DYNAMICS AND SIMPLICIAL CLOSURE EVENTS

Simplicial closure describes how previously open higher-order structures become closed when their nodes later coappear in a simplex. Closure probability generally rises with edge density and tie strength, although their relative importance varies by dataset and remains consistent across three- and four-node structures.

  • Temporal dynamics: 61.1%–97.4% of open triangles have three edges with overlapping activity, so temporal asynchrony does not explain most open triangles.The overlap is 89.5% for Congress committees.
  • Simplicial closure: A simplicial closure event converts an open k-clique into a new simplex containing the same k nodes.This higher-order event can occur without necessarily changing the projected pairwise graph.
  • Competing features: 102 of 113 denser configuration comparisons significantly increased closure probability, while the less dense structure was never significantly more likely to close.The comparison adds one unit-weight edge to a fixed weighted three-node configuration; p < 10^-5.
  • Competing features: 82 of 113 tie-strength comparisons significantly increased closure probability, versus only 6 significant decreases.The test converts a weak tie into a strong tie within a fixed weighted induced subgraph; p < 10^-5.
  • Competing features: Edge density and tie strength compete: weak ties close more often in some datasets, whereas two strong ties are more predictive in others.The weak-tie configuration wins in 4 of 19 datasets, while the two-strong-tie configuration wins in 6 of 19; p < 10^-5.
  • Four-node structures: The same four findings hold for four-node closure events, with tie strength measured by prior appearances of the three-node subsets.The relative importance of density and tie strength is consistent between the three-node and four-node cases.

4 HIGHER-ORDER LINK PREDICTION

The paper formulates forecasting future higher-order interactions as a link-prediction benchmark and evaluates local and longer-range models on open-triangle closure. Local tie-strength heuristics often outperform random prediction, while no single model is best across all datasets.

  • Task: The benchmark uses structural information up to time t to predict new higher-order interactions after t, accommodating mechanistic, statistical, heuristic, and supervised models.The evaluated models include classical link-prediction-inspired approaches and logistic regression.
  • Task: Higher-order link prediction forecasts which triples not yet coappearing in a simplex will later be included in one.The study focuses on open-triangle closure for scalability and simplicity.
  • Evaluation: The data are split into the first 80% of timestamped simplices for training and the final 20% for testing, with AUC-PR evaluated against a random baseline.AUC-PR is used because closure prediction is class-imbalanced.
  • Results: No single model is best across all datasets, but the proposed baseline algorithms substantially outperform random guessing.In thread datasets, harmonic and geometric means improve performance by one to two orders of magnitude.
  • Results: Harmonic and geometric means of edge weights perform well broadly, highlighting local tie strength rather than long-range path information.This differs fundamentally from traditional pairwise link prediction, where non-trivial-length paths are valuable.
  • Results: Generalized-mean performance is typically unimodal in p, maximized for p ∈ [-1, 0], and better for p < -1 than for p > 1.The reported pattern has exceptions for NDC-classes and coauth-MAG-History.
  • Results: Supervised learning performs broadly well, especially on larger coauthorship datasets, but does not always perform best, likely because of overfitting.The method can capture dataset-specific features, such as lower simplex participation predicting closure in Congress bills.

5 DISCUSSION

The study finds diverse higher-order network structure across datasets, while local features reveal system domains and predict simplicial closure. Tie strength and edge density are positive but competing indicators, and local measures outperform long-range information for higher-order link prediction.

  • 19 datasets show rich structural variety, while local egonet statistics can identify system domains.
  • Tie strength and edge density both positively indicate simplicial closure among sets of three and four nodes.
  • The more influential predictor depends on the dataset: edge density matters more in human interaction, whereas tie strength matters more for online discussion tagging.
  • Higher-order link prediction offers a general methodology for evaluating models of temporal higher-order structure.
  • Simple local measures based on generalized means of edge weights effectively predict higher-order interactions, unlike traditional link prediction's emphasis on long paths.

A DATASET COLLECTION AND CONSTRUCTION

The authors assemble timestamped group interactions into a diverse collection of higher-order datasets, representing each shared group event as a simplex.

  • The collection contains 19 datasets of timestamped interactions among groups of entities.
  • Coauthorship: In coauthorship data, nodes are authors and each simplex represents the authors of a scientific publication.
  • Stack Exchange tags: Stack Exchange tag datasets represent tags as nodes and the tags attached to each question as a simplex timestamped by posting time.
  • Email: Email datasets represent email addresses as nodes and messages sent to multiple recipients as higher-order interactions.

B TEMPORAL ASYNCHRONY AND OPEN TRIANGLES

The analysis tests whether temporal asynchrony explains open triangles by comparing the active intervals of their three edges.

  • An edge's active interval spans from the earliest to the latest timestamp of simplices containing that edge.
  • For each open triangle, the authors count pairwise overlaps among the three edges' active intervals.
  • Most open triangles have three pairwise-overlapping intervals, implying a period when all three edges were simultaneously active by Helly's theorem.
  • The authors conclude that temporal asynchrony is not a major explanation for open triangles in these datasets.

C SIMPLICIAL CLOSURE PROBABILITIES

Simplicial closure probabilities are estimated from earlier configurations of three- and four-node sets and their later appearance in a simplex.

  • The data are split into the first 80% for training and the final 20% for testing closure events.
  • 3-node closure: For three-node sets, the open configuration records how often each pair co-appeared in a simplex during training.
  • 4-node closure: For four-node sets, each triangle is classified as open, weak, or strong according to prior group co-appearance.
  • 4-node closure: The four-node analysis measures closure across 27 open configurations containing at least one triangle in the projected graph.
  • Heat maps condition future simplex appearance on the observed open configuration for three- and four-node sets.

D SIMPLICIAL CLOSURE EVENTS AT DIFFERENT POINTS IN TIME

The study tests whether simplicial closure patterns persist across different temporal slices and finds broadly stable closure trends, including positive roles for edge density and tie strength. Efficient counting procedures support closure probabilities for three- and four-node configurations.

  • Temporal consistency: Closure probabilities remain broadly similar when datasets are truncated at 40%, 60%, 80%, or 100% of their timestamped simplices.Each truncated dataset is split into an earlier 80% and later 20% interval for measuring conditional closure probabilities.
  • Temporal consistency: Edge density and tie strength are consistently positive indicators of simplicial closure events across the tested time slices.The analysis tests whether adding an edge or increasing tie strength changes closure probabilities, using a significance level of 10^-5 for edge-density effects.
  • Competing effects: The weak open triangle closes more often than the strong wedge in several collaboration and legislative datasets, whereas the strong wedge dominates in the three Stack Exchange tag networks, DAWN, and thred-like datasets.The relative ordering is dataset-dependent but remains consistent across the listed X values where reported.
  • Definitions and counting: An open configuration closes when its nodes subsequently co-appear in a simplex, and its event probability is the number of closures divided by the number of times that configuration was open.The method uses the first 80% of timestamped simplices as training data and the final 20% as test data.
  • Definitions and counting: Efficient algorithms avoid enumerating every training configuration by counting all open configurations and identifying closures directly in the test data.For three-node configurations, triangle enumeration and simplex-to-node adjacency checks recover open counts by subtracting closed triangles from total triangles.

F SCORE FUNCTIONS, HIGHER-ORDER LINK PREDICTION PERFORMANCE, AND EXAMPLE PREDICTIONS

The paper evaluates higher-order link prediction through score functions built from projected-graph information. The proposed categories range from edge weights and local neighborhoods to random walks and supervised learning.

  • Score-function categories: Higher-order link-prediction scores fall into edge-weight, local-neighborhood, random-walk, and learned logistic-regression categories.Several functions generalize traditional dyadic link-prediction methods to triples of nodes.
  • Projected-graph representation: The projected graph represents each pair of nodes by an edge weighted by the number of simplices in which they co-appear.An unweighted adjacency matrix records only whether the pair co-appears at least once.
  • Projected-graph representation: Weight-based triple scores assign larger values when the three candidate nodes have stronger pairwise ties.These scores are motivated by the positive aggregate association between tie strength and simplicial closure probability.

F.2 Local neighborhood features

Local-neighborhood scores use shared neighbors and related projected-graph structure to estimate whether a triple will close. The section also contrasts these local features with path-based and simplicial random-walk scores.

  • Local neighborhood features: Three-way common-neighbor scores count nodes that have appeared in at least one simplex with each candidate node.The score is |N(i) ∩ N(j) ∩ N(k)|, where N(x) is the projected-graph neighborhood.
  • Local neighborhood features: The three-way Jaccard coefficient normalizes common-neighbor overlap by the total neighborhoods of the candidate triple.The paper introduces this multi-way similarity score for link prediction, extending its prior use as a binary-vector similarity measure.
  • Local neighborhood features: Preferential-attachment scores use either projected-graph degrees or simplicial degrees for the three candidate nodes.The projected-graph version multiplies |N(i)|, |N(j)|, and |N(k)|, while the simplicial version multiplies |R(i)|, |R(j)|, and |R(k)|.
  • Paths and random walks: Path-based metrics assign higher scores when candidate nodes are connected by more projected-graph paths, using weighted or unweighted adjacency information.Katz scores geometrically damp path lengths, while personalized PageRank uses random walks and can be adapted to weighted graphs.
  • Paths and random walks: Simplicial PageRank extends random-walk scoring to an abstract simplicial complex containing vertices, edges, and closed triangles.The construction uses a normalized combinatorial Hodge Laplacian and aggregates pairwise edge scores into a triple score.

F.4 Supervised learning

The supervised approach learns triple-closure scores with regularized logistic regression from structural features computed on temporally separated data. Features include pairwise, node-level, simplex-level, and neighborhood statistics.

  • Training procedure: The model trains ℓ2-regularized logistic regression using an early sub-training interval and a later validation interval.The first 60% of the dataset is used for sub-training, and the 60th–80th percentile interval is used for validation.
  • Features: The feature set includes pairwise simplex counts, projected-graph degrees, simplicial degrees, pairwise common neighbors, and triple common neighbors.Log-transformed versions of several counts and smoothed common-neighbor features are also included.
  • Performance comparison: Table 8 compares open-triangle prediction using random, weight-based, neighborhood, preferential-attachment, Katz, PageRank, and simplicial scores.The listed baselines include harmonic, geometric, and arithmetic means of edge weights, common neighbors, Jaccard, Adamic–Adar, and supervised approaches.
  • Training procedure: After training, the model predicts test-set closures using the same features computed from the full first 80% training interval.The prediction features therefore use information available before the test interval.

F.5 Prediction performance

The study evaluates higher-order closure prediction using AUC-PR against random rankings and examines Hodge-decomposition components of simplicial PageRank scores. The proposed algorithms outperform random guessing, while no individual Hodge component consistently dominates.

  • AUC-PR evaluates rankings from the score functions against a random-ranking baseline.Scores are reported relative to random performance.
  • The proposed algorithms achieve much higher performance than randomly guessing which open triangles undergo simplicial closure.Harmonic and geometric means, along with the supervised approach, also perform well across the expanded score-function set.
  • Hodge decomposition separates simplicial PageRank pairwise scores into gradient, curl, and harmonic components.These components are then used to construct score functions on node triples.
  • Hodge components can substantially outperform the combined simplicial PageRank score, but no component consistently outperforms the others.This comparison is reported only for datasets small enough to make the decomposition computationally feasible.

F.6 Example predictions

The DAWN example shows that Adamic-Adar can prioritize rare but successful closure predictions. Four of the top 25 predictions correspond to simplicial closure events, including novel proton-pump-inhibitor combinations.

  • 4 of the top 25 Adamic-Adar predictions in DAWN undergo simplicial closure events.Fewer than one in a hundred open training triangles close during the test period.
  • Three correct DAWN predictions involve novel combinations with proton pump inhibitors.
Loading 1802.06916v2…