Growing Hypergraphs with
Edge Copying

TopoNets@NetSci
June 2nd, 2026

Phil Chodrow
Department of Computer Science
Middlebury College

Hi everyone! I’m Phil Chodrow



Prof. of CS at Middlebury College, a small liberal arts college in Vermont.

Students/postdocs: ask me about #LiberalArtsLife if you’re curious.

I like aikido, tea, my cats, being outside, math models of social systems, and hypergraphs.

My Intellectual Journey in Hypergraphs






network_topics = [
    "configuration models", 
    "directed configuration models",
    "modularity", 
    "spectral clustering", 
    "detectability thresholds"
    ]

for topic in network_topics:
    do_but_for_hypergraphs(topic)

Real talk: this was a reliable source of low-risk theory problems as I established my career.



But…







What structures exist in hypergraphs that we can’t study in graphs at all?




One answer: two-edge motifs.

2-edge motifs in (simple) undirected graphs

2-edge motifs in hypergraphs

Claim: What’s special about the structure of hypergraphs is that they have diverse, undirected, two-edge motifs: intersections.

Intersections in Temporal Hypergraphs


Let \(r_k^{(t)}\) be the probability that two uniformly random hyperedges which arrive before time \(t\) have an intersection of size \(k\).

In empirical hypergraphs, \(r_k^{(t)}\) often decays at rates close to \(t^{-1}\) or \(t^{-2}\), regardless of \(k\).

Benson, Abebe, Schaub, and Kleinberg (2018). Simplicial closure and higher-order link prediction. PNAS

Chodrow (2020). Configuration models of random hypergraphs. JCN

Landry, Young, and Eikmeier (2023). The simpliciality of higher-order networks. EPJ Data Sci.


Dashed lines give slope of \(t^{-1}\) and \(t^{-2}\) decay.

Xie He
Dartmouth + Microsoft

Phil Chodrow
Middlebury

Peter Mucha
Dartmouth

Xie He
Dartmouth + Microsoft

Phil Chodrow
Middlebury

Peter Mucha
Dartmouth





He

Chodrow

Mucha

Xie He
Dartmouth + Microsoft

Phil Chodrow
Middlebury

Peter Mucha
Dartmouth





Hyperedge

Copy

Model

Hyperedge Copy Model




Inspo from…

Benson, Kumar, and Tomkins (2018). “Sequences of Sets.” KDD

Benson, Abebe, Schaub, and Kleinberg (2018). “Simplicial closure and higher-order link prediction.” PNAS

Avin, Lotker, Nahum, and Peleg (2019). “Random preferential attachment hypergraph.” ASONAM


Hyperedge Copy Model




In each timestep…


Hyperedge Copy Model




Select a random edge


Hyperedge Copy Model




Select random nodes from edge


Hyperedge Copy Model




Add nodes from hypergraph

Add novel nodes


Hyperedge Copy Model




Form edge


Hyperedge Copy Model




Repeat


Hyperedge Copy Model




Repeat


Hyperedge Copy Model


Formally

In each timestep \(t\):

  • Start with an empty edge \(f = \emptyset\).
  • Select an edge \(e \in H\).
  • Accept each node from \(e\) into \(f\) with probability \(\eta\) (condition on at least one).
  • Add \(X \sim \boldsymbol{\beta}\) novel nodes.
  • Add \(Y \sim \boldsymbol{\gamma}\) nodes from \(H \setminus e\).


“Tractable” Asymptotics

Proposition (HCM ’25): There exist constants \(q_k\) such that, as \(t\rightarrow \infty\), \[ \begin{aligned} r_{k}(t) = \text{Rate of $k$-intersections at time $t$}\simeq \begin{cases} q_k & \quad \text{if } k = 0\\ \color{#ff9f1c}{t^{-1}} q_k &\quad \mathrm{otherwise}\;. \end{cases} \end{aligned} \]

Here, \(q_k = \sum_{ij} q_{ijk}\) and \(\{q_{ijk}\}\) solve the system

\[ q_{ijk} = \begin{cases} \frac{1}{2}\sum_{\ell} \left(q_{\ell j 0} \alpha_{i0|\ell j0} + q_{j \ell 0} \alpha_{i0|j\ell 0}\right) & \quad k = 0\\ \frac{1}{2}\beta_{ik|j} \sum_{\ell} (q_{\ell j0} + q_{j\ell 0}) + \frac{1}{2}\sum_{\ell, h\geq k} \left(q_{\ell j h} \alpha_{ik|\ell jh} + q_{j \ell h} \alpha_{ik|j\ell h}\right) &\quad k \geq 1\;, \end{cases} \]

where \(\alpha_{ik|\ell jh}\) and \(\beta_{ik|j}\) are constants determined by the model parameters.

These come out of linearized compartmental equations.

Edge intersections

Proposition (HCM ’25): There exist constants \(q_k\) such that, as \(t\rightarrow \infty\), \(r_{k}(t) \simeq \begin{cases} q_k & \quad \text{if } k = k_0\\ \color{#ff9f1c}{t^{-1}} q_k &\quad \mathrm{otherwise}\;. \end{cases}\)

Degree and edge-size distributions

From statistically-inferred parameters, not regression fits!

Scalable online learning via stochastic EM



Aim: given the sequence of edges \(\{e_t\}\), estimate:

  • \(\eta\), the edge retention rate.
  • \(\beta\), the distribution of the number of novel nodes added to each edge.
  • \(\gamma\), distribution of the number of pre-existing nodes added to each edge.
  1. Sample \(e_t\) and form a belief about seed edge \(f\).
  2. Update a vector of expected sufficient statistics \(\theta_t\) and current parameter estimates \(\bar{\eta}\), \(\bar{\beta}\), and \(\bar{\gamma}\).
  3. Repeat until tired.




Simple models can be predictive!

We computed AUC scores for a link prediction task in which our model learns parameters on 20% training data from three metabolic and organic reaction data sets with edges up to size 5. We compared these against previously-reported AUC scores on the same task for two dedicated neural network hypergraph link prediction algorithms.

Yadati et al. (2020) NHP: Neural Hypergraph Link Prediction. CIKM

Yang et al. (2023) LHP: Logical hypergraph link prediction. Expert Systems with Applications

\(n\) \(m\) HCM
11 pars		 NHP
?? pars		 LHP
\(10^6\) pars
iAF1260b 1,668 2,084 0.605 0.582 0.639
iJO1366 1,805 2,253 0.774 0.599 0.638
USPTO 16,293 11,433 0.515 0.662 0.733

We are competitive with neural networks (on some data sets) using an 11-parameter model!

Thank you!!

Hypergraphs have interesting two-edge motifs (intersections). Learnable, mechanistic models of hypergraph growth can be tractable and predictive.

Edge correlations and link prediction in growing hypergraphs. He, Chodrow, and Mucha. Physical Review E (2025)

Xie He

Peter Mucha





Hompohily in Hypergraph Growth??


Violet Ross (CU Boulder)



Modeling Homophilic Hypergraph Growth Using Edge Copying (#201)

Wednesday @4:45pm in Central Square