ICLR20 | GraphZoom：可缩放图嵌入

今天给大家介绍康奈尔大学和密西根理工大学发表在ICLR2020上的 一篇论文，该论文指出：现有图嵌入模型在训练期间不能很好的合并节点属性信息，模型可能会受到节点属性噪声的干扰，而且由于图嵌入模型的高计算复杂度和内存使用量，很少有模型能够应用到大图上。针对以上问题，该论文提出了一种用于提高无监督图嵌入算法准确性和可伸缩性的多级框架—GraphZoom。通过实验证明，与最新的无监督图嵌入方法相比，GraphZoom可以显著提高分类精度并且极快加速整个图嵌入过程。

1

介绍

近年来，人们对图嵌入领域产生了极大的兴趣。图嵌入旨在将节点、边或图编码为可最大程度保留图结构信息的低维向量，随着研究的进行，图嵌入技术已在顶点分类、链接预测和社区检测等任务中有着不错效果。但是，当前的图嵌入方法在准确性和可伸缩性方面有着多个缺点，除此之外，由于图嵌入算法高昂的计算和存储成本，几乎没有图嵌入算法可以很好地扩展到具有数百万个节点的大型图(Zhang等人，2018a)，大量的内存被用于存储中间结果。在研究过程中，增加图嵌入模型的准确度和可伸缩性被视为两个正交问题。因此，大多数研究工作仅致力于解决其中一个问题。

本文中作者提出了可以同时提高无监督图嵌入方法的嵌入质量和可伸缩性的多级频谱方法-GraphZoom，GraphZoom主要由四个内核组成：(1)图融合，(2)频谱图粗化，(3)图嵌入，(4)嵌入优化。图融合首先将节点特征矩阵转换为特征图，然后将其与原始拓扑图融合，生成的融合图可以为后续的图嵌入步骤提供更丰富的信息，提高准确性。频谱图粗化通过基于节点频谱相似度的节点合并来生成一系列连续的粗化图，可以保留关键的图结构。在图嵌入步骤中，可以应用任何现有的无监督图嵌入方法在最粗的级别上获取图的节点嵌入。嵌入优化通过使用适当的图过滤器将嵌入图重新嵌入到原始图上，这样可以保证在图上的嵌入是平滑的。

2

模型

图1是GraphZoom框架，该框架包含四个关键阶段，按照顺序分别为图融合、频谱图粗化、图嵌入、嵌入优化。

图1 GraphZoom结构

阶段1：图融合

阶段2：频谱粗化

作者采用有效的局部频谱嵌入方法，使用新兴的图信号处理技术来识别节点群集。作者将简单的平滑（低通图滤波）函数应用于k个随机向量来取代直接使用原始图拉普拉斯算子的第一向量，以获得用于k维图嵌入的平滑向量,这样就可以在线性时间内实现功能。

考虑到一个由图的拉普拉斯算子的特征向量u线性组合表示的随机矢量（图形信号）x，作者采用低通图滤波器来快速滤出随机图信号的高频分量或与图拉普拉斯图的高特征值相对应的特征向量，通过在x上应用平滑函数，作者可以获得由前几个特征向量的线性组合表示的平滑的向量。

阶段3：图嵌入

在构造了最粗糙的图后，作者使用

来将节点嵌入到上，其中可以是任何无监督的图嵌入方法。

阶段4：嵌入优化

3

实验

作者对GraphZoom框架与几种最先进的无监督图嵌入技术和多级嵌入框架基于五个标准图数据集进行了比较评估。除此之外，作者还评估了GraphZoom在包含800万个节点和4亿个边的Friendster数据集上的可扩展性。最后，作者进行消融研究，以了解GraphZoom中主要内核的有效性。作者还展示了GraphZoom在三个用于直推式学习的粗化级别和两个用于转换学习的粗化级别上的结果。

图二为本文实验中用到的数据集，作者将Cora、Citeseer、Pubmed和Friendster，用于直推式学习，PPI和Reddit用于归纳学习。在直推式学习中，作者采用了DeepWalk（Perozzi等人，2014）、node2vec（Grover和Leskovec，2016）和DeepGraphInfomax（DGI）（Veliˇckovi´c等人，2019）三种模型，以及两个多层次的图形嵌入框架：HARP（Chen等人，2018）和MILE（Liang等人，2018）与GraphZoom进行比较。为了显示GraphZoom还可以增强归纳学习，作者采用了使用四种不同的聚合函数（包括GCN、均值、LSTM和池化）的GraphSAGE（Hamilton等人，2017）与之进行了比较。

图2 实验数据集统计

图3，图4分别展示了直推式任务的平均分类精度和归纳任务的平均F1分数，以及所有模型和GraphZoom的执行时间。从结果中可以看到，对于直推式学习任务，GraphZoom可以使DeepWalk和node2vec在Cora、Pubmed和Citeseer上的分类准确率分别提高8.3％、10.4％和19.4％，同时达到减少40.8倍运行时间的目的。与DGI相比，GraphZoom可以达到可比或更高的精度，并且速度提高了11.2倍。同样，对于归纳学习任务，GraphZoom在PPI和Reddit上的性能均优于其他模型，分别提高了3.4％和3.3％，提速高达7.6倍。作者指出当增加粗化级别时，，GraphZoom仍可以以较短的CPU时间产生可比的甚至更好的嵌入精度。实验结果表明GraphZoom与底层的嵌入方法无关，能够提高各种数据集上最新的监督式嵌入方法的准确性和速度。这些结果表明，多级频谱方法可以提高填充的速度和质量，所以GraphZoom的运行速度要快得多。除了减小图形尺寸之外，作者的粗化方法还可以从原始图形中过滤出多余的信息，同时保留嵌入的关键频谱特性，因此分类准确率方面的嵌入质量也得到提高。

图3 直推式任务实验结果

图4 归纳任务实验结果

为了单独研究GraphZoom内核的有效性，作者在固定其他内核的同时将它们与MILE中的相应内核进行了比较，图5为GraphZoom和MILE中不同内核组合的分类准确性比较，GZoom_F、GZoom_C、GZoom_R分别表示在GraphZoom中提出的融合、粗化和修饰内核。MILE_C和MILE_R分别表示MILE中的粗化和修饰内核。当粗化内核一样时，尤其是当粗化级别较大时，GraphZoom的优化内核可以改善在MILE优化内核上的嵌入结果。作者认为这表明GraphZoom优化内核中提出的图形滤波器可以成功地从图形中滤除高频噪声，从而提高嵌入质量。同样对粗化内核进行比较时，GraphZoom粗化内核也可以提高MILE粗化内核的嵌入质量，这表明频谱图粗化算法确实可以保留关键图结构，供基础图嵌入模型使用。当结合使用GraphZoom粗化和优化内核时，与在MILE中使用任何其他内核的内核相比，可以获得更好的分类精度。作者认为这表明GraphZoom粗化和精炼内核对于提高缓冲层性能发挥了很大的作用，而它们的组合可以进一步改善嵌入效果。此外，增加图融合可以大大提高分类的准确性，这表明图融合可以适当地合并图拓扑和节点属性信息，这对于提升下游嵌入模型的嵌入质量至关重要。

为了显示GraphZoom可以显著提高大图上底层嵌入模型的性能和可伸缩性，作者在Friendster数据集上测试了以DeepWalk作为嵌入内核的GraphZoom和MILE，图6为对应的实验结果。根据实验结果所示，GraphZoom与MILE和DeepWalk相比Micro-F1得分显著提高，运行速度也有大幅提升。当增加粗化级别时，GraphZoom可以实现更高的加速，同时嵌入精度会适度降低。

图6 Friendster数据集上GraphZoom和MILE的比较

4

总结

作者在本文提出并介绍了一个可提高无监督图嵌入任务的准确性和可伸缩性的多级框架GraphZoom，。GraphZoom首先融合原始图的节点属性和拓扑，以构造新的加权图。然后，它使用频谱粗化来生成粗化图的层次结构，其中在最粗级对最小的图执行嵌入。最后，使用权图过滤器迭代地重新定义图嵌入，以获得最终结果。实验表明，GraphZoom可以提高分类精度，并提高在常用数据集上的图嵌入速度。

参考资料

https://arxiv.org/abs/1910.02370