提出并行算法PTMT，高效发现大规模时序图中模式的动态演化过程。
Efficient Discovery of Motif Transition Process for Large-Scale Temporal Graphs
- 采用树形框架与时间-结构分区策略，实现无损模式转移追踪。
- 在10个真实数据集上比现有最优方法快12.0至50.3倍。
- 适合处理超大规模时序图的模式演化分析，如社交网络、交通系统。
理解时序图中模式的动态演化对于揭示图结构随时间的变化、识别关键模式和预测未来行为至关重要，但现有方法通常依赖预定义模式，难以全面捕捉转移关系。我们提出一种并行模式转移过程发现算法PTMT，通过树形框架结合时间区划分（TZP）策略，按时间和结构分割时序图，在保留无损模式转移的同时实现大规模并行。PTMT包含三个阶段：生长区并行扩展、重叠感知结果聚合、模式转移确定性编码，确保对动态转移与交互的精确追踪。在10个真实数据集上的实验表明，相比当前最优方法，PTMT速度提升达12.0×至50.3×。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。