Plain Transformers are Surprisingly Powerful Link Predictors

Quang Truong; Yu Song; Donald Loveland; Mingxuan Ju; Tong Zhao; Neil Shah; Jiliang Tang

cs.LGFeb 2, 2026

Plain Transformers are Surprisingly Powerful Link Predictors

Authors: Quang Truong, Yu Song, Donald Loveland, Mingxuan Ju, Tong Zhao, Neil Shah, Jiliang Tang

Organizations: Department of Computer Science and Engineering, Michigan State University, East Lansing, MI, USA. · Snap Inc., Bellevue, WA, USA.

Abstract

Link prediction is a core challenge in graph machine learning, demanding models that capture rich and complex topological dependencies. While Graph Neural Networks (GNNs) are the standard solution, state-of-the-art pipelines often rely on explicit structural heuristics or memory-intensive node embeddings -- approaches that struggle to generalize or scale to massive graphs. Emerging Graph Transformers (GTs) offer a potential alternative but often incur significant overhead due to complex structural encodings, hindering their applications to large-scale link prediction. We challenge these sophisticated paradigms with PENCIL, an encoder-only plain Transformer that replaces hand-crafted priors with attention over sampled local subgraphs, retaining the scalability and hardware efficiency of standard Transformers. Through experimental and theoretical analysis, we show that PENCIL extracts richer structural signals than GNNs, implicitly generalizing a broad class of heuristics and subgraph-based expressivity. Empirically, PENCIL outperforms heuristic-informed GNNs and is far more parameter-efficient than ID-embedding--based alternatives, while remaining competitive across diverse benchmarks -- even without node features. Our results challenge the prevailing reliance on complex engineering techniques, demonstrating that simple design choices are potentially sufficient to achieve the same capabilities. Our code is publicly available at https://github.com/quang-truong/pencil.

Figures & tables

Figure 1 : Parameter efficiency vs. performance on ogbl-ppa . PENCIL ( $\bigstar$ $\bigstar$ $\bigstar$ $\bigstar$ $\bigstar$ $\bigstar$ $\bigstar$ $\bigstar$ $\bigstar$ $\bigstar$ $\bigstar$ $\bigstar$ $\bigstar$ $\bigstar$ $\bigstar$ $\bigstar$ $\bigstar$ ) achieves state-of-the-art performance without node IDs or handcrafted heuristics, using orders of magnitude fewer parameters than leading ID-based methods.

Figure 2 : Visualization of the input encoding scheme for a sampled subgraph revolving around a query link (dashed), with the number of nodes $N=5$ and the sampling budget $N_{\max}=6$ . Blue block corresponds to the sampled nodes (the context set). Green block contains one-hot identifiers of nodes, yellow block contains nodes’ adjacency row, purple block contains role flags, and red block contains task tokens. Context-node ordering is permutable; only $v_{\mathrm{src}}$ and $v_{\mathrm{dst}}$ are fixed to $v_{0}$ and $v_{1}$ .

Figure 3 : PENCIL architecture. Node features can be optionally used as discussed in Section 3.2 , but we omit them from the figure for clarity.

Figure 4 : RMSE of PENCIL and other GNNs for estimating pairwise heuristics on the cora dataset.

Type	Model	cora	citeseer	pubmed	ogbl-collab	ogbl-ppa	ogbl-citation2
Type	Model	MRR	MRR	MRR	H@50	H@100	MRR
	SEAL	26.69 ± 5.89	39.36 ± 4.99	38.06 ± 5.18	63.37 ± 0.69	48.80 ± 5.61	86.93 ± 0.43
	Neo-GNN	22.65 ± 2.60	53.97 ± 5.88	31.45 ± 3.17	66.13 ± 0.61	48.45 ± 1.01	83.54 ± 0.32
	BUDDY	26.40 ± 4.40	59.48 ± 8.96	23.98 ± 5.11	64.59 ± 0.46	47.33 ± 1.96	87.86 ± 0.18
	NCN	32.93 ± 3.80	54.97 ± 6.03	35.65 ± 4.60	63.86 ± 0.51	62.63 ± 1.15	89.27 ± 0.05
	NCNC	29.01 ± 3.83	64.03 ± 3.67	25.70 ± 4.48	65.97 ± 1.03	62.61 ± 0.76	89.82 ± 0.43

Table 1 : Results on the original benchmark datasets. N/A means results are not available. Colored results indicate the

1^{\text{st}}

2^{\text{nd}}

, and

3^{\text{rd}}

-best performance in the corresponding metric. Category markers: Heuristic-informed, ID-based, and Heuristic-agnostic + ID-free.

Type	Model	cora	citeseer	pubmed	ogbl-collab	ogbl-ppa	ogbl-ddi	ogbl-citation2
	SEAL	10.67 ± 3.46	13.16 ± 1.66	5.88 ± 0.53	6.43 ± 0.32	29.71 ± 0.71	9.99 ± 0.90	20.60 ± 1.28
	Neo-GNN	13.95 ± 0.39	17.34 ± 0.84	7.74 ± 0.30	5.23 ± 0.90	21.68 ± 1.14	10.86 ± 2.16	16.12 ± 0.25
	BUDDY	13.71 ± 0.59	22.84 ± 0.36	7.56 ± 0.18	5.67 ± 0.36	27.70 ± 0.33	12.43 ± 0.50	19.17 ± 0.20
	NCN	14.66 ± 0.95	28.65 ± 1.21	5.84 ± 0.22	5.09 ± 0.38	35.06 ± 0.26	12.86 ± 0.78	23.35 ± 0.28
	NCNC	14.98 ± 1.00	24.10 ± 0.65	8.58 ± 0.59	4.73 ± 0.86	33.52 ± 0.26	N/A	19.61 ± 0.54
	LPFormer	16.80 ± 0.52	26.34 ± 0.67	9.99 ± 0.52	7.62 ± 0.26	40.25 ± 0.24	13.20 ± 0.54	24.70 ± 0.55

Table 2 : Results under HeaRT. N/A means results are not available. Colored results indicate the

1^{\text{st}}

2^{\text{nd}}

, and

3^{\text{rd}}

-best performance in MRR. Category markers: Heuristic-informed, ID-based, and Heuristic-agnostic + ID-free.

Figure 5 : Effect of model depth on different performance metrics across the cora , pubmed , and ogbl-collab datasets.

Appendix figures & tables17 assets

Supplementary material from the paper’s appendix.

Appendix

Model	COMB	$g$	$k_{\phi}$	AGG	$\psi$	$k_{\rho}$	$m$	$h$
Pure GNN	/	$\odot$	1-WL	/	/	/	/	/
NCN	$\\|$	$\odot$	1-WL	$\sum$	$\rho(i;G,\mathbf{X}^{0})$	1-WL	1	$\mathbf{X}^{0}$
ELPH	$\\|$	$\\|$	1-WL	$\sum$	$\rho(i;G,\mathbf{X}^{1})\cdot\prod_{r=1}^{m}\prod_{d=1}^{m}\mathbbm{1}_{dr}(i)$	1-WL	m	$\mathbf{x}_{i}^{1}=1$
Neo-GNN	$\\|$	$\\|$	1-WL	$\sum$	$b\cdot\rho(i;G,\mathbf{X}^{0})$ with $b=\sum_{r=1}^{m}\sum_{d=1}^{m}(\mathbf{A}^{r})_{uv}\cdot(\mathbf{A}^{d})_{uv}$	1-WL	m	$\mathbf{X}^{0}$
SEAL	/	/	/	$\sum$	$\rho(i;G,\mathbf{X}^{D})$	$1-\|N^{m}(u,v)\|\text{-WL}$	m	$\mathbf{x}_{i}^{D}=\mathbf{x}_{i}^{0}\\|\min_{u,v}(\delta(i,u),\delta(i,v))+1$
PENCIL	/	/	/	$\sum$	$\psi_{\text{end}}\!\big(\rho(i;G,\tilde{\mathbf{X}}),u,v\big)$ with $\psi_{\text{end}}(z_{i},u,v)=\big[\mathbbm{1}(i=u)\,z_{i}\ \\|\ \mathbbm{1}(i=v)\,z_{i}\big]$	$1-\|N^{m}(u,v)\|\text{-WL}$	m	$\tilde{\mathbf{x}}_{i}=\mathbf{r}_{i}$

Appendix

Table 3 : Model formulations expressed within the

k_{\phi}

k_{\rho}

m

framework. A ‘/’ indicates that the corresponding component is not included in the model. Table is extracted from ( Lachi et al., 2025 ) , where PENCIL is our contribution.

Figure 6 : RMSE of PENCIL and other GNNs for estimating pairwise heuristics on the citeseer dataset.

Hyperparameter	GNNs	PENCIL
Sampling Configuration	(2, 20)	(2, 20)
Hidden Size	512	256
Intermediate Size	N/A	512
# Attention Heads	N/A	4
Effective Batch Size	2048	2048
Learning Rate	2.0E-04	2.0E-04

Appendix

Table 4 : Hyperparameter configurations of GNNs and PENCIL for the pairwise heuristic estimation experiments. N/A means the hyperparameter is not applicable.

Hyperparameter	cora	citeseer	pubmed	ogbl-collab	ogbl-ppa	ogbl-citation2
Sampling Configuration	(2, 20)	(2, 20)	(2, 16)	(1, 75)	(1, 150)	(1, 40)
Hidden Size	512	1024	512	512	512	512
Intermediate Size	2048	2048	2048	2048	2048	2048
# Layers	8	2	8	8	4	3
# Attention Heads	8	8	8	8	8	8
Effective Batch Size	2048	2048	4096	8192	16384	65536

Appendix

Table 5 : Hyperparameter configurations of PENCIL for the original benchmark settings.

Hyperparameter	cora	citeseer	pubmed	ogbl-collab	ogbl-ppa	ogbl-citation2	ogbl-ddi
Sampling Configuration	(2, 20)	(2, 20)	(2, 20)	(1, 75)	(1, 150)	(1, 40)	(1, 350)
Hidden Size	512	1024	512	512	512	512	512
Intermediate Size	2048	2048	2048	2048	2048	2048	2048
# Layers	4	2	4	8	4	3	8
# Attention Heads	8	8	8	8	8	8	8
Effective Batch Size	2048	2048	2048	8192	16384	65536	4096

Appendix

Table 6 : Hyperparameter configurations of PENCIL for the HeaRT benchmark settings.

Type	Model	cora	citeseer	pubmed	ogbl-collab	ogbl-ppa	ogbl-citation2
Type	Model	MRR	MRR	MRR	H@50	H@100	MRR
	CN	20.99 ± 0.00	28.34 ± 0.00	14.02 ± 0.00	61.37 ± 0.00	27.65 ± 0.00	74.30 ± 0.00
	AA	31.87 ± 0.00	29.37 ± 0.00	16.66 ± 0.00	64.17 ± 0.00	32.45 ± 0.00	75.96 ± 0.00
	RA	30.79 ± 0.00	27.61 ± 0.00	15.63 ± 0.00	63.81 ± 0.00	49.33 ± 0.00	76.04 ± 0.00
	SEAL	26.69 ± 5.89	39.36 ± 4.99	38.06 ± 5.18	63.37 ± 0.69	48.80 ± 5.61	86.93 ± 0.43
	Neo-GNN	22.65 ± 2.60	53.97 ± 5.88	31.45 ± 3.17	66.13 ± 0.61	48.45 ± 1.01	83.54 ± 0.32

Appendix

Table 7 : Results on the original benchmark datasets. N/A means results are not available. Colored results indicate the

1^{\text{st}}

2^{\text{nd}}

, and

3^{\text{rd}}

-best performance in the corresponding metric. Category markers: Pure Heuristic, Heuristic-informed, ID-based, and Heuristic-agnostic + ID-free.

Type	Model	cora	citeseer	pubmed	ogbl-collab	ogbl-ppa	ogbl-ddi	ogbl-citation2
	CN	9.78 ± 0.00	8.42 ± 0.00	2.28 ± 0.00	4.20 ± 0.00	25.70 ± 0.00	6.71 ± 0.00	17.11 ± 0.00
	AA	11.91 ± 0.00	10.82 ± 0.00	2.63 ± 0.00	5.07 ± 0.00	26.85 ± 0.00	6.97 ± 0.00	17.83 ± 0.00
	RA	11.81 ± 0.00	10.84 ± 0.00	2.47 ± 0.00	6.29 ± 0.00	28.34 ± 0.00	8.70 ± 0.00	17.79 ± 0.00
	SEAL	10.67 ± 3.46	13.16 ± 1.66	5.88 ± 0.53	6.43 ± 0.32	29.71 ± 0.71	9.99 ± 0.90	20.60 ± 1.28
	Neo-GNN	13.95 ± 0.39	17.34 ± 0.84	7.74 ± 0.30	5.23 ± 0.90	21.68 ± 1.14	10.86 ± 2.16	16.12 ± 0.25
	BUDDY	13.71 ± 0.59	22.84 ± 0.36	7.56 ± 0.18	5.67 ± 0.36	27.70 ± 0.33	12.43 ± 0.50	19.17 ± 0.20

Appendix

Table 8 : Results under HeaRT. N/A means results are not available. Colored results indicate the

1^{\text{st}}

2^{\text{nd}}

, and

3^{\text{rd}}

-best performance in MRR. Category markers: Pure Heuristic, Heuristic-informed, ID-based, and Heuristic-agnostic + ID-free.

Model	cora (2, 20)			pubmed (2, 16)			ogbl-collab (1, 75)
Model	MRR	H@3	H@20	MRR	H@3	H@20	H@20	H@50	H@100
PENCIL \MR	34.64 ± 1.99	35.98 ± 3.97	58.67 ± 2.57	21.49 ± 4.30	21.81 ± 2.81	31.81 ± 2.32	49.52 ± 3.01	53.43 ± 1.92	56.04 ± 1.24
PENCIL	42.23 ± 1.98	43.34 ± 1.03	67.32 ± 3.56	38.28 ± 2.59	43.61 ± 1.48	57.49 ± 0.94	53.47 ± 0.85	66.88 ± 0.34	69.75 ± 0.45
Performance Gain	+7.59	+7.36	+8.65	+16.79	+21.80	+25.68	+3.95	+13.45	+13.71

Appendix

Table 9 : Ablation study on Multiplicative Residual (MR).

Figure 7 : MRR averaged over 5 runs on the citeseer , cora , and pubmed datasets using different input embeddings’ initializations.

Model	cora (2, 20)	citeseer (2, 20)	ogbl-collab (1, 75)
Model	MRR	MRR	H@50
PENCIL	$42.23\pm 1.98$	$47.51\pm 3.09$	$66.88\pm 0.34$
PENCIL + LRP-3	39.18	42.17	67.05

Appendix

Table 10 : Effect of using multiple labeled subgraphs. We compare PENCIL with a variant that applies DeepSets-style pooling over three labeled subgraphs per sample. Higher values are better.

Figure 8 : Latent geometry under varying cluster separation $s$ .

Figure 9 : Squared latent-distance distributions for positive and negative intra-/inter-cluster pairs under varying $s$ .

Model	$(s=0,\mu=1)$	$(s=1,\mu=1)$	$(s=2,\mu=1)$	$(s=2,\mu=0)$
CN	1.58	4.78	4.48	4.48
AA	2.85	5.43	7.37	7.37
GCN	75.48	70.08	83.68	40.67
GAT	71.44	81.29	82.11	6.27
PENCIL	77.63	74.37	93.59	36.01

Appendix

Table 11 : Link-prediction performance on latent-space graphs when varying the structural signal

s

while fixing

\mu=1

, with the additional edge case

(s,\mu)=(2,0)

. Reported metric is MRR.

Model	$(s=1,\mu=0)$	$(s=1,\mu=2)$	$(s=1,\mu=8)$	$(s=0,\mu=8)$
CN	4.78	4.78	4.78	1.58
AA	5.43	5.43	5.43	2.85
GCN	10.09	71.04	73.85	77.05
GAT	5.36	83.57	83.04	76.01
PENCIL	17.21	84.90	92.05	95.34

Appendix

Table 12 : Link-prediction performance on latent-space graphs when varying the node-feature signal

\mu

while fixing

s=1

, with the additional edge case

(s,\mu)=(0,8)

. Reported metric is MRR.

Figure 10 : Batching time and memory comparison of Transformers and GNNs on the ogbl-collab dataset.

Model	# Params	ogbl-collab (1, 75)		pubmed (1, 75)
Model	# Params	Training Time Per Batch	Inference Time Per Batch	Training Time Per Batch	Inference Time Per Batch
PENCIL-3L	10.2M	0.019 ± 0.045	0.012 ± 0.039	0.016 ± 0.036	0.010 ± 0.029
PENCIL-8L	27.3M	0.035 ± 0.049	0.020 ± 0.043	0.029 ± 0.038	0.016 ± 0.031
GAT-3L	1.32M	0.021 ± 0.078	0.015 ± 0.070	0.011 ± 0.033	0.007 ± 0.026
GAT-8L	3.95M	0.032 ± 0.079	0.017 ± 0.047	0.020 ± 0.034	0.011 ± 0.027

Appendix

Table 13 : Number of parameters and wall-clock time per mini-batch (seconds; mean

\pm

std) for training and inference of PENCIL and GAT with 3 and 8 layers on ogbl-collab and pubmed under the

(1,75)

sampling configuration. All measurements are collected on the same hardware configuration, using batch size 100, and averaged over 50 batches.

Sampling config	Maximum # nodes	No labeling		DRNL		RWPE		LapPE
Sampling config	Maximum # nodes	Time	Mem.	Time	Mem.	Time	Mem.	Time	Mem.
$(1,20)$	42	0.109	0.07	0.430	0.19	0.161	0.05	0.270	0.07
$(1,30)$	62	0.132	0.05	0.454	0.05	0.184	0.05	0.387	0.11
$(2,20)$	842	1.392	0.07	2.225	0.35	6.980	0.07	6.889	0.24
$(2,30)$	1862	4.155	0.17	5.676	1.10	60.371	0.17	20.846	0.50

Appendix

Table 14 : Subgraph extraction overhead on a

10{,}000

-node graph with average degree

15

. Time is reported in milliseconds and memory is reported in megabytes.

Explore similar work

Early-Exit Graph Neural Networks for Link Prediction
Jun 20, 2026Roman Knyazhitskiy, Andrea Giuseppe Di FrancescoZero-Shot Link Prediction Graph Neural Networks
University of Cambridge · Sapienza University of Rome
Mini-Batch Class Composition Bias in Link Prediction
Apr 28, 2026Kieran Maguire, Srinandan DasmahapatraGraph Neural Networks Network Science
University of Southampton School of Electronics and Computer Science
Link prediction on multi-relational graphs from an influence propagation perspective
Aug 5, 2026Zidu Yin, Yuankai Qi, Dong Gong +3Zero-Shot Link Prediction Epidemiological Models
School of Information Science and Technology, Yunnan Normal University, Kunming, China · School of Computing, Macquarie University, Sydney, Australia · School of Computer Science and Engineering, The University of New South Wales, Sydney, Australia +2

Jun 20, 2026, cs.LGJ/K move · Enter open · S save

Early-Exit Graph Neural Networks for Link Prediction

Roman Knyazhitskiy, Andrea Giuseppe Di Francesco

University of Cambridge · Sapienza University of Rome

Zero-Shot Link Prediction Graph Neural Networks Network Science Neural Network

Open paper AskPDF arXiv

Graph Neural Networks are great for link prediction in various network-like structures; however, the question of their speed/quality tradeoff has been barely studied. While in practice the time it takes to do inference matters little for small benchmarks, the latency does limit applicability in large-scale domains. In this work, we explore early-exiting strategies that can be applied to Graph Neural Networks to solve the problem of link-prediction faster. We use no auxiliary losses to enforce early exiting, allowing it to emerge as an implicit property of the architecture. We show that our method enables early exiting in several setups, moving the Pareto frontier on the HeaRT benchmark for GCN and SAS-GNN backbones. Our findings show that inference speed of GNNs on many link-prediction problems can be improved, while losing little, or even winning in terms of prediction quality. The code is available in our repository: https://github.com/knyazer/link_prediction.

Abstract

Explore similar work

Early-Exit Graph Neural Networks for Link Prediction

Mini-Batch Class Composition Bias in Link Prediction

Link prediction on multi-relational graphs from an influence propagation perspective