Efficient Graph Embedding Generation and Update for Large-Scale Temporal Graph

doi:10.14778/3717755.3717756

Efficient Graph Embedding Generation and Update for Large-Scale Temporal Graph

2024-12-01

0

PRE

AI

DOI：10.14778/3717755.3717756

原文链接

原文求助

摘要

En 中文

图嵌入旨在将每个节点映射到低维向量，这对诸如模式匹配、检索增强生成和推荐等应用有益。本文研究了大规模时序图嵌入问题。不同于简单图，时序图的每条边都带有时间戳，这要求嵌入能够编码时序偏差。分解相似度矩阵是生成简单图嵌入的常用方法，其中相似度可以通过诸如个性化PageRank等常规指标很好地表征。然而，如何构建能够编码含时序偏差的相似度，是大规模时序图的一个关键问题。为解决此问题，我们引入了基于时序的二分图（TBG）的概念，并开发了反映节点随时间并发活动情况的时序偏好连接相似度（TPASim）。直接分解包含近n²个非零元素的TPASim矩阵，对于具有n个节点的大型图来说并不可行。相反，我们提出了LTGE，它构建并分解一个最多包含2m个非零元素的时序矩阵，其中m为边的数量。我们的理论分析表明，LTGE在分解TPASim矩阵时能达到相同的嵌入效果，但通过n²/m的因子显著降低了复杂度。另一方面，当图随时间演化时，为避免重新计算，我们进一步提出了LTGEInc，它利用一种具有可证明保证的新型增量奇异值分解（SVD）算法来更新嵌入。在包含多达1700万个节点和130亿条边的多个数据集上的广泛实验表明，LTGE显著优于当前最优方法，且比专门为时序图设计的基线快几个数量级。对于嵌入更新，LTGEInc在保持性能的同时具有较小的计算开销。

Efficient Graph Embedding Generation and Update for Large-Scale Temporal Graph

摘要

期刊

机构

引用论文