Papers › On the Connection Between MPNN and Graph Transformer

On the Connection Between MPNN and Graph Transformer

27 Jan 2023arXiv:2301.11956archive 2025-07-28

Chen Cai, Truong Son Hy, Rose Yu, Yusu Wang

Graph Transformer (GT) recently has emerged as a new paradigm of graph learning algorithms, outperforming the previously popular Message Passing Neural Network (MPNN) on multiple benchmarks. Previous work (Kim et al., 2022) shows that with proper position embedding, GT can approximate MPNN arbitrarily well, implying that GT is at least as powerful as MPNN. In this paper, we study the inverse connection and show that MPNN with virtual node (VN), a commonly used heuristic with little theoretical understanding, is powerful enough to arbitrarily approximate the self-attention layer of GT. In particular, we first show that if we consider one type of linear transformer, the so-called Performer/Linear Transformer (Choromanski et al., 2020; Katharopoulos et al., 2020), then MPNN + VN with only O(1) depth and O(1) width can approximate a self-attention layer in Performer/Linear Transformer. Next, via a connection between MPNN + VN and DeepSets, we prove the MPNN + VN with O(n^d) width and O(1) depth can approximate the self-attention layer arbitrarily well, where d is the input feature dimension. Lastly, under some assumptions, we provide an explicit construction of MPNN + VN with O(1) width and O(n) depth approximating the self-attention layer in GT arbitrarily well. On the empirical side, we demonstrate that 1) MPNN + VN is a surprisingly strong baseline, outperforming GT on the recently proposed Long Range Graph Benchmark (LRGB) dataset, 2) our MPNN + VN improves over early implementation on a wide range of OGB datasets and 3) MPNN + VN outperforms Linear Transformer and MPNN on the climate modeling task.

Paper PDF Code

In Syntology Open this paper in Syntology's Atlas, the map of the papers in Syntology's graph and their citations.

Code

chen-cai-osu/mpnn-gt-connection officialmentioned in paperpytorch report

Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.

Code Syntology ran Syntology

Not run by Syntology. Nothing on this page verifies that the listed code works.

Tasks

Graph Classification Graph Learning Graph Regression Node Classification

Results from the paper archive 2025-07-28

Task	Dataset	Model	Metric	Value	Rank at snapshot	Leaderboard	Report
Graph Classification	Peptides-func	GatedGCN+RWSE+virtual node	AP	0.6685±0.0062	#24 of 44	Archive leaderboard	report
Graph Regression	Peptides-struct	GCN+virtual node	MAE	0.2488±0.0021	#20 of 39	Archive leaderboard	report
Node Classification	PascalVOC-SP	GatedGCN+LapPE+virtual node	macro F1	0.3103±0.0068	#12 of 21	Archive leaderboard	report

Ranks are positions in the archive's leaderboards as they stood at the 2025-07-28 snapshot. Results published since then are not among these rows, so a rank here is not a current standing.

Methods

Absolute Position Encodings Adam Attention BPE Dense Connections Dropout Label Smoothing Layer Normalization Linear Layer MPNN Multi-Head Attention Position-Wise Feed-Forward Layer Residual Connection Softmax Transformer

Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections