CS Paper Radar

Motifs in temporal hypergraphs

Quintino Francesco Lotito, Lorenzo Betti, Federico Battiston, Giuseppe Francesco Italiano

cs.SI cs.DSphysics.soc-ph ·submitted 2026-09-10 20:08 UTC · v1

Abstract

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Faster network motif discovery by counting isomorphic subtrees

cs.DS ·2026-09-30 ·Tarek Tohme, Joshua A. Grochow
theory similarity 0.67
Abstract

We develop a new algorithm for counting the number of subgraphs of a network isomorphic to a given query graph (#SubgraphIsomorphism), motivated by network motif search. High-degree vertices (hubs), common in real-world networks, contribute to a combinatorial explosion in the number of subgraphs, making existing motif search algorithms intractable for motif sizes greater than $\approx 8$ on a wide variety of networks of interest. Our procedure leverages the $k$-core decomposition and a novel subtree-counting technique to quickly scan the periphery of a network. These two innovations allow our algorithm to significantly speed up its predecessors in practice, especially as most real-world networks have a relatively large periphery. We prove that #RootedSubtreeIsomorphism, a key subroutine in our algorithm, is #P-complete via a reduction from counting bipartite matchings. We provide analytic upper bounds on our algorithm's execution time, and evaluate its performance on 11 real-world networks of varying topologies.

0.15

Activity-based temporal hypergraphs: from individual activity to collective social dynamics

cs.SI physics.soc-phcond-mat.stat-mechphysics.data-an ·2026-10-26 ·Marco Mancastroppa, Giulia Cencetti, Iacopo Iacopini, Giovanni Petri, Alain Barrat
similarity 0.65
Abstract · 19 pages, 6 figures

Temporal hypergraphs provide an interesting representation for many social systems, as they integrate both the temporal and group nature of social interactions. Designing models of time-varying hyper-networks yields thus a convenient way to generate surrogates of empirical social systems, to understand the mechanisms underlying their emergent properties, and to investigate the evolution of dynamical processes taking place on such structures. Here, we focus on a specific and powerful class of these models, the activity-based temporal hypergraphs. We show how activity mechanisms provide control over the time scale of the dynamics, allow high modelling flexibility, and capture heterogeneity in agents' behavior. We also highlight how the activity can straightforwardly be extracted from empirical data to create surrogate datasets. We present paradigmatic examples of such models: the higher-order activity-driven models (HADx), which show that different underlying rules for the selection of active interactions produce different higher-order dynamics; the Emerging Activity Temporal Hypergraph model (EATH), able to generate surrogates of empirical systems by using higher-order mechanisms driven by both activity and group memory. We conclude discussing future perspectives for activity-based temporal hypergraphs, highlighting the potential of this framework to bridge realistic modelling of social dynamics with the study of the complex dynamical process they can support, from social contagion to opinion dynamics.

0.13

Directed-Hypergraph Analytics and Fragility Testing for Anti-Money Laundering

eess.SP ·2026-10-16 ·Run Li, Paul Laux
similarity 0.63
Abstract

Illicit activity in financial networks is difficult to detect. We exploit the idea that the chance of a transaction being illicit depends partly on the concurrent positions and recent actions of counterparties, as well as the higher-order organization of fund flows. We combine hypergraph features and machine learning to demonstrate practical ef fectiveness. Specifically, we use the Elliptic++ Bitcoin dataset to show that graph and directed-hypergraph-based features improve illicit-address classification. The suc cess of the predictive model then allows us to examine potential money-laundering chains are structurally fragile. Several illicit-to-licit transaction motifs with unknown intermediary addresses specified, and the fragility of these motifs is evaluated through progressive removal of the highest-risk intermediaries. Surprisingly, these motifs are fragile, suggesting that money laundering could be disrupted via the identification and exclusion of owners of a limited number of crypto wallets.

0.22

An Interpretable Approach to Money Laundering Detection in Transaction Graphs using Pass-Through Templates

cs.SI ·2026-09-17 ·Paolo Climaco
similarity 0.60
Abstract

Layering is a key stage of the money laundering process in which assets are moved through intermediate entities to obscure their origin. We model this movement as a transaction graph, a labeled directed multigraph where nodes represent entities, such as individuals or organizations, and edges represent transactions between them. This work addresses the detection of layering patterns in transaction graphs. We define pass-through templates, a class of transaction graphs whose structure is indicative of a specific layering pattern in which entities receive funds and rapidly forward them. We formulate detecting instances of these templates within a larger transaction graph as a maximum-cardinality, maximum-weight matching problem. The resulting method uses Edmonds' blossom algorithm, which provably finds an optimal solution to this problem. Here we present a case study on publicly available Ethereum transaction data. We identify 283 pass-through template instances, chained through shared address nodes into a densely interconnected network that moves hundreds of millions of dollars in stablecoin value. We find that six addresses in the identified network are sanctioned by the U.S. Department of the Treasury for associations with criminal organizations, providing evidence of ties between the network and sanctioned criminal entities.

0.16

A Novel Information Workflow for Structural Behavioural Analysis in Dynamic Attributed Graphs

cs.SI ·2026-08-27 ·Gatadi Ashwitha, K. Swarupa Rani
similarity 0.59
Abstract · 12 pages, 2 figures

Social systems play a vital role through interactions around shared interests and the maintenance of relationships, which are part of society. These can be represented as networks, and their analysis plays a crucial role in dynamic environments, which can be achieved through link prediction and community detection tasks. Several link prediction approaches estimate new relationships, such as suggesting friends on social media. On the other hand, a social faction is a group of connected people that reveals the internal structure of the social system and can be identified through community detection approaches. The evolution of social systems can be understood using these approaches by analysing their structure and behaviour. To handle this, a combination of these approaches, along with interaction-based analysis, is used to form cohesive communities, thereby enabling the study of social systems dynamically. In addition, attribute information plays a critical role. Most real-world graphs, like Facebook and Twitter, have attribute information that provides context, and integrating them with structural information offers deeper insights into patterns, which is a critical task. However, existing approaches have limitations in handling dynamics of social systems. Additionally, no existing approaches in the literature help identify potential links and form densely connected communities for attributed graphs. To address these challenges, we have proposed an information workflow, i.e., inc-LPCDAG (\underline{inc}remental Link Prediction and Community Detection in Attributed Graphs). We conducted experiments to evaluate efficiency, and results demonstrate the effectiveness of our proposed workflow by analysing and understanding structural and behavioural processes.

0.34

WCCS: Efficient Wedge Conductance Community Search over Large Temporal Bipartite Graphs (Full Paper)

cs.SI ·2026-09-15 ·Longlong Lin, Wei Chen, Pingpeng Yuan, Ruikun Luo, Qiangqiang Dai +1 more
similarity 0.59
Abstract

Bipartite graphs are ubiquitous for modeling complex interactions between two distinct entity types across numerous practical applications such as e-commerce, academic networks, and social systems. Despite significant progress in community search over bipartite graphs, most prior work is limited to static settings and ignores the rich temporal dynamics present in real-world networks. Moreover, existing methods typically adopt edge-centric measures and strict consecutivity constraints, failing to capture higher-order interactions and frequent yet non-consecutive activities. More importantly, they often neglect the crucial community-quality requirements of both internal cohesiveness and external sparsity, failing to identify critical nodes or including many irrelevant nodes. To address these dilemmas, we propose the novel problem of \emph{Wedge Conductance Community Search (WCCS)}, which aims to identify a query-dependent community that is not only structurally and temporally cohesive but also well-separated from the rest of the network over non-consecutive timestamps. We formalize WCCS by generalizing the classical $(α,β)$-core to a higher-order $(α,β,τ)$-wedge core, and by proposing a novel temporal wedge conductance metric that explicitly balances internal density and external sparsity. To solve WCCS efficiently, we first develop an online priority-driven filter-and-expand framework with several effective pruning techniques and a powerful geometric slope optimization for rapid temporal wedge conductance calculation. Subsequently, to further improve scalability, we propose an offline compressed index to accelerate search. Finally, comprehensive experiments on seven real-world datasets demonstrate the effectiveness, efficiency, and scalability of our solutions compared to eight competitors.

0.11

DyNA-Mixer: Decoupling Time and Topology for Scalable Dynamic Node Affinity Prediction

cs.LG ·2026-11-18 ·Yuanxing Zheng, Liping Wang, Xuemin Lin
benchmark similarity 0.59
Abstract · Includes appendices

Continuous-time dynamic graphs preserve the ordering, timing, and evolving strength of interactions that static snapshots discard, making dynamic graph mining essential for evolving systems such as recommender systems, trade networks, and transaction platforms. Research in this area has centered on dynamic link prediction, which forecasts only whether a future interaction will occur, whereas many applications also need its intensity. The dynamic node affinity prediction (DNAP) problem generalizes this task to continuous targets and full-candidate ranking, making it more broadly applicable but substantially harder. This raises two coupled difficulties: ranking requires a predictor expressive enough to capture both multi-scale temporal evolution and graph-wide collaborative patterns, yet running such a predictor over every source--destination pair is computationally prohibitive. We propose DyNA-Mixer, which decouples temporal forecasting from collaborative structure modeling. It adopts a multi-scale temporal predictor for pair-specific affinity evolution, constructs a Virtual Collaborative Graph that infers query-time relationships and aggregates trends from related interactions, and fuses the two through a gated residual mechanism. A sparsity-aware evaluation strategy further restricts expensive forecasting to pairs with recent non-zero affinities. Experiments on four Temporal Graph Benchmark datasets for the DNAP problem show that DyNA-Mixer achieves new state-of-the-art NDCG@10 on every dataset, including a 17.8\% relative test improvement over the strongest baseline on tgbn-token, the largest dataset.

0.10

Mining Correlated Motifs with Wildcards in PPI Networks: Exact and Optimal

cs.DS ·2026-10-13 ·Lucas P. Oliveira, Ben Bals, Aalt D. J. van Dijk, Solon P. Pissis
similarity 0.59
Abstract · ALENEX 2027

A protein-protein interaction (PPI) network is a graph whose nodes are protein sequences and whose edges represent physical interactions between proteins. Correlated Motif Mining (CMM) seeks pairs of sequence motifs whose co-occurrence in interacting proteins reveals binding sites and interaction mechanisms. Formally, in the $(\ell,d)$-CMM problem, we are given a graph $G=(V,E)$, with $V\subseteqΣ^*$ for an alphabet $Σ$, and integers $0\leq d<\ell$, and we seek a pair $\{X,Y\}$ of motifs, each of length $\ell$ and containing $d$ wildcards, that maximizes a support measure $f(G,\{X,Y\})$; e.g., the count $f_E$ of edges $\{u,v\}\in E$ such that $X$ matches a substring of $u$ and $Y$ matches a substring of $v$, or vice versa. Although existing approaches have produced biologically meaningful results, they are either inefficient or heuristic-based, as the underlying optimization problem is NP-hard. Here, we revisit $(\ell,d)$-CMM. For $d=0$, we give an exact $\mathcal{O}(N^2)$-time and $\mathcal{O}(N)$-space algorithm, where $N$ is the total length of the node strings, and prove that this time is conditionally optimal under the Strong Exponential-Time Hypothesis. For any $d>0$, we give an exact $\mathcal{O}\!\left(\binom{\ell}{d}^2N^2\right)$-time and $\mathcal{O}(N)$-space algorithm, and observe that the problem is W[1]-hard parameterized by $d$. The latter algorithm improves the state of the art by exponentially large factors in both time and space. We further demonstrate experimentally that our algorithms are practical on real-world PPI networks and find significantly higher-scoring motif pairs than the state of the art. Moreover, we show that our algorithms find many top-scoring motif pairs that the state of the art misses entirely. Taken together, our results suggest that exact CMM with wildcards is more tractable in practice than previously assumed.

0.23