摘要

本文重新审视了一种简单的图学习方法，即通过图上的随机游走来产生机器可读记录，然后由深度神经网络处理该记录以直接进行顶点级或图级预测。作者将这些随机机器称为随机游走神经网络，并证明了可以设计它们在概率上具有同构不变性和图函数的通用逼近能力。本文的发现之一是，几乎任何类型的随机游走记录都能保证概率不变性，只要顶点被匿名化。这使得作者能够将随机游走记录为纯文本，并采用预训练的转换器语言模型来读取这些文本记录以解决图任务。此外，作者还建立了随机游走神经网络与消息传递神经网络的并行性，证明了消息传递中的过平滑现象在随机游走神经网络中是内在避免的，而过挤压则表现为概率性的欠到达。作者在几个困难的图问题上测试了基于预训练语言模型的随机游走神经网络，结果表明该方法在图分类、子结构计数和无训练的归纳分类等任务上具有竞争力。

原理

随机游走神经网络的工作原理如下：

1. 随机游走算法：在输入图上产生顶点转换的随机游走。
2. 记录函数：将随机游走转换为机器可读记录。
3. 读者神经网络：处理记录并输出预测。

通过选择适当的随机游走算法和记录函数，随机游走神经网络可以实现概率上的同构不变性和图函数的通用逼近。

流程

随机游走神经网络的工作流程如下：

1. 给定输入图和可选的输入顶点。
2. 运行随机游走算法，生成顶点转换序列。
3. 使用记录函数将随机游走转换为机器可读记录。
4. 将记录输入到读者神经网络中，得到预测结果。

在实际应用中，可以根据具体任务和数据特点选择合适的随机游走算法、记录函数和读者神经网络。

应用

随机游走神经网络在以下领域具有广泛的应用前景：

1. 图分类：可以用于对不同类型的图进行分类，例如社交网络、生物网络等。
2. 子结构计数：能够计算图中的特定子结构的数量，如三角形、四边形等。
3. 归纳分类：可应用于无训练的归纳分类问题，如在大型图上进行顶点分类。
4. 其他图任务：还可以用于图生成、图嵌入等其他图相关任务。