重温图上的随机游走学习

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

machine learning on graphs random walk neural networks isomorphism invariant language model graph tasks

发现论文，激发创造

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

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

Jan, 2019

使用随机游走采样训练差分隐私图神经网络

研究深度学习模型在保护隐私方面的挑战，尤其是在图形结构数据上应用差分隐私随机梯度下降来防止训练数据泄漏。这篇论文提出通过在给定训练图的不相交子图上训练图神经网络来解决这个问题，并且进行了大量实验来验证方法的有效性。

Jan, 2023

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

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

Sep, 2017

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

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

Feb, 2021

NetGAN：通过随机游走生成图形

NetGAN 是第一个用隐式生成模型来模拟真实网络的方法，通过学习偏置随机游走在输入图上的分布来生成图形。该方法基于生成离散输出样本的随机神经网络，并使用 Wasserstein GAN 目标进行训练。尽管未经过特意训练，NetGAN 在链路预测性能方面表现出强大的泛化能力。

Mar, 2018

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

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

Oct, 2017

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

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

Jun, 2024

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

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

Nov, 2010

超图上的随机游走

本篇研究提出了一种基于高阶网络结构的新型随机游走模型，探究高阶网络中的扩散过程及其对信息扩散的影响，旨在揭示复杂网络系统中偏向性信息传播机制并成功应用于多特征对象分类任务中。

Nov, 2019

用随机游走初始化训练超深度前馈网络

该研究论文探讨了在机器学习中训练深度网络的困难之处，并提出了一种方法解决梯度消失问题，即适当增加各层的宽度以缓解问题。

Dec, 2014