图表征学习领域的最新进展：从形状入手了解大规模数据
文 / 图挖掘团队研究实习生 Anton Tsitsulin 和高级研究员 Bryan Perozzi，Google Research
了解复杂数据集之间的异同点是一项有趣的挑战，我们在处理数据时经常会遇到。常见方法之一是将每个数据集视作一张图 (Graph)，用以描述事物间如何相互联系的数学模型。我们常用图来建模与表达对象间的关系，如，互联网图连接相互引用的页面，社交图将朋友互联到一起，而分子图则将原子相互连接。
常用图来表达多种不同类型数据之间关系建模的离散对象，如网页（左）、社交关系（中）或分子（右）
对于由多张图构成的集合，我们通常会希望将每个图的部分属性作为一个集合进行预测（即，为每张图设置一个标签）。以通过结构预测蛋白质功能的任务为例：此处的每个数据集都是一种蛋白质，而预测任务为最终结构是否对酶进行编码。由于需要有模型来实际计算预测值，所以我们需要一种可以泛化不同蛋白质结构的表征。理想情况下，我们需要一种无需耗费大量标签即可将图表示为向量的方法。而随着图规模的不断扩大，这个问题也越来越棘手。以分子为例，人类虽然已掌握一些关于分子属性的知识，但想要对规模更大更为复杂的数据集进行推理，难度也不断增加。
在本文中，我们重点介绍图表征学习领域的一些最新进展，其中包括《您逼近的只是 SLaQ：网络级图的精确谱距离》(Just SLaQ When You Approximate: Accurate Spectral Distances for Web-Scale Graphs)（发表于 WWW'20），此论文提升了我们的早期研究《DDGK：学习深度发散图核的图表征》(DDGK: Learning Graph Representations for Deep Divergence Graph Kernels)（发表于 WWW’19）的可扩展性。SLaQ 引入一种方法，可扩展计算以接近特定类别的图统计数据，进而快速高效地描述大型图特征。另外，我们很高兴地宣布，我们已在 Google Research GitHub 代码库的图嵌入向量板块中发布了这两篇论文的代码。
您逼近的只是 SLaQ：网络级图的精确谱距离
https://doi.org/10.1145/3366423.3380026DDGK：学习深度发散图核的图表征
https://dl.acm.org/doi/10.1145/3308558.3313668Github: 图嵌入向量
https://github.com/google-research/google-research/tree/master/graph_embedding
完全无监督的图相似性学习
在 2019 年的论文中，我们展示了既不利用领域知识，也不利用监督来学习图相似性表征的可能性。我们提出了 深度发散图核 (Deep Divergence Graph Kernels, DDGK)，学习图表征的无监督方法，可对图之间的相似性映射进行编码。与以前的研究不同，我们的无监督方法可连带学习节点表征、图表征以及图之间基于注意力的对齐方式。
上图是一张 t-SNE 可视化图像，呈现了 DDGK 学习的比较蛋白质的潜在表征。蓝点表示对酶进行编码的蛋白质，红点表示不对酶进行编码的蛋白质。我们可以看到，编码与蛋白质的结构属性相关（无论其是否对酶进行编码），即使在训练过程中未提供此上下文也是如此（请注意，这是对表征的投射，因此绝对轴值没有意义）
在 2019 年的论文中
https://arxiv.org/abs/1904.09671
在上方示例中，我们演示了这些表征如何自动学习表示图，并以对其潜在功能相似性进行编码的方式将图对齐。通过在其他数据集上进行的实验表明，我们可以捕获不同类型的图（语言、生物学和社交互动）之间的异同。
使用 DDGK 编码和对齐的不同数据集之间的成对距离：颜色表示潜在空间中的距离，相似性尺度的范围从 0（相同）到 1.0（不同）。我们看到，表征可被聚合，进而将相似的数据集聚集到一起，例如，数据集 nci1 和 ptc 都是化合物数据集
谱描述符的快速准确逼近
图谱是一种强大的表征，可对属性进行编码，包括图节点之间的连接模式和聚类信息。我们已经证实，谱可以传达有关不同对象属性的丰富信息，例如鼓声、3D 形状、图形和一般高维数据。常见的使用谱图描述符的应用包括 AutoML 系统、动态图中的异常检测和化学分子特性等。
图谱
https://mathworld.wolfram.com/GraphSpectrum.htmlAutoML
https://dl.acm.org/doi/10.1145/3292500.3330848
当前，如 DDGK 等基于学习的系统无法扩展至大型图或大型图集合。作为替代方案，我们可以在没有学习组件的情况下使用谱信息获得更需要的缩放特性。不过，计算大型图的谱描述符在计算上无法实现。我们最近发表的论文通过提出 SLaQ 解决了这个问题。SLaQ 是一种用于估算一系列图描述符近似值的方法。我们的方法使用随机近似算法来计算谱函数的轨迹，从而能够研究几种著名的谱图特征，例如冯·诺依曼图熵、Estrada 指数、图能量和 NetLSD。
论文
https://arxiv.org/abs/2003.01282
例如，我们使用 SLaQ 来监控维基百科图结构中的异常变化。SLaQ 使我们能够从细微改变中（如批量页面重命名）中识别出页面图结构中真正有意义的变化。我们的实验表明，SLaQ 将近似准确度平均提高了两个数量级。
左：著名的空手道图：表示了两个武术俱乐部之间的社交互动；右：为原始图计算的谱描述符（NetLSD、VNGE 和 Estrada 指数）为蓝色，已删除边缘的版本则为红色
结论
图的无监督表征学习是一个重要问题，我们相信，本文重点介绍的方法将是该领域一次振奋人心的进步！
具体而言，SLaQ 使我们能够计算大型数据集的原理表征，DDGK 则引入了一种数据集之间自动学习对齐情况的机制。我们希望本项研究成果能够助力对大型数据集的分析，并有助于理解时变图数据集（如推荐系统中使用的数据集）的变化。
SLaQ
https://github.com/google-research/google-research/tree/master/graph_embedding/slaqDDGK
https://github.com/google-research/google-research/tree/master/graph_embedding/ddgk
致谢
我们在此感谢 Marina Munkhoeva、Rami Al-Rfou 和 Dustin Zelle 为这些研究付出的努力。有关图挖掘团队（算法和优化小组成员）的更多信息，请访问我们的网页。
更多 AI 相关阅读：