Pith. sign in

REVIEW 4 major objections 5 minor 2 cited by

A Theory for Compressibility of Graph Transformers for Transductive Learning

T0 review · 4 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The hidden width of graph transformers can be compressed to O(log n / epsilon^2) or to the rank of internal embeddings while keeping outputs and attention scores close.

desk verdict Conditional existence theorems for graph-transformer width compression, with a strong unverified clustering assumption carrying the headline claim and a few fixable proof errors. read the letter →

arxiv 2411.13028 v1 pith:6PD4RVBG submitted 2024-11-20 cs.LG stat.ML

Hamed Shirzad , Honghao Lin , Ameya Velingker , Balaji Venkatachalam , David Woodruff , Danica Sutherland This is my paper · ORCID
classification cs.LGstat.ML
keywords graphtransformerstransductivelearninghiddendimensioncompressionJohnson-Lindenstrausslemmalow-rankembeddingsnodeclassificationattentionsparsitywidthreduction
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

On transductive node-classification graphs, where all train and test nodes are visible during training, the paper asks how much the hidden width of a Graph Transformer can be reduced without changing what the network computes. It claims that the query and key projections can always be shrunk to width O(log n / $epsilon^{2}$) using the Johnson-Lindenstrauss lemma, keeping output vectors within O(epsilon) and attention scores within a 1 +/- O(epsilon) factor, for any attention pattern. For the whole network, it proves that width d suffices whenever the internal embeddings are approximately low-rank or, after attention pooling, cluster into at most d well-separated centers; under the clustering condition all weight matrices become d x d. These structural conditions are not checked on trained models, so the unconditional result is the attention compression, while the full-width compression is conditional. Experiments on three graph datasets show that small width-4 networks trained from scratch can reach accuracy close to width-64 networks, supporting the existence of such compressed models without providing an algorithm that finds them.

What carries the argument

The central mechanism is the Johnson-Lindenstrauss lemma, which guarantees that a random projection to O(\log n / \$epsilon^{2}$) dimensions preserves all pairwise dot products among n vectors up to an additive \epsilon; Theorem 3.3 uses this to compress W_Q and W_K by mapping query and key vectors into a low-dimensional space before taking their dot product. For full-width compression, the paper replaces the probabilistic argument with deterministic structural assumptions: approximate low-rankness of embeddings allows a U \Lambda decomposition so that U \Lambda H is column-wise within \epsilon of H, letting every linear map be replaced by a d \times d matrix, and the clustering assumption in Theorem 4.4 builds almost one-hot ReLU responses that let the feed-forward block collapse to d \times d weights. The counter-example in Appendix C.3.1 shows why the same U-\Lambda trick cannot pass through the activation function without one of these structural assumptions.

What would settle it

Take a trained Graph Transformer on a standard transductive dataset (for example, one of the three used in the paper) and compute, for each layer, the column-wise \$ell^{2}$ distance from $H^{{(\ell+3/4)}}$ to its best rank-d approximation over a range of d; if the minimum distance needed to make the network practical is not O(\epsilon), then Theorem 4.2's condition fails and the full hidden-dimension compression claim does not apply. Similarly, run a clustering algorithm on each $H^{{(\ell+1/2)}}$ and check whether at most d centers exist with the separation condition c_a \cdot c_b < \$gamma_1^{2}$ / 2; a negative answer would break Theorem 4.4.

Watch

Extended reading notes

Core claim

The paper's central claim is that a Graph Transformer T of hidden width D has a compressed counterpart \hat{T} of width d such that for every node i the output error \|T(X)_i - \hat{T}(X)_i\|_2 = O(\epsilon) and every attention score satisfies a_{ij}/\hat{a}_{ij} = 1 + O(\epsilon). Theorem 3.3 achieves this for the attention computation by compressing the query and key matrices W_Q, W_K \in \mathbb{R}^{d \times D} with d = O(\log n / \$epsilon^{2}$), a direct application of the Johnson-Lindenstrauss lemma to the dot products that define attention. Theorem 4.2 extends this to all linear maps under an approximate low-rank condition: if the post-activation embeddings $H^{{(\ell+3/4)}}$ are column-wise within \epsilon of a rank-d matrix, then the value, key, and query maps become d \times d, with only W_1 \in \mathbb{R}^{d \times D} and W_2 \in \mathbb{R}^{D \times d} retaining size-D components. Theorem 4.4 goes further: if the post-attention embeddings $H^{{(\ell+1/2)}}$ cluster into at most d well-separated centers, then every weight matrix in the network can be d \times d, giving a fully width-d transformer. These results hold for dense, sparse, and intermediate attention patterns because the analysis decouples the attention pattern from the graph structure.

Load-bearing premise

The full-width compression theorems rest on the assumption that, after each layer, the trained network's node embeddings are either well approximated by a low-rank matrix or form a small number of well-separated clusters; if trained Graph Transformers do not actually have this structure, only the query/key compression in Theorem 3.3 is guaranteed.

Editorial extensions

If this is right

  • Because Theorem 3.3 holds for any attention pattern, a single JL-based projection can make the attention pass of sparse, dense, and hybrid graph transformers run in O(m \log n / \epsilon^2) time instead of O(mD).
  • If a trained network's embeddings are column-wise close to a rank-d matrix, the network can be rebuilt with d \times d weight matrices for value, key, and query, leaving only a small number of D-dimensional vectors after the activation; the cost of width then scales with the rank of the data rather than the nominal width.
  • When post-attention embeddings form d well-separated clusters, the entire transformer, including the feed-forward block, collapses to width d, and attention scores of the compressed network remain within a 1 + O(\epsilon) factor of the original.
  • The results are existence guarantees: the compressed weights are constructed in the proofs, but gradient descent is not shown to find them, so the theorems define a target for future compression and distillation methods rather than a training recipe.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The low-rank and clustering conditions are exactly the signatures of oversmoothing and class-wise embedding convergence that graph neural networks are known to exhibit, so the conditions may become easier to satisfy as networks get deeper, turning a known failure mode into a compressibility certificate.
  • A practical compression pipeline could monitor the effective rank of H^{(\ell+3/4)} during training and, once the rank stabilizes below d, apply the constructive maps from Theorem 4.2; the paper gives no such procedure, but its proofs would supply the maps in the exact low-rank case.
  • The 99% guarantee of Proposition 4.3 suggests a slack-tolerant compression heuristic: compress most nodes exactly and allow a small outlier fraction, which may be enough in practice because a few mis-scaled attention rows will not change all downstream node predictions.
  • The attention-score ratio guarantee means compressed networks could serve as explainability proxies: if attention is the explanation, the narrow network's attention scores are provably close to the wide network's, so explanations transfer up to O(\epsilon).
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

Summary. The paper studies whether the hidden dimension of a trained single-head Graph Transformer can be reduced while approximately preserving its outputs and attention scores on transductive node-classification tasks. Section 3 gives a Johnson-Lindenstrauss-based result compressing the query and key projections to dimension d = O(log n / ε^2), with an output-error guarantee O(ε) and attention-score ratios 1 + O(ε). Section 4 extends this to the value and feed-forward maps under exact low-rank (Proposition 4.1), approximate low-rank (Theorem 4.2), and post-attention clustering (Theorem 4.4) assumptions, with the clustering result giving all maps in R^{d×d}. Section 5 reports experiments training width-4 Graph Transformers from scratch on three datasets and comparing their test metrics to width-64 models, together with measurements of operator norms and vector norms in the large models.

Significance. If the proof issues are repaired, the paper would provide a useful conditional theory: the Q/K compression theorem gives a concrete logarithmic width bound with explicit error accumulation over a constant number of layers, and the low-rank/clustering results identify structural conditions under which full width reduction is possible. The paper is constructive rather than circular: the compressed networks are built from the original weights and activations, no parameters are fitted to make the theorems true, and the dependence of the error constants on the norm bounds α, β and the depth L = O(1) is made explicit. At the same time, the practical reach of the paper is currently limited: the full width-d statement depends on a clustering hypothesis that is not checked on trained models, and several load-bearing proof steps are incorrect as written. The contribution is therefore not yet in publishable form, but the central ideas are plausible and appear salvageable.

major comments (4)
  1. [§3, Corollary 3.2 and Appendix C.1] Corollary 3.2 is stated as a multiplicative relative-error bound on x^T y. This is not the standard JLT dot-product guarantee and is false as stated when x^T y ≤ 0; for x^T y = 0 the claimed interval collapses and the assertion cannot hold for a general JL distribution. The proof of Theorem 3.3 only needs the additive bound |x^T M^T M y − x^T y| ≤ εγ, so the corollary should be restated in additive form. In the same appendix, the inequality exp(−2ε_a) > 1 − ε_a is false for small ε_a (the correct leading behavior is exp(−2ε_a) = 1 − 2ε_a + O(ε_a^2)); the attention-ratio bound can be repaired by using exp(−2ε_a) > 1 − 2ε_a and adjusting constants. Also, in the displayed bound for ∥h_i^{(ℓ+1/2)} − bhat h_i^{(ℓ+1/2)}∥, the sum over j is dropped in the first term of the final line; the intended bound can be recovered by applying Jensen/convexity to the attention-weighted average, but the written equality is formally incorrect. Since Theorem 3.3 is the foundational result of the paper, these proof steps must be corrected.
  2. [Appendix C.5, proof of Lemma C.6] The construction of the compressed value map is invalid. The proof bounds the bilinear form bhat h_i^T U^T W_V^T W_V U bhat h_j and then sets cW_V = U^T W_V^T W_V U. But with the transformer convention bhat v_i = cW_V bhat h_i, one obtains bhat v_i · bhat v_j = bhat h_i^T U^T W_V^T W_V U U^T W_V^T W_V U bhat h_j, which is not the quantity bounded in the proof unless U U^T acts as the identity on the relevant subspace. This step is load-bearing for Theorem 4.4. It can be fixed by choosing cW_V to be a matrix square root (or Cholesky factor) of U^T W_V^T W_V U, so that cW_V^T cW_V = U^T W_V^T W_V U; the proof should be rewritten accordingly.
  3. [Theorem 4.2 and Appendix C.3] The theorem statement has a dimension error: it says W1 ∈ R^{d×D} and W2 ∈ R^{D×d}, but the proof constructs cW1 = W1 U ∈ R^{D×d} and cW2 = Λ W2 ∈ R^{d×D}. The statement should be corrected to match the proof. More substantively, this theorem is not full width-d compression: the post-activation vector is D-dimensional, so the feed-forward computation in the compressed network still costs n·D·d. The abstract and introduction should state explicitly that full hidden-dimension compression is established only under the exact low-rank condition of Proposition 4.1 or the clustering condition of Theorem 4.4, and that Theorem 4.2 leaves a D-dimensional activation bottleneck.
  4. [§5, Experiments] The experiments do not test the hypotheses of Theorems 4.2 and 4.4. Table 1 validates the norm bounds of Section 2, but no measurements are reported of approximate rank of H^{(ℓ+3/4)} or of post-attention cluster radii/separation for H^{(ℓ+1/2)}, and the small networks are trained from scratch rather than constructed from a large pretrained model. As a result, the empirical section provides evidence that small networks can reach competitive test metrics, but not that the structural conditions of the main compression theorems hold on trained graph transformers. Either add diagnostics for the low-rank/clustering conditions or explicitly state that the experiments do not validate the applicability of those assumptions.
minor comments (5)
  1. [Theorem 3.3 statement] The phrase "for any layer WQ and WK are in R^{d×D}" is imprecise: the theorem compresses the query and key maps of the attention block while keeping the feed-forward maps W1 and W2 in R^{D×D}. The statement should say the compressed maps cW_Q, cW_K are in R^{d×D} and that the MLP is not compressed in this theorem.
  2. [Theorem 4.2 statement] The list "cWV, cWQ, and cWQ ∈ R^{d×d}" contains a duplicated cWQ; the third entry should be cWK.
  3. [Appendix C.4, proof of Proposition 4.3] In the displayed chain "∥USh_i − h_i∥ = ∥A(SA^−)h_i − h_i∥ = ∥SAx − Sh_i∥", the final equality conflates x with the solution x_i = (SA)^− S h_i of the sampled regression problem. Defining x_i explicitly would make the argument correct.
  4. [Theorem 4.4 proof] The construction of cW1 uses a bias term (the constant −3∥c_a∥^2), but the Transformer formulation in Section 2 has no bias in the linear maps. The theorem should either be stated for affine maps or the architecture should be extended to include biases.
  5. [Notation, Appendix C.5] The symbol bhat c_a is used before it is defined; the proof should state explicitly whether bhat c_a is a selected compressed-space node representation or the image of an original center under the low-dimensional map U, since the denominator ∥c_a∥ is the norm of the original high-dimensional center.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the compression guarantees are conditional constructions from JLT and low-rank/clustering hypotheses; the only self-citation is attribution, and the proof in the appendix is self-contained.

full rationale

Walking the derivation chain: Theorem 3.3 is proved from the Johnson-Lindenstrauss lemma (Lemma 3.1) and its dot-product corollary via a union bound in Appendix C.1. The compressed Q/K maps are constructed as M_QK W_Q and M_QK W_K with M_QK a JL matrix, and the error analysis is an inductive Lipschitz contraction over L=O(1) layers. Nothing is fitted to make the theorem true, and the sentence 'A version of this result also appeared in our recent work (Shirzad et al., 2024)' is attribution, not a load-bearing premise, because the appendix proof is self-contained and does not cite that work. Theorem 4.2 is a conditional construction: under the stated rank-d column-wise closeness of X and H^{l+3/4}, the proof in Appendix C.3 uses Lemma C.1 to build W1 in R^{d x D}, W2 in R^{D x d} and propagates an O(epsilon) contraction whose error term is exactly the assumption's epsilon. It is a genuine limitation, not circularity, that this leaves a D-dimensional activation inside the MLP; the abstract's broad 'width can be compressed' claim is only fully realized by Theorem 4.4's clustering assumption, and Section 5 does not verify that clustering or approximate-rank condition on the trained models. This weakens the strength of the headline claim but is a correctness/evidence concern, not a circular reduction. Theorem 4.4 is also conditional: it assumes post-attention embeddings cluster into d well-separated centers and then constructs a width-d network whose MLP rows act as cluster indicators, using knowledge of the original network's weights and activations. That is the correct form of an existence/compression guarantee. The experiments independently train width-4 networks from scratch and report the maximum over 100 initializations; the paper explicitly says that practical compression algorithms are future work, so no fitted parameter is renamed as a prediction. No step in the paper's derivation reduces, by its own equations or by a self-citation chain, to its own conclusion.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The proofs rest on standard sketching results plus structural assumptions on the original network's internal embeddings. The norm bounds were measured on three datasets, but the low-rank and clustering assumptions were not checked. The architecture analyzed drops LayerNorm, biases, skip connections, and multi-head attention; the empirical model includes them.

assumptions (6)
  • standard math Johnson-Lindenstrauss lemma and its dot-product corollary hold with d = O(log n / eps^2).
    Used in Theorem 3.3 and Lemma C.5 to preserve query-key dot products over all attention pairs.
  • domain assumption Inputs and all layer inputs have Euclidean norm at most sqrt(alpha), and all weight matrices have operator norm at most beta.
    Section 2 states these bounds; Table 1 gives average measured values on three datasets but they are not proven for trained graph transformers in general.
  • domain assumption The number of layers L is O(1).
    Section 2 notes graph transformers are typically 2-4 layers, so error propagation stays bounded by a constant.
  • domain assumption For every layer, the post-activation embedding H^{l+3/4} is column-wise within eps of a rank-d matrix.
    Assumed in Theorem 4.2 and used in the induction; not validated empirically in the paper.
  • domain assumption After each attention pooling, the embeddings H^{l+1/2} cluster into at most d well-separated centers with bounded norms.
    Assumed in Theorem 4.4 to construct the low-dimensional feed-forward layers; not checked on trained models.
  • domain assumption The simplified architecture without LayerNorm, biases, skip connections, and multi-head attention captures the behavior of practical graph transformers.
    Section 2 says these are simplifications; the experiments in Appendix D use batch norm, skip connections, and 1/sqrt(D) scaling, so the analyzed and tested models differ.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A Theory for Compressibility of Graph Transformers for Transductive Learning." pith.science (2026). https://pith.science/paper/6PD4RVBG

@misc{pith2026241113028,
  author       = {Pith},
  title        = {Pith review of: A Theory for Compressibility of Graph Transformers for Transductive Learning},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6PD4RVBG}},
  note         = {Machine review of arXiv:2411.13028}
}
read the original 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.

Figures

Figures reproduced from arXiv: 2411.13028 by the authors.

Figure 1
Figure 1. Comparison of the results from a relatively large network with hidden dimension 64 and a small network with hidden dimension 4. competitively with larger networks. While much of the theory in this work is constructive, some steps require extensive trial and error. To explore this question, we conduct the following experiment instead of directly compressing the actual network: we train a very small network with a hid… view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. TxPert: Leveraging Biochemical Relationships for Out-of-Distribution Transcriptomic Perturbation Prediction

    cs.LG 2025-05 conditional novelty 6.0 of 10

    TxPert uses graph neural networks over multiple gene interaction graphs to predict transcriptional responses to unseen single, double, and cross-cell-line perturbations, outperforming GEARS and scLAMBDA in benchmark tests.

  2. Even Sparser Graph Transformers

    cs.LG 2024-11 conditional novelty 6.0 of 10

    Spexphormer trains a narrow graph transformer to identify important attention edges, then trains a wider model on the sparsified graph, achieving competitive accuracy with far less memory.

Reference graph

Works this paper leans on

45 extracted references · 9 canonical work pages · cited by 2 Pith papers

  1. [1]

    Burr, M., Gao, S., and Knoll, F. (2018). Optimal bounds for J ohnson- L indenstrauss transformations. Journal of Machine Learning Research , 19(73):1--22

    work page 2018

  2. [2]

    and Price, E

    Chen, X. and Price, E. (2019). Active regression via linear-sample sparsification. In Beygelzimer, A. and Hsu, D., editors, Conference on Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA , volume 99 of Proceedings of Machine Learning Research , pages 663--695. PMLR

    work page 2019

  3. [3]

    Deng, C., Yue, Z., and Zhang, Z. (2024). Polynormer: Polynomial-expressive graph transformer in linear time. arXiv preprint arXiv:2403.01232

    arXiv 2024

  4. [4]

    Devlin, J., Chang, M.-W., Lee, K., and Toutanova, K. (2018). Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04805

    arXiv 2018

  5. [5]

    Dong, Y., Cordonnier, J.-B., and Loukas, A. (2021). Attention is not all you need: Pure attention loses rank doubly exponentially with depth. In International Conference on Machine Learning , pages 2793--2803. PMLR

    work page 2021

  6. [6]

    Dosovitskiy, A., Beyer, L., Kolesnikov, A., Weissenborn, D., Zhai, X., Unterthiner, T., Dehghani, M., Minderer, M., Heigold, G., Gelly, S., et al. (2020). An image is worth 16x16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010.11929

    arXiv 2020

  7. [7]

    Dwivedi, V. P. and Bresson, X. (2020). A generalization of transformer networks to graphs. CoRR , abs/2012.09699

    arXiv 2020

  8. [8]

    and Lenssen, J

    Fey, M. and Lenssen, J. E. (2019). Fast graph representation learning with PyTorch Geometric . In ICLR Workshop on Representation Learning on Graphs and Manifolds

    2019

Show all 45 references
  1. [9]

    Hamilton, W., Ying, Z., and Leskovec, J. (2017). Inductive representation learning on large graphs. Advances in neural information processing systems , 30

    2017

  2. [10]

    Hu, W., Fey, M., Ren, H., Nakata, M., Dong, Y., and Leskovec, J. (2021). OGB-LSC: A large-scale challenge for machine learning on graphs. CoRR , abs/2103.09430

    2021 arXiv

  3. [11]

    Johnson, W. B. (1984). Extensions of lipshitz mapping into hilbert space. In Conference modern analysis and probability, 1984 , pages 189--206

    1984

  4. [12]

    and Shakhnarovich, G

    Kakade, S. and Shakhnarovich, G. (2009). Lecture notes in large scale learning. https://home.ttic.edu/ gregory/courses/LargeScaleLearning/lectures/jl.pdf

    2009

  5. [13]

    Kipf, T. N. and Welling, M. (2016). Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907

    2016 arXiv

  6. [14]

    L., L \'e tourneau, V., and Tossou, P

    Kreuzer, D., Beaini, D., Hamilton, W. L., L \'e tourneau, V., and Tossou, P. (2021). Rethinking graph transformers with spectral attention. arXiv preprint arXiv:2106.03893

    2021 arXiv

  7. [15]

    Leskovec, J. (2014). Snap datasets: Stanford large network dataset collection. Retrieved December 2021 from http://snap. stanford. edu/data

    2014

  8. [16]

    Likhosherstov, V., Choromanski, K., and Weller, A. (2021). On the expressive power of self-attention matrices. arXiv preprint arXiv:2106.03764

    2021 arXiv

  9. [17]

    Liu, C., Zhan, Y., Wu, J., Li, C., Du, B., Hu, W., Liu, T., and Tao, D. (2022). Graph pooling for graph neural networks: Progress, challenges, and opportunities. arXiv preprint arXiv:2204.07321

    2022 arXiv

  10. [18]

    and Hutter, F

    Loshchilov, I. and Hutter, F. (2016). Sgdr: Stochastic gradient descent with warm restarts. arXiv preprint arXiv:1608.03983

    2016 arXiv

  11. [19]

    Loshchilov, I., Hutter, F., et al. (2017). Fixing weight decay regularization in adam. arXiv preprint arXiv:1711.05101 , 5

    2017 arXiv

  12. [20]

    Loukas, A. (2019). What graph neural networks cannot learn: depth vs width. arXiv preprint arXiv:1907.03199

    2019 arXiv

  13. [21]

    McAuley, J., Targett, C., Shi, Q., and Van Den Hengel, A. (2015). Image-based recommendations on styles and substitutes. In Proceedings of the 38th international ACM SIGIR conference on research and development in information retrieval , pages 43--52

    2015

  14. [22]

    M \"u ller, L., Galkin, M., Morris, C., and Ramp \'a s ek, L. (2023). Attending to graph transformers. arXiv preprint arXiv:2302.04181

    2023 arXiv

  15. [23]

    P., and Yasuda, T

    Musco, C., Musco, C., Woodruff, D. P., and Yasuda, T. (2022). Active linear regression for _p norms and beyond. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022 , pages 744--753. IEEE

    2022

  16. [24]

    and Maehara, T

    Nt, H. and Maehara, T. (2019). Revisiting graph neural networks: All we have is low-pass filters. arXiv preprint arXiv:1905.09550

    2019 arXiv

  17. [25]

    and Suzuki, T

    Oono, K. and Suzuki, T. (2019). Graph neural networks exponentially lose expressive power for node classification. arXiv preprint arXiv:1905.10947

    2019 arXiv

  18. [26]

    Platonov, O., Kuznedelev, D., Diskin, M., Babenko, A., and Prokhorenkova, L. (2023). A critical look at the evaluation of gnns under heterophily: Are we really making progress? arXiv preprint arXiv:2302.11640

    2023 arXiv

  19. [27]

    P., Luu, A

    Ramp \'a s ek, L., Galkin, M., Dwivedi, V. P., Luu, A. T., Wolf, G., and Beaini, D. (2022). Recipe for a general, powerful, scalable graph transformer. Advances in Neural Information Processing Systems , 35:14501--14515

    2022

  20. [28]

    M., and Liebig, T

    Roth, A., Bause, F., Kriege, N. M., and Liebig, T. (2024). Preventing representational rank collapse in mpnns by splitting the computational graph. arXiv preprint arXiv:2409.11504

    2024 arXiv

  21. [29]

    Sanford, C., Fatemi, B., Hall, E., Tsitsulin, A., Kazemi, M., Halcrow, J., Perozzi, B., and Mirrokni, V. (2024a). Understanding transformer reasoning capabilities via graph algorithms. arXiv preprint arXiv:2405.18512

    2024 arXiv

  22. [30]

    Sanford, C., Hsu, D., and Telgarsky, M. (2024b). Transformers, parallel computation, and logarithmic depth. arXiv preprint arXiv:2402.09268

    2024 arXiv

  23. [31]

    J., and Telgarsky, M

    Sanford, C., Hsu, D. J., and Telgarsky, M. (2024c). Representational strengths and limitations of transformers. Advances in Neural Information Processing Systems , 36

    2024

  24. [32]

    Shchur, O., Mumme, M., Bojchevski, A., and G \"u nnemann, S. (2018). Pitfalls of graph neural network evaluation. arXiv preprint arXiv:1811.05868

    2018 arXiv

  25. [33]

    Shirzad, H., Lin, H., Venkatachalam, B., Velingker, A., Woodruff, D., and Sutherland, D. J. (2024). Even sparser graph transformers. In The Thirty-eighth Annual Conference on Neural Information Processing Systems

    2024

  26. [34]

    J., and Sinop, A

    Shirzad, H., Velingker, A., Venkatachalam, B., Sutherland, D. J., and Sinop, A. K. (2023). Exphormer: Sparse transformers for graphs. In ICML

    2023

  27. [35]

    N., Kaiser, L., and Polosukhin, I

    Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L., and Polosukhin, I. (2017). Attention is all you need. In NeurIPS , pages 5998--6008

    2017

  28. [36]

    Veli c kovi \'c , P., Cucurull, G., Casanova, A., Romero, A., Lio, P., and Bengio, Y. (2018). Graph attention networks. In ICLR

    2018

  29. [37]

    Wang, M., Zheng, D., Ye, Z., Gan, Q., Li, M., Song, X., Zhou, J., Ma, C., Yu, L., Gai, Y., et al. (2019). Deep graph library: A graph-centric, highly-performant package for graph neural networks. arXiv preprint arXiv:1909.01315

    2019 arXiv

  30. [38]

    Z., Khabsa, M., Fang, H., and Ma, H

    Wang, S., Li, B. Z., Khabsa, M., Fang, H., and Ma, H. (2020). Linformer: Self-attention with linear complexity. arXiv preprint arXiv:2006.04768

    2020 arXiv

  31. [39]

    Woodruff, D. P. (2014). Sketching as a tool for numerical linear algebra. Found. Trends Theor. Comput. Sci. , 10(1-2):1--157

    2014

  32. [40]

    Wu, F., Souza, A., Zhang, T., Fifty, C., Yu, T., and Weinberger, K. (2019). Simplifying graph convolutional networks. In International conference on machine learning , pages 6861--6871. PMLR

    2019

  33. [41]

    Wu, Q., Yang, C., Zhao, W., He, Y., Wipf, D., and Yan, J. (2023). Difformer: Scalable (graph) transformers induced by energy constrained diffusion. arXiv preprint arXiv:2301.09474

    2023 arXiv

  34. [42]

    P., and Yan, J

    Wu, Q., Zhao, W., Li, Z., Wipf, D. P., and Yan, J. (2022). Nodeformer: A scalable graph structure learning transformer for node classification. NeurIPS , 35:27387--27401

    2022

  35. [43]

    Wu, Q., Zhao, W., Yang, C., Zhang, H., Nie, F., Jiang, H., Bian, Y., and Yan, J. (2024). Simplifying and empowering transformers for large-graph representations. Advances in Neural Information Processing Systems , 36

    2024

  36. [44]

    Ying, C., Cai, T., Luo, S., Zheng, S., Ke, G., He, D., Shen, Y., and Liu, T.-Y. (2021). Do transformers really perform bad for graph representation? ArXiv , abs/2106.05234

    2021 arXiv

  37. [45]

    A., Ainslie, J., Alberti, C., Ontanon, S., Pham, P., Ravula, A., Wang, Q., Yang, L., et al

    Zaheer, M., Guruganesh, G., Dubey, K. A., Ainslie, J., Alberti, C., Ontanon, S., Pham, P., Ravula, A., Wang, Q., Yang, L., et al. (2020). Big bird: Transformers for longer sequences. Advances in neural information processing systems , 33:17283--17297

    2020

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.