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

Jun 20, 2026cs.LG

Early-Exit Graph Neural Networks for Link Prediction

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.

Roman Knyazhitskiy, Andrea Giuseppe Di Francesco

University of Cambridge · Sapienza University of Rome

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

Ask PDF

Apr 28, 2026cs.LG

Mini-Batch Class Composition Bias in Link Prediction

Prior work on node classification has shown that Graph Neural Networks (GNNs) can learn representations that transfer across graphs, when underlying graph properties are shared. For a fixed graph, one would then expect GNNs trained for link prediction to learn a representation consistent with that learnt for node classification. We show this intuition does not hold in the general case. Instead, we find popular link prediction models can learn a trivial mini-batch dependent heuristic, enabled by batch-normalisation layers, to solve the edge classification task. When correcting for this, we observe increased alignment of the network representation with node-class relevant features, suggesting the network has learnt a graph representation that better aligns with the underlying graph's properties. Our findings suggest that standard link prediction training may be leading us to overestimate link predictors' ability to learn a generalised representation of a graph that is consistent across tasks.

Kieran Maguire, Srinandan Dasmahapatra

University of Southampton School of Electronics and Computer Science

Graph Neural Networks Network Science Imbalanced Classification

Ask PDF

Aug 5, 2026cs.SI

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

Predicting the existence and type of links (edges) between nodes in a multi-relational graph is key for applications from social interaction prediction to knowledge relationship identification. Enhancing local features with relevant global information is crucial for accurate link prediction, yet it remains challenging. We address this by modeling the relationship between node pairs as node influence. That is, whether the node influence can be propagated and what type of influence is propagated indicates where and what type the edge is, which will be the most relevant local and global information to predict the edges. To this end, we extend the Susceptible-Infectious-Recovered (SIR) epidemic model to capture the influence propagation of nodes on a large scale through sub-graph structures. Subsequently, these sub-graphs are compressed using virtual edges, thereby substantially reducing the computation associated with utilizing the global graph structure. Finally, we propose the Influential Graph Neural Predictor, referred to as IGNP, a link prediction framework guided by influence propagation. Extensive experiments demonstrate the superiority of the proposed method, which outperforms strong baselines by a large margin on the widely used and real-world datasets.

Zidu Yin, Yuankai Qi, Dong Gong +3

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

Zero-Shot Link Prediction Epidemiological Models

Ask PDF