线性Transformer可模拟电流传导与特征分解，实现图数据高效计算。
Graph Transformers Dream of Electric Flow
- 基于图关联矩阵设计权重，让Transformer模拟经典图算法
- 理论误差受底层算法误差约束，实验验证合成数据有效性
- 在分子回归任务中学习更优位置编码，优于传统拉普拉斯特征向量
我们从理论和实证两方面证明，当应用于图数据时，线性Transformer能够实现求解经典问题如电流传导和特征向量分解的算法。Transformer仅通过图的关联矩阵获取输入图信息。我们给出了实现各算法的显式权重配置，并将构造的Transformer误差控制在底层算法误差范围内。理论结果在合成数据上得到实验验证。此外，在真实世界的分子回归任务中，观察到线性Transformer能学习到比基于拉普拉斯特征向量的默认位置编码更有效的表示。本工作为揭示Transformer在图数据中的内部机理迈出初步一步。代码已开源：https://github.com/chengxiang/LinearGraphTransformer
原文摘要 · Abstract (English)
We show theoretically and empirically that the linear Transformer, when applied to graph data, can implement algorithms that solve canonical problems such as electric flow and eigenvector decomposition. The Transformer has access to information on the input graph only via the graph's incidence matrix. We present explicit weight configurations for implementing each algorithm, and we bound the constructed Transformers' errors by the errors of the underlying algorithms. Our theoretical findings are corroborated by experiments on synthetic data. Additionally, on a real-world molecular regression task, we observe that the linear Transformer is capable of learning a more effective positional encoding than the default one based on Laplacian eigenvectors. Our work is an initial step towards elucidating the inner-workings of the Transformer for graph data. Code is available at https://github.com/chengxiang/LinearGraphTransformer
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。