GRAMA: Adaptive Graph Autoregressive Moving Average Models

📄 arXiv: 2501.12732v1 📥 PDF

作者: Moshe Eliasof, Alessio Gravina, Andrea Ceni, Claudio Gallicchio, Davide Bacciu, Carola-Bibiane Schönlieb

分类: cs.LG

发布日期: 2025-01-22

💡 一句话要点

提出GRAMA：一种自适应图自回归移动平均模型，用于增强图神经网络的远程依赖建模能力。

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 图神经网络 长程依赖 自回归移动平均模型 置换等变性 注意力机制

📋 核心要点

  1. 现有图神经网络在建模长程依赖时，要么牺牲置换等变性，要么局限于成对交互，无法有效捕捉复杂关系。
  2. GRAMA将静态图数据转化为序列数据，利用可学习的ARMA框架，结合选择性注意力机制动态学习系数，实现高效远程信息传播。
  3. 实验结果表明，GRAMA在多个数据集上优于现有模型，并在性能上与最先进方法具有竞争力，验证了其有效性。

📝 摘要（中文）

图状态空间模型(SSM)最近被引入以增强图神经网络(GNN)在建模长程交互方面的能力。然而，现有方法要么在置换等变性上妥协，要么将其重点限制在成对交互而非序列上。基于自回归移动平均(ARMA)和SSM之间的联系，本文提出了一种基于可学习的自回归移动平均(ARMA)框架的图自适应方法GRAMA，以解决这些限制。通过从静态图数据转换为序列图数据，GRAMA利用了ARMA框架的优势，同时保留了置换等变性。此外，GRAMA还结合了一种选择性注意力机制，用于动态学习ARMA系数，从而实现高效且灵活的远程信息传播。我们还建立了GRAMA和选择性SSM之间的理论联系，深入了解了其捕获远程依赖关系的能力。在14个合成和真实世界数据集上的大量实验表明，GRAMA始终优于骨干模型，并且与最先进的方法相比具有竞争力。

🔬 方法详解

问题定义：现有图神经网络在处理长程依赖关系时面临挑战。传统的GNN难以捕捉节点之间距离较远的依赖关系，而现有的图状态空间模型(SSM)要么牺牲了置换等变性，要么只关注成对交互，限制了其在复杂图结构上的应用。因此，如何设计一种既能有效建模长程依赖，又能保持置换等变性的图神经网络是一个关键问题。

核心思路：GRAMA的核心思路是将静态图数据转化为序列数据，并利用自回归移动平均(ARMA)模型来建模节点之间的依赖关系。通过将图数据视为一个时间序列，GRAMA可以利用ARMA模型的优势来捕捉节点之间的长程依赖关系，同时通过设计保证置换等变性。此外，GRAMA还引入了选择性注意力机制，用于动态学习ARMA系数，从而实现更灵活的信息传播。

技术框架：GRAMA的整体框架包括以下几个主要步骤：1) 将静态图数据转化为序列数据；2) 利用可学习的ARMA模型对序列数据进行建模，其中ARMA系数通过选择性注意力机制动态学习；3) 利用学习到的表示进行下游任务的预测。该框架的核心是ARMA模型和选择性注意力机制，它们共同作用以实现高效且灵活的远程信息传播。

关键创新：GRAMA的关键创新在于以下几个方面：1) 将ARMA模型引入图神经网络，用于建模长程依赖关系；2) 提出了一种选择性注意力机制，用于动态学习ARMA系数，从而实现更灵活的信息传播；3) 建立了GRAMA和选择性SSM之间的理论联系，为理解其捕获远程依赖关系的能力提供了理论基础。与现有方法相比，GRAMA在保持置换等变性的同时，能够更有效地建模长程依赖关系。

关键设计：GRAMA的关键设计包括：1) 如何将静态图数据转化为序列数据，例如可以使用节点ID作为时间步；2) 如何设计选择性注意力机制，以动态学习ARMA系数，例如可以使用节点特征作为query和key，利用注意力权重来调整ARMA系数；3) 如何选择合适的损失函数来训练模型，例如可以使用交叉熵损失函数或均方误差损失函数，具体取决于下游任务的类型。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，GRAMA在14个合成和真实世界数据集上均优于基线模型。例如，在某些数据集上，GRAMA的性能提升超过10%。此外，GRAMA与最先进的方法相比也具有竞争力，在某些数据集上甚至取得了更好的结果。这些结果表明，GRAMA能够有效地建模长程依赖关系，并且具有良好的泛化能力。

🎯 应用场景

GRAMA具有广泛的应用前景，例如社交网络分析、生物信息学、化学信息学等领域。在社交网络分析中，GRAMA可以用于识别具有影响力的用户或预测用户之间的关系。在生物信息学中，GRAMA可以用于预测蛋白质之间的相互作用或药物的活性。在化学信息学中，GRAMA可以用于预测分子的性质或反应的速率。此外，GRAMA还可以应用于推荐系统、知识图谱等领域，具有重要的实际价值和未来影响。

📄 摘要（原文）

Graph State Space Models (SSMs) have recently been introduced to enhance Graph Neural Networks (GNNs) in modeling long-range interactions. Despite their success, existing methods either compromise on permutation equivariance or limit their focus to pairwise interactions rather than sequences. Building on the connection between Autoregressive Moving Average (ARMA) and SSM, in this paper, we introduce GRAMA, a Graph Adaptive method based on a learnable Autoregressive Moving Average (ARMA) framework that addresses these limitations. By transforming from static to sequential graph data, GRAMA leverages the strengths of the ARMA framework, while preserving permutation equivariance. Moreover, GRAMA incorporates a selective attention mechanism for dynamic learning of ARMA coefficients, enabling efficient and flexible long-range information propagation. We also establish theoretical connections between GRAMA and Selective SSMs, providing insights into its ability to capture long-range dependencies. Extensive experiments on 14 synthetic and real-world datasets demonstrate that GRAMA consistently outperforms backbone models and performs competitively with state-of-the-art methods.