2024/11/20 by Hamed Shirzad, Shirzad, Hamed, Honghao Lin +11 · 1 voice
Computer Science · #Advanced Graph Neural Networks #Machine Learning and Algorithms #Machine Learning and ELM #cs.LG #stat.ML
paper · pdf · doi:10.48550/arxiv.2411.13028
openalex publication_date 2024/11/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.