重温图上的随机游走学习

Jul, 2024

Revisiting Random Walks for Learning on Graphs

Jinwoo Kim, Olga Zaghen, Ayhan Suleymanzade, Youngmin Ryou, Seunghoon Hong

TL;DR通过对图的随机游走产生机器可读的记录，并通过深度神经网络处理这些记录，直接进行顶点级或图级的预测，我们重新审视了图上机器学习的一个简单思想。我们称这些随机机器为随机游走神经网络，并表明我们可以设计它们成为同构不变并具备概率下图函数的通用逼近能力。一个有用的发现是，只要顶点匿名，几乎任何种类的随机游走记录都保证了概率不变性。这使得我们能够以纯文本的形式记录随机游走，并采用语言模型读取这些文本记录以解决图任务。我们进一步使用马尔科夫链理论中的工具，建立了与消息传递神经网络的并行性，并表明随机游走神经网络在构建过程中减轻了消息传递中的过度平滑，而概率性不达到则表现为概率性不足。我们展示了基于预训练模型的随机游走神经网络能够解决图上的一些难题，如分离三阶通用WL测试失败的强正则图、计数子结构和在arXiv引用网络上进行传导分类，而无需训练。代码可在此链接中获取。

Abstract

We revisit a simple idea for machine learning on graphs, where a random walk on a graph produces a machine-readable record, and this record is processed by a deep neural network to directly make vertex-level or graph-level predictions. We refer to these stochastic machines as

发现论文，激发创造

监督随机游走: 在社交网络中预测和推荐链接

本研究提出了一种基于监督随机游走的算法，结合网络结构和节点/边缘级属性信息进行边缘强度估计，并在 Facebook 社交图和大型协作网络上得到了验证。

Nov, 2010

基于图的表示学习方法泛化框架

本论文介绍了带标记的随机游走的概念，以此为基础对现有的一些利用随机游走的算法如DeepWalk、node2vec等进行了推广，可适用于传导学习、归纳学习以及具备属性的图形数据，并在多个领域的各种图形上验证了该算法的有效性。

Sep, 2017

大规模属性图的归纳表征学习

本研究提出了一个基于属性随机游走的框架用于推断网络表示学习，该框架可以更广泛地应用于现有的机器学习方法中，并解决了现有方法中节点身份相关性的固有问题。

Oct, 2017

利用随机游走进行动态图形的高效表征学习

本文介绍了一种有效的算法，可以基于动态图扩展随机游走技术用于顶点表示学习，并以实验数据说明了其在多分类和多标签顶点分类等机器学习任务中表现出与最先进方法相当的计算效率。

Jan, 2019

半监督分类的循环注意漫步

本文使用基于图的半监督学习方法对带属性节点进行分类。通过提出图游走的策略，使用强化学习来实现分类器的最大化精度，使得该方法能够灵活应对不同的归纳或传导学习任务，并且在四种数据集上测试结果表明，该方法胜过当前多种方法。

Oct, 2019

基于随机游走的1D卷积图学习

本研究提出了 CRaWl，一种基于 1D CNNs 处理小子图序列的神经网络架构，用于图学习，可高效地进行小子图计数和随机游走技术，并在分类和回归上的图多个基准数据集上，表现出与最新 GNN 架构匹配或优于其表现。

Feb, 2021

利用简化复形上的随机游走促进图神经网络

图神经网络中广泛使用了节点级随机游走以提高性能，但对于边缘和更一般地，k-单形的随机游走关注有限。本文系统地分析了不同阶数单形复合物（SC）上的随机游走如何在理论表达能力方面促进GNN。首先，在0-单形或节点级上，我们通过随机游走的桥梁建立了现有位置编码（PE）和结构编码（SE）方法之间的联系。其次，在1-单形或边缘级上，我们通过边级随机游走和Hodge 1-Laplacians建立了联系，并分别设计了相应的边界PE。在空间域中，我们直接利用边界级随机游走构建了EdgeRWSE。基于Hodge 1-Laplacians的谱分析，我们提出了Hodge1Lap，一种置换等价并具有表达能力的边界位置编码。第三，在高阶单形上推广了我们的理论，并提出了基于随机游走和Hodge Laplacians设计单形PE的一般原则。还引入了跨层次的随机游走来统一广泛范围的单形网络。大量实验证实了我们基于随机游走的方法的有效性。

Oct, 2023

通过随机游走学习图上的长程依赖

本文提出了一种名为NeuralWalker的新型架构，通过将随机游走视为序列，利用序列模型捕捉这些游走中的长程依赖关系，从而克服了消息传递图神经网络和图变换器方法的局限性，实现更具表达力的图表示，并能够使用任何序列模型来捕捉长程依赖关系，同时具备集成各种图神经网络和图变换器架构的灵活性。实验证明，NeuralWalker在19个图和节点基准数据集上取得了显著的性能改进，在PascalVoc-SP和COCO-SP数据集上的性能超过现有方法高达13%。

Jun, 2024

非卷积图神经网络

本研究针对卷积基图神经网络的局限性，如表达能力不足、过度平滑和过度压缩等问题，提出了一种全新的图学习模块——统一记忆与随机游走（RUM）神经网络。该方法结合了拓扑和语义图特征，实验结果表明，RUM在多种节点和图级分类回归任务中表现竞争力，具有更高的表达能力和更好的鲁棒性。

Jul, 2024

非卷积图神经网络

本研究解决了基于卷积的图神经网络（GNN）在表现力、过度平滑和过度挤压等方面的局限性。我们提出了一种完全不使用卷积运算的图学习模块——统一记忆随机游走（RUM）神经网络，该网络结合了节点的拓扑和语义特征。研究结果表明，RUM在多种节点和图级分类及回归任务中表现出色，且在效率、鲁棒性以及速度上均优于传统卷积GNN。

Jul, 2024