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 random walk neural networks, and show
that we can design them to be isomorphism invariant while capable of universal
approximation of graph functions in probability. A useful finding is that
almost any kind of record of random walk guarantees probabilistic invariance as
long as the vertices are anonymized. This enables us to record random walks in
plain text and adopt a language model to read these text records to solve graph
tasks. We further establish a parallelism to message passing neural networks
using tools from Markov chain theory, and show that over-smoothing in message
passing is alleviated by construction in random walk neural networks, while
over-squashing manifests as probabilistic under-reaching. We show that random
walk neural networks based on pre-trained language models can solve several
hard problems on graphs, such as separating strongly regular graphs where the
3-WL test fails, counting substructures, and transductive classification on
arXiv citation network without training. Code is available at
this https URL

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

重温图上的随机游走学习

Revisiting Random Walks for Learning on Graphs

Machine learning on graphs has recently found extensive applications across
domains. However, the commonly used Message Passing Neural Networks (MPNNs)
suffer from limited expressive power and struggle to capture long-range
dependencies. Graph transformers offer a strong alternative due to their global
attention mechanism, but they come with great computational overheads,
especially for large graphs. In recent years, State Space Models (SSMs) have
emerged as a compelling approach to replace full attention in transformers to
model sequential data. It blends the strengths of RNNs and CNNs, offering a)
efficient computation, b) the ability to capture long-range dependencies, and
c) good generalization across sequences of various lengths. However, extending
SSMs to graph-structured data presents unique challenges due to the lack of
canonical node ordering in graphs. In this work, we propose Graph State Space
Convolution (GSSC) as a principled extension of SSMs to graph-structured data.
By leveraging global permutation-equivariant set aggregation and factorizable
graph kernels that rely on relative node distances as the convolution kernels,
GSSC preserves all three advantages of SSMs. We demonstrate the provably
stronger expressiveness of GSSC than MPNNs in counting graph substructures and
show its effectiveness across 10 real-world, widely used benchmark datasets,
where GSSC achieves best results on 7 out of 10 datasets with all significant
improvements compared to the state-of-the-art baselines and second-best results
on the other 3 datasets. Our findings highlight the potential of GSSC as a
powerful and scalable model for graph machine learning. Our code is available
at this https URL

提出了一种名为 Graph State Space Convolution (GSSC) 的方法，该方法是 State Space Models (SSMs) 在图结构数据上的扩展，通过利用全局置换等变集合聚合和以节点之间的相对距离作为卷积核的可分解图卷积核，保留了 SSMs 的三个优点。实验证明 GSSC 在计算图子结构和十个常用基准数据集的表现上比 Message Passing Neural Networks (MPNNs) 更加表达能力强，且在 7 个数据集上取得了最佳结果，在其他 3 个数据集上也有显著提升。该研究结果突出了 GSSC 作为一种强大且可扩展的图机器学习模型的潜力。