图表示学习进展：理解大规模数据的形状
01
在处理数据时，理解复杂数据集之间的差异和相似性是一个有趣的挑战。形式化这个问题的一种方法是将每个数据集视为一个图，图是一种表示数据项之间相互关系的数学模型。图被广泛用于建模对象之间的关系——互联网图连接了相互引用的页面，社交图将朋友联系在一起，而分子图连接了相互结合的原子。
图是离散的对象，可以建模许多不同类型数据之间的关系，包括 Web 页面(左图)、社会关系(中间的图)或分子(右图)。
一旦有了多个图的集合，通常就需要预测每个图的某些属性(例如，每个图一个标签)。例如，考虑从结构预测蛋白质功能的任务：这里的每个数据集都是一个蛋白质，而预测任务是最终的结构是否对酶进行编码。因为我们想要一个模型来计算预测，所以我们需要一种表示法来让我们在不同的蛋白质结构中实现泛化。理想情况下，人们会想要一种不需要代价很高的标签就能将图表示为向量的方法。随着图的增大，这个问题变得更加困难——在分子的例子中，人们拥有一些关于它们属性的知识，然而，面对更大、更复杂的数据集时，推理就会变得越来越困难。
在本帖里,我们将重点介绍图表示学习领域的一些最新进展” Just SLaQ When You Approximate: Accurate Spectral Distances for Web-Scale Graphs ”(发表在 WWW’20)，这篇发表文章改善了我们早期研究的可伸缩性,“DDGK: Learning Graph Representations for Deep Divergence Graph Kernels”(发表在 WWW’19)。SLaQ 引入了一种缩放计算的方法，以近似于某类图统计数据，从而允许快速有效地描述大型图。我们也很高兴地宣布，我们已经在谷歌 Research GitHub图嵌入库中发布了这两篇论文的代码。
02
图相似性的完全无监督学习
在我们2019年的论文中，我们证明了在不需要领域知识和监督的情况下学习图相似性的表示是可能的。我们提出了深度发散图核(deep divergence graph kernels, DDGK)，这是一种无监督的方法，用于学习对图的相似性进行编码的表示。与以前的工作不同，我们的无监督方法能够做到共同学习节点表示、图表示和基于注意力的图对齐。
这是通过 DDGK 学习到的潜在表达的 t-SNE 可视化来比较蛋白质。蓝色的点表示编码酶的蛋白质，红色的点表示不编码酶的蛋白质。我们可以看到，编码与蛋白质的结构属性相关(无论它是否编码酶)，即使在训练中没有提供这种背景。(注意，这是表示的投影，因此绝对轴上的值没有意义。)
使用 DDGK 编码和对齐不同数据集之间的成对距离。颜色表示潜在空间中的距离，相似度的范围从 0(相同)到 1.0(非常不同)。我们看到，可以将表示聚类来将类似的数据集分组在一起——例如，数据集 nci1 和 ptc 都是化合物的数据集。
03
谱描述符的快速准确近似
图的谱是一种强大的表示，它对图的属性进行编码，包括图节点和聚类信息之间的连接模式。谱已被证明可以传递关于不同对象属性的丰富信息，例如鼓声、三维形状、图和一般的高维数据。谱图描述符的应用包括自动系统、动态图中的异常检测和化学分子表征。
目前，基于学习的系统(如 DDGK)既不能伸缩到大型图，也不能伸缩到大型图集合。或者，我们可以使用没有学习成分的谱信息来获得更理想的尺度特性。然而，计算大型图的谱描述符在计算上是禁止的。我们最近的一篇论文通过提出 SLaQ 来解决这个问题，SLaQ 是一种近似于一系列图描述符的方法。我们的方法使用随机逼近算法来计算谱函数的轨迹，这使我们能够研究几个著名的谱图特征，如冯诺依曼图熵、Estrada 指数、图能量和 NetLSD。
例如，我们使用 SLaQ 来监视Wikipedia图结构中的异常变化。SLaQ 允许我们从诸如大量页面重命名之类的琐碎更改中辨别出页面图结构中的有意义的改变。我们的实验表明，平均而言，近似精度提高了两个数量级。
左:著名的空手道图形代表了两个武术俱乐部的社会互动。右边:原始图的谱描述符(NetLSD、VNGE 和 Estrada 指数)用蓝色表示，去掉边的图用红色表示。
04
结论
图的无监督表示学习是一个重要的问题，而且我们相信我们在这里强调的方法是这一领域一大令人兴奋的进展! 具体来说，SLaQ 允许我们为大量数据集计算原则表示， DDGK 引入了一种自动学习数据集之间对齐的机制。我们希望我们的贡献将有助于推动大型数据集的分析，并将有助于理解时变图数据集的变化，如在 推荐系统中使用的那些。
致谢
我们感谢 Marina Munkhoeva, Rami Al-Rfou 和 Dustin Zelle 对这些工作的贡献。有关 图挖掘团队(部分 算法和优化组)的更多信息，请访问我们的页面。
