Graph diffusion equations are intimately related to graph neural networks
(GNNs) and have recently attracted attention as a principled framework for
analyzing GNN dynamics, formalizing their expressive power, and justifying
architectural choices. One key open questions in graph learning is the
generalization capabilities of GNNs. A major limitation of current approaches
hinges on the assumption that the graph topologies in the training and test
sets come from the same distribution. In this paper, we make steps towards
understanding the generalization of GNNs by exploring how graph diffusion
equations extrapolate and generalize in the presence of varying graph
topologies. We first show deficiencies in the generalization capability of
existing models built upon local diffusion on graphs, stemming from the
exponential sensitivity to topology variation. Our subsequent analysis reveals
the promise of non-local diffusion, which advocates for feature propagation
over fully-connected latent graphs, under the assumption of a specific
data-generating condition. In addition to these findings, we propose a novel
graph encoder backbone, Advective Diffusion Transformer (ADiT), inspired by
advective graph diffusion equations that have a closed-form solution backed up
with theoretical guarantees of desired generalization under topological
distribution shifts. The new model, functioning as a versatile graph
Transformer, demonstrates superior performance across a wide range of graph
learning tasks.

图扩散方程与图神经网络紧密相关，并近期引起关注，作为一种分析图神经网络动态、形式化其表达能力并证明架构选择的原则性框架。本文通过探索图扩散方程在不同图拓扑存在下的外推与概括能力，向理解图神经网络的泛化能力迈出了一步。在现有基于图局部扩散的模型中，我们首先展示了其泛化能力的不足之处，这源于对拓扑变化的指数敏感性。随后的分析揭示了非局部扩散的潜力，它提倡在具有特定数据生成条件的情况下，通过在完全连接的潜在图上进行特征传播。除了这些发现，我们提出了一种新颖的图编码器骨干，即 Advective Diffusion Transformer (ADiT)，它受到具有封闭形式解和理论保证的 Advective 图扩散方程的启发，在拓扑分布转移情况下具有期望的泛化能力。这个新模型作为一种多功能图 Transformer，在各种图学习任务中展现出卓越的表现。