A Theory for Compressibility of Graph Transformers for Transductive Learning

• URL: http://arxiv.org/abs/2411.13028v1
• Date: Wed, 20 Nov 2024 04:20:17 GMT
• Title: A Theory for Compressibility of Graph Transformers for Transductive Learning
• Authors: Hamed Shirzad, Honghao Lin, Ameya Velingker, Balaji Venkatachalam, David Woodruff, Danica Sutherland,
• Abstract summary: Transductive tasks on graphs differ fundamentally from typical supervised machine learning tasks. All train/test/validation samples are present during training, making them more akin to a semi-supervised task. We establish some theoretical bounds on how and under what conditions the hidden dimension of these networks can be compressed.
• Score: 6.298115235439078
• License:
• Abstract: 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.

Related papers

• On the Role of Depth and Looping for In-Context Learning with Task Diversity [69.4145579827826]
  We study in-context learning for linear regression with diverse tasks. We show that multilayer Transformers are not robust to even distributional shifts as small as $O(e-L)$ in Wasserstein distance.
  arXiv  Detail & Related papers  (2024-10-29T03:27:56Z)
• Unveil Benign Overfitting for Transformer in Vision: Training Dynamics, Convergence, and Generalization [88.5582111768376]
  We study the optimization of a Transformer composed of a self-attention layer with softmax followed by a fully connected layer under gradient descent on a certain data distribution model. Our results establish a sharp condition that can distinguish between the small test error phase and the large test error regime, based on the signal-to-noise ratio in the data model.
  arXiv  Detail & Related papers  (2024-09-28T13:24:11Z)
• Robust representations of oil wells' intervals via sparse attention mechanism [2.604557228169423]
  We introduce the class of efficient Transformers named Regularized Transformers (Reguformers) The focus in our experiments is on oil&gas data, namely, well logs. To evaluate our models for such problems, we work with an industry-scale open dataset consisting of well logs of more than 20 wells.
  arXiv  Detail & Related papers  (2022-12-29T09:56:33Z)
• Deformable Graph Transformer [31.254872949603982]
  We propose Deformable Graph Transformer (DGT) that performs sparse attention with dynamically sampled key and value pairs. Experiments demonstrate that our novel graph Transformer consistently outperforms existing Transformer-based models.
  arXiv  Detail & Related papers  (2022-06-29T00:23:25Z)
• What Dense Graph Do You Need for Self-Attention? [73.82686008622596]
  We present Hypercube Transformer, a sparse Transformer that models token interactions in a hypercube and shows comparable or even better results with vanilla Transformer. Experiments on tasks requiring various sequence lengths lay validation for our graph function well.
  arXiv  Detail & Related papers  (2022-05-27T14:36:55Z)
• Revisiting Over-smoothing in BERT from the Perspective of Graph [111.24636158179908]
  Recently over-smoothing phenomenon of Transformer-based models is observed in both vision and language fields. We find that layer normalization plays a key role in the over-smoothing issue of Transformer-based models. We consider hierarchical fusion strategies, which combine the representations from different layers adaptively to make the output more diverse.
  arXiv  Detail & Related papers  (2022-02-17T12:20:52Z)
• Gophormer: Ego-Graph Transformer for Node Classification [27.491500255498845]
  In this paper, we propose a novel Gophormer model which applies transformers on ego-graphs instead of full-graphs. Specifically, Node2Seq module is proposed to sample ego-graphs as the input of transformers, which alleviates the challenge of scalability. In order to handle the uncertainty introduced by the ego-graph sampling, we propose a consistency regularization and a multi-sample inference strategy.
  arXiv  Detail & Related papers  (2021-10-25T16:43:32Z)
• Grounding inductive biases in natural images:invariance stems from variations in data [20.432568247732206]
  We study the factors of variation in a real dataset, ImageNet. We show standard augmentation relies on a precise combination of translation and scale. We find that the main factors of variation in ImageNet mostly relate to appearance.
  arXiv  Detail & Related papers  (2021-06-09T14:58:57Z)
• Vision Transformers are Robust Learners [65.91359312429147]
  We study the robustness of the Vision Transformer (ViT) against common corruptions and perturbations, distribution shifts, and natural adversarial examples. We present analyses that provide both quantitative and qualitative indications to explain why ViTs are indeed more robust learners.
  arXiv  Detail & Related papers  (2021-05-17T02:39:22Z)
• Category-Learning with Context-Augmented Autoencoder [63.05016513788047]
  Finding an interpretable non-redundant representation of real-world data is one of the key problems in Machine Learning. We propose a novel method of using data augmentations when training autoencoders. We train a Variational Autoencoder in such a way, that it makes transformation outcome predictable by auxiliary network.
  arXiv  Detail & Related papers  (2020-10-10T14:04:44Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.