🔬 physics

Higher-order dissimilarity measures for hypergraph comparison

This paper introduces two novel metrics, Hyper NetSimile and Hyperedge Portrait Divergence, to effectively compare hypergraphs by capturing their higher-order structural features that traditional pairwise network measures fail to represent.

Original authors: Cosimo Agostinelli, Marco Mancastroppa, Alain Barrat

Published 2026-02-24

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Cosimo Agostinelli, Marco Mancastroppa, Alain Barrat

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 city works.

The Old Way (Pairwise Networks):
Traditionally, scientists have looked at cities like a map of roads connecting houses. If Alice lives next to Bob, there's a road between them. If Bob is friends with Charlie, there's a road there too. This is called a "network." It's great for seeing who knows who.

But real life is messier. Sometimes, Alice, Bob, and Charlie all meet at a coffee shop together. They aren't just three separate pairs; they are a group. In the old "road map" method, this group meeting gets flattened. The map just shows three roads: Alice-Bob, Bob-Charlie, and Alice-Charlie. It loses the fact that they were all there at the same time as a single unit.

The Problem:
Scientists realized that many complex systems—from how viruses spread in a hospital to how people collaborate on research papers—rely on these group interactions. If you only look at the "roads" (pairs), you miss the "coffee shop meetings" (groups). You might think two different cities are identical just because they have the same number of roads, even if one city has huge community centers and the other doesn't.

The Solution: Two New "Group Scanners"
The authors of this paper invented two new tools to measure how similar or different these "group-heavy" systems are. They call them Hyper NetSimile and Hyperedge Portrait Divergence.

Think of them as two different ways to compare two different cities:

1. Hyper NetSimile (The "Local Neighborhood" Scanner)

How it works: Imagine walking through a city and asking every person, "Who are your friends, and how many people are in your friend groups?"
The Analogy: This tool looks at the local details. It checks:
- How many groups is this person in?
- Are those groups small (just 2 people) or huge (a whole team)?
- What are their friends' group sizes like?
The Result: It creates a "fingerprint" for the whole city based on the average experience of its people. If two cities have people with very different group habits, this tool will say, "These cities are totally different!" even if they have the same number of roads.

2. Hyperedge Portrait Divergence (The "Group Journey" Scanner)

How it works: Instead of looking at people, this tool looks at the groups themselves as the main characters. Imagine the groups are islands, and you can travel from one island to another if they share a person.
The Analogy: This tool maps out journeys between groups.
- How many steps does it take to get from a "Book Club" to a "Gym Group"?
- Are there many small groups or a few giant ones?
- How are the groups connected?
The Result: It creates a "portrait" of the city's group structure. It's like looking at the city from a drone, seeing how the clusters of people connect to each other, rather than just looking at individual people.

Why Do We Need These?

The authors tested these tools on fake data and real-world data (like face-to-face interactions in hospitals, scientific collaborations, and online forums).

The Test: They tried to trick the tools. They took a real group network and broke the groups apart, turning them into simple pairs (like turning a group meeting into just a list of who sat next to whom).
The Old Tools' Failure: The old "road map" tools couldn't tell the difference. They said the broken version was identical to the original because the "roads" were the same.
The New Tools' Success: The new scanners immediately shouted, "These are different!" They could see that the "group spirit" was gone.

The Big Takeaway

Just because two systems look similar on the surface (like two cities with the same number of roads) doesn't mean they function the same way.

Old Tools: Good for simple "A knows B" relationships.
New Tools: Essential for understanding "A, B, and C did something together."

By using these new measures, scientists can finally tell the difference between a system where people interact in tight-knit teams versus one where they just have random one-on-one chats. This helps us better understand everything from how diseases spread in a crowd to how ideas evolve in a scientific community.

1. Problem Statement

Complex systems in domains ranging from biology to social sciences often involve multi-body interactions (group interactions) rather than simple pairwise links. While hypergraphs provide a mathematical framework to model these systems (where hyperedges connect $k$ nodes, $k > 2$ ), a significant challenge remains: how to effectively compare and quantify the dissimilarity between two hypergraphs.

Existing similarity measures designed for standard pairwise networks (e.g., NetSimile, Portrait Divergence) fail when applied to hypergraphs because:

Information Loss: Converting a hypergraph to a pairwise network (via projection) collapses higher-order structures into cliques, destroying the specific group interaction information.
Inadequacy: Two distinct hypergraphs can have identical pairwise projections, making them indistinguishable to traditional metrics despite having different underlying higher-order dynamics.
Lack of Tools: There are few principled methods specifically designed to capture the structural complexity of hypergraphs without requiring node-to-node correspondence.

2. Methodology

The authors propose two novel, complementary dissimilarity measures specifically designed for hypergraphs. Both measures are invariant to node relabeling and can compare hypergraphs of different sizes.

A. Hyper NetSimile (HNS)

Concept: A generalization of the NetSimile metric for pairwise networks, adopting a node-centric perspective.
Mechanism: It constructs a "signature vector" for each hypergraph based on the statistical distributions of local features across all nodes.
Features: The vector includes 7 key quantities measured for every node $i$ $i$ :
1. Number of neighbors.
2. Hyperdegree (number of hyperedges containing $i$ ).
3. Average size of hyperedges containing $i$ .
4. Standard deviation of hyperedge sizes containing $i$ .
5. Average number of neighbors of $i$ 's neighbors.
6. Average hyperdegree of $i$ 's neighbors.
7. Size of $i$ 's ego-net (nodes at distance 2).
Calculation: For each feature, the mean, median, and standard deviation are computed, resulting in a 21-dimensional vector. The dissimilarity is calculated using the Canberra distance between the vectors of two hypergraphs.
Note: The authors explicitly exclude skewness and kurtosis (used in original NetSimile) and clustering coefficients, as tests showed these degrade performance or are computationally expensive.

B. Hyperedge Portrait Divergence (HPD)

Concept: A generalization of the Portrait Divergence metric, adopting a hyperedge-centric perspective. It focuses on the global topology and diffusive properties of the system.
Mechanism: It treats hyperedges as the fundamental building blocks. It defines a Hyperedge Portrait, a 4-index tensor $\Gamma_{m,n,l,k}$ representing the number of hyperedges of size $m$ that have $k$ hyperedges of size $n$ at distance $l$ .
Distance Definition: Two hyperedges are adjacent (distance 1) if they share at least one node. The distance between hyperedges is the length of the shortest path through adjacent hyperedges (equivalent to distance in the bipartite representation).
Calculation: The tensor is normalized into a probability distribution $P(m, n, l, k)$ . The dissimilarity between two hypergraphs is the Jensen-Shannon divergence between their respective distributions.

3. Key Contributions

Novel Metrics: Introduction of HNS and HPD, the first metrics explicitly designed to capture higher-order structural features without projecting to pairwise networks.
Complementarity: The two metrics offer different viewpoints: HNS captures local structural heterogeneity (node-centric), while HPD captures global path statistics and interaction sizes (hyperedge-centric).
Robustness: Both metrics work on hypergraphs of arbitrary sizes and do not require a mapping between the nodes of the two systems being compared.
Validation Framework: A comprehensive benchmarking suite comparing these higher-order metrics against their pairwise counterparts (NetSimile and Portrait Divergence applied to projected networks) across synthetic models, randomized data, and empirical datasets.

4. Results

A. Distinguishing Purely Higher-Order Differences

The authors demonstrated that traditional pairwise metrics fail to distinguish hypergraphs that share the same pairwise projection.

Null Models: When hyperedges were partially projected to pairwise links (or vice versa), HNS and HPD detected increasing dissimilarity as the higher-order structure changed, whereas pairwise metrics (NS, PD) reported zero dissimilarity because the projected graphs were identical.

B. Clustering Synthetic Models

The metrics were tested on 300 synthetic hypergraphs generated by three models: Erdős-Rényi (ER), Configuration Model (CM), and Watts-Strogatz (WS).

Performance: HNS and HPD perfectly clustered the data according to the generative model (Rand Index = 1.0).
Comparison: While NS also achieved perfect clustering, PD failed to distinguish between CM and WS models. Furthermore, HNS and HPD yielded higher Dunn Indices, indicating better separation between clusters than pairwise methods.
Parameter Sensitivity: When varying the maximum hyperedge size ( $M$ ) in ER models while keeping the pairwise projection degree constant, only HNS and HPD could distinguish the groups. Pairwise metrics failed as the underlying pairwise structure remained random and similar.

C. Clustering Randomized Empirical Data

The metrics were applied to a real-world face-to-face interaction dataset (SocioPatterns) subjected to three randomization methods:

Random Shuffling (RS): Destroys all structure.
Proportional Shuffling (PS): Preserves hyperdegree distribution but destroys specific groupings.
Degree-preserving Shuffling (DS): Preserves exact hyperdegrees for every interaction order.

Result: HPD was the most effective metric, clearly separating the three randomization types (Dunn Index = 2.49). HNS and NS also performed well, while PD struggled to separate PS and DS methods.

D. Clustering Real-World Hypergraphs

The authors clustered diverse empirical datasets (co-authorships, online interactions, political committees, face-to-face contacts).

Findings: Higher-order metrics (HNS, HPD) produced dendrograms that aligned much better with the semantic context of the data (e.g., grouping co-authorship networks together and separating them from face-to-face interactions) compared to pairwise metrics.
Specific Insight: HPD correctly identified that co-authorship networks from the same journal in consecutive time periods were the most similar, a nuance missed by some pairwise approaches.

5. Significance and Implications

Structural Signature: The study proves that higher-order interactions are not just dynamic features but constitute a distinct structural signature essential for classifying complex systems.
Superiority over Projections: Relying on pairwise projections leads to a loss of critical information. The proposed metrics capture the "full structural complexity" of systems, offering better discrimination power.
Applications: These tools are vital for:
- Model Validation: Checking if synthetic data generation models accurately reproduce empirical higher-order structures.
- Reconstruction: Evaluating algorithms that infer hypergraphs from time-series data.
- Temporal Analysis: Extending state-detection methods to time-varying hypergraphs.
Computational Efficiency: HNS is highly efficient (local features). HPD has a complexity of $O(E + N(\langle k^2 \rangle - \langle k \rangle))$ , which is manageable for medium-sized systems but may require sampling approximations for very large hypergraphs.

In conclusion, Agostinelli et al. provide a robust mathematical toolkit for the comparative analysis of higher-order networks, demonstrating that explicitly modeling group interactions is necessary for accurate system characterization and classification.