摘要

我们提出了一种名为CRaWl的新颖神经网络架构，用于图学习。与图神经网络（GNN）类似，CRaWl的每一层均可在图上更新节点特征，因此可自由地与GNN层组合或交替使用。然而，CRaWl在本质上与基于消息传递的图神经网络存在根本差异。CRaWl通过在图中随机游走路径上出现的子图上提取并聚合信息，利用一维卷积（1D Convolution）实现特征学习，从而能够捕捉长程依赖关系，并计算非局部特征。作为本方法的理论基础，我们证明了一个定理：CRaWl的表达能力与Weisfeiler-Leman（WL）算法的表达能力不可比较，因而也与图神经网络的表达能力不可比较。这意味着存在一些函数可由CRaWl表示，但无法被GNN表示，反之亦然。该结论可推广至Weisfeiler-Leman层次结构的更高阶情形，因此同样适用于高阶图神经网络。在实验方面，我们在多个图分类与回归任务的基准数据集上验证了CRaWl的性能，结果表明其在各类任务中均能达到与当前最先进GNN架构相当的水平。