ICDM’21 | ACE-HGNN：自适应曲率探索的双曲图神经网络

Houye

发布于 2021-12-28 08:35:36

1.5K0

发布于 2021-12-28 08:35:36

文章被收录于专栏：图与推荐

本文主要介绍我们在ICDM‘2021发表的工作，ACE-HGNN: Adaptive Curvature Exploration Hyperbolic Graph Neural Network。

Paper: https://arxiv.org/pdf/2110.07888.pdf Code: https://github.com/RingBDStack/ACE-HGNN

摘要

图神经网络（GNNs）在各种图数据挖掘任务中得到了广泛的研究,但是大多数现有的工作都是基于欧式空间嵌入，难以自然的捕捉图数据的非欧式结构。因此，近年来一些基于非欧几何空间的工作在机器学习领域快速增长，其中双曲几何空间的图神经网络（Hyperbolic Graph Neural Networks，HGNNs）将GNNs扩展到双曲空间，从而在节点表示学习中更有效地捕捉图的树状/层次结构。然而现实中复杂多样拓扑结构的图数据，HGNNs对于具有异质拓扑结构的图数据往往性能不佳。为了能够为HGNNs自适应的探索到合适的双曲嵌入空间，我们首次引入了强化学习的学习框架到HGNNs中，提出了ACE-HGNN自适应曲率探索的双曲图神经网络，根据输入图和下游任务自适应学习最优曲率。我们将曲率的探索和图的表征学习视作一个同时进行的多目标优化问题，使用多智能体强化学习（MARL）分别设计用于学习曲率和节点表示的ACE-Agent和HGNN-Agent，并通过Nash-Q学习算法协同学习，通过使智能体达到纳什均衡来求解问题。在多个真实图数据集上进行的大量实验表明，在模型质量方面具有显著且一致的性能改进和良好的泛化能力。

研究背景

图常被用来建模复杂关系，通过图表示学习可以有效的学习到数据的顺序、拓扑、几何等关系特征。众所周知，图是非欧几里得结构的，因此非欧几里得几何嵌入受到了机器学习领域的关注，被引入来提高对图的拓扑结果的学习能力。并且，复杂网络领域的研究表明，现实的网络数据中大量存在着无标度性质（scale-free），意味着现实中普遍存在着树状（tree-like）/层次结构。其中，双曲几何在传统网络科学领域被视作树状/层次结构的底层连续表达，最近涌现出大量优秀的工作。在双曲几何中，双曲空间的曲率是几何空间弯曲的度量，不同的曲率可以控制双曲几何流形来近似图的不同程度树状/层次结构（如下图）。

Tree-like 结构

然而，现有的HGNNs方法对于现实中结构复杂图数据和多样的下游任务往往性能不佳，主要由以下两点缺陷导致：

适应性问题：数据方面，现实的图数据通常是具有异质拓扑结构（即，同时存在树、环或网格结构）；任务方面，不同的下游任务对特征信息和拓扑信息的要求不同，而层次结构这样的特殊拓扑结构对任务的重要性是未知的。 最优曲率问题：现有的工作对于曲率选择主要有两种方式。将曲率作为超参数，启发式的使用经验或利用采样估计算法估计；将曲率直接作为神经网络参数在训练过程中学习。前一种方法仅依靠对原始图的拓扑来估计曲率，不能适应不同下游任务；后一种方法严重依赖节点表征的梯度下降方向，模型只会对曲率进行微调来保证节点表征的快速收敛，难以探索到最优的曲率。

因此一个自然而然的问题是，"我们能否基于不同图的树状/层次结构和下游任务驱动，自适应的找到最优曲率的双曲几何空间并利用双曲图神经网络学习到更好的节点表征？” 为了解决上述问题，我们提出了一个新的自适应曲率探索双曲图神经网络名为ACE-HGNN。主要贡献如下：

对双曲空间中不同层次结构的HGNN的适应性问题进行观察和分析，将嵌入空间适应性问题转化为双曲空间的最佳曲率探索问题。
我们首次在双曲几何机器学习中引入强化学习，提出了一种新的端到端架构，即自适应曲率探索双曲图神经网络（ACE-HGNN），以指导选择最优的双曲几何空间。
对五个典型真实数据集的广泛实验表明，模型适应性和竞争性能显著且得到改进。我们可视化了ACE-HGNN的结果，直观地展示了我们方法捕获图结构的能力。

双曲几何中的曲率与图的层次结构

双曲几何嵌入在复杂网络领域中已经被广泛研究和应用，一个双曲几何空间（流形）能够直接理解为一颗连续近似的树，其中曲率度量了这个弯曲流形（双曲空间）的弯曲程度。现有的工作表明，具有不同结构（例如，环或树结构）的图在嵌入到欧式或双曲几何空间时具有不同的信息失真。下图（Figure 1）说明了双曲曲率和图层次结构之间的内在联系。它表明，不同的曲率显著影响双曲曲空间中的距离指标。曲率降低时，双曲的嵌入距离会更反映树的结构，因为它接近两个节点的最短路径长度（即双曲曲线图距离）。当曲率接近于零时，双曲的嵌入距离接近欧几里德嵌入距离，导致层次结构的信息丢失。

为了保证曲率这一度量能达成我们的目的，首先我们需要进行定性分析。以往的工作通常使用嵌入空间中测地距离（geodesic）和拓扑距离（shortest path）的积性失真来度量信息损失，侧重考虑拓扑信息保持能力的度量。而在图表示学习场景下，节点的特征信息与结构信息都十分重要。如下图（Figure 2 (a),(b)）所示，我们利用嵌入距离d和图距离g来度量图嵌入到双曲空间中的失真程度。嵌入距离d可以认为是两个节点之间的语义距离或特征相似度；图距离g图中两个节点之间最短路径的长度。对于双曲曲率K=-1/\zeta^2 ，当K<0 时，三角形的内角和小于\pi ，并且随着曲率参数\zeta 的减小而减小。另外，对于树状图，两个节点之间的最短路径导航趋向于靠近中心，随着曲率参数\zeta 的减小，这一性质得到增强。根据双曲空间树状图的上述性质，我们可以观察到当\zeta→0 即K→-\infty,\delta \theta \rightarrow 0 时的d_{\mathbb{H}}→g_{\mathbb{H}} 。

为了更直观地解释，上图（Figure 2 (c)）给出了不同曲率的双曲面流形中的一个简单结构，该结构可以很容易地推广到任何环/网格结构，在现实中可能用于描述简单家庭关系的三角形，或者交通网络的环路。通过测量嵌入距离和图距离，我们可以直观地看到不同曲率下的嵌入失真。在此基础上，进一步分析了曲率是影响模型表达能力的主要因素。最后，将双曲图表示学习的适应性问题转化为曲率探索和模型优化的多目标优化问题。

多目标优化问题定义

我们的目标是最小化嵌入失真，同时学习HGNN的最优图节点表示。因此，我们将最优曲率选择与HGNN优化的结合作为一个多目标优化问题。给定一个label为Y 的图G ，问题可以定义为：

\begin{aligned} &argmin_{\phi,K}\vec{f}(G)=\left [Loss\left (\mathbf{h},Y;\phi,K\right ),\mathcal{D}\left (\mathbf{h};K\right )\right ]\\ &\mathbf{s.t.}~\mathbf{h}=\mathrm{HGNN}(G), K\in (-\infty,0\;]. \end{aligned}

然而，在多目标优化中，通常没有唯一的全局最优解。在大多数情况下，搜索整个帕累托最优是不可行的，幸运的是，当前的深度强化学习范式为我们提供了启示。我们尝试引入多智能体作为交互式决策者，有效地解决特定下游任务的多目标优化问题。

自适应曲率探索双曲神经网络

下图（Figure 3）显示了我们与两个智能体的协作强化学习框架，以解决多目标优化问题，其中自适应曲率探索智能体（ACE-Agent）探索曲率以获得更好的双曲面表示空间，而双曲图神经网络智能体（HGNN-Agent）学习了特定曲率的双曲曲空间中的节点表示。

ACE-Agent：自适应曲率探索智能体

由于hyperbolic logarithmic mapping 和Riemannian optimization的特性，在保证节点表征的梯度下降方向的前提下，曲率更新的范围非常小（我们在实验中证实了这一现象），在HGNN模型中使用反向传播来学习曲率很容易使曲率陷入局部最优。因此我们的目的是独立设计一个智能体来负责自适应的曲率探索。ACE-Agent的形式化定义如下：

状态

S^{t}_{\mathrm{ACE}}：我们直接使用曲率表示双曲的嵌入空间，并把强化学习终止时的状态作为探索的最佳曲率。由此，对于L 层的HGNN模型，我们将第t 个epoch的状态定义为 S^{t}_{\mathrm{ACE}} = \left (\zeta^{t-1}_1,\dots,\zeta^{t-1}_L\right )。

动作

A_{\mathrm{ACE}}^t：为了最大限度地减少嵌入失真，并探索最佳曲率，我们使用经典的Parallelogram Law偏差方法来估计图曲率\zeta^t 。对于每个节点，我们执行上述采样n_s 次，并将平均值作为新的估计曲率。然后，我们将HGNN-Agent在t-1 个epoch中的嵌入h^{\zeta^{t-1},t-1} 结合新的曲率\zeta^t 输入到双曲流形，给定估计曲率的权重参数\gamma 和原点切线空间\mathcal{T}_{\mathbf{o}} \mathbb{H}^{n} ，动作 A_{\mathrm{ACE}}^t的形式化定义如下：

\begin{aligned} \zeta^{t} &= \left (1-\gamma\right )\zeta^{t-1} + \frac{\gamma}{\sqrt{-\kappa^{t}}}, \\ \mathbf{h}^{\zeta^{t},t} &\gets \mathrm{exp}^{\zeta^{t}}_{\mathbf{o}}\left ( \mathrm{log}^{\zeta^{t-1}}_\mathbf{o}\left (\mathbf{h}^{\zeta^{t-1},t-1}\right )\right )。 \end{aligned}

奖励

R_{\mathrm{ACE}}^t：我们根据与上次状态相比的具体任务的效益直接定义智能体的奖励，对于双曲表征向量\mathbf{h}^{\zeta^{t},t} 和下游任务的评价反馈\mathcal{M}(\cdot) ，奖励R_{\mathrm{ACE}}^t 的定义如下：

R^{t}_{\mathrm{ACE}}=\mathcal{M}(\mathbf{h}^{\zeta^{t},t})-\mathcal{M}(\mathbf{h}^{\zeta^{t-1},t-1})。

HGNN-Agent：双曲神经网络智能体

双曲图神经网络智能体旨在双曲空间中学习节点表示融合图结构和特征的信息。这里我们可以嵌入任意的双曲图神经网络模型，本文使用了HGCN（NeurIPS 2019，Stanford）。HGNN在原点\mathrm{o} 的切线空间\mathcal{T}_{\mathbf{o}} \mathbb{H}^{n} 中模型的每一层转换并聚合前一层的邻居隐藏特征，然后将结果映射到具有不同曲率的双曲空间中：

\mathbf{h}^{\ell} = \sigma^{\otimes^{\zeta}} \left (\rm{AGG}^{\zeta} \left ( \left ( \mathbf{W}^{\ell} \otimes^{\zeta^{\ell-1}} \mathbf{h}^{\ell-1}\right) \oplus^{\zeta^{\ell-1}} \mathbf{b}^{\ell}\right) \right)

其中\oplus^{\zeta} ,\otimes^{\zeta} 分别是曲率为\zeta 的Möbius向量加法和乘法操作，\sigma^{\otimes^{\zeta}} 是双曲非线性激活函数，\rm{AGG}^{\zeta} 是双曲邻居聚合函数。HGNN-Agent的形式化定义如下:

状态

S^{t}_{\mathrm{HGNN}}： HGNN-Agent目标是学习具有给定曲率的双曲空间中的最佳节点表示。给定第t-1个epoch的曲率\left (\zeta^{t-1}_1,\dots,\zeta^{t-1}_\ell\right ) 和HGNN模型的层数L ，其状态定义为：

S^{t}_{\mathrm{HGNN}} = \left (\zeta^{t-1}_1,\zeta^{t-1}_2,\dots,\zeta^{t-1}_L\right )

动作：

A^{t}_{\mathrm{HGNN}}： HGNN-Agent的动作定义为是否通过获取新的曲率来更新已学到的嵌入。定义为：

A^{t}_{\mathrm{HGNN}}=\{\zeta^{t}_{\mathrm{HGNN}} \gets \zeta^{t}_{\mathrm{ACE}}, \ \zeta^{t}_{\mathrm{HGNN}} \gets \zeta^{t-1}_{\mathrm{HGNN}}\}

奖励

R^{t}_{\mathrm{HGNN}}：与 ACE-Agent相同，HGNN-Agent的奖励也基于与上次状态相比特定任务的性能改进来定义：

R^{t}_{\mathrm{HGNN}}=\mathcal{M}(\mathbf{h}^{t})-\mathcal{M}(\mathbf{h}^{t-1})

多智能体强化学习MARL和纳什均衡

我们利用博弈论来为多个智能体求解。具体来说，我们需要对HGNN-Agent和 ACE-Agent的协作学习来进行正和博弈，目标是将两个智能体的学习融合到纳什均衡（即所有智能体不能独立更新学习结果以提高下游任务的协作性能）。我们利用Nash Q-learning来更新两个智能体，并在采取行动时采用具有探索概率的贪婪策略。ACE-Agent和 HGNN-Agent共享一个全局状态S，Nash Q-learning优化符合Bellman优化方程如下：

\begin{aligned} NashQ_i\left (S'\right ) ~=~ & \pi_{\mathrm{HGNN}}^*\left (S'\right ) \pi_{\mathrm{ACE}}^*\left (S'\right ) Q_i\left (S'\right ),\\ Q_i\left (S, A^t_{\mathrm{HGNN}}, A^t_{\mathrm{ACE}}\right ) \gets ~& Q_i\left (S, A^{t}_{\mathrm{HGNN}}, A^t_{\mathrm{ACE}}\right )\\ & + \alpha\left (R^t_i + \beta NashQ_i\left (S'\right )\right. \\ & \left.- Q_i\left (S, A^{t}_{\mathrm{HGNN}}, A^t_{\mathrm{ACE}}\right )\right ), \end{aligned}

其中Q(\cdot) 为Q -function，\alpha 是学习率，\beta 是学习因子。如果HGNN-Agent和ACE-Agent已达到纳什平衡，则强化学习算法将停止，曲率参数\zeta 将在下一个培训过程中保持固定。

\pi_{\mathrm{HGNN}}^*\left (S'\right ),\! \pi_{\mathrm{ACE}}^*\left (S'\right ) \gets Nash\left (Q_{\mathrm{HGNN}}\left (S'\right ),\! Q_{\mathrm{ACE}}\left (S'\right )\right ),

其中，\pi_{\mathrm{HGNN}}^* 和 \pi_{\mathrm{ACE}}^* 分别是两个智能体的最佳策略，上式可以找到最优曲率。

整体算法如下：

实验验证

我们在包括引文网络（Cora 、Citeseer 和 Pubmed）、超文本网络（WebKB）和蛋白质网络（PPI）进行全面的验证，对比的baseline方法包括欧式空间和双曲空间的神经网络（MLP，HNN）、欧式空间的GNNs（GCN，GAT，GraphSAGE）和双曲空间的HGNNs（HGCN，κGCN）。总的来说，我们可以得到以下结论：（1）我们的 ACE-HGNN 具有很好的性能，并在所有数据集中达到最佳平均性能；（2）一般来说，之前的双曲模型（HNN、HGCN 和 kGCN）在具有较高双曲性的数据集上表现更好，但在具有较低双曲性的数据集上表现差。观测表明，有必要对层次拓扑和特征信息进行自适应融合。与其将曲率作为超参数（如κGCN）或学习参数（如HGCN），ACE-HGNN中的自适应曲率探索机制收益更好。

我们进一步分析嵌入失真、曲率探索和注意力权重，以研究ACE-HGNN的表征能力。

嵌入失真： 如图所示ACE-HGNN在这些模型中的平均嵌入失真率最低，这表明我们ACE-HGNN 的自适应曲率探索可以有效地保留不同图的层次结构。

曲率探索： 在学习过程中，κGCN的曲率是预先估计的并保持固定的。与HGCN相比（几乎是轻微震荡的直线），我们的ACE-HGNN可以在学习过程中探索更大的曲率范围。此外，ACE-HGNN 学到的曲率最终接近估计的最佳曲率，并自动微调以实现更好的性能。我们还观察到，两层双曲图卷积层（ACE-HGNN 1和ACE-HGNN 2）的曲率存在着竞争与合作的关系：（1）在几个连续的epoch中，两个HGNN层的曲率经常同时选择相反的动作或同时保持不变；（2）但就整个训练过程的规模而言，两层的整体趋势是相同的。

可视化和注意力机制： 下图（Figure 7）表示了Cora数据集中节点嵌入的可视化，ACE-HGNN 在不同类别之间和类内相似性有更清晰的区分。我们能直观的观察到，曲率不适当的双曲空间会产生"欠拟合"或"过拟合"，这可能会降低下游任务的性能。为了进一步说明曲率对聚合邻居信息的影响，我们可视化不同δ的数据集上 HGNN-智能体邻居聚合的注意力权重。下图（Figure 8）显示了较低δ的数据集上，中心节点更关心他们父节点（关注层级关系）。

总结

在本文中，我们提出了ACE-HGNN，一种新的自适应曲率探索双曲图神经网络。我们是首个将强化学习引入到双曲图表示学习中的工作，并获得了ICDM'2021 Best Paper Candidate的提名。对于具有不同层次结构的图和各种下游任务，多智能体强化学习方法可以搜索具有最佳曲率的适当双曲空间，并同时学习良好的节点表示。此外，自适应曲率探索还可以直观地对模型学习进行合理的解释，反映了模型对图特征或结构信息学习的偏好。