Source-linked AI summary
Higher-order motif analysis in hypergraphs
Quintino Francesco Lotito, Federico Musciotto, Alberto Montresor, Federico Battiston
TL;DR
Many real systems contain group interactions that pairwise networks and motif methods cannot fully represent. This paper defines higher-order motifs in hypergraphs, derives their combinatorial bounds, and develops an algorithm for empirical significance profiles. The analysis identifies domain-related higher-order network families and evidence of structural reinforcement, while exhaustive scalability limits the study to motif sizes 3 and 4.
Problem
Many real-world systems involve group interactions, while existing motif methods analyze only pairwise patterns and therefore provide limited higher-order local characterization.
Method
The paper defines statistically over-represented connected higher-order motifs in hypergraphs and develops algorithms to count, compare, and evaluate their significance in empirical data.
Results
The analysis extracts microscale fingerprints, identifies families with distinct higher-order connectivity patterns, and observes structural reinforcement linking group interactions with pairwise structure.
Takeaways & Limitations
Higher-order motif profiles provide a way to distinguish local connectivity patterns across real-world systems and domains.
Takeaways & Limitations
The exhaustive algorithm is limited by scalability and therefore focuses on higher-order motifs of size 3 and 4.
Abstract
from arXiv · showhide
A deluge of new data on social, technological and biological networked systems suggests that a large number of interactions among system units are not limited to pairs, but rather involve a higher number of nodes. To properly encode such higher-order interactions, richer mathematical frameworks such as hypergraphs are needed, where hyperlinks describe connections among an arbitrary number of nodes. Here we introduce the concept of higher-order motifs, small connected subgraphs where vertices may be linked by interactions of any order. We provide lower and upper bounds on the number of higher-order motifs as a function of the motif size, and propose an efficient algorithm to extract complete higher-order motif profiles from empirical data. We identify different families of hypergraphs, characterized by distinct higher-order connectivity patterns at the local scale. We also capture evidences of structural reinforcement, a mechanism that associates higher strengths of higher-order interactions for the nodes that interact more at the pairwise level. Our work highlights the informative power of higher-order motifs, providing a first way to extract higher-order fingerprints in hypergraphs at the network microscale.
INTRODUCTION
Higher-order interactions occur across many social, biological, technological, and ecological systems, but conventional motif methods represent only pairwise structure. The paper introduces higher-order motifs in hypergraphs to characterize local connectivity and identify recurring system families.
- Empirical systems including collaboration, face-to-face, ecological, and brain networks contain interactions involving groups rather than only pairs.
- Hypergraphs encode group interactions through hyperedges connecting an arbitrary number of nodes.
- Traditional motif analysis identifies small, statistically over-represented connected subgraphs as microscale network fingerprints.
- Existing motif methods focus on pairwise interactions, limiting characterization of systems with group interactions.
- The paper defines higher-order motifs, develops significance-testing algorithms, identifies higher-order network families, and reports structural reinforcement.
RESULTS
Higher-order motif analysis extends conventional motif workflows to hypergraphs by counting connected interaction patterns, comparing them with a null model, and evaluating their statistical expression. The empirical analysis combines naturally encoded and inferred higher-order structures across several domains.
- Higher-order motifs are connected patterns that are statistically over-represented in an observed hypergraph relative to a randomized system.
- The analysis counts each motif, compares its frequency with a null model, and evaluates over- or under-expression statistically.
- Traditional motif-counting algorithms cannot capture patterns encoded by hyperlinks, motivating specialized higher-order algorithms.
- Datasets span social, technological, biological, and co-authorship domains, with higher-order structures either directly encoded or inferred from simultaneous cliques.
A. Combinatorial analysis of higher-order motifs
The number of higher-order motifs grows rapidly with motif order because hypergraphs permit many combinations of higher-order edges. Analytical bounds and exact small-order counts expose this combinatorial growth, motivating a focus on orders 3 and 4.
- Six higher-order interaction patterns are possible on three connected nodes, compared with two pairwise undirected patterns.
- The number of labelled hypergraphs is bounded by counting possible hyperedges and allowing each to be included or excluded.
- A connected-hypergraph lower bound is constructed by fixing a chain of edges and varying the remaining possible edges.
- Upper and lower bounds, together with exact small-order counts, show super-exponential growth in the number of higher-order motifs.
- The combinatorial explosion makes high-order motif storage and indexing intractable, so the analysis focuses on motifs of orders 3 and 4.
Motifs of order 3
Order-3 significance profiles reveal domain-specific higher-order connectivity patterns and distinguish families of empirical systems. Group interactions are often associated with supporting pairwise structure, while some domains show underrepresented group-only interactions.
- Significance profiles summarize motif over- and under-expression and provide fingerprints of local network structure.
- The pairwise triangle B is strong across clusters, while motifs combining a 3-hyperlink with dyadic edges differ most across domains.
- Social and technological networks show a strong motif combining a 3-hyperlink with a dyadic triangle, indicating group and individual interactions co-occur.
- Co-authorship networks emphasize motifs D and E, involving a 3-hyperlink with one or two dyadic edges and a hierarchical pairwise structure.
- The 3-hyperlink without dyadic interaction is an anti-motif in social and technological networks, whereas biological and co-authorship networks show no strong anti-motif.
- Correlation-based clustering yields two main higher-order network families, grouping social with technological datasets and biological with co-authorship datasets.
Motifs of order 4
Motifs of order 4 provide more nuanced local-structure information than order-3 motifs, separating two higher-order families and revealing their characteristic interaction patterns.
- Motifs of order 4: 171 possible four-node higher-order interaction patterns, compared with 6 for three-node motifs, make order-4 analysis richer but more difficult.The authors use order-4 motifs despite this combinatorial increase.
- Motifs of order 4: Order-4 significance profiles sort motifs by their ability to discriminate Biological / Co-authorship from Sociological / Technological networks.Motifs at opposite ends are respectively over-represented in one family and under-represented or uncharacteristic in the other.
- Motifs of order 4: Order-4 clustering reproduces the two main families while producing better separation and richer hierarchical organization within clusters.This provides more structural information than the corresponding order-3 analysis.
- Motifs of order 4: Sociological / Technological networks over-represent structures with more lower-order inner relations, whereas Biological / Co-authorship networks prefer fewer, higher-order relations.The comparison is based on the most over-expressed representative order-4 motifs.
Higher-order motifs and reinforcement
The analysis identifies structural reinforcement: group interactions become stronger when their underlying pairwise structure is richer, with related evidence from friendship data.
- Reinforcement: A positive correlation links hyperlink weight with the number of underlying pairwise links, defining higher-order structural reinforcement.Hyperlink weight is measured by how many times each hyperlink appears.
- Higher-order families: Order-4 motifs reveal distinct family-level connectivity patterns alongside the reinforcement mechanism.The two higher-order families are Sociological / Technological and Biological / Co-authorship.
- Reinforcement: Friendship metadata from Facebook and questionnaires shows more friends in size-three group interactions with more pairwise connections.The finding further supports reinforcement in the proximity hypergraph.
Nested organization of higher-order interactions
Because exhaustive motif analysis is feasible only for orders 3 and 4, the paper characterizes larger hyperlinks through nested interaction structures, which differ systematically between network families.
- Scope and alternative: Exhaustive higher-order motif analysis is feasible only for motifs of order 3 and 4 because computational demands rise sharply with motif order.For larger hyperlinks, the authors replace exact pattern counts with statistics of internal hierarchical structure.
- Nested link counts: Socio / Tech hyperedges show a growing number of nested links with increasing hyperedge size, whereas Bio / Co-auth hyperedges remain comparatively static.The Socio / Tech trend changes slope after orders 5 and 6.
- Nested link sizes: Both families have increasing mean nested-link size, but Bio / Co-auth grows faster than Socio / Tech.Socio / Tech therefore tends toward many small internal edges, while Bio / Co-auth favors fewer large edges.
- Nested organization: The nested organization of higher-order interactions differs substantially between the two higher-order families.These statistics extend family-level structural comparison beyond exhaustively counted motifs.
DISCUSSION
The paper extends network-motif analysis to hypergraphs to characterize local higher-order structure, develop empirical analysis tools, and identify recurring higher-order organization and reinforcement.
- Contribution: Higher-order motifs are statistically over-represented connected subgraphs in which interactions may involve more than two nodes.They extend motif analysis beyond pairwise interaction patterns.
- Contribution: The paper provides a combinatorial characterization and an efficient algorithm for evaluating higher-order motif significance on empirical data.These tools support higher-order fingerprint extraction from real-world hypergraphs.
- Findings: Empirical analyses reveal families of hypergraphs with similar local higher-order structures and a reinforcement mechanism linking stronger higher-order interactions to richer pairwise interaction structure.The reinforcement association concerns groups whose nodes interact more at the pairwise level.
- Limitations and outlook: The exhaustive algorithm focuses on motif sizes 3 and 4, while larger motifs require non-exhaustive approaches or sampling methods for broader applications.The paper studies nested structures of larger hyperlinks as an initial alternative.
METHODS
Higher-order motif analysis counts target motifs, compares them with configuration-model null networks, and summarizes over- and under-expression in significance profiles.
- The analysis counts each target higher-order motif and compares its frequency with a null model to identify over- or under-expression.
- An exact algorithm counts order-k motifs by enumerating connected subgraphs and resolving hypergraph isomorphism through indexed relabelings.For motifs of order 3 and 4, the method stores all non-isomorphic patterns and updates occurrences efficiently.
- The configuration model is sampled 20 times to estimate random motif frequencies for validating motif abundance relative to random networks.
- The significance profile is formed by normalizing the vector of motif over- and under-expression values to length 1.The method sets ϵ = 4 when computing the over- and under-expression measure.
Supplementary Information Higher-order motif analysis in hypergraphs
The supplied passage identifies the authors of the paper.
- The paper is authored by Quintino Francesco Lotito, Federico Musciotto, Alberto Montresor, and Federico Battiston.
S1. DATASETS
The study analyzes higher-order datasets spanning social, technological, biological, co-authorship, and proximity-contact systems.
- The datasets include social, technological, biological, and co-authorship networks gathered for higher-order motif analysis.
- Gene/disease, drug-label, drug-substance, and publication datasets represent associated entities as hyperedges, with drugs or papers carrying timestamps where specified.
- The Wiki and Justice datasets represent voting events as hyperedges containing users or justices expressing the same vote.
- Email datasets represent each message as a timestamped hyperedge containing the sender and all recipients.
- Proximity-contact datasets aggregate wearable-sensor contacts into 20-second windows and represent maximal cliques in each temporal layer as hyperedges.
- The dataset table reports node counts, total hyperedge counts, and counts of hyperedges of sizes 2, 3, 4, and 5.