Source-linked AI summary
Higher-order motif analysis in hypergraphs
Quintino Francesco Lotito, Federico Musciotto, Alberto Montresor, Federico Battiston
TL;DR
Existing motif methods capture pairwise patterns, leaving group interactions outside their local-structure analysis. This paper defines higher-order motifs and an algorithm to assess their significance, finding distinct motif patterns across social, technological, and co-authorship networks.
Problem
Existing motif methods consider only pairwise interactions, limiting characterization of local structure in systems with group interactions.
Source: INTRODUCTION · p. 2Method
The paper defines higher-order motifs as statistically over-represented connected patterns in hypergraphs and develops an algorithm to evaluate their statistical significance.
Source: INTRODUCTION · p. 2, RESULTS · p. 2Results
Social and technological networks show strong motif F, while co-authorship networks show strongest motifs D and E.
Source: Motifs of order 3 · p. 3Takeaways & Limitations
Higher-order motif profiles provide a way to extract microscale fingerprints and distinguish families of higher-order systems.
Source: INTRODUCTION · p. 2The exhaustive-search approach focuses on higher-order motifs of sizes 3 and 4, limiting scalability.
Source: DISCUSSION · p. 7
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
Because many real-world interactions involve groups rather than pairs, pairwise motif methods miss part of network structure. This paper defines statistically over-represented connected subgraphs with higher-order interactions as hypergraph motifs and uses them to identify local structural fingerprints and structural reinforcement.
Introduction
- Empirical evidence indicates that many interactions involve groups, not just pairs, across collaboration, face-to-face, ecological, and brain systems [2–7].Hypergraphs encode such interactions with hyperedges linking an arbitrary number of nodes.Source: INTRODUCTION · p. 1
- Motifs are small connected subgraphs that occur more often than expected in randomized networks, and their patterns can fingerprint network families and offer insight into dynamics and resilience.Prior work also treats motifs as elementary computational circuits and has proposed process motifs to connect local structure to system dynamics.Source: INTRODUCTION · p. 1
- Microscale motif analysis has considered richer frameworks, including weighted, temporal, and multilayer networks, characterized through link-weight intensity and coherence, time-restricted interaction patterns, and statistically over-represented small multilayer subgraphs.Source: INTRODUCTION · p. 2
RESULTS
The section defines higher-order motifs as unusually frequent connected patterns of higher-order interactions and outlines their analysis in real-world hypergraphs.
RESULTS
- Higher-order motifs are small connected patterns of interactions that occur in an observed hypergraph significantly more often than in a suitably randomized system.They extend the traditional definition of network motifs, which are used to identify microscale network fingerprints and structural and functional building blocks.Source: RESULTS · p. 2
- Higher-order motif analysis counts each pattern, compares its frequency with a null model, and statistically evaluates over- or under-expression.Traditional motif-counting algorithms cannot capture patterns of hyperlinks; the paper's algorithms and tools are described in the Methods section.Source: RESULTS · p. 2
- Datasets span social, technological, biological, and co-authorship systems, with hyperlinks either directly observed or inferred from simultaneous dyadic cliques.For face-to-face interactions, cliques of size k are promoted to order-k hyperlinks when the corresponding dyadic encounters happen at the same time.Source: RESULTS · p. 2
A. Combinatorial analysis of higher-order motifs
Higher-order interactions expand the motif patterns available even among three nodes, and the number of possible higher-order motifs grows super-exponentially with motif order. The analysis bounds this growth and motivates focusing on motifs of orders 3 and 4.
A. Combinatorial analysis of higher-order motifs
- Six higher-order interaction patterns are possible on three connected nodes, compared with only two pairwise undirected patterns.These are the patterns enumerated in Fig. 1a.Source: A. Combinatorial analysis of… · p. 2, Figure 1 · p. 3
- The analysis bounds motif counts by counting all labelled hypergraphs for an upper bound and constructing connected hypergraphs for a lower bound, then accounting for at most k! labelings per unlabelled graph.For the lower bound, it includes a chain of k − 1 edges to ensure connectivity and independently adds or omits the remaining possible edges.Source: A. Combinatorial analysis of… · pp. 2–3
- The number of possible higher-order motifs grows super-exponentially with order, making storage and indexing intractable at high orders and motivating analysis of orders 3 and 4.The figure reports analytical upper and lower bounds alongside exact counts for small orders.Source: A. Combinatorial analysis of… · p. 3, Figure 1 · p. 3
Motifs of order 3
Order-3 significance profiles fingerprint local hypergraph structure and reveal domain-specific patterns of higher-order connectivity. Profile correlations further group datasets into two families that broadly reproduce the domain partitions.
Motifs of order 3
- The over- and under-expression measures of each order-3 motif are concatenated into significance profiles that fingerprint local network structure.The profiles are grouped and averaged by domain to characterize empirical networks at the smallest scale.Source: Motifs of order 3 · p. 3
- Triangle B is strong across all clusters, while motif F is strong in social and technological networks and motifs D and E dominate co-authorship networks.F combines a 3-hyperlink with a dyadic triangle; D and E combine a 3-hyperlink with one or two dyadic edges, suggesting hierarchical interaction structure in co-authorship, with a similar motif overabundant in biological systems.Source: Motifs of order 3 · p. 3
- Motif C, a 3-hyperlink without dyadic interactions, is underrepresented in social and technological networks, while biological and co-authorship networks show no strong anti-motif.Source: Motifs of order 3 · p. 3
- Correlations between significance profiles reveal two network families: social and technological datasets cluster together, as do biological and co-authorship datasets.The clusters reproduce the domain partitions while offering a more nuanced view of similarities among datasets.Source: Motifs of order 3 · p. 3
Motifs of order 4
Order-4 motifs provide more nuanced information about local network structure than order-3 motifs and reveal distinct patterns across the two main domain clusters.
Motifs of order 4
- The number of possible higher-order interaction patterns for 4 nodes grows from 6 to 171, yielding more nuanced local-structure information than 3-node motifs.Source: Motifs of order 4 · p. 3
- Order-4 significance-profile extremes distinguish motifs over-represented in Biological / Co-authorship networks from those characteristic of Sociological / Technological networks.The two ends of the motif axis carry information about structural differences among the clusters.Source: Motifs of order 4 · p. 4
- Order-4 motif clustering retains the two main clusters while revealing richer hierarchical organization within them and better separation between them.Source: Motifs of order 4 · p. 4
- The Sociological / Technological cluster over-represents structures with more lower-order inner relations, while the Biological / Co-authorship cluster favors fewer, higher-order relations.Source: Motifs of order 4 · p. 4
Higher-order motifs and reinforcement
Hyperlink weight rises with the number of underlying pairwise links, a pattern termed higher-order structural reinforcement; student friendship data show a similar pattern for groups in size-three hyperlinks.
Higher-order motifs and reinforcement
- A clear positive trend links the number of underlying pairwise links to hyperlink weight, which the authors term higher-order structural reinforcement.Hyperlink weight is the number of times the hyperlink appears.Source: Higher-order motifs and reinforcement · p. 4
- Order-4 significance profiles distinguish the two higher-order network families, with richer local-structure information and better-separated clusters than order-3 profiles.The profiles also show richer intra-cluster hierarchical structure.Source: Figure 3 · p. 5
- In the High School dataset, groups in size-three hyperlinks with more pairwise interactions also have more friends, further supporting reinforcement.The friendship data came from Facebook accounts and questionnaires.Source: Higher-order motifs and reinforcement · pp. 4–5
Nested organization of higher-order interactions
Because exhaustive motif counting is feasible only for orders 3 and 4, the section characterizes larger hyperlinks through nested-structure statistics with linear complexity in the number of hyperedges. These statistics reveal different nested organization in Socio / Tech and Bio / Co-auth networks.
Nested organization of higher-order interactions
- For motifs above orders 3 and 4, the analysis extracts hierarchical interaction statistics rather than exact pattern frequencies, with complexity linear in the number of hyperedges.This approach characterizes local sub-modules through nested structures of hyperlinks of any size.Source: Nested organization of higher-order… · p. 5
- Socio / Tech hyperedges show increasing numbers of nested edges, with a slope change after orders 5 and 6, while Bio / Co-auth shows no evident increase.The comparison is shown in Fig. 5a.Source: Nested organization of higher-order… · p. 5, Figure 5 · p. 6
- Both clusters have larger nested edges as hyperedge size grows, but growth is faster in Bio / Co-auth; Socio / Tech instead has more, smaller nested edges, while Bio / Co-auth has fewer, larger ones.The comparison is shown in Fig. 5b.Source: Nested organization of higher-order… · p. 5, Figure 5 · p. 6
DISCUSSION
Building on network motifs as tools for characterizing local network structure, the discussion presents higher-order motifs as a way to fingerprint hypergraphs and identify patterns in higher-order interactions.
DISCUSSION
- Higher-order motifs are overrepresented, possibly overlapping interaction patterns; their combinatorial characterization and significance testing reveal local fingerprints, structural families, and pairwise-linked reinforcement.The reinforcement mechanism associates stronger higher-order interaction weights with groups that interact more at the pairwise level.Source: DISCUSSION · p. 7
- The exhaustive algorithm is limited by scalability and focuses on higher-order motifs of sizes 3 and 4.Source: DISCUSSION · p. 7
- Future work could examine larger hyperlink patterns with non-exhaustive approaches and develop sampling methods for statistical evaluation to support wider real-world applications.Source: DISCUSSION · p. 7
METHODS
The methods count connected higher-order motif occurrences exactly, then compare their frequencies with null networks to identify over- and under-expression.
METHODS
- An exact hierarchical algorithm counts order-k motifs by enumerating candidate k-node subgraphs, resolving relabelings, and constructing each induced subgraph.It proceeds from hyperlinks of size k down to dyadic links, uses neighborhoods to select remaining nodes, and checks possible hyperedges. Indexing motifs with their relabelings enables constant-time updates; 171 non-isomorphic patterns on four nodes can be stored in memory.Source: METHODS · p. 7
- Motif over- or under-expression is assessed against 20 configuration-model samples, using each motif’s abundance relative to random networks.Higher-order motif analysis counts motif frequencies in the observed network and compares them with a null model.Source: METHODS · p. 7
- Following, the method sets ϵ = 4 and defines the Significance Profile as the vector of motif ∆i values normalized to length 1.Source: METHODS · p. 7
S1. DATASETS
The study assembles real-world higher-order datasets from social, technological, biological, and co-authorship domains, with hyperedges representing group interactions or shared attributes.
S1. DATASETS
- The dataset collection spans social proximity and voting, technology emails, biological gene/disease and drug data, and co-authorship networks.The section presents these datasets as the empirical basis for motif analysis of real-world higher-order systems.Source: S1. DATASETS · p. 11
- Gene/disease hyperedges group genes associated with a disease, while NDC classes and NDC substances group drug classification labels and constituent substances, respectively.Each drug in the two NDC datasets is timestamped by its first marketed day.Source: S1. DATASETS · p. 11
- DBLP, history, and geology hyperedges group publication coauthors, while PACS also timestamps papers and enables division into ten physics subfields.PACS subfields use the highest hierarchical level of the classification.Source: S1. DATASETS · p. 11
- Wiki and Justice encode same-vote groups among users and Supreme Court justices, while email-EU and email-ENRON hyperedges join each sender with all recipients.The Justice data cover US Supreme Court votes from 1946 to 2019; email events are timestamped in both email datasets.Source: S1. DATASETS · p. 11
- Primary school and high school contacts use 20-second windows, with each hyperedge a maximal clique in a temporal-network layer.Nodes are students; wearable sensors record proximity contacts.Source: S1. DATASETS · p. 11
- Conference, hospital, workplace, and baboon proximity datasets likewise encode 20-second contact windows as maximal cliques in temporal-network layers.Nodes are people at the respective settings, and baboons in an enclosure at a French Primate Center.Source: S1. DATASETS · pp. 11–12