arXiv:2507.20441cs.DBcs.DS2025-07

提出快速估算任意规模时序图模式的方法,突破现有算法只能处理四顶点以下的限制。

TIMEST: Temporal Information Motif Estimator Using Sampling Trees

  • 设计基于加权采样的时序生成树,高效采样目标时序模式的子结构
  • 在百万边图上实现万亿级时序模式的精准估算,误差低于5%
  • 适用于金融欺诈等复杂时序网络分析,适合需要快速结果的研究者

模式子图挖掘(即动机)是图挖掘中的核心任务。现实网络中的边常带有时间戳,因此需要进行时序动机挖掘。时序动机是在动机边中施加时间约束的更丰富结构,已被用于分析社交网络、金融交易和生物网络。在时序图中统计动机尤其困难:一个包含数百万条边的图可能产生数万亿个时序动机,因为同一条边可出现多个时间戳,导致可能性呈组合爆炸式增长。当前最先进的算法仅能处理不超过四个顶点的动机。本文提出TIMEST:一种通用、快速且精确的算法,可对任意规模的时序网络中的时序动机进行估算。该方法引入时序生成树采样器,利用加权采样生成目标时序动机的子结构,并巧妙选择可联合高效采样的部分时间约束。TIMEST采用随机估算技术获得动机计数的高精度估计。我们给出了运行时间和近似保证的理论分析。实验表明,与之前算法相比,TIMEST更快且更准确。其CPU实现平均比最先进GPU精确算法快28倍,比最先进近似算法快6倍,且大多数情况下误差低于5%。例如,可在4分钟内以0.6%误差完成金融欺诈时序动机实例计数,而精确方法需超过两天。

原文摘要 · Abstract (English)

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.

时序图模式挖掘采样算法金融欺诈

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。