Degraded but Not Entirely Ineffective: PE-Based Deformable Graph Neural Networks

Jinhua Wu; Xinliang Zhang

cs.AISep 12, 2026

Degraded but Not Entirely Ineffective: PE-Based Deformable Graph Neural Networks

Authors: Jinhua Wu, Xinliang Zhang

Organizations: Henan Polytechnic University, Jiaozuo, 454000, Henan, China

Abstract

Many real-world scenarios can be represented using graph-structured data. However, traditional GNNs that transmit messages based on first-order neighbors have long faced several fundamental contradictions: increasing depth leads to over-smoothing, long-range dependencies cause over-compression, fixed neighborhoods restrict the receptive field, and on heterophilous graphs, topological neighbors become a source of noise. Although many works have addressed these issues individually, few mechanisms can simultaneously alleviate all of these challenges. To address the aforementioned problems, we propose a Position Encoding-Based Deformable Spatial Aggregation Module (PEBDSAM) that solves them all in one step. Specifically, we utilize a deformable mechanism in the position space to identify relevant nodes to supplement the original first-order neighbor information of GNNs, allowing traditional GNNs to adapt to heterophilous scenarios. Through diagnostic experiments, we obtained several major findings: current offsets fail to have any effect; subsequently, we analyzed the causes of offset failure and why model performance still improves even after offset failure, pointing out future research directions. Based on these diagnostic experiments, we streamlined the original PEBDSAM, resulting in a simplified version, which we call the Position Encoding-Based Spatial Aggregation Module (PEBSAM). In addition, we propose a PEBSAM-Speed to adapt to large datasets. Finally, we designed the module to be plug-and-play and applied it to GCN, GAT, GIN, and GraphSAGE, achieving desirable results on three homophilous datasets and six heterophilous graph datasets.

Figures & tables

Figure 5: Trends of OffsetAbsMean across two layers of the model with varying training epochs

$M$	1	4	8
Accuracy (%)	$70.60\pm 0.24$	$71.93\pm 0.34$	$72.41\pm 0.39$

Table 1: Effects of different values of

M

on node - classification accuracy over the Chameleon dataset and use Laplacian positional encoding.

Panel of Figure 6 — Figure 6: $2D$ t - SNE visualization of Laplacian positional encoding and $Katz$ positional encoding on the Chameleon and Squirrel datasets,where Colors indicate ground - truth node labels.

$M$	1	4	8
Accuracy (%)	$71.76\pm 0.13$	$72.44\pm 0.33$	$71.42\pm 0.35$

Table 2: Effects of different values of

M

on node - classification accuracy over the Chameleon dataset, we omit dropout after

\alpha_{i,j}^{k}

and use Laplacian positional encoding.

Laplace PE	Katz PE	$pe=2$	$pe=4$	$pe=6$	$pe=8$	$K=2$	$K=4$	$K=6$	LH(%)
$\checkmark$	$\times$	$\checkmark$	$\times$	$\times$	$\times$	$\checkmark$	$\times$	$\times$	77.10
$\checkmark$	$\times$	$\times$	$\checkmark$	$\times$	$\times$	$\checkmark$	$\times$	$\times$	79.27
$\checkmark$	$\times$	$\times$	$\times$	$\checkmark$	$\times$	$\checkmark$	$\times$	$\times$	79.69
$\checkmark$	$\times$	$\times$	$\times$	$\times$	$\checkmark$	$\checkmark$	$\times$	$\times$	79.38
$\checkmark$	$\times$	$\times$	$\times$	$\times$	$\checkmark$	$\times$	$\checkmark$	$\times$	72.61
$\checkmark$	$\times$	$\times$	$\times$	$\times$	$\checkmark$	$\times$	$\times$	$\checkmark$	68.38

Table 3: We investigate the effects of different position-encoding types, position-encoding dimensionality, and the number of neighbors k on the latent representation LH over the Chameleon dataset. Here,

k

denotes the number of neighbors,

pe

denotes the dimensionality of position encoding, and LH is the K-NN Label Homophily defined by Equation ( 12 ).

PE-type	PE-dim	K	LH(%)	Accuracy (%)
Katz	8	2	73.47	$71.81\pm 0.57$
Laplace	8	2	79.38	$71.93\pm 0.34$
Laplace	8	4	72.61	$71.69\pm 0.31$
Laplace	8	6	68.38	$68.10\pm 0.19$
Laplace	2	2	77.10	$70.56\pm 0.35$

Table 4: Correlation between K - NN Label Homophily and model performance

Laplace PE	$pe=2$	$pe=4$	$pe=6$	$pe=8$	$K=2$	$K=4$	$K=6$	LH(%)
✓	$\checkmark$	$\times$	$\times$	$\times$	$\checkmark$	$\times$	$\times$	22.10
✓	$\times$	$\checkmark$	$\times$	$\times$	$\checkmark$	$\times$	$\times$	20.72
✓	$\times$	$\times$	$\checkmark$	$\times$	$\checkmark$	$\times$	$\times$	21.39
✓	$\times$	$\times$	$\times$	$\checkmark$	$\checkmark$	$\times$	$\times$	21.28
✓	$\times$	$\times$	$\times$	$\checkmark$	$\times$	$\checkmark$	$\times$	20.87
✓	$\times$	$\times$	$\times$	$\checkmark$	$\times$	$\times$	$\checkmark$	21.00

Table 5: We investigate the effects of position - encoding dimensionality, and the number of neighbors k on the latent representation LH over the Actor dataset. Here,

k

denotes the number of neighbors,

pe

denotes the dimensionality of position encoding, and LH is the K - NN Label Homophily defined by Equation ( 12 ).

$Node$	$\mathcal{N}$	$\mathcal{PE}$	Overlap Ratio(%)
Node:0	[812, 2051, 6341]	[5930, 3912]	0.0
Node:1	[3809]	[3196, 6128]	0.0
Node:2	[93, 258, 361 … 7571]	[1437, 1714]	0.0
All Node	$\backslash$	$\backslash$	0.86

Table 6:

\text{Overlap Ratio}(v)

under

pe_{dim}=2

on the Actor Dataset, where

\mathcal{N}

denotes the set of

first-order

neighbors in the original graph, and

\mathcal{PE}

denotes the set of K - nearest neighbors in the PE space.

Dataset	Cora	Cite.	Pubm.	Cham.	Squi.	Actor	Corn.	Texa.	Wisc.
Nodes	2708	3327	19717	2277	5201	7600	183	183	251
Edges	5429	4732	44338	36101	217073	33544	295	309	499
Features	1433	3703	500	2325	2089	931	1703	1703	1703
Classes	7	6	3	5	5	5	5	5	5

Table 7: Dataset statistics. Pei et al. (2020)

Dataset	GCN	GCN+	GAT	GAT+	GIN	GIN+	GraphSAGE	GraphSAGE+
Cora	85.89 $\pm$ 0.23	85.50 $\pm$ 0.24	86.53 $\pm$ 0.21	86.84 $\pm$ 0.26	84.24 $\pm$ 0.35	85.56 $\pm$ 0.32	84.79 $\pm$ 0.26	85.22 $\pm$ 0.34
Citeseer	75.52 $\pm$ 0.26	74.24 $\pm$ 0.18	75.57 $\pm$ 0.14	73.94 $\pm$ 0.19	73.17 $\pm$ 0.34	74.57 $\pm$ 0.38	74.54 $\pm$ 0.21	74.90 $\pm$ 0.24
Pubmed	88.10 $\pm$ 0.05	88.50 $\pm$ 0.05	86.84 $\pm$ 0.07	88.43 $\pm$ 0.04	88.35 $\pm$ 0.06	88.33 $\pm$ 0.06	88.76 $\pm$ 0.05	88.78 $\pm$ 0.05
Chameleon	38.93 $\pm$ 0.46	71.14 $\pm$ 0.27	44.39 $\pm$ 0.64	72.38 $\pm$ 0.42	39.81 $\pm$ 0.63	71.93 $\pm$ 0.26	48.79 $\pm$ 0.42	70.68 $\pm$ 0.37
Squirrel	27.73 $\pm$ 0.42	56.02 $\pm$ 0.33	30.09 $\pm$ 0.32	51.17 $\pm$ 0.30	31.85 $\pm$ 0.39	57.12 $\pm$ 0.64	36.48 $\pm$ 0.43	53.79 $\pm$ 0.22
Actor	28.51 $\pm$ 0.19	33.77 $\pm$ 0.15	28.62 $\pm$ 0.21	34.54 $\pm$ 0.15	28.87 $\pm$ 0.27	34.10 $\pm$ 0.27	35.64 $\pm$ 0.30	35.94 $\pm$ 0.22

Table 8: Model accuracy for each dataset, with Laplacian positional encoding adopted for position encoding. + denotes embedding our plug-and-play module (PEBSAM or PEBSAM-Speed); for the Pubmed dataset, + refers to the PEBSAM-Speed, while for other datasets, + refers to the PEBSAM. The final results are reported as the mean ± standard deviation across 10 independent experiments.

PE-type	PE-dim	LH(%)	Dataset	Accuracy (%)
Laplace	8	79.38	Chameleon	$72.38\pm 0.42$
Katz	8	73.47	Chameleon	$72.24\pm 0.22$
Katz-err	8	80.86	Chameleon	$74.73\pm 0.39$
Laplace	8	67.22	Squirrel	$51.17\pm 0.30$
Katz	8	68.65	Squirrel	$64.78\pm 0.20$
Katz-err	8	82.25	Squirrel	$69.80\pm 0.18$

Table 9: Ablation Study on Positional Encoding with offset-num Fixed at 4 and use GAT+ model

PE-type	Without FiLM	Dataset	Accuracy (%)
Laplace	No	Chameleon	$72.56\pm 0.16$
Laplace	Yes	Chameleon	$70.79\pm 0.23$
Laplace	No	Squirrel	$59.47\pm 0.17$
Laplace	Yes	Squirrel	$54.16\pm 0.22$

Table 10: An ablation study on the FiLM module is performed using the GAT+ model, with offset-num set to 4.

$V_{Str}$	$V_{Spa}$	Dataset	Accuracy (%)
$\checkmark$	$\times$	Actor	$34.22\pm 0.24$
$\times$	$\checkmark$	Actor	$32.32\pm 0.18$
$\checkmark$	$\checkmark$	Actor	$35.06\pm 0.13$
$\checkmark$	$\times$	Texas	$67.30\pm 1.08$
$\times$	$\checkmark$	Texas	$71.35\pm 0.70$
$\checkmark$	$\checkmark$	Texas	$72.05\pm 1.25$

Table 11: Gating ablation study of GAT+ with Katz positional encoding on the Actor and Texas datasets, with offset-num set to 4. A single

\checkmark

indicates the single-branch setting, while two

\checkmark

\checkmark

indicate the dual-branch setting with gated fusion.

$Dataset$	PE	K-NN Label Homophily(%)	Accuracy(%)
Chameleon	Laplacian	78.02	$72.80\pm 0.29$
Chameleon	Corrected-Laplacian	76.66	$72.71\pm 0.21$
Squirrel	Laplacian	66.11	$57.52\pm 0.20$
Squirrel	Corrected-Laplacian	78.22	$66.17\pm 0.33$
Actor	Laplacian	21.59	$34.69\pm 0.26$
Actor	Corrected-Laplacian	20.82	$34.84\pm 0.06$

Table 12: Results of GAT+ equipped with corrected Laplacian positional encoding (

\text{offset-num}=4

) on various datasets.It can be observed that on Squirrel, Laplacian PE and Corrected-Laplacian PE exhibit a marked difference in K-NN Label Homophily, leading to a large gap in the final performance. On the other two datasets, however, the K-NN Label Homophily values of Laplacian PE and Corrected-Laplacian PE are comparable, and the final results remain close.

$Dataset$	K-NN Label Homophily(%)	Overlap Ratio(%)
Cora	23.59	2.51
Citeseer	53.98	14.76
Texas	50.82	10.11
Wisconsin	45.78	14.54
Cornell	35.95	7.38

Table 13: Metrics K-NN Label Homophily and Overlap Ratio with Laplacian positional encoding on different datasets

Graph Neural Networks

Graph Neural Networks learn from graph-structured data by combining information across connected nodes, edges, and larger structures.

See all 714 papers

Understanding Truncated Positional Encodings for Graph Neural Networks
Jun 11, 2026James Flora, Mitchell Black, Weng-Keen Wong +1GNN Expressivity Positional Encoding
School of Electrical Engineering and Computer Science, Oregon State University, Corvallis, Oregon, USA · Halıcıoğlu Data Science Institute, University of California San Diego, San Diego, California, USA.
Revisiting Pre-Propagation GNNs: Robust Diffusion Operators and Hidden-State Re-Propagation
May 24, 2026Zichao Yue, Zhiru ZhangGraph Neural Networks Graph Diffusion
School of Electrical and Computer Engineering, Cornell University, Ithaca, New York, USA.
PEANUT: Perturbations by Eigenvector Alignment for Attacking Graph Neural Networks Under Topology-Driven Message Passing
Mar 27, 2026Bhavya Kohli, Biplab SikdarAdversarial Attacks Graph Neural Networks
National University of Singapore, Singapore

Jun 11, 2026J/K move · Enter open · S save

Understanding Truncated Positional Encodings for Graph Neural Networks

James Flora, Mitchell Black, Weng-Keen Wong, Amir Nayyeri

School of Electrical Engineering and Computer Science, Oregon State University, Corvallis, Oregon, USA · Halıcıoğlu Data Science Institute, University of California San Diego, San Diego, California, USA.

GNN Expressivity Positional Encoding Graph Positional Encoding

Open paper AskPDF arXiv

Positional encodings (PEs) enhance the power of graph neural networks (GNNs), both theoretically and empirically. Two of the most popular families of PEs - spectral (e.g., Laplacian eigenspaces, effective resistance) and walk-based (polynomials of the adjacency matrix) - are theoretically equivalent in expressive power, with expressivity between the 1-WL and 3-WL tests. However, this equivalence assumes the GNN uses the "complete" version of these PEs, which requires

O(n^3)

time and space complexity. Instead, practitioners commonly use truncated variants of these encodings, such as the first

k

eigenspaces or powers of the adjacency matrix. However, the theoretical properties of these truncated PEs are unknown. In this work, we initiate the study of these truncated PEs. Theoretically, we show that, under truncation, several families of PEs are fundamentally different in expressive power. As a corollary, we show that truncated spectral PEs are no longer stronger than the 1-WL test. We also study a family of spectral PEs, the

k

-harmonic distances, to highlight the differences in expressive power of even closely related truncated PEs. Finally, we experimentally show that a mix of truncated PEs is preferable to any single family on real-world datasets.

Abstract

Graph Neural Networks

Explore similar work

Understanding Truncated Positional Encodings for Graph Neural Networks

Revisiting Pre-Propagation GNNs: Robust Diffusion Operators and Hidden-State Re-Propagation

PEANUT: Perturbations by Eigenvector Alignment for Attacking Graph Neural Networks Under Topology-Driven Message Passing