论文标题
使用低纤维化扩散捕获图
Capturing Graphs with Hypo-Elliptic Diffusions
论文作者
论文摘要
图神经网络中的卷积层通过汇总有关当地邻里结构的信息来运行；编码此类子结构的一种常见方法是通过随机步行。这些随机步行的分布根据使用图拉普拉斯式定义的扩散方程而演变。我们通过利用有关低纤维化扩散的经典数学结果来扩展这种方法。这导致了一种新颖的张量值图算子，我们称之为低纤维化图拉普拉斯。我们提供理论保证和有效的低级近似算法。特别是，这提供了一种结构化的方法，可以捕获对汇总功能强大的图形的长距离依赖性。除了有吸引力的理论属性外，我们的实验表明，该方法与需要长距离推理的数据集上的图形变压器竞争，但仅在边缘数量上进行线性缩放，而不是在节点中四次缩放。
Convolutional layers within graph neural networks operate by aggregating information about local neighbourhood structures; one common way to encode such substructures is through random walks. The distribution of these random walks evolves according to a diffusion equation defined using the graph Laplacian. We extend this approach by leveraging classic mathematical results about hypo-elliptic diffusions. This results in a novel tensor-valued graph operator, which we call the hypo-elliptic graph Laplacian. We provide theoretical guarantees and efficient low-rank approximation algorithms. In particular, this gives a structured approach to capture long-range dependencies on graphs that is robust to pooling. Besides the attractive theoretical properties, our experiments show that this method competes with graph transformers on datasets requiring long-range reasoning but scales only linearly in the number of edges as opposed to quadratically in nodes.
