NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification

By Qitian Wu, Wentao Zhao, Zenan Li, David Paul Wipf, Junchi Yan. Neural Information Processing Systems, 2023

429 citations recorded by the source corpus.

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 \textsc{NodeFormer}. 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.

Subfields: Artificial Intelligence, Electrical and Electronic Engineering

View Paper: https://www.semanticscholar.org/paper/01de6d0c00e7e77050a90945246b2b4acde497a2

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Heng Ji
2. Jiawei Han
3. Meng Jiang
4. Bowen Jin
5. Shuyuan Xu
6. Chi Han
7. Ruosong Ye
8. Yunhao Zhang

In Electrical and Electronic Engineering

1. Jiawei Han
2. Yunhao Zhang
3. Junchi Yan

Citations in the corpus

• GraphGPT: Graph Instruction Tuning for Large Language Models (2023, neutral): “The publications are categorized into Experimental induced diabetes, Type 1 diabetes, and Type 2 diabetes.”
• Language is All a Graph Needs (2023, methodology): “We also include the three most outstanding Transformer-based graph learners under this dataset setting, i.e., ANS-GT, NodeFormer and SGFormer (Zhang et al., 2022b; Wu et al., 2022, 2023).”
• Large Language Models on Graphs: A Comprehensive Survey (2023, background): “They integrate the inductive biases of graphs into the model by positional encoding, structural encoding, the combination of message-passing layers with attention layers [142], or improving the efficiency of attention on large graphs [144].”
• Crossformer: Transformer Utilizing Cross-Dimension Dependency for Multivariate Time Series Forecasting (2023, background): “Recent sparse and efficient Graph Transformers (Wu et al., 2022) can benefit our TSA layer on this problem.”