Efficient Discovery of Motif Transition Process for Large-Scale Temporal Graphs

• URL: http://arxiv.org/abs/2504.15979v2
• Date: Mon, 18 Aug 2025 10:03:29 GMT
• Title: Efficient Discovery of Motif Transition Process for Large-Scale Temporal Graphs
• Abstract summary: PTMT is a novel method for discovering transition processes in large-scale temporal graphs.<n>It integrates a tree-based framework with the temporal zone (TZP) strategy, which partitions temporal zone by time and structure.<n>Results on 10 real-world datasets demonstrate that PTMT speedups range from 12.0$times$ 50.3$times$ compared to the SOTA method.
• Score: 28.680759318270727
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Understanding the dynamic transition of motifs in temporal graphs is essential for revealing how graph structures evolve over time, identifying critical patterns, and predicting future behaviors, yet existing methods often focus on predefined motifs, limiting their ability to comprehensively capture transitions and interrelationships. We propose a parallel motif transition process discovery algorithm, PTMT, a novel parallel method for discovering motif transition processes in large-scale temporal graphs. PTMT integrates a tree-based framework with the temporal zone partitioning (TZP) strategy, which partitions temporal graphs by time and structure while preserving lossless motif transitions and enabling massive parallelism. PTMT comprises three phases: growth zone parallel expansion, overlap-aware result aggregation, and deterministic encoding of motif transitions, ensuring accurate tracking of dynamic transitions and interactions. Results on 10 real-world datasets demonstrate that PTMT achieves speedups ranging from 12.0$\times$ to 50.3$\times$ compared to the SOTA method.

Related papers

• DyG$^2$T: Modeling Object Dynamics with 3D Gaussian Temporal-Spatial Particle Graph Transformer [86.4618122245946]
  DyG$2$T is a dynamics modeling framework that infers object motion trajectories by spatially completing and temporally discriminating Key Point representations.<n>Experiments on both synthetic and real-world datasets demonstrate that DyG$2$T achieves accurate dynamics modeling and reasoning.
  arXiv  Detail & Related papers  (2026-08-19T03:44:28Z)
• Learning Long Range Spatio-Temporal Representations over Continuous Time Dynamic Graphs with State Space Models [22.610672356493378]
  Continuous-time dynamic graphs (CTDGs) provide a richer framework to capture fine-grained temporal patterns in evolving data.<n>We derive a parameter-efficient state-space modeling framework for continuous-time dynamic graphs.<n>CTDG-SSM achieves large performance gains on datasets that require long range temporal (LRT) and spatial reasoning.
  arXiv  Detail & Related papers  (2026-06-03T09:54:35Z)
• BTS-rPPG: Orthogonal Butterfly Temporal Shifting for Remote Photoplethysmography [2.5608506499175103]
  Remote photoplethysmography (r) enables contactless physiological sensing from facial videos by analyzing subtle appearance variations induced by blood circulation.<n>We propose BTS-r, a temporal modeling framework based on Ortho Butterfly Temporal Shifting.<n>We show that BTS-r improves long-range temporal modeling of physiological dynamics and consistently outperforms existing temporal modeling strategies for r estimation.
  arXiv  Detail & Related papers  (2026-04-02T06:31:09Z)
• Temporal Graph Pattern Machine [17.352525018007473]
  Temporal Graph Pattern Machine (TGPM) conceptualizes each interaction as an interaction patch synthesized via temporally-biased random walks.<n>TGPM consistently achieves state-of-the-art performance in both transductive and inductive link prediction.
  arXiv  Detail & Related papers  (2026-01-30T01:46:13Z)
• Temporal Attention Evolutional Graph Convolutional Network for Multivariate Time Series Forecasting [2.6138578479379104]
  This paper introduces the Temporal Attention Evolutional Graph Convolutional Network (TAEGCN) TAEGCN adeptly captures temporal causal relationships and hidden spatial dependencies within the data. Experimental results conducted on two public transportation network datasets, METR-LA and PEMS-BAY, demonstrate the superior performance of the proposed model.
  arXiv  Detail & Related papers  (2025-05-01T04:50:00Z)
• ScaDyG:A New Paradigm for Large-scale Dynamic Graph Learning [31.629956388962814]
  ScaDyG is a time-aware scalable learning paradigm for dynamic graph networks.<n> experiments on 12 datasets demonstrate that ScaDyG performs comparably well or even outperforms other SOTA methods in both node and link-level downstream tasks.
  arXiv  Detail & Related papers  (2025-01-27T12:39:16Z)
• Community-Aware Temporal Walks: Parameter-Free Representation Learning on Continuous-Time Dynamic Graphs [3.833708891059351]
  Community-aware Temporal Walks (CTWalks) is a novel framework for representation learning on continuous-time dynamic graphs.<n>CTWalks integrates a community-based parameter-free temporal walk sampling mechanism, an anonymization strategy enriched with community labels, and an encoding process.<n> Experiments on benchmark datasets demonstrate that CTWalks outperforms established methods in temporal link prediction tasks.
  arXiv  Detail & Related papers  (2025-01-21T04:16:46Z)
• A Poisson-Gamma Dynamic Factor Model with Time-Varying Transition Dynamics [51.147876395589925]
  A non-stationary PGDS is proposed to allow the underlying transition matrices to evolve over time. A fully-conjugate and efficient Gibbs sampler is developed to perform posterior simulation. Experiments show that, in comparison with related models, the proposed non-stationary PGDS achieves improved predictive performance.
  arXiv  Detail & Related papers  (2024-02-26T04:39:01Z)
• TimeGraphs: Graph-based Temporal Reasoning [64.18083371645956]
  TimeGraphs is a novel approach that characterizes dynamic interactions as a hierarchical temporal graph. Our approach models the interactions using a compact graph-based representation, enabling adaptive reasoning across diverse time scales. We evaluate TimeGraphs on multiple datasets with complex, dynamic agent interactions, including a football simulator, the Resistance game, and the MOMA human activity dataset.
  arXiv  Detail & Related papers  (2024-01-06T06:26:49Z)
• Using Motif Transitions for Temporal Graph Generation [0.0]
  We develop a practical temporal graph generator to generate synthetic temporal networks with realistic global and local features. Our key idea is modeling the arrival of new events as temporal motif transition processes. We demonstrate that our model consistently outperforms the baselines with respect to preserving various global and local temporal graph statistics and runtime performance.
  arXiv  Detail & Related papers  (2023-06-19T22:53:42Z)
• EasyDGL: Encode, Train and Interpret for Continuous-time Dynamic Graph Learning [92.71579608528907]
  This paper aims to design an easy-to-use pipeline (termed as EasyDGL) composed of three key modules with both strong ability fitting and interpretability. EasyDGL can effectively quantify the predictive power of frequency content that a model learn from the evolving graph data.
  arXiv  Detail & Related papers  (2023-03-22T06:35:08Z)
• Time-aware Dynamic Graph Embedding for Asynchronous Structural Evolution [60.695162101159134]
  Existing works merely view a dynamic graph as a sequence of changes. We formulate dynamic graphs as temporal edge sequences associated with joining time of. vertex and timespan of edges. A time-aware Transformer is proposed to embed. vertex' dynamic connections and ToEs into the learned. vertex representations.
  arXiv  Detail & Related papers  (2022-07-01T15:32:56Z)
• Spatio-Temporal Joint Graph Convolutional Networks for Traffic Forecasting [75.10017445699532]
  Recent have shifted their focus towards formulating traffic forecasting as atemporal graph modeling problem. We propose a novel approach for accurate traffic forecasting on road networks over multiple future time steps.
  arXiv  Detail & Related papers  (2021-11-25T08:45:14Z)
• Continuous-Time Sequential Recommendation with Temporal Graph Collaborative Transformer [69.0621959845251]
  We propose a new framework Temporal Graph Sequential Recommender (TGSRec) upon our defined continuous-time bi-partite graph. TCT layer can simultaneously capture collaborative signals from both users and items, as well as considering temporal dynamics inside sequential patterns. Empirical results on five datasets show that TGSRec significantly outperforms other baselines.
  arXiv  Detail & Related papers  (2021-08-14T22:50:53Z)

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.