arXiv:2412.03783cs.LGcs.AI2024-12中稿 · TMLR综述被引 2

从信息流动视角分析动态图表示学习的表达能力,指导模型选型与设计。

Expressivity of Representation Learning on Continuous-Time Dynamic Graphs: An Information-Flow Centric Review

  • 提出信息流理论框架,量化动态图模型传播时序与结构信息的能力。
  • 在合成与真实数据集上验证不同方法在长程、二分、社区图中的表现差异。
  • 针对无监督学习设计适配动态图的预测与对比方法,减少对标注数据依赖。

图在现实世界中广泛应用,涵盖社交网络到生物系统,推动了图神经网络(GNN)用于学习高表达性表示。尽管多数研究聚焦于静态图,但现实中许多场景涉及随时间演化的动态图,催生了连续时间动态图(CTDG)模型的需求。本文全面综述了在CTDG上的图表示学习(GRL),重点关注自监督表示学习(SSRL)。我们提出一种新颖的理论框架,通过信息流(IF)视角分析CTDG模型的表达能力,量化其传播和编码时序与结构信息的能力。基于该框架,我们将现有方法按适用图类型与应用场景分类。同时,探讨专为CTDG设计的SSRL方法,如预测式与对比式方法,突出其降低对标签数据依赖的潜力。在合成与真实数据集上的实证评估验证了理论洞察,展示了各类方法在长程、二分及社区图中的优劣。本工作为选择与开发CTDG模型提供了理论基础与实践指导,推进了动态环境下图表示学习的理解。

原文摘要 · Abstract (English)

Graphs are ubiquitous in real-world applications, ranging from social networks to biological systems, and have inspired the development of Graph Neural Networks (GNNs) for learning expressive representations. While most research has centered on static graphs, many real-world scenarios involve dynamic, temporally evolving graphs, motivating the need for Continuous-Time Dynamic Graph (CTDG) models. This paper provides a comprehensive review of Graph Representation Learning (GRL) on CTDGs with a focus on Self-Supervised Representation Learning (SSRL). We introduce a novel theoretical framework that analyzes the expressivity of CTDG models through an Information-Flow (IF) lens, quantifying their ability to propagate and encode temporal and structural information. Leveraging this framework, we categorize existing CTDG methods based on their suitability for different graph types and application scenarios. Within the same scope, we examine the design of SSRL methods tailored to CTDGs, such as predictive and contrastive approaches, highlighting their potential to mitigate the reliance on labeled data. Empirical evaluations on synthetic and real-world datasets validate our theoretical insights, demonstrating the strengths and limitations of various methods across long-range, bi-partite and community-based graphs. This work offers both a theoretical foundation and practical guidance for selecting and developing CTDG models, advancing the understanding of GRL in dynamic settings.

动态图表示学习自监督信息流

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