A Theory for Compressibility of Graph Transformers for Transductive Learning
This work addresses efficiency issues for researchers and practitioners using Graph Transformers in graph-based tasks, but it is incremental as it builds on existing compression methods.
The paper tackles the problem of high computational complexity in Graph Transformers for transductive learning by establishing theoretical bounds on compressing the hidden dimension of these networks, applicable to both sparse and dense variants.
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.