Source-linked AI summary
Motifs in temporal hypergraphs
Quintino Francesco Lotito, Lorenzo Betti, Federico Battiston, Giuseppe Francesco Italiano
TL;DR
Static pairwise networks can miss interactions that involve groups, unfold over time, or encode direction. The paper defines temporal motifs for hypergraphs, develops exact mining algorithms and a null model, and reports that these motifs distinguish local organization across domains while dynamic programming achieves orders-of-magnitude speedups on empirical datasets.
Problem
Static pairwise networks may not represent interactions that involve groups, occur over time, or encode directionality.
Source: §I · p. 1Method
The paper defines temporal motifs for directed and undirected hypergraphs, develops exact enumeration algorithms, and uses a null model to assess motif expression.
Source: §I · p. 1, §VI · p. 6Results
Temporal hypergraph motifs distinguish forms of local organization across domains, and dynamic programming achieves orders-of-magnitude speedups over direct enumeration on empirical datasets.
Source: §I · p. 1Takeaways & Limitations
Temporal hypergraph motifs provide a local-scale description of how higher-order interaction patterns unfold over time.
Source: §IX · p. 11
Abstract
from arXiv · showhide
Network motifs, recurrent local patterns of interactions in graphs, provide fundamental insights on the interplay between structure and functionality in complex systems. Many real-world systems are not well represented by traditional static pairwise networks, as interactions may involve groups of nodes, occur over time, or encode directionality. In this paper, we introduce temporal motifs for hypergraphs and directed hypergraphs, extending motif analysis to timestamped many-body interactions. We formalize the corresponding mining problem, study the combinatorial structure of these motifs, and develop exact algorithms for their enumeration. In particular, we propose a dynamic programming algorithm that substantially reduces the computational cost of motif mining, achieving orders of magnitude speedups on empirical datasets. We also introduce a null model for temporal hypergraphs to assess the statistical over- and under-expression of motifs. Applying the proposed framework to real-world datasets from different domains, including face-to-face contacts, scientific collaborations, e-mail exchanges, and Bitcoin transactions, we show that temporal hypergraph motifs reveal distinct forms of local organization across systems. Finally, we demonstrate their use as an exploratory tool through focused case studies on persistent patterns in scientific collaborations and e-mail communications.
I. INTRODUCTION
Static pairwise networks can miss important organization in systems with group interactions and temporal ordering, motivating motif analysis for temporal hypergraphs. The paper introduces definitions, exact mining algorithms, and a null model, then uses motifs to characterize local organization across domains.
I. INTRODUCTION
- Static pairwise representations may hide structural organization in systems where interactions involve groups or evolve over time.Hypergraphs represent many-body interactions, while temporal ordering can carry information about local patterns.Source: §I · p. 1
- Across domains, over-expressed motifs distinguish local organization, including rapid group formation, persistent collaboration cores, dynamic email threads, and stable transaction roles.Two case studies use motifs as descriptors of group persistence and individual participation.Source: §I · p. 1
- The paper defines temporal motifs for undirected and directed hypergraphs, studies their combinatorics, develops exact mining algorithms, and introduces a null model.The null model is used to characterize motif over- and under-expression across empirical datasets.Source: §I · p. 1
A. Temporal and higher-order interactions in complex systems
- Hypergraphs and temporal networks extend motif analysis to capture many-body interactions and patterns occurring within limited time windows.Prior work also studied temporal hypergraphs and their distinctive group formation, growth, and dissolution.Source: A. Temporal and higher-order… · p. 2
B. Network motifs beyond simple graphs
Motif analysis has expanded beyond simple graphs, but prior hypergraph approaches treat temporal patterns differently or focus on static subhypergraphs. This paper defines temporal motifs for directed and undirected hypergraphs and formalizes their occurrence-counting problem.
B. Network motifs beyond simple graphs
- Prior hypergraph motif frameworks analyze recurrent overlapping hyperedges or over-expressed subhypergraphs, with separate extensions for direction and time.This work adds time to a node-based framework for both undirected and directed hypergraphs.Source: B. Network motifs beyond simple graphs · p. 2
III. PRELIMINARIES AND PROBLEM STATEMENT
- A temporal hypergraph consists of timestamped undirected group interactions or directed interactions with disjoint, nonempty source and target sets.Directed hyperedge size is the number of nodes in the union of its source and target sets.Source: §III · pp. 2–3
- A temporal motif has ordered hyperedges spanning at most δ, uses exactly K nodes, has connected static projection, and includes a higher-order interaction.An occurrence maps the motif's nodes injectively to observed nodes while preserving event order and, in directed cases, source and target sets.Source: §III · p. 3
- The mining problem counts occurrences in each isomorphism class of (K, L, δ)-temporal motifs in a given temporal hypergraph.Motifs differing only by node relabelling count as the same pattern.Source: §III · p. 3
IV. COMBINATORIAL ANALYSIS
The combinatorial analysis bounds the number of connected temporal motifs by relating them to labelled hyperedge sequences and node relabellings. The framework is instantiated for undirected and directed hyperedge catalogues, with bounds intended as growth characterizations rather than tight estimates.
IV. COMBINATORIAL ANALYSIS
- The total number of labelled length-L temporal sequences on K vertices is based on the catalogue size H(K), giving the upper bound mT(K, L) ≤ H(K)^L.Here, mT(K, L) counts non-isomorphic connected temporal motifs on K nodes and length L.Source: §IV · pp. 3–4
- A motif can produce at most K! labelled sequences, and requiring a spanning hyperedge supplies a connected-sequence lower-bound construction.The lower bound accounts for node-label permutations by dividing by K!.Source: §IV · pp. 3–4
- The analysis substitutes undirected and directed hyperedge catalogue sizes into the general bounds to obtain model-specific bounds.The proposed bounds characterize motif-space growth but are not intended to be tight.Source: §IV · pp. 3–4
V. ALGORITHMS
The two exact counting algorithms share an initial reduction: they construct candidate node supports and count motif occurrences only within those supports.
V. ALGORITHMS
- Both exact algorithms first construct a reduced set of candidate node supports, then restrict motif-occurrence counting to those supports.This shared step is the common opening stage of the two algorithms.Source: §V · p. 4
A. Common support computation
The shared support step narrows motif counting to candidate node sets generated from higher-order events. The baseline then directly enumerates valid temporal sequences within each support.
A. Common support computation
- Candidate supports are built from higher-order seed events: a size-K seed defines a support, while smaller seeds are extended through an overlapping event whose union has K nodes.The strategy is exact for K ∈ {3, 4}, because every valid motif contains at least one higher-order interaction.Source: A. Common support computation · p. 4
B. Baseline
- For each support, the baseline extracts its local event sequence and enumerates length-L subsequences with strictly increasing timestamps and span at most δ.A sequence counts only if it uses all K support nodes, contains a higher-order event, and has connected static projection.Source: B. Baseline · p. 4
- The baseline’s cost is dominated by enumerating local length-L subsequences, which can become numerous in dense event sequences.The cost proxy sums the number of eligible subsequences across candidate supports.Source: B. Baseline · pp. 4–5
C. Local window dynamic programming
LocalWindow-DP replaces repeated subsequence enumeration with prefix counting over local event states. It preserves exact counts while reducing repeated work within the temporal window.
C. Local window dynamic programming
- For each support, events become local states, and the method precomputes valid length-L state sequences and their canonical motif labels.Undirected states are node subsets of size at least two; directed states are pairs of disjoint non-empty source and target subsets.Source: C. Local window dynamic programming · p. 5
- The algorithm scans each local event sequence once, maintaining prefix counts in a sliding window whose events are within δ of the current event.When an event leaves the window, counts for prefixes beginning with that event are subtracted, preserving the temporal constraint.Source: C. Local window dynamic programming · p. 5
- Same-timestamp events are processed as a batch, so they may be alternative choices in an occurrence but cannot appear together in one occurrence.Counts are updated against earlier prefixes before the prefix tables are updated in decreasing sequence length.Source: C. Local window dynamic programming · p. 5
- LocalWindow-DP is exact and returns the same counts as the baseline, while avoiding repeated work on overlapping local subsequences.After shared support computation, a useful counting-cost proxy is the sum of local sequence lengths; for the experiments, K and L are in {3, 4}, so state-space factors are constant.Source: C. Local window dynamic programming · p. 5
VI. NULL MODELS AND EVALUATION OF TEMPORAL
The null model shuffles timestamps within coarse windows and event-signature groups while leaving hyperedge participants unchanged. Motif counts are compared with null realizations and converted to z-scores for ranking over- and under-expression.
VI. NULL MODELS AND EVALUATION OF TEMPORAL
- For each motif, the observed count is compared with counts from independent null-model realizations to obtain a null mean, standard deviation, and z-score.The windowed shuffle is designed to preserve coarse local event density while disrupting fine-scale temporal correlations.Source: §VI · p. 6
- Motifs are ranked within each dataset by z-score, with large positive or negative scores labeled over- or under-expressed relative to the null model.The scores standardize the deviation between the empirical count and the null ensemble.Source: §VI · p. 6
- The null model uniformly permutes timestamps within coarse time windows and groups of matching event signatures, preserving participants and the static hypergraph.Undirected signatures use hyperedge size; directed signatures use the ordered source- and target-set sizes.Source: §VI · p. 6
VII. EXPERIMENTAL RESULTS
Across four empirical datasets, the dynamic-programming approach consistently outperformed the baseline, often by several orders of magnitude. The evaluation also reports dataset statistics and the parameter settings used for runtime and statistical analyses.
VII. EXPERIMENTAL RESULTS
- The four datasets cover undirected face-to-face contacts and scientific collaborations, and directed e-mail exchanges and Bitcoin transactions.The datasets use different temporal resolutions, ranging from 20-second contacts to daily-indexed collaborations.Source: §VII · p. 6
- Runtime tests used K ∈ {3, 4} and L ∈ {3, 4}; statistical analyses used K ∈ {3, 4}, L = 3, and 10 null-model realizations.Z-scores were used descriptively to rank motif enrichment rather than for formal hypothesis testing.Source: §VII · p. 6
A. Performance evaluation
- LocalWindow-DP consistently outperformed the baseline across the four datasets and tested configurations, often by several orders of magnitude.Fig. 2 reports mean runtime over 10 runs on a logarithmic scale; hatched bars mark configurations stopped after 24 hours.Source: A. Performance evaluation · pp. 6–7, Figure 2 · p. 7
B. Undirected hypergraphs
Over-expressed motifs reveal distinct temporal organization in undirected and directed hypergraphs, while occurrence-level analyses characterize persistent groups and individual participation.
B. Undirected hypergraphs
- Face-to-face motifs trace group encounters splitting into overlapping contacts or reappearing, as well as smaller contacts growing into group interactions.These patterns suggest groups form through smaller contacts, split into overlapping subgroups, and sometimes reappear shortly afterward.Source: B. Undirected hypergraphs · p. 7
- Scientific collaboration motifs often preserve a subset of authors across papers while other collaborators enter or leave.The authors interpret this as a persistent collaboration core with a changing periphery.Source: B. Undirected hypergraphs · p. 7
C. Directed hypergraphs
- Over-expressed e-mail motifs include repeated broadcasts, replies, and relays, forming recurring local threads with reused or redirected audiences.These patterns involve local changes in sender and recipient roles.Source: C. Directed hypergraphs · p. 7
- Bitcoin motifs more often retain source-target roles, with repeated source addresses sending to partially overlapping target sets.The authors interpret these patterns as consistent with repeated payments or other practices with comparatively stable transaction roles.Source: C. Directed hypergraphs · p. 7
VIII. PRACTICAL USE CASES
- The case studies shift from enriched motif types to all motif occurrences to characterize persistent groups and individual participation.The core is the set of nodes present in every interaction; coreness measures a node’s fraction of motif participations in the core, while neighbor turnover is mean Jaccard distance between consecutive active-time neighborhoods separated by at most δ.Source: §VIII · p. 9
A. Persistent collaboration cores in scientific production
The collaboration-core analysis links recurring author groups with individual participation over time. It finds that a small set of recurring groups accounts for a disproportionate share of motif occurrences, alongside changing author roles and generally high neighbor turnover.
A. Persistent collaboration cores in scientific production
- The analysis uses K = 4, L = 3 motifs with δ = 1826 days in Computer Science arXiv data from 1998 to 2022.Motifs are extracted separately within five disjoint five-year periods; author roles are assigned using coreness averages, with thresholds below 0.25 for peripheral and above 0.75 for core.Source: A. Persistent collaboration cores in… · p. 9
- A small set of recurring author groups accounts for a disproportionate share of motif occurrences.Pairs dominate the multi-author cores analyzed.Source: A. Persistent collaboration cores in… · p. 9
- Most authors initially classified as peripheral remain peripheral, while most initially core authors later become mixed or peripheral.The authors describe this as an asymmetry in the persistence of these roles.Source: A. Persistent collaboration cores in… · p. 9
- Neighbor turnover is generally high across the coreness range, and authors with similar coreness can differ substantially in partner stability.Author profiles span almost the full coreness range.Source: A. Persistent collaboration cores in… · p. 9
- The study connects recurrence of specific author groups with changes in individual participation.This is the authors’ overall characterization of the analysis.Source: A. Persistent collaboration cores in… · p. 9
B. Persistent communication cores in e-mail exchanges
The e-mail case study uses directed temporal motifs to characterize persistent cores, reciprocity, and role switching. The conclusion presents these analyses as descriptive uses of a broader temporal-hypergraph mining framework.
B. Persistent communication cores in e-mail exchanges
- The e-mail analysis extracts directed motifs with K ∈ {3, 4}, L = 3, and δ = 1 day, and defines role change and weak reciprocity within motif occurrences.Weak reciprocity requires nodes to move in both directions between target and source roles across two interactions.Source: B. Persistent communication cores in… · p. 9
- Group interactions are often reciprocated through selective exchanges; low-coreness nodes can have stable neighborhoods, while high-coreness participants combine persistence with changing groups.Low-coreness participants can still alternate between sending and receiving within motif cores.Source: B. Persistent communication cores in… · p. 10
- Persistent groups dominate 3-node motifs, whereas 4-node motifs center on one persistent participant; same-size reciprocal interactions have shorter median delays.The reciprocity analysis counts each qualifying pair once and retains the earliest qualifying reciprocation within extracted motifs and the one-day horizon.Source: B. Persistent communication cores in… · p. 10, Figure 6 · p. 11
IX. CONCLUSION
- The framework provides exact mining algorithms and a null model, while its dynamic programming approach achieves orders-of-magnitude speedups over direct enumeration on empirical datasets.The paper presents motif observables as local-scale descriptions of how higher-order interactions unfold over time.Source: §IX · pp. 10–11
- The conclusion identifies sampling algorithms that trade solution quality for performance as future work, noting that motif size K and temporal length L may affect algorithm choice.Source: §IX · p. 11
APPENDIX
The appendix uses the null model to identify under-expressed temporal motifs across undirected and directed datasets. These anti-motifs indicate arrangements that systems tend to suppress, not configurations that are impossible.
APPENDIX
- Anti-motifs occur less often than expected under the null model, which preserves the static hypergraph and coarse temporal activity profile; they are suppressed arrangements, not impossible ones.Source: APPENDIX · p. 11
- In undirected datasets, some under-expressed motifs fragment a group interaction into weakly overlapping or disconnected subgroups.This complements over-expression of repeated cores and partially reappearing groups in face-to-face contacts and scientific collaborations.Source: APPENDIX · p. 11
- Directed under-expressed motifs often combine role changes with unstable source–target configurations; e-mail suppresses incoherent role changes, while Bitcoin motifs tend to preserve stable transaction roles.In Bitcoin, patterns combining repeated transactions with abrupt role reversals are comparatively avoided.Source: APPENDIX · p. 11