NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification

2023/06/14 by Qitian Wu, Wentao Zhao, Wu, Qitian +7 · 24 citations
Computer Science · Engineering · #Advanced Graph Neural Networks #Advanced Memory and Neural Computing #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Ferroelectric and Negative Capacitance Devices #Machine Learning (cs.LG)

paper · pdf · doi:10.48550/arxiv.2306.08385

openalex publication_date 2023/06/14 · openalex created_date 2023/06/17 · openalex updated_date 2026/08/01

Abstract

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 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.

Cited by

• ParaFormer: A Generalized PageRank Graph Transformer for Graph Representation Learning
• Fully Inductive Node Representation Learning via Graph View Transformation
• Solving Oversmoothing in GNNs via Nonlocal Message Passing: Algebraic Smoothing and Depth Scalability
• VS-Graph: Scalable and Efficient Graph Classification Using Hyperdimensional Computing
• Are Graph Transformers Necessary? Efficient Long-Range Message Passing with Fractal Nodes in MPNNs
• Self-Adaptive Graph Mixture of Models
• Generalizable Insights for Graph Transformers in Theory and Practice
• How Particle-System Random Batch Methods Enhance Graph Transformer: Memory Efficiency and Parallel Computing Strategy
• Empowering LLMs with Structural Role Inference for Zero-Shot Graph Learning
• Relieving the Over-Aggregating Effect in Graph Transformers
• An Active Diffusion Neural Network for Graphs
• Unifying and Enhancing Graph Transformers via a Hierarchical Mask Framework
• A Hierarchical Quantized Tokenization Framework for Task-Adaptive Graph Representation Learning
• GraphShaper: Geometry-aware Alignment for Improving Transfer Learning in Text-Attributed Graphs
• GraphTARIF: Linear Graph Transformer with Augmented Rank and Improved Focus
• HeSRN: Representation Learning On Heterogeneous Graphs via Slot-Aware Retentive Network
• Beyond Pairwise Connections: Extracting High-Order Functional Brain Network Structures under Global Constraints
• Exploring the Global-to-Local Attention Scheme in Graph Transformers: An Empirical Study
• Scaling Graph Transformers: A Comparative Study of Sparse and Dense Attention
• MSRFormer: Road Network Representation Learning using Multi-scale Feature Fusion of Heterogeneous Spatial Interactions
• Intellectual Property in Graph-Based Machine Learning as a Service: Attacks and Defenses
• ATLAS: A Self-Supervised and Cross-Stage Netlist Power Model for Fine-Grained Time-Based Layout Power Analysis
• Graph is a Natural Regularization: Revisiting Vector Quantization for Graph Representation Learning
• MPFSR-Enhanced GNNs: Spectral Graph Neural Networks Enhancement Through Learnable Multiple-Parameter Graph Fractional Fourier Transforms

Related

• Rethinking Graph Transformer Architecture Design for Node Classification
• Graph Transformer Networks: Learning Meta-path Graphs to Improve GNNs
• Graph Transformer Networks
• AGFormer: Efficient Graph Representation with Anchor-Graph Transformer
• Scalable Message Passing Neural Networks: No Need for Attention in Large Graph Representation Learning