TIMEST: Temporal Information Motif Estimator Using Sampling Trees

• URL: http://arxiv.org/abs/2507.20441v1
• Date: Sun, 27 Jul 2025 23:31:55 GMT
• Title: TIMEST: Temporal Information Motif Estimator Using Sampling Trees
• Authors: Yunjie Pan, Omkar Bhalerao, C. Seshadhri, Nishil Talati,
• Abstract summary: We present TIMEST: a general, fast, and accurate estimation algorithm to count temporal motifs of arbitrary sizes in temporal networks.<n>We show that TIMEST is both faster and more accurate than previous algorithms.<n>For example, TIMEST can count the number of instances of a financial temporal motif in four minutes with 0.6% error, while exact methods take more than two days.
• Score: 5.114632024458956
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: The mining of pattern subgraphs, known as motifs, is a core task in the field of graph mining. Edges in real-world networks often have timestamps, so there is a need for temporal motif mining. A temporal motif is a richer structure that imposes timing constraints on the edges of the motif. Temporal motifs have been used to analyze social networks, financial transactions, and biological networks. Motif counting in temporal graphs is particularly challenging. A graph with millions of edges can have trillions of temporal motifs, since the same edge can occur with multiple timestamps. There is a combinatorial explosion of possibilities, and state-of-the-art algorithms cannot manage motifs with more than four vertices. In this work, we present TIMEST: a general, fast, and accurate estimation algorithm to count temporal motifs of arbitrary sizes in temporal networks. Our approach introduces a temporal spanning tree sampler that leverages weighted sampling to generate substructures of target temporal motifs. This method carefully takes a subset of temporal constraints of the motif that can be jointly and efficiently sampled. TIMEST uses randomized estimation techniques to obtain accurate estimates of motif counts. We give theoretical guarantees on the running time and approximation guarantees of TIMEST. We perform an extensive experimental evaluation and show that TIMEST is both faster and more accurate than previous algorithms. Our CPU implementation exhibits an average speedup of 28x over state-of-the-art GPU implementation of the exact algorithm, and 6x speedup over SOTA approximate algorithms while consistently showcasing less than 5% error in most cases. For example, TIMEST can count the number of instances of a financial fraud temporal motif in four minutes with 0.6% error, while exact methods take more than two days.

Related papers

• $\texttt{SPECS}$: Faster Test-Time Scaling through Speculative Drafts [55.231201692232894]
  $textttSPECS$ is a latency-aware test-time scaling method inspired by speculative decoding.<n>Our results show that $textttSPECS$matches or surpasses beam search accuracy while reducing latency by up to $sim$19.1%.
  arXiv  Detail & Related papers  (2025-06-15T05:50:05Z)
• Accurate and Fast Estimation of Temporal Motifs using Path Sampling [5.114632024458956]
  Counting the number of small subgraphs, called motifs, is a fundamental problem in social network analysis and graph mining. We propose an algorithm, TEACUPS, that addresses this problem using a novel technique of temporal path sampling. For a Bitcoin graph with hundreds of millions of edges, TEACUPS runs in less than 1 minute, while the exact counting algorithm takes more than a day.
  arXiv  Detail & Related papers  (2024-09-13T16:48:39Z)
• Representation Learning for Frequent Subgraph Mining [64.32430554934021]
  Subgraph Pattern Miner (SPMiner) is a novel neural approach for finding frequent subgraphs in a large target graph. For 5- and 6-node motifs, SPMiner can almost perfectly identify the most frequent motifs while being 100x faster than exact enumeration methods. SPMiner can also reliably identify frequent 10-node motifs, which is well beyond the size limit of exact enumeration approaches.
  arXiv  Detail & Related papers  (2024-02-22T08:11:22Z)
• Temporal Aggregation and Propagation Graph Neural Networks for Dynamic Representation [67.26422477327179]
  Temporal graphs exhibit dynamic interactions between nodes over continuous time. We propose a novel method of temporal graph convolution with the whole neighborhood. Our proposed TAP-GNN outperforms existing temporal graph methods by a large margin in terms of both predictive performance and online inference latency.
  arXiv  Detail & Related papers  (2023-04-15T08:17:18Z)
• Uncovering the Missing Pattern: Unified Framework Towards Trajectory Imputation and Prediction [60.60223171143206]
  Trajectory prediction is a crucial undertaking in understanding entity movement or human behavior from observed sequences. Current methods often assume that the observed sequences are complete while ignoring the potential for missing values. This paper presents a unified framework, the Graph-based Conditional Variational Recurrent Neural Network (GC-VRNN), which can perform trajectory imputation and prediction simultaneously.
  arXiv  Detail & Related papers  (2023-03-28T14:27:27Z)
• TimesNet: Temporal 2D-Variation Modeling for General Time Series Analysis [80.56913334060404]
  Time series analysis is of immense importance in applications, such as weather forecasting, anomaly detection, and action recognition. Previous methods attempt to accomplish this directly from the 1D time series. We ravel out the complex temporal variations into the multiple intraperiod- and interperiod-variations.
  arXiv  Detail & Related papers  (2022-10-05T12:19:51Z)
• Direct Embedding of Temporal Network Edges via Time-Decayed Line Graphs [51.51417735550026]
  Methods for machine learning on temporal networks generally exhibit at least one of two limitations. We present a simple method that avoids both shortcomings: construct the line graph of the network, which includes a node for each interaction, and weigh the edges of this graph based on the difference in time between interactions. Empirical results on real-world networks demonstrate our method's efficacy and efficiency on both edge classification and temporal link prediction.
  arXiv  Detail & Related papers  (2022-09-30T18:24:13Z)
• Motiflets -- Simple and Accurate Detection of Motifs in Time Series [3.6463708995502273]
  A time series motif intuitively is a short time series that repeats itself approximately the same within a larger time series. Motif discovery (MD) is the task of finding such motifs in a given input series. We present exact and approximate algorithms for finding k-Motiflets and analyze their complexity.
  arXiv  Detail & Related papers  (2022-06-08T08:22:28Z)
• Scalable Motif Counting for Large-scale Temporal Graphs [25.90869257290865]
  We propose a scalable parallel framework for exactly counting temporal motifs in large-scale temporal graphs. Based on the proposed counting algorithms, we design a hierarchical parallel framework that features both inter- and intra-node parallel strategies. Experiments on sixteen real-world temporal graph datasets demonstrate the superiority and capability of our proposed framework.
  arXiv  Detail & Related papers  (2022-04-20T05:41:38Z)
• odeN: Simultaneous Approximation of Multiple Motif Counts in Large Temporal Networks [7.025709586759655]
  One of the main complications in studying temporal motifs is the large number of motifs that can be built. We propose odeN, a sampling-based algorithm that provides an accurate approximation of all the counts of the motifs.
  arXiv  Detail & Related papers  (2021-08-19T15:06:05Z)
• Multi-Temporal Convolutions for Human Action Recognition in Videos [83.43682368129072]
  We present a novel temporal-temporal convolution block that is capable of extracting at multiple resolutions. The proposed blocks are lightweight and can be integrated into any 3D-CNN architecture.
  arXiv  Detail & Related papers  (2020-11-08T10:40:26Z)
• Efficient Sampling Algorithms for Approximate Temporal Motif Counting (Extended Version) [24.33313864327473]
  We propose a generic edge sampling (ES) algorithm for estimating the number of instances of any temporal motif. We also devise an improved EWS algorithm that hybridizes edge sampling with wedge sampling for counting temporal motifs with 3 vertices and 3 edges. Our algorithms have higher efficiency, better accuracy, and greater scalability than the state-of-the-art sampling method for temporal motif counting.
  arXiv  Detail & Related papers  (2020-07-28T07:15:25Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.