🌀 nonlinear sciences

Growing Hypergraphs with Homophily

This paper introduces a mechanistic model for growing hypergraphs that relaxes the assumption of edge independence by incorporating homophily-driven edge copying, enabling power-law degree distributions, parameter estimation via expectation maximization, and improved community detection on complex polyadic systems.

Original authors: Violet Ross, Francis Cataldo, Philip S. Chodrow

Published 2026-07-20

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Violet Ross, Francis Cataldo, Philip S. Chodrow

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to understand how a massive, chaotic party evolves. In the world of science, this is the study of networks. Usually, scientists look at these networks as simple webs of connections between two people at a time—like a phone call between Alice and Bob. This is called a "dyadic" interaction. But real life is messier. Sometimes, a whole group of friends hangs out together, or a committee of five people signs a bill at once. These are "hypergraphs," where a single connection (an edge) can link three, four, or even dozens of people simultaneously.

For a long time, computer scientists have tried to build computer models to guess how these groups form. A popular idea is homophily, which is just a fancy word for "birds of a feather flock together." It's the tendency for people with similar traits (like wearing the same band t-shirt or voting for the same party) to hang out with each other. Most old models assumed that every new group forms completely independently, like rolling a fresh die for every new party. They didn't think that the groups you've already seen would influence the next one. But in real life, groups often feel like echoes of previous groups. If you see a group of friends, the next group they form is likely to have some of the same people, or at least people who are very similar to them. This paper asks: What happens if we stop pretending every new group is a random roll of the dice, and instead assume that new groups are messy, noisy copies of old ones?

The authors of this paper, Violet Ross, Francis Cataldo, and Philip S. Chodrow, introduce a new computer model called CHILI (Copying Hyperedges Influenced by Label Interactions). Think of CHILI as a recipe for growing a hypergraph, one group at a time. In their simulation, a new group doesn't just appear out of nowhere. Instead, the computer picks an existing group (a "seed") and tries to copy it. But it's a noisy copy. Some members of the original group are invited to the new one, while others are left out. Crucially, the decision to invite someone depends on their "label"—like whether they are a Democrat or a Republican, or a boy or a girl. If the labels match, they are more likely to be copied over; if they don't, they are less likely to be included. The model also adds in some brand-new people and some people who were already at the party but weren't in the original group.

The researchers found that this simple "copy-paste-with-a-twist" mechanism creates very realistic-looking networks. When they ran their simulations, they discovered that the model naturally produces a specific mathematical pattern called a power law for how many connections each person has. This means that in these simulated worlds, a few people become super-connected "hubs" while most people have only a few connections, just like in real social networks. They also mapped out how the "labels" (the traits) spread through the network over time. They found that if the copying is very strong (high homophily), the groups tend to become very uniform—like a room full of people all wearing the same color shirt. However, even if the copying is strong, the system eventually balances out so that the total number of people with each label stays equal in the long run, even if individual groups look very different.

To prove their model works, the authors taught a computer to "learn" the rules of the game. They used a technique called Stochastic Expectation Maximization (SEM). Imagine you are a detective trying to figure out the rules of a game just by watching people play. You make a guess, watch a few moves, adjust your guess, and repeat. The authors showed that this method works very well on fake data they generated with CHILI; the computer could accurately guess the exact rules they had used to create the data. They then applied this detective work to real-world data, like bills co-sponsored by US Senators or emails sent by employees at the Enron corporation. On the Enron data, for instance, the model suggested that email groups were formed in a way that looked "heterophilic" (opposites attract), which the authors explain is likely because emails often link a core group of people to many different outsiders, rather than just copying a previous email thread exactly.

Finally, the team tried to use their model to find "communities"—groups of people who belong together. They used a method called simulated annealing, which is like a computer slowly cooling down a metal to find its strongest shape, but here it's used to find the best arrangement of labels. They tested this on real data sets, like high school social interactions and Senate bills. The results were a mixed bag but very promising. On some tricky data sets where other standard methods (which assume groups form independently) failed, the CHILI model did a better job at finding the hidden groups. For example, on the Senate bills data, it outperformed other methods in identifying political parties. However, the authors admit that this method is very slow and computationally expensive, like trying to solve a giant puzzle by checking every single possible move one by one. While it's not a magic bullet that solves everything instantly, the paper suggests that ignoring the fact that "groups copy groups" might be a big mistake. By explicitly modeling how edges depend on previous edges and the labels of the people in them, we might get a much clearer picture of how complex social systems actually grow and change.

Technical Summary: Growing Hypergraphs with Homophily

Problem Statement
Existing generative models for hypergraphs often rely on the assumption of conditional edge independence, where the formation of an edge depends solely on node parameters and not on the history of previous edges. While stochastic block models and latent-space models facilitate efficient inference, this independence assumption is frequently unrealistic for polyadic data, which often exhibits significant edge correlations (e.g., new interactions overlapping heavily with observed ones). Furthermore, while models incorporating edge dependence and node labels exist, they generally lack frameworks for statistically principled inference of either dynamical parameters or latent node labels. This paper addresses the gap in modeling growing hypergraphs where edge formation is driven by both previous edges and binary node labels (homophily), while simultaneously enabling parameter estimation and community detection.

Methodology: The CHILI Model
The authors introduce Copying Hyperedges Influenced by Label Interactions (CHILI), a mechanistic generative model for growing hypergraphs with binary node labels ( $z \in \{0, 1\}$ ). CHILI extends the Hyperedge Copy Model (HCM) by integrating label-aware parameters into three distinct steps for forming a new edge $e$ at time $t+1$ :

Edge-Copying: A seed edge $f$ and a focal node $u \in f$ are sampled. Other nodes $v \in f$ are copied into $e$ with probability $\rho_+$ if $z_v = z_u$ (homophilic copy) or $\rho_-$ if $z_v \neq z_u$ (heterophilic copy).
Extant Node Addition: Nodes from the existing set $N_t \setminus f$ are added to $e$ . The number of nodes with label $z_u$ and $\bar{z}_u$ follows Poisson distributions with rates $\gamma_+$ and $\gamma_-$ , respectively.
Novel Node Addition: New nodes are introduced to both the edge and the network. The number of new nodes with labels $z_u$ and $\bar{z}_u$ follows Poisson distributions with rates $\eta_+$ and $\eta_-$ .

The model is defined by the parameter vector $\theta = (\rho_+, \rho_-, \gamma_+, \gamma_-, \eta_+, \eta_-)$ .

Theoretical Analysis
The authors derive asymptotic properties of the model:

Joint Label Distribution: The stationary joint distribution of label counts in an edge, $q(k_0, k_1)$ , is shown to be the leading eigenvector of a linear transition map $T$ . The spectral gap of $T$ determines the rate of convergence; small gaps (high $\rho_+$ , low $\rho_-$ ) allow for long-lived transient dynamics where a single label group dominates edges, even if the long-term stationary state is symmetric.
Degree Distribution: Under a mean-field assumption, the degree distribution follows a power law. The exponent $\zeta$ is derived in closed form as a function of the model parameters and the stationary joint distribution.

Inference Algorithms
The paper proposes two inference tasks:

Parameter Estimation (SEM): Given observed edges and known node labels, the authors use a Stochastic Expectation-Maximization (SEM) algorithm. Because computing the full likelihood requires marginalizing over latent variables (seed edges and focal nodes) leading to quadratic complexity, SEM utilizes noisy exponentially weighted moving averages of sufficient statistics. This allows for scalable, online parameter updates.
Community Detection (Simulated Annealing): Given observed edges and fixed parameters, the goal is to infer latent node labels $z$ . Due to the edge-dependence structure, standard efficient heuristics (like those used for stochastic block models) are difficult to apply. The authors employ Simulated Annealing to maximize the likelihood. To mitigate the $O(m^2)$ computational cost of evaluating likelihood changes, they use an intersection-based approximation, summing only over candidate seed edges with large overlap with the target edge.

Results

Synthetic Data: The SEM algorithm demonstrates consistency and scalability in recovering parameters from synthetic data generated by CHILI. The accuracy of recovery depends on the strength of homophily and copy rates; however, even in high-error regimes, estimates remain visually close to true values.
Empirical Parameter Estimation: Applied to six datasets (including legislative bills, school interactions, co-authorship, and Enron emails), the model reveals distinct mechanisms. For instance, in the co-authorship dataset, gender homophily is detected primarily in the recruitment of novel nodes (novices), whereas the edge copy mechanism shows no significant gender bias. In the Enron dataset, the model captures heterophily in edge copying, attributed to the sampling strategy where core nodes frequently interact with fringe nodes.
Community Detection: On synthetic data, simulated annealing under the "Nishimori condition" (using true parameters) outperforms baseline spectral clustering in specific parameter regimes, particularly where homophily is weak. On empirical datasets (senate-bills, primary-school, high-school), CHILI-based simulated annealing achieves competitive Adjusted Rand Index (ARI) scores, outperforming dyadic spectral clustering and greedy modularity maximization on the senate-bills dataset.

Significance and Claims
The paper claims that incorporating edge-dependence and label-dependence into higher-order modeling offers benefits for data analysis. Specifically:

Generative Modeling: CHILI provides a likelihood-based framework for describing the operation of homophily in empirical polyadic systems, moving beyond the independence assumptions of standard models.
Community Detection: While computationally expensive, the results serve as a "proof-of-concept" that maximizing likelihood under an edge-dependent model can detect community structure more reliably than standard methods in certain regimes.
Future Directions: The authors modestly note that the current computational cost of simulated annealing limits scalability. They identify the development of more efficient optimization heuristics as a critical direction for future work to make the model practical for large-scale applications. They also suggest extensions to multinary labels, spontaneous edge formation, and recency-bias in copying mechanisms.

More like this