本文介绍两个基于双曲空间和陀螺矢量空间构建的GNN模型,区分传统GNN网络和双曲GNN的区别,希望能够带领读者对双曲空间上的模型构造进行更深入的理解。
1 引言
双曲图表示学习已经显示出非常优越的结果。然而,在双曲空间中设计图注意网络有两个关键挑战:(1)一个是GNN中有许多不同的过程,例如投影步骤、注意机制和传播步骤。然而,与欧几里得空间不同,双曲空间不是向量空间,因此向量运算(例如,包括向量加法、减法和标量乘法)不能在双曲空间中进行。尽管这些是设计一些双曲图操作的一些尝试,例如特征变换,但目前尚不清楚如何在双曲设置中设计多头注意力机制,这是GAT(图注意力网络)中的关键步骤。此外,由于双曲空间具有负曲率,因此我们的模型需要选择适当的曲率。我们如何以优雅的方式有效地实现GNN的双曲图操作,尤其是针对多头注意力?(2) 另一个挑战是双曲空间中的数学运算可能比欧几里得空间中的更复杂。数学运算的一些基本性质,如“向量加法”的交换性或结合性,在双曲空间中不再满足。我们如何保证所提出的模型中的学习效率?
2 两个双曲空间模型
2.1 Hyperbolic Graph Attention Network
总的来说,使用陀螺矢量空间来在双曲空间中构建GNN, 使用陀螺矢量空间中的操作来将向量变形(transform),之后根据节点在双曲空间中的距离来构建多头注意力机制。在这个基础上,作者还设计了一个对数和指数映射的并行策略提升了模型的效率:
如图所示,HAT的模型结构大体为:第一步使用指数映射和线性双曲变化来对输入的节点特征做变化,以获得节点在双曲空间的潜在表示.第二步根据节点在双曲空间中的距离远近设计了注意力机制,并使用对数和指数映射并行的策略来加速了模型。
2.1.1 双曲空间下的特征映射
fi是nodei的初始feature,x是双曲空间中的一个点,这里我们假设featurefi在x=0的切空间中,通过上述指数映射可以获得在双曲空间中的新特征pi之后再乘上一个权重矩阵,因为在双曲空间之中不能直接应用普通的矩阵乘法,因此使用莫比欧斯矩阵乘法,表达式如下:
得到的hi就是节点i在双曲空间中的feature表示.
2.1.2 双曲空间下的注意力机制
两个节点在双曲空间上的距离越近,那么他们之间的注意力系数越大,这里的距离是这样计算的:
注意力系数直接等于上述距离的倒数,再使用softmax正则化.最终的聚合函数等于:
其中,是基于陀螺矢量空间的莫比欧斯加法。是基于陀螺矢量空间的莫比欧斯乘法。
2.1.3 HAT的切片投影加速法
因为莫比欧斯加法不适用交换律和结合律,因此上面的莫比欧斯累加式并不能并行计算,造成了极大的资源和时间消耗。为了解决这个问题,作者提出了将邻居聚合投影到切片空间上来进行加速的方法。众所周知,双曲空间截取出的切空间可以近似地视为一个欧几里得空间,因此投影后的聚合函数适用加法交换律和结合律,这为并行的计算加速提供了可能。
如图所示,作者将节点特征投影到切空间上进行聚合,最终聚合函数将由
变形成
这时的聚合函数就可以用并行计算来加速了。
2.1.4 实验结果
HAT的最终实验结果记录如下:
其中,在某一数据集上最优秀的结果用黑色加粗标识。可以看到HAT的性能比传统的GNN网络更优秀。
2.2 Lorentzian Graph Convolutional Network
2.2.1 特征的投影转换
LGCN模型中特征投影转换的原理与HAT大致相同,区别在于LGCN还提供了一种在不同曲率的双曲空间之间转换的方式:
这个转换的原理还是将双曲空间上的点投影到切片空间上,再利用切片空间来进行曲率坐标的校准。
2.2.2 劳伦特兹邻居聚合
在欧式空间中,邻居聚合的数学含义可以概括为计算器邻域特征的加权算术平均值或质心。在欧式空间之中,弗雷歇统计方法的定义与这个概念非常贴合,其核心统计思想是使一个点集的距离之和期望最小。如果想将这个概念扩展到双曲空间上来,如何定义双曲空间上的固有距离就显得十分重要。在本文中,作者提供了一种计算双曲空间上两点之间距离的方法:
有了这个距离的计算方法,我们就能将一个邻域点集上的点的质心找出来(特征空间上的),利用这个质心就可以实现邻居聚合后的特征更新了。
上图展示了几种邻居聚合的示意图,左上角的图显示的是传统的基于欧几里得空间的邻居聚合方法,下面的图展示的是HAT适用的投影到切片空间上的聚合方法,右上展示的是劳伦特兹聚合方法。可以看到,HAT使用的投影聚合方法虽然可以起到加速的作用,但它聚合的只是质点在切片空间上的投影,这是质心的一个近似坐标,是可能存在偏差的。但是劳伦特兹聚合方法直接作用于双曲空间,它聚合得到的质心坐标相对准确。
2.2.3 定义的特殊算子
本文中还定义了几个基于陀螺矢量空间的特殊算子。因为在双曲空间上不能直接应用欧式空间中的向量算子,因此需要基于双曲空间设计新的算子。这些算子具有通用性,为之后双曲空间上的模型构造提供了便利。
(1)劳伦特兹矩阵乘法
(2) 劳伦特兹非线性激活函数
2.2.4 实验结果
LGCN实验中引入了一个重要的衡量指𝛿𝑎𝑣𝑔-hyperbolicity,这个值越低代表这个数据集越有可能具有一些隐含的双曲空间几何性质,理论上来说双曲空间模型作用于这些数据集的效果会越好。
(最优结果用加粗字体标出)
可以看到LGCN的效果较之传统的欧几里得空间上的模型来说有着更优秀的性能。
长按下图并点击“识别图中二维码”
即可关注北邮 GAMMA Lab 公众号
原文始发于微信公众号(北邮 GAMMA Lab):《Advances in Graph Neural Networks》第6章读书笔记
- 左青龙
- 微信扫一扫
-
- 右白虎
- 微信扫一扫
-
评论