This paper introduces novel methodologies, the Distance Recomputator and
Topology Reconstructor, aimed at enhancing Graph Neural Networks (GNNs). The
Distance Recomputator dynamically recalibrates node distances within k-hop
neighborhoods using a dynamic encoding scheme, thereby improving the accuracy
and adaptability of node representations. Concurrently, the Topology
Reconstructor adjusts local graph structures based on computed "similarity
distances," optimizing network configurations for improved learning outcomes.
These methods address the limitations of static node representations and fixed
aggregation schemes in traditional GNNs, offering a more nuanced approach to
modeling complex and dynamic graph topologies.
Furthermore, our experimental evaluations demonstrate significant performance
advantages over existing methods across various benchmark datasets. The
proposed Distance Recomputator and Topology Reconstructor not only enhance node
relationship modeling accuracy but also optimize information aggregation
efficiency through an asynchronous aggregation mechanism. This approach proves
particularly effective in scenarios involving dynamic or large-scale graphs,
showcasing the methods' robustness and applicability in real-world graph
learning tasks.

本文介绍了一种增强图神经网络（Graph Neural Networks）的新方法，即 Distance Recomputator 和 Topology Reconstructor。通过动态编码方案，Distance Recomputator 动态重新调整 k-hop 邻域内的节点距离，提高节点表示的准确性和适应性。同时，Topology Reconstructor 基于计算出的 ' 相似距离 ' 调整了局部图结构，优化了网络配置以改善学习效果。这些方法解决了传统图神经网络中静态节点表示和固定聚合方案的局限性，提供了一种更细致的建模复杂动态图拓扑结构的方法。此外，我们的实验评估结果显示，所提出的 Distance Recomputator 和 Topology Reconstructor 在各种基准数据集上都具有显著的性能优势。这些方法不仅提升了节点关系建模的准确性，还通过异步聚合机制优化了信息聚合效率。这种方法在处理动态或大规模图的情景中表现出强大的鲁棒性和适用性，展示了这些方法在实际图学习任务中的潜力。

图神经网络的距离重计算器和拓扑重构器

Distance Recomputator and Topology Reconstructor for Graph Neural  Networks

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，在各种图学习任务中展现出卓越的表现。

流动扩散变压器在图学习中的拓扑泛化

Advective Diffusion Transformers for Topological Generalization in Graph  Learning

Human syntactic structures are usually represented as graphs. Much research
has focused on the mapping between such graphs and linguistic sequences, but
less attention has been paid to the shapes of the graphs themselves: their
topologies. This study investigates how the topologies of syntactic graphs
reveal traces of the processes that led to their emergence. I report a new
universal regularity in syntactic structures: Their topology is communicatively
efficient above chance. The pattern holds, without exception, for all 124
languages studied, across linguistic families and modalities (spoken, written,
and signed). This pattern can arise from a process optimizing for communicative
efficiency or, alternatively, by construction, as a by-effect of a sublinear
preferential attachment process reflecting language production mechanisms known
from psycholinguistics. This dual explanation shows how communicative
efficiency, per se, does not require optimization. Among the two options,
efficiency without optimization offers the better explanation for the new
pattern.

研究人类句法结构展现为图形表示后发现，其拓扑图形自身便符合有效沟通机制，而非优化沟通效率而来，此定论同时说明了语言沟通效率自身不一定优化。

语法结构的普遍拓扑规律：从优化中解耦效率

Universal Topological Regularities of Syntactic Structures: Decoupling Efficiency from Optimization

Graph convolutional networks are a new promising learning approach to deal
with data on irregular domains. They are predestined to overcome certain
limitations of conventional grid-based architectures and will enable efficient
handling of point clouds or related graphical data representations, e.g.
superpixel graphs. Learning feature extractors and classifiers on 3D point
clouds is still an underdeveloped area and has potential restrictions to equal
graph topologies. In this work, we derive a new architectural design that
combines rotationally and topologically invariant graph diffusion operators and
node-wise feature learning through 1x1 convolutions. By combining multiple
isotropic diffusion operations based on the Laplace-Beltrami operator, we can
learn an optimal linear combination of diffusion kernels for effective feature
propagation across nodes on an irregular graph. We validated our approach for
learning point descriptors as well as semantic classification on real 3D point
clouds of human poses and demonstrate an improvement from 85% to 95% in Dice
overlap with our multi-kernel approach.

本研究提出一种新的架构设计，结合了旋转和拓扑不变的图扩散算子和 1x1 卷积的逐点特征学习，从而有效地在不规则图形上传播特征并提高 3D 点云的特征提取和语义分类精度。