mlsanityData to 14 Oct 2026

NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification

arXiv 2306.08385 ↗First posted 14 Jun 2023cs.LG cs.AIcited by 210

Not on the map. Why?

Abstract (arXiv)

Graph neural networks have been extensively studied for learning with inter-connected data. Despite this, recent evidence has revealed GNNs' deficiencies related to over-squashing, heterophily, handling long-range dependencies, edge incompleteness and particularly, the absence of graphs altogether. While a plausible solution is to learn new adaptive topology for message passing, issues concerning quadratic complexity hinder simultaneous guarantees for scalability and precision in large networks. In this paper, we introduce a novel all-pair message passing scheme for efficiently propagating node signals between arbitrary nodes, as an important building block for a pioneering Transformer-style network for node classification on large graphs, dubbed as textscNodeFormer. Specifically, the efficient computation is enabled by a kernerlized Gumbel-Softmax operator that reduces the algorithmic complexity to linearity w.r.t. node numbers for learning latent graph structures from large, potentially fully-connected graphs in a differentiable manner. We also provide accompanying theory as justification for our design. Extensive experiments demonstrate the promising efficacy of the method in various tasks including node classification on graphs (with up to 2M nodes) and graph-enhanced applications (e.g., image classification) where input graphs are missing.

Key facts. Cited by 210 papers in the map (data through 14 Oct 2026). Builds on 39 of its 63 references that are in the map. First posted on arXiv 14 Jun 2023.

Builds on

39 of 63 references.

References · 39

  1. 2017Attention Is All You Needcited by 60,361
  2. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  3. 2017Graph Attention Networkscited by 8,923
  4. 2017Inductive Representation Learning on Large Graphscited by 6,320
  5. 2016Categorical Reparameterization with Gumbel-Softmaxcited by 2,739
  6. 2016Matching Networks for One Shot Learningcited by 2,255
  7. 2018Dynamic Graph CNN for Learning on Point Cloudscited by 2,223
  8. 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,163
  9. 2020Rethinking Attention with Performerscited by 1,601
  10. 2019Simplifying Graph Convolutional Networkscited by 1,477
  11. 2016The Concrete Distribution: A Continuous Relaxation of Discrete Random Variablescited by 1,148
  12. 2016Geometric deep learning: going beyond Euclidean datacited by 1,048
27 more
  1. 2020Learning to Simulate Complex Physics with Graph Networkscited by 880
  2. 2018Representation Learning on Graphs with Jumping Knowledge Networkscited by 877
  3. 2020Geom-GCN: Geometric Graph Convolutional Networkscited by 826
  4. 2019DropEdge: Towards Deep Graph Convolutional Networks on Node Classificationcited by 680
  5. 2020A Generalization of Transformer Networks to Graphscited by 661
  6. 2020On the Bottleneck of Graph Neural Networks and its Practical Implicationscited by 631
  7. 2019GraphSAINT: Graph Sampling Based Inductive Learning Methodcited by 618
  8. 2019Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networkscited by 541
  9. 2019MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixingcited by 443
  10. 2020Graph Structure Learning for Robust Graph Neural Networkscited by 371
  11. 2018Graph Convolutional Networks for Text Classificationcited by 345
  12. 2017Few-Shot Learning with Graph Neural Networkscited by 324
  13. 2019Learning Discrete Structures for Graph Neural Networkscited by 231
  14. 2020Iterative Deep Graph Learning for Graph Neural Networks: Better and Robust Node Embeddingscited by 214
  15. 2020GNNGuard: Defending Graph Neural Networks against Adversarial Attackscited by 195
  16. 2020Graph Information Bottleneckcited by 168
  17. 2020Learning to Drop: Robust Graph Neural Network via Topological Denoisingcited by 127
  18. 2020Characteristic Functions on Graphs: Birds of a Feather, from Statistical Descriptors to Parametric Modelscited by 116
  19. 2020Implicit Graph Neural Networkscited by 100
  20. 2015Inferring Networks of Substitutable and Complementary Productscited by 92
  21. 2018Bayesian graph convolutional neural networks for semi-supervised classificationcited by 89
  22. 2021New Benchmarks for Learning on Non-Homophilous Graphscited by 81
  23. 2022Geometric Knowledge Distillation: Topology Compression for Graph Neural Networkscited by 22
  24. 2020Towards Open-World Recommendation: An Inductive Model-based Collaborative Filtering Approachcited by 20
  25. 2021Towards Open-World Feature Extrapolation: An Inductive Graph Learning Approachcited by 20
  26. 2020Fast Graph Attention Networks Using Effective Resistance Based Graph Sparsificationcited by 16
  27. 2019A Quest for Structure: Jointly Learning the Graph Structure and Semi-Supervised Classificationcited by 13

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 31; 2024: 78; 2025: 54; 2026: 47.

210 papers.

Sort:

By area:

  1. 2023GraphGPT: Graph Instruction Tuning for Large Language Modelscited by 226
  2. 2023Language is All a Graph Needscited by 220
  3. 2023Large Language Models on Graphs: A Comprehensive Surveycited by 192
  4. 2024LLaGA: Large Language and Graph Assistantcited by 181
  5. 2024GraphRouter: A Graph-based Router for LLM Selectionscited by 165
  6. 2023SGFormer: Simplifying and Empowering Transformers for Large-Graph Representationscited by 133
  7. 2024Position: Graph Foundation Models are Already Herecited by 86
  8. 2024Graph Mamba: Towards Learning on Graphs with State Space Modelscited by 86
  9. 2024Classic GNNs are Strong Baselines: Reassessing GNNs for Node Classificationcited by 85
  10. 2024A Survey of Large Language Models for Graphscited by 72
  11. 2024Polynormer: Polynomial-Expressive Graph Transformer in Linear Timecited by 65
  12. 2024LLMs as Zero-shot Graph Learners: Alignment of GNN Representations with LLM Token Embeddingscited by 61
38 more
  1. 2024GraphCLIP: Enhancing Transferability in Graph Foundation Models for Text-Attributed Graphscited by 58
  2. 2024Efficient Tuning and Inference for Large Language Models on Textual Graphscited by 54
  3. 2023GSLB: The Graph Structure Learning Benchmarkcited by 50
  4. 2024Hypformer: Exploring Efficient Transformer Fully in Hyperbolic Spacecited by 43
  5. 2024VCR-Graphormer: A Mini-batch Graph Transformer via Virtual Connectionscited by 34
  6. 2024GraphEdit: Large Language Models for Graph Structure Learningcited by 33
  7. 2024Graph Transformers: A Surveycited by 32
  8. 2023OpenGSL: A Comprehensive Benchmark for Graph Structure Learningcited by 30
  9. 2023Exposition on over-squashing problem on GNNs: Current Methods, Benchmarks and Challengescited by 22
  10. 2025LLM as GNN: Graph Vocabulary Learning for Text-Attributed Graph Foundation Modelscited by 22
  11. 2024Contrastive Graph Representation Learning with Adversarial Cross-view Reconstruction and Information Bottleneckcited by 21
  12. 2024Learning Graph Quantized Tokenizerscited by 19
  13. 2023LPFormer: An Adaptive Graph Transformer for Link Predictioncited by 17
  14. 2023GraphGPT: Generative Pre-trained Graph Eulerian Transformercited by 17
  15. 2024Graph Sparsification via Mixture of Graphscited by 17
  16. 2025Beyond Message Passing: Neural Graph Pattern Machinecited by 17
  17. 2023Enhancing Graph Transformers with Hierarchical Distance Structural Encodingcited by 16
  18. 2024DeepRicci: Self-supervised Graph Structure-Feature Co-Refinement for Alleviating Over-squashingcited by 16
  19. 2023Spatiotemporal-Augmented Graph Neural Networks for Human Mobility Simulationcited by 15
  20. 2024Bridging Local Details and Global Context in Text-Attributed Graphscited by 15
  21. 2024DSLR: Diversity Enhancement and Structure Learning for Rehearsal-based Graph Continual Learningcited by 14
  22. 2024What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encodingcited by 14
  23. 2025A Survey of Graph Transformers: Architectures, Theories and Applicationscited by 14
  24. 2024What Can We Learn from State Space Models for Machine Learning on Graphs?cited by 13
  25. 2024Benchmarking Positional Encodings for GNNs and Graph Transformerscited by 13
  26. 2024Even Sparser Graph Transformerscited by 13
  27. 2023GraphGLOW: Universal and Generalizable Structure Learning for Graph Neural Networkscited by 12
  28. 2024Locality-Sensitive Hashing-Based Efficient Point Transformer with Applications in High-Energy Physicscited by 12
  29. 2024Beyond Redundancy: Information-aware Unsupervised Multiplex Graph Structure Learningcited by 12
  30. 2025DeepGate4: Efficient and Effective Representation Learning for Circuit Design at Scalecited by 12
  31. 2025Return of ChebNet: Understanding and Improving an Overlooked GNN on Long Range Taskscited by 12
  32. 2024Gradformer: Graph Transformer with Exponential Decaycited by 11
  33. 2024Towards Dynamic Message Passing on Graphscited by 11
  34. 2023A Hierarchical Spatial Transformer for Massive Point Samples in Continuous Spacecited by 10
  35. 2023Graph Transformers for Large Graphscited by 10
  36. 2024Node Identifiers: Compact, Discrete Representations for Efficient Graph Learningcited by 10
  37. 2023UGSL: A Unified Framework for Benchmarking Graph Structure Learningcited by 9
  38. 2023Latent Graph Inference with Limited Supervisioncited by 9

50 most cited of 210 All 210 (JSON)