Pith. sign in

REVIEW 3 major objections 5 minor 57 references

Even Sparser Graph Transformers

T0 review · 3 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 A narrow graph transformer can be trained first to map the attention edges a wide graph transformer needs, and that map can be used to prune the graph before the expensive model is trained.

desk verdict A genuinely useful two-stage sparsification method whose empirical case is stronger than its theory; the abstract overstates the theoretical backing. read the letter →

arxiv 2411.16278 v1 pith:NI53VVUD submitted 2024-11-25 cs.LG stat.ML

Hamed Shirzad , Honghao Lin , Balaji Venkatachalam , Ameya Velingker , David Woodruff , Danica Sutherland This is my paper · ORCID
classification cs.LGstat.ML
keywords graphtransformerssparseattentionscoreestimationsparsificationexpandergraphstwo-stagetrainingnodeclassificationlarge-scalelearning
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

Graph transformers can model long-range dependencies in graphs, but their memory cost grows with the square of the number of nodes and with every edge they attend over, which blocks them from scaling. This paper tries to establish that a much smaller network can remove that bottleneck: the attention scores learned by a narrow graph transformer are usually close to those of a wide one, so the narrow network can be trained once to find the edges that matter, and the wide network can then be trained on only those edges. The proposed two-stage method, Spexphormer, first trains a width-4 or width-8 network on the full augmented graph, then samples a fixed number of neighbors per node per layer using those learned scores, and trains a wider network on the resulting sparse graph. The paper backs this with an existence proof (a narrow network whose query/key maps are a random projection of the wide network's can match its attention scores up to $\varepsilon$) and a sampling bound (about $O(n\log n/\varepsilon^2)$ edges per layer suffice for spectral approximation), and shows the full procedure runs on graphs with over two million nodes using only a few gigabytes of GPU memory.

What carries the argument

The carrying object is the attention score estimator: a deliberately narrow (width 4 or 8), single-head graph transformer whose only job is to produce per-layer attention scores over a graph augmented with graph edges, expander edges, and self-loops. Two small modifications make its scores more transferable: the value vectors are normalized (with one learnable global scale per head) so that attention scores reflect actual contribution, and the softmax temperature is annealed from 1.0 down to 0.05 to sharpen the scores. The scores are converted into a sparse attention pattern by weighted reservoir sampling, where each node keeps a fixed number of neighbors per layer using weights proportional to the estimated attention scores; resampling each epoch lets the model spread probability across equally informative neighbors. The theoretical engine is the Johnson-Lindenstrauss lemma, used to show that low-dimensional query/key maps can preserve the dot products that determine attention up to $\varepsilon$, together with a matrix-Bernstein analysis of entrywise sampling that gives the $O(n\log n/\varepsilon^2)$ sample bound for spectral approximation.

What would settle it

Train a width-4 and a width-256 network with the same architecture on a graph small enough to run both, and measure the average Jaccard overlap between their top-10 attention neighbors per node; if the overlap is no better than sampling from a uniform distribution, the consistency claim fails. A second check is to compare Spexphormer's accuracy when sparsification uses the narrow network's scores versus the wide network's own scores; a large accuracy gap would mean the estimated scores are not faithful enough for the method's promise.

Watch

Extended reading notes

Core claim

The central claim is that attention scores in graph transformers are stable across different network widths, and that this stability is a usable resource rather than a curiosity. Empirically, the paper measures distributions of attention scores for networks of widths 4 through 64 on two datasets, using energy distance and precision/recall/density/coverage, and finds that even a width-4 network's per-node attention distributions are far closer to a width-64 network's than uniform or random baselines are. Theoretically, the paper proves that for a wide network with bounded hidden-state norms and weight operator norms, there exists a narrow network whose attention scores satisfy $\hat a_{ij}/a_{ij}=1+O(\varepsilon)$ for every edge, with query/key width $d=O(\log n/\varepsilon^2)$; the construction multiplies the wide network's query and key maps by a random Johnson-Lindenstrauss projection. For sparsification, the paper proves that sampling $O(n\log n/\varepsilon^2)$ entries of the attention matrix per layer yields a sparse matrix within $\varepsilon$ spectral norm of the full attention matrix, and that the same guarantee survives when sampling is driven by a narrow network's scores provided those scores do not seriously under-estimate the true ones. The resulting method, Spexphormer, does per-layer weighted reservoir sampling to build a fixed-degree directed attention graph, which makes attention computable with dense batched matrix multiplications and enables memory-controlled batching that preserves task-relevant edges.

Load-bearing premise

The whole procedure relies on a narrow network trained from scratch by gradient descent actually learning attention scores close to those of a much wider network, but the theory only shows that such a narrow network exists, not that training finds it.

Editorial extensions

If this is right

  • Graph transformers can be trained on graphs with millions of nodes within a few gigabytes of GPU memory, since the wide model only ever sees a fixed-degree sparse graph.
  • High-degree expander augmentations become affordable: the cheap estimator can be trained on them, and the final network keeps only the expander edges that actually receive attention.
  • Per-epoch resampling lets the final model hedge among equally informative neighbors, avoiding the brittleness of always keeping only the top-scored edges.
  • The same estimated attention scores can be reused to train several final networks of different widths and depths without retraining the estimator.
  • Because each layer can have its own fixed degree, the model can spend more edges where attention is diffuse (typically the first layer) and fewer where attention is sharp (later layers).

Reading between the lines

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

  • We infer that the estimator's edge sets could be produced once as a preprocessing step for a dataset and then reused by any downstream model, making attention-based sparsification a commodity rather than part of each training run.
  • The theory only proves existence of a narrow network via random projection, so we infer the empirical consistency result is the load-bearing part; a natural stress test is widths far beyond 64, where the paper provides no measurements.
  • We infer that the same width-consistency mechanism may transfer to non-graph token sets whose representations are low-rank or clustered, since the JL argument itself only needs bounded norms and a union bound over pairs.
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

3 major / 5 minor

Summary. The paper proposes Spexphormer, a two-stage procedure for scaling graph transformers. In the first stage, a narrow network (width 4 or 8) is trained on the full augmented graph, and its per-layer attention scores are used to sample a fixed number of neighbors per node via reservoir sampling. In the second stage, a wider network is trained on this sparsified, layer-wise graph. The paper claims, empirically and with theoretical backing, that attention scores are consistent across network widths, and it provides two theoretical results: Theorem E.4, an existence result showing that a network with low-dimensional Q/K projections can approximate the attention scores of a wide network, and Theorem E.5/Proposition E.7, sampling bounds for approximating an attention matrix from sampled entries. Experiments cover twelve medium-sized graphs and three large graphs, with ablations and memory comparisons.

Significance. If the attention-consistency premise holds, Spexphormer offers a practical route to train graph transformers on large graphs with drastically reduced memory: the narrow estimator identifies important edges, and the wide network trains on a sparse pattern with regular degree, enabling efficient dense matrix operations and batching. The paper's strengths include a reproducible open-source implementation, extensive ablations (Table 4, Figures 5-8), a careful comparison against many baselines, and a direct memory-reduction demonstration (Figure 4, Table 3). The theoretical results are clearly stated and the paper is honest about their scope in Section 4.1, noting that the existence theorem does not guarantee that SGD finds the constructed weights. The main weakness is that the central claim, that a trained narrow network's attention scores can stand in for a wide network's, is only partially supported: the theory covers an existence construction, and the empirical study uses distributional metrics on two datasets.

major comments (3)
  1. [§4.1, Theorem E.4] The theoretical result constructs a network whose Q/K weight matrices are random Johnson-Lindenstrauss projections of the wide network's weights, while all other weight matrices remain unchanged; it is an existence result for a partially narrow network, not a statement about the fully narrow width-4/8 estimator trained from scratch by SGD that the method actually uses. The paper explicitly concedes this at the end of Section E.1, but the abstract's phrase 'with theoretical backing' is not supported by this theorem. This gap is load-bearing because the two-stage procedure's first stage must produce reliable attention scores from a narrow network trained via gradient descent, and no argument links the trained estimator to the constructed solution.
  2. [§E.2, Proposition E.7] The sampling guarantee depends on the per-entry condition |A'_ij| >= |A_ij|/alpha for every edge, a condition that is neither proved for trained narrow networks nor verified empirically. The experiments in Section 5.1 measure distributional distances (energy distance, PRDC) across per-node attention distributions; these metrics can be small even when the two networks disagree on which specific edges receive high attention, which is precisely the information used for sparsification. The ablation in Table 4 shows that attention-based sampling beats uniform sampling, but this does not quantify the per-entry condition. Please either add a direct edge-level agreement metric (e.g., overlap of top-k edges) or explicitly frame the sampling bound as conditional on an unverified assumption.
  3. [§5.1 / §5.2] The empirical evidence for the core attention-consistency claim is limited to two small datasets (Actor and Photo) with 100 runs each, measuring distributional similarity rather than the edge-level agreement that the sparsification step requires. While the competitive results on twelve medium and three large graphs in Section 5.2 and the ablation in Table 4 are encouraging, they do not directly establish that narrow and wide networks rank edges similarly. A direct comparison of top-k edge sets between narrow and wide networks, or additional attention-consistency measurements on at least one larger or heterophilic dataset, would substantially strengthen the paper's central claim.
minor comments (5)
  1. [Appendix F.1] The energy distance formula is written as 2E[X − Y] − E[X − X′] − E[Y − Y′]; the absolute value signs are missing and should read 2E[|X − Y|] − E[|X − X′|] − E[|Y − Y′|].
  2. [Algorithm 1] The input notation 'a(ℓ) i,NH (i)' is difficult to parse; please define it explicitly as the vector of attention scores from node i to all neighbors in layer ℓ.
  3. [Figure 4] The caption should clarify that the memory value for Exphormer with degree 30 on ogbn-arxiv is a lower bound, since the configuration could not fit into the 40GB GPU device.
  4. [Appendix G] There is a typo: 'Unline' should be 'Unlike' in the last sentence of the first paragraph.
  5. [Section 3] The attention equation uses 'Ej ⊙ Kj' without defining the shapes or the intended element-wise product; please specify the dimensions of Ej and Kj and clarify the operation.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the core transfer claim rests on independent experiments, and the theory is stated as existence and sampling bounds with explicit assumptions.

full rationale

The paper's two-stage procedure trains a narrow network and then uses its attention scores to sparsify before training a wider network; the wide network's scores are never used as training targets for the narrow network, so no prediction is fitted by construction. Theorem E.4 is an existence result: it constructs cW_Q and cW_K as JL projections of the wide network's weights ("we can define cW_Q = M_QK W_Q and cW_K = M_QK W_K") and the authors explicitly concede that "this does not mean that training with a gradient-based algorithm will necessarily lead to the introduced weights." The practical claim is therefore supported by the independent experiments in Section 5.1 (energy distance and PRDC on Actor and Photo), not by the theorem alone. Proposition E.7 is an explicit conditional bound: it assumes |A'_ij| >= (1/alpha)|A_ij| and does not claim this holds automatically for a trained narrow network. The only self-citations (Shirzad et al. 2023 for Exphormer background and Shirzad et al. 2024 for further compressibility scenarios) are not load-bearing: the paper states "This is an existence claim; we will justify experimentally that in practice, training a narrow network does approximate attention scores well," and then supplies that experimental justification. No equation in the paper reduces to its own input by definition, and no fitted parameter is renamed as a prediction. The identified gaps are correctness risks about the link between existence and trained optimization, not circularity.

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

The method relies on hyperparameters chosen by hand (temperature schedule, sampling degrees, expander degree) and on theoretical assumptions about norm bounds and the attention matrix structure. No new physical entities or unfalsifiable constructs are introduced. The most fragile assumption is that the trained narrow network's attention scores satisfy the no-underestimation condition, which is not verified.

free parameters (4)
  • V-normalization scale s = learned
    Introduced in Section 4 to preserve performance when normalizing V; a learnable global scale.
  • Temperature schedule (lambda, gamma) = lambda=5, gamma=0.95 or 0.99
    Annealing parameters chosen by hand in Section 4 to sharpen attention scores.
  • Per-layer sampling degree deg_l = varies per dataset/layer, e.g., [5,5,5,5], [12,5,5,5]
    Chosen per dataset and layer in Tables 7-9; controls sparsity, tuned on validation.
  • Expander degree = 30 to 200 for estimator
    Higher than Exphormer's 6; chosen to enlarge receptive field before sparsification.
assumptions (4)
  • standard math JLT lemma: for d=O(log n / eps^2), there is a random projection preserving dot products up to eps.
    Used in Theorem E.4 to construct narrow Q/K matrices.
  • domain assumption Bounded norm assumptions: for all layers and nodes, ||h||_2 <= sqrt(alpha) and operator norms ||W|| <= beta.
    Assumed in Section E.1; justified by layer norm and init, not proven during training.
  • domain assumption Attention matrix A satisfies row-stochastic, max column sum K, and column sparsity ell.
    Conditions of Theorem E.5; not verified empirically.
  • ad hoc to paper No serious underestimation: A'_ij >= A_ij / alpha for a large constant alpha.
    Proposition E.7 relies on this assumption to bound sampling with estimated scores; no evidence provided.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Even Sparser Graph Transformers." pith.science (2026). https://pith.science/paper/NI53VVUD

@misc{pith2026241116278,
  author       = {Pith},
  title        = {Pith review of: Even Sparser Graph Transformers},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NI53VVUD}},
  note         = {Machine review of arXiv:2411.16278}
}
read the original abstract

Graph Transformers excel in long-range dependency modeling, but generally require quadratic memory complexity in the number of nodes in an input graph, and hence have trouble scaling to large graphs. Sparse attention variants such as Exphormer can help, but may require high-degree augmentations to the input graph for good performance, and do not attempt to sparsify an already-dense input graph. As the learned attention mechanisms tend to use few of these edges, such high-degree connections may be unnecessary. We show (empirically and with theoretical backing) that attention scores on graphs are usually quite consistent across network widths, and use this observation to propose a two-stage procedure, which we call Spexphormer: first, train a narrow network on the full augmented graph. Next, use only the active connections to train a wider network on a much sparser graph. We establish theoretical conditions when a narrow network's attention scores can match those of a wide network, and show that Spexphormer achieves good performance with drastically reduced memory requirements on various graph datasets.

Figures

Figures reproduced from arXiv: 2411.16278 by the authors.

Figure 1
Figure 1. Figure (a) shows a very simple synthetic graph where each node has a binary classification task of determining whether there exists a node of the opposite color in the same connected component. This task requires learning long-range dependencies. Figure (b) shows a natural clustering of the graph. This clustering would mean no node can do its task if models are trained only on one cluster at a time. Figure (c) shows… view at source ↗
Figure 2
Figure 2. Steps of our method. (a) The attention mechanism for the attention score estimator network combines graph edges with an expander graph and self-loops. The expander graphs are constructed by combining a small number of Hamiltonian cycles – here two, in red and in purple – then confirming the spectral gap is large enough. (b) Self-attention layers in the estimator network use this sparse attention mechanism; its self-… view at source ↗
Figure 3
Figure 3. Energy distance between the attention scores of various networks to a network of width 64. “Uniform” refers to the baseline placing equal scores to each neighbor, while “random” refers to the baseline with uniformly distributed logits. The remaining bars refer to networks trained on the appropriately labeled width. We ran this experiment in two scenarios: first, with just graph edges, and then, by adding expander an… view at source ↗
Figures from the paper (19 more)
Figure 4
Figure 4. Figure 4: Memory usage comparison: Attention Score Estimator network and Spexphormer vs. Exphormer with expander degrees 6 and 30. Exphormer with de￾gree 30 for the ogbn-arxiv dataset could not fit into the memory of a 40GB GPU device, and thus the number here is a lower bound. …
Figure 5
Figure 5. Figure 5: The memory and runtime trade-off for the ogbn-proteins and ogbn-arxiv datasets. The plot demon￾strates that memory and time can be effectively exchanged in our approach. The reported runtime includes the whole process of preprocessing the batches, train, and validation…
Figure 6
Figure 6. Figure 6: The neighborhood expansion of the graph is analyzed to determine the number of nodes required in each layer to obtain representations for 10 nodes in the final layer. This is compared between Spexphormer’s degree-based sampling and full-neighborhood selection. The shad…
Figure 7
Figure 7. Figure 7: The memory and runtime comparison between our model and the GCN demonstrates that our model, with sparsification, significantly outperforms even a very simple GCN model on a forward pass. C.4 Accuracy, Memory, and Runtime with Sampling Degree For four datasets—Tolokers…
Figure 8
Figure 8. Figure 8: AUC and accuracy results, along with memory and runtime analysis, are presented for four datasets: two homophilic datasets (Amazon-Photo and Coauthor-CS) and two heterophilic datasets (Tolokers and Minesweeper). Larger sampling degrees generally lead to better results;…
Figure 9
Figure 9. Figure 9: Pairwise energy distance across networks with different hidden dimensions, uniform distribution, and randomly generated attention scores. For all these metrics, we first consider the distribution of attention scores for each individual node’s neighborhood in a single l…
Figure 10
Figure 10. Figure 10: Pairwise energy distance between networks with different hidden dimensions, uniform distribution, and random attention scores for the Actor dataset, without the expander graph, on individual layers. This dataset has a very low average degree and it appears that almost…
Figure 11
Figure 11. Figure 11: Pairwise energy distance between networks with different hidden dimensions, uniform distribution, and random attention scores for the Actor dataset, with the expander graph, on individual layers. suggests that for sampling, larger neighborhood sizes may be needed in t…
Figure 12
Figure 12. Figure 12: Pairwise energy distance between networks with different hidden dimensions, uniform distribution, and random attention scores for the Amazon-Photo dataset, without the expander graph, on individual layers.  Insight 3 The attention scores in the layers after the first…
Figure 13
Figure 13. Figure 13: Pairwise energy distance between networks with different hidden dimensions, uniform distribution, and random attention scores for the Amazon-Photo dataset, with the expander graph, on individual layers. F.6 Top-k Attention Sum Another way to assess the sharpness of th…
Figure 14
Figure 14. Figure 14: Average entropy of attention scores for nodes across different layers. F.7 Attention Scores by Edge Type An interesting question is to examine the ratio of attention scores coming from graph edges versus expander edges and self-loops [PITH_FULL_IMAGE:figures/full_fig…
Figure 15
Figure 15. Figure 15: Inter-layer energy distances (×100) for different hidden dimensions. allowing the model to decide the subset of edges that suit the task better — only graph edges, only expander edges or a combination of both. Short-range Vs. Long-range Dependencies If the neighboring…
Figure 16
Figure 16. Figure 16: Violin plots of Precision, Recall, Density, and Coverage metrics for the Actor dataset without expander graphs. 4 8 16 32 uniform random 0.0 0.2 0.4 0.6 0.8 1.0 Precision 4 8 16 32 uniform random 0.0 0.2 0.4 0.6 0.8 1.0 Recall 4 8 16 32 uniform random 0 2 4 6 8 Densit…
Figure 17
Figure 17. Figure 17: Violin plots of Precision, Recall, Density, and Coverage metrics for the Actor dataset with expander graphs. 35 [PITH_FULL_IMAGE:figures/full_fig_p035_17.png]
Figure 18
Figure 18. Figure 18: Violin plots of Precision, Recall, Density, and Coverage metrics for the Amazon-Photo dataset without expander graphs. 4 8 16 32 uniform random 0.00 0.25 0.50 0.75 1.00 Precision 4 8 16 32 uniform random 0.0 0.2 0.4 0.6 0.8 1.0 Recall 4 8 16 32 uniform random 0 1 2 3 …
Figure 19
Figure 19. Figure 19: Violin plots of Precision, Recall, Density, and Coverage metrics for the Amazon-Photo dataset with expander graphs. 36 [PITH_FULL_IMAGE:figures/full_fig_p036_19.png]
Figure 20
Figure 20. Figure 20: Top-k attention scores sum for k values between 1 to 10. 4 8 16 32 64 Hidden Dimension 0.0 0.2 0.4 0.6 0.8 1.0 Ratio Amazon-Photo Dataset 4 8 16 32 64 Hidden Dimension Actor Dataset Ratio of Attention Scores by Edge Type Graph Edges Expander Edges Self-loops [PITH_FU…
Figure 21
Figure 21. Figure 21: Average sum of attention scores for different edge types—graph edges, expander edges, and self￾loops—per node neighborhood. The total sum of attention scores per node is one. 37 [PITH_FULL_IMAGE:figures/full_fig_p037_21.png]
Figure 22
Figure 22. Figure 22: Average attention scores for different edge types across two datasets and for different hidden dimensions. designed specifically for some of these tasks may have the advantage of reduced complexity. But our approach lets learning without concern about the nature of th…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

57 extracted references · 29 canonical work pages

  1. [1]

    Abadi, M., Agarwal, A., Barham, P., Brevdo, E., Chen, Z., Citro, C., Corrado, G. S., Davis, A., Dean, J., Devin, M., Ghemawat, S., Goodfellow, I., Harp, A., Irving, G., Isard, M., Jia, Y., Jozefowicz, R., Kaiser, L., Kudlur, M., Levenberg, J., Man\' e , D., Monga, R., Moore, S., Murray, D., Olah, C., Schuster, M., Shlens, J., Steiner, B., Sutskever, I., T...

    2015

  2. [2]

    S., and Liberty, E

    Achlioptas, D., Karnin, Z. S., and Liberty, E. (2013). Near-optimal entrywise sampling for data matrices. Advances in Neural Information Processing Systems , 26

    work page 2013

  3. [3]

    Chen, J., Gao, K., Li, G., and He, K. (2022a). Nagphormer: Neighborhood aggregation graph transformer for node classification in large graphs. CoRR , abs/2206.04910

    arXiv 2022

  4. [4]

    Chen, Y., Zeng, Q., Hakkani - Tur, D., Jin, D., Ji, H., and Yang, Y. (2022b). Sketching as a tool for understanding and accelerating self-attention for long sequences. In Carpuat, M., de Marneffe, M., and Ru \' z, I. V. M., editors, Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Lan...

    work page 2022

  5. [5]

    M., Likhosherstov, V., Dohan, D., Song, X., Gane, A., Sarl \' o s, T., Hawkins, P., Davis, J

    Choromanski, K. M., Likhosherstov, V., Dohan, D., Song, X., Gane, A., Sarl \' o s, T., Hawkins, P., Davis, J. Q., Mohiuddin, A., Kaiser, L., Belanger, D. B., Colwell, L. J., and Weller, A. (2021). Rethinking attention with performers. In ICLR

    work page 2021

  6. [6]

    Cram \'e r, H. (1928). On the composition of elementary errors: First paper: Mathematical deductions. Scandinavian Actuarial Journal , 1928(1):13--74

    work page 1928

  7. [7]

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

    arXiv 2024

  8. [8]

    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

Show all 57 references
  1. [9]

    Di Giovanni, F., Giusti, L., Barbero, F., Luise, G., Lio, P., and Bronstein, M. M. (2023a). On over-squashing in message passing neural networks: The impact of width, depth, and topology. In International Conference on Machine Learning , pages 7865--7885. PMLR

    2023

  2. [10]

    K., Bronstein, M

    Di Giovanni, F., Rusch, T. K., Bronstein, M. M., Deac, A., Lackenby, M., Mishra, S., and Veli c kovi \'c , P. (2023b). How does over-squashing affect the power of gnns? arXiv preprint arXiv:2306.03589

    2023 arXiv

  3. [11]

    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

    2020 arXiv

  4. [12]

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

    2020 arXiv

  5. [13]

    Efraimidis, P. S. and Spirakis, P. G. (2006). Weighted random sampling with a reservoir. Information processing letters , 97(5):181--185

    2006

  6. [14]

    \.I ., Bronstein, M., and Levie, R

    Finkelshtein, B., Ceylan, \.I . \.I ., Bronstein, M., and Levie, R. (2024). Learning on large graphs using intersecting communities. arXiv preprint arXiv:2405.20724

    2024 arXiv

  7. [15]

    J., Morris, C., Velingker, A., and Geerts, F

    Franks, B. J., Morris, C., Velingker, A., and Geerts, F. (2024). Weisfeiler-leman at the margin: When more expressivity matters. arXiv preprint arXiv:2402.07568

    2024 arXiv

  8. [16]

    Frasca, F., Rossi, E., Eynard, D., Chamberlain, B., Bronstein, M., and Monti, F. (2020). Sign: Scalable inception graph neural networks. arXiv preprint arXiv:2004.11198

    2020 arXiv

  9. [17]

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

    2017

  10. [18]

    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

  11. [19]

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

    1984

  12. [20]

    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

  13. [21]

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

    2016 arXiv

  14. [22]

    B., and Goldstein, T

    Kong, K., Chen, J., Kirchenbauer, J., Ni, R., Bruss, C. B., and Goldstein, T. (2023). Goat: A global transformer on large-scale graphs. In International Conference on Machine Learning , pages 17375--17390. PMLR

    2023

  15. [23]

    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

  16. [24]

    Li, X., Zhu, R., Cheng, Y., Shan, C., Luo, S., Li, D., and Qian, W. (2022). Finding global homophily in graph neural networks when meeting heterophily. In International Conference on Machine Learning , pages 13242--13256. PMLR

    2022

  17. [25]

    L., Gupta, V., Bhalerao, O., and Lim, S

    Lim, D., Hohne, F., Li, X., Huang, S. L., Gupta, V., Bhalerao, O., and Lim, S. N. (2021). Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods. Advances in Neural Information Processing Systems , 34:20887--20902

    2021

  18. [26]

    Liu, X., Yan, M., Deng, L., Li, G., Ye, X., and Fan, D. (2021). Sampling methods for efficient training of graph convolutional networks: A survey. IEEE/CAA Journal of Automatica Sinica , 9(2):205--234

    2021

  19. [27]

    and Cangea, C

    Mernyei, P. and Cangea, C. (2020). Wiki-cs: A wikipedia-based benchmark for graph neural networks. arXiv preprint arXiv:2007.02901

    2020 arXiv

  20. [28]

    Mialon, G., Chen, D., Selosse, M., and Mairal, J. (2021). Graphit: Encoding graph structure in transformers. CoRR , abs/2106.05667

    2021 arXiv

  21. [29]

    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

  22. [30]

    F., Oh, S

    Naeem, M. F., Oh, S. J., Uh, Y., Choi, Y., and Yoo, J. (2020). Reliable fidelity and diversity metrics for generative models. In International Conference on Machine Learning , pages 7176--7185. PMLR

    2020

  23. [31]

    Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., et al. (2019). Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems , 32

    2019

  24. [32]

    C.-C., Lei, Y., and Yang, B

    Pei, H., Wei, B., Chang, K. C.-C., Lei, Y., and Yang, B. (2020). Geom-gcn: Geometric graph convolutional networks. arXiv preprint arXiv:2002.05287

    2020 arXiv

  25. [33]

    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

  26. [34]

    Prabhu, A., Varma, G., and Namboodiri, A. M. (2018). Deep expander networks: Efficient deep networks from graph theory. In Ferrari, V., Hebert, M., Sminchisescu, C., and Weiss, Y., editors, Computer Vision - ECCV 2018 - 15th European Conference, Munich, Germany, September 8-14...

    2018

  27. [35]

    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

  28. [36]

    Rizzo, M. L. and Sz \'e kely, G. J. (2016). Energy distance. wiley interdisciplinary reviews: Computational statistics , 8(1):27--38

    2016

  29. [37]

    K., Bronstein, M

    Rusch, T. K., Bronstein, M. M., and Mishra, S. (2023). A survey on oversmoothing in graph neural networks. arXiv preprint arXiv:2303.10993

    2023 arXiv

  30. [38]

    S., Bachem, O., Lucic, M., Bousquet, O., and Gelly, S

    Sajjadi, M. S., Bachem, O., Lucic, M., Bousquet, O., and Gelly, S. (2018). Assessing generative models via precision and recall. Advances in neural information processing systems , 31

    2018

  31. [39]

    Sejdinovic, D., Sriperumbudur, B., Gretton, A., and Fukumizu, K. (2013). Equivalence of distance-based and RKHS -based statistics in hypothesis testing. The Annals of Statistics , 41(5):2263 -- 2291

    2013

  32. [40]

    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

  33. [41]

    P., and Sutherland, D

    Shirzad, H., Lin, H., Venkatachalam, B., Velingker, A., Woodruff, D. P., and Sutherland, D. J. (2024). A theory for compressibility of graph transformers for transductive learning. In Machine Learning and Compression Workshop at NeurIPS . arXiv preprint arXiv:2411.13028

    2024 arXiv

  34. [42]

    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

  35. [43]

    Székely, G. J. and Rizzo, M. L. (2013). Energy statistics: A class of statistics based on distances. Journal of Statistical Planning and Inference , 143(8):1249--1272

    2013

  36. [44]

    and Zabovsky, M

    Takac, L. and Zabovsky, M. (2012). Data analysis in public social networks. In International scientific conference and international workshop present day trends of innovations , volume 1

    2012

  37. [45]

    Tay, Y., Dehghani, M., Bahri, D., and Metzler, D. (2020). Efficient transformers: A survey. arXiv preprint arXiv:2009.06732

    2020 arXiv

  38. [46]

    P., Dong, X., and Bronstein, M

    Topping, J., Di Giovanni, F., Chamberlain, B. P., Dong, X., and Bronstein, M. M. (2021). Understanding over-squashing and bottlenecks on graphs via curvature. arXiv preprint arXiv:2111.14522

    2021 arXiv

  39. [47]

    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

  40. [48]

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

    2018

  41. [49]

    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

  42. [50]

    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

  43. [51]

    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

  44. [52]

    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

  45. [53]

    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

  46. [54]

    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

  47. [55]

    Zeng, H., Zhou, H., Srivastava, A., Kannan, R., and Prasanna, V. K. (2020). Graphsaint: Graph sampling based inductive learning method. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020 . OpenReview.net

    2020

  48. [56]

    Zhang, J., Zhang, H., Xia, C., and Sun, L. (2020). Graph- B ert: Only attention is needed for learning graph representations. arXiv preprint arXiv:2001.05140

    2020 arXiv

  49. [57]

    Zhao, J., Li, C., Wen, Q., Wang, Y., Liu, Y., Sun, H., Xie, X., and Ye, Y. (2021). Gophormer: Ego-graph transformer for node classification. CoRR , abs/2110.13094

    2021 arXiv

Pith tools

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