TIMEST: Temporal Information Motif Estimator Using Sampling Trees

doi:10.14778/3772181.3772183

2025-09-01

PRE

DOI：10.14778/3772181.3772183

原文链接

原文求助

摘要

En 中文

时序模式子图（称为motifs）的挖掘是图挖掘领域的一项核心任务。现实网络中的边通常带有时间戳，因此需要时序motif挖掘。时序motif是一种更丰富的结构，对motif的边施加时间约束。时序motif已用于分析社交网络、金融交易和生物网络。时序图中的motif计数尤其具有挑战性。一个包含数百万边的图可以有数万亿个时序motif，因为同一条边可以具有多个时间戳。存在组合爆炸的可能性，而现有最先进算法无法处理超过四个顶点的motif。在本文中，我们提出TIM EST：一种通用的、快速的、精确的估计算法，用于统计时序网络中任意大小的时序motif。我们的方法引入了一种时序生成树采样器，利用加权采样生成目标时序motif的子结构。该方法仔细选取motif的一部分时序约束，这些约束可以联合高效地采样。TIM EST使用随机估计技术获得motif计数的精确估计。我们给出了关于TIM EST运行时间和近似保证的理论保证。我们进行了广泛的实验评估，表明TIM EST比之前的算法更快且更准确。我们的CPU实现相比精确算法的最先进GPU实现平均快28倍，相比SOTA近似算法快6倍，同时大多数情况下误差始终低于5%。例如，TIM EST可以在4分钟内以0.6%的误差统计金融欺诈时序motif的实例数量，而精确方法需要超过两天。

Keyword:

NETWORK MOTIFS

COUNTS