Cover Image

SGFormer: Single-Layer Graph Transformers with Approximation-Free Linear Complexity

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Wu, Qitian, Yang, Kai, Zhang, Hengrui, Wipf, David, Yan, Junchi
Format:	Preprint
Published:	2024
Subjects:	Machine Learning Artificial Intelligence
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Handling Distribution Shifts on Graphs: An Invariance Perspective
by: Wu, Qitian, et al.
Published: (2022)

SGFormer: Simplifying and Empowering Transformers for Large-Graph Representations
by: Wu, Qitian, et al.
Published: (2023)

Transformers from Diffusion: A Unified Framework for Neural Message Passing
by: Wu, Qitian, et al.
Published: (2024)

Learning Divergence Fields for Shift-Robust Graph Representations
by: Wu, Qitian, et al.
Published: (2024)

Supercharging Graph Transformers with Advective Diffusion
by: Wu, Qitian, et al.
Published: (2023)

How Graph Neural Networks Learn: Lessons from Training Dynamics
by: Yang, Chenxiao, et al.
Published: (2023)

PAINET: A Principled Efficient Transformer for 3D Dynamics Modeling
by: Yang, Kai, et al.
Published: (2025)

Universal Approximation Theorem for a Single-Layer Transformer
by: Gumaan, Esmail
Published: (2025)

Molecule Generation for Drug Design: a Graph Learning Perspective
by: Yang, Nianzu, et al.
Published: (2022)

Learning to Solve Combinatorial Optimization under Positive Linear Constraints via Non-Autoregressive Neural Networks
by: Wang, Runzhong, et al.
Published: (2024)

On the Emergence of Cross-Task Linearity in the Pretraining-Finetuning Paradigm
by: Zhou, Zhanpeng, et al.
Published: (2024)

Multi-Layer Transformers Gradient Can be Approximated in Almost Linear Time
by: Liang, Yingyu, et al.
Published: (2024)

Griffin: Towards a Graph-Centric Relational Database Foundation Model
by: Wang, Yanbo, et al.
Published: (2025)

Polynormer: Polynomial-Expressive Graph Transformer in Linear Time
by: Deng, Chenhui, et al.
Published: (2024)

Computing Approximate Graph Edit Distance via Optimal Transport
by: Cheng, Qihao, et al.
Published: (2024)

On the Learning Dynamics of Two-layer Linear Networks with Label Noise SGD
by: Zhang, Tongcheng, et al.
Published: (2026)

GSINA: Improving Subgraph Extraction for Graph Invariant Learning via Graph Sinkhorn Attention
by: Yan, Junchi, et al.
Published: (2024)

Reasoning Is Not Free: Robust Adaptive Cost-Efficient Routing for LLM-as-a-Judge
by: Zhang, Wenbo, et al.
Published: (2026)

Decentralized Transformers with Centralized Aggregation are Sample-Efficient Multi-Agent World Models
by: Zhang, Yang, et al.
Published: (2024)

Sparse Autoencoders, Again?
by: Lu, Yin, et al.
Published: (2025)

AGaLiTe: Approximate Gated Linear Transformers for Online Reinforcement Learning
by: Pramanik, Subhojeet, et al.
Published: (2023)

Conservative Distributional Reinforcement Learning with Safety Constraints
by: Zhang, Hengrui, et al.
Published: (2022)

Misspecified $Q$-Learning with Sparse Linear Function Approximation: Tight Bounds on Approximation Error
by: Du, Ally Yalei, et al.
Published: (2024)

The Sharpness Disparity Principle in Transformers for Accelerating Language Model Pre-Training
by: Wang, Jinbo, et al.
Published: (2025)

Graph Out-of-Distribution Generalization via Causal Intervention
by: Wu, Qitian, et al.
Published: (2024)

Scalable Production Scheduling: Linear Complexity via Unified Homogeneous Graphs
by: Hoss, Jonathan, et al.
Published: (2026)

ZeroS: Zero-Sum Linear Attention for Efficient Transformers
by: Lu, Jiecheng, et al.
Published: (2026)

Refined Edge Usage of Graph Neural Networks for Edge Prediction
by: Jin, Jiarui, et al.
Published: (2022)

Towards Comprehensive and Prerequisite-Free Explainer for Graph Neural Networks
by: Zhang, Han, et al.
Published: (2025)

Dynamic Layer Tying for Parameter-Efficient Transformers
by: Hay, Tamir David, et al.
Published: (2024)

RDBLearn: Simple In-Context Prediction Over Relational Databases
by: Zhang, Yanlin, et al.
Published: (2026)

No Need to Train Your RDB Foundation Model
by: Xu, Linjie, et al.
Published: (2026)

Ginger: An Efficient Curvature Approximation with Linear Complexity for General Neural Networks
by: Hao, Yongchang, et al.
Published: (2024)

Attention Dispersion in Dynamic Graph Transformers: Diagnosis and a Transferable Fix
by: Zhang, Jinhao, et al.
Published: (2026)

Learning to Approximate Adaptive Kernel Convolution on Graphs
by: Sim, Jaeyoon, et al.
Published: (2024)

Uncertainty-Aware Reward-Free Exploration with General Function Approximation
by: Zhang, Junkai, et al.
Published: (2024)

Layer Embedding Deep Fusion Graph Neural Network
by: Xu, Taihua, et al.
Published: (2026)

Graph Tokenization for Bridging Graphs and Transformers
by: Guo, Zeyuan, et al.
Published: (2026)

Reduce Computational Complexity for Convolutional Layers by Skipping Zeros
by: Zhang, Zhiyi, et al.
Published: (2023)

Unbiased Online Curvature Approximation for Regularized Graph Continual Learning
by: Yin, Jie, et al.
Published: (2025)