提出图Transformer隐层维度压缩的理论边界，适用于稀疏与密集变体。
A Theory for Compressibility of Graph Transformers for Transductive Learning
- 基于图结构半监督特性，推导隐层维度压缩的理论条件。
- 证明在特定条件下，隐层维度可显著降低而不损失性能。
- 为高效图Transformer设计提供理论依据，适合模型压缩研究者。
图上的归纳任务与典型监督学习任务有本质区别，因样本不满足独立同分布假设。训练时所有测试/验证样本均已知，更接近半监督学习。这一差异使得模型分析不同于其他模型。近期，图Transformer通过克服长距离依赖问题，在此类数据集上取得了显著提升。然而，全量Transformer的二次复杂度促使学界探索更高效的变体，如稀疏注意力模式。尽管注意力矩阵被广泛研究，网络隐层维度（宽度）的关注较少。本文建立了关于图Transformer隐层维度压缩的理论边界，适用于稀疏与密集变体。
原文摘要 · Abstract (English)
Transductive tasks on graphs differ fundamentally from typical supervised machine learning tasks, as the independent and identically distributed (i.i.d.) assumption does not hold among samples. Instead, all train/test/validation samples are present during training, making them more akin to a semi-supervised task. These differences make the analysis of the models substantially different from other models. Recently, Graph Transformers have significantly improved results on these datasets by overcoming long-range dependency problems. However, the quadratic complexity of full Transformers has driven the community to explore more efficient variants, such as those with sparser attention patterns. While the attention matrix has been extensively discussed, the hidden dimension or width of the network has received less attention. In this work, we establish some theoretical bounds on how and under what conditions the hidden dimension of these networks can be compressed. Our results apply to both sparse and dense variants of Graph Transformers.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。