PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Jinhua Wu, Xinliang Zhang

arXiv:2609.13712v1cs.AI

TL;DR

Traditional GNNs have limited first-order neighborhoods and often perform suboptimally on heterophilous graphs. The paper adds deformable position-space aggregation to structural messages, but diagnostics find that offsets fail. It reports promising results across homophilous and heterophilous datasets and uses the diagnostics to motivate a simpler module.

  • Problem

    Traditional GNNs aggregate first-order neighbors, which limits their receptive field and often yields suboptimal performance on heterophilous graphs.

    Source: §1 · pp. 2–3

  • Method

    PEBDSAM uses deformable offsets in position space to identify relevant nodes beyond first-order neighbors and adaptively fuse their spatial features with structural features.

    Source: §1 · p. 4, §3.2 · p. 7

  • Results

    The authors report promising performance on three homophilous and six heterophilous graphs, with especially pronounced improvements on heterophilous graphs.

    Source: §1 · p. 4

  • Takeaways & Limitations

    Diagnostics show that performance can remain satisfactory after offset failure, motivating a simplified PEBSAM and further work on positional encodings.

    Source: §1 · p. 4, §8 · p. 25

    The design significantly relies on positional encoding, and current offsets can collapse toward zero, leaving fixed PE nearest-neighbor aggregation.

    Source: §4.3 · p. 15, §8 · p. 25

Abstract

from arXiv · show

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.

1. Introduction

Traditional GNNs face limited receptive fields, information loss across long-range dependencies, and weak performance on heterophilous graphs. PEBDSAM adds position-space spatial aggregation to first-order structural information, while diagnostics reveal that its offsets fail and motivate simpler variants.

1. Introduction

  • Traditional GNNs have fixed first-order receptive fields, lose information as distant nodes communicate across multiple edges, and often perform suboptimally on heterophilous graphs.Expanding receptive fields by stacking layers also risks oversmoothing.Source: §1 · pp. 2–3
  • PEBDSAM supplements first-order structural information with spatially relevant nodes identified in position space, then adaptively fuses structural and spatial features.The newly identified nodes can be several graph hops away, enlarging the receptive field and alleviating oversquashing.Source: §1 · pp. 3–4
  • Diagnostics found that learned offsets approach zero, prompting the authors to analyze the failure and introduce PEBSAM and PEBSAM-Speed.The paper also reports that performance can improve despite offset failure.Source: §1 · p. 4
  • The proposed architecture combines structural and spatial information to address traditional GNNs’ poor performance on heterophilous graphs.The authors also present position encoding as an underused resource for GNNs.Source: §1 · p. 4
  • PEBDSAM achieves promising performance on three homophilous and six heterophilous graphs, with especially pronounced improvements on heterophilous graphs.The authors identify these results as highlighting the strengths of spatial information.Source: §1 · p. 4

2. Related Work

The related work traces deformable convolution from vision to graph neural networks. It distinguishes prior graph approaches from this paper’s use of offsets in position-encoding space to identify relevant nodes beyond first-order neighbors.

2.1. Deformable Convolution

  • Deformable convolution learns offsets to escape fixed receptive fields, inspiring this work’s effort to bring adaptive receptive fields to GNNs.The cited vision methods are Dai et al. (2017) and Zhu et al. (2019).Source: §2.1 · p. 5

2.2. Existing Deformable Mechanisms in GNNs

  • DGCN modifies aggregation weights but retains first-order neighbors; its receptive-field expansion instead comes from aggregating multiple latent neighbor graphs.The cited work is Park et al. (2022).Source: §2.2 · p. 5
  • Unlike DGCN’s latent graphs and DGT’s reordered feature sequences, this approach uses position-space offsets to identify relevant nodes beyond first-order neighbors.Park et al. (2025) introduced DGT; both prior methods require graph-data preprocessing.Source: §2.2 · p. 6

3. Proposed Method

The method supplements conventional GNN aggregation with spatial information from nodes selected in positional-encoding space, then fuses spatial and structural information. Its design also considers noise from the larger receptive field and computational costs of edge-level operations.

3.1. Overall Architecture and Brief Analysis

  • The initial edge-adjustment approach faced high computational complexity because graph datasets have many more edges than nodes, and preliminary experiments still left a gap with state of the art.The authors therefore introduce a simplified version of their approach.Source: §3.1 · pp. 6–7
  • The simplified design uses gating to filter structural and spatial information, while attention reduces noisy-node influence within the spatial information.The larger receptive field may introduce unnecessary noise; conventional models such as GAT can also reduce noise in structural information.Source: §3.1 · p. 7

3.2. Model Introduction

  • For each input, PEBDSAM produces M query points from offsets and retrieves K relevant nodes in positional-encoding space by Euclidean distance.Each query point is formed from a node's positional encoding and an offset; the search space is spanned by all graph nodes.Source: §3.2 · p. 8
  • The retrieved nodes' feature and positional information are fused using a hybrid module, with FiLM used to modulate structural and spatial information.The method first aggregates the positional information and corresponding features of the K spatial nodes.Source: §3.2 · pp. 8–10
  • PEBDSAM's spatially aware output is adaptively gated with the structure-aware output of a conventional GNN, and the module includes residual connections and activation.The GNN module can use various graph neural network models; the activation used in this work is Tanh.Source: §3.2 · pp. 8, 11

4. Diagnostic Experiments And Analysis

The diagnostic analysis finds that learned offsets approach zero, yet positional-space neighbors can still contribute useful information. It relates this behavior to positional-encoding structure and dropout, then examines when spatial and structural information complement each other.

4.1. Metric Definitions

  • The analysis uses OffsetAbsMean for offset magnitude, K-NN Label Homophily for label agreement among positional neighbors, Node Homophily for first-order neighbors, and Overlap Ratio for structural–spatial neighbor overlap.A low OffsetAbsMean can indicate fine-grained adjustments, while K-NN Label Homophily measures spatial-neighbor selection quality.Source: §4.1 · pp. 11–12

4.2. Experimental Findings

  • OffsetAbsMean approaches zero during training, while reducing M from 8 to 4 to 1 lowers observed accuracy despite the theoretical prediction that the final output is independent of M.With λ = 0, the offsets are identical and their aggregation is equivalent to a single offset.Source: §4.2 · pp. 13–14, Table 1 · p. 13

4.3. Analysis

  • Laplacian and Katz positional encodings scatter same-label nodes, making nearby points noisy and causing offsets to collapse; removing attention-coefficient dropout leaves results nearly unchanged.The authors interpret the multioffset design as a cheap random ensemble through dropout, improving generalization despite not producing meaningful dynamic jumps.Source: §4.3 · pp. 14–15, Table 2 · p. 15

4.4. In-depth Analysis

  • On Chameleon, same-class nodes occur among positional-space K-nearest neighbors despite imperfect clustering, and attention-filtered spatial features retain meaningful information; higher K-NN Label Homophily corresponds to better model accuracy.On Actor, homophily is around 20%, near the 1/5 = 0.2 random baseline for five categories; for nodes 0, 1, and 2, structural and spatial effective information do not overlap, and the final output contains more than 20% effective information (possibly 30%).Source: §4.4 · pp. 15–18
  • K-NN Label Homophily varies with positional encoding, encoding dimension, and neighbor count, and higher values correspond to better Chameleon accuracy.The section also defines OffsetAbsMean, Node Homophily, and Overlap Ratio to characterize offsets, first-order neighbors, and overlap between structural and spatial neighbors.Source: §4.1 · pp. 11–12, §4.4 · p. 16

5. Simplified Model

Removing the ineffective offset branch streamlines PEBDSAM into PEBSAM, which directly selects the k-nearest neighbors in positional-encoding space.

5. Simplified Model

  • Removing the offset branch reduces parameters and yields PEBSAM, which directly selects k-nearest neighbors in positional-encoding space.The offset module is removed by eliminating offsetmlp and its offset terms.Source: §5 · p. 18

6. Experiments

Experiments evaluate the framework on three homophilic and six heterophilic node-classification datasets. PEBSAM consistently improves results on heterophilic graphs, while homophilic gains are slight and some cases decline.

6.1. Datasets

  • The node-classification experiments cover three homophilic and six heterophilic graphs, using 10 predefined public splits per dataset.The splits follow Geom-GCN; Table 7 provides dataset statistics.Source: §6 · p. 18, §6.1 · p. 19, Table 7 · p. 19

6.2. Baselines and Experimental Settings

  • GCN, GAT, GIN, and GraphSAGE serve as two-layer baselines, with shared settings including 64-dimensional embeddings, dropout 0.5, and learning rate 0.005.Experiments use Adam, early stopping, and 10 repeated trials; Pubmed uses PEBSAM-Speed, while the other datasets use PEBSAM.Source: §6.2 · pp. 19–20

6.3. Experimental Results

  • PEBSAM consistently improves performance on heterophilic graphs and slightly improves it on homophilic graphs, though GAT+ is 1.63% worse than GAT on Citeseer.Table 8 reports model accuracy as mean ± standard deviation over 10 independent experiments; Pubmed uses PEBSAM-Speed, while the other datasets use PEBSAM.Source: Table 8 · p. 20, §6.3 · pp. 20–21

6.4. Ablation Experiments

  • The positional-encoding ablation reports that encoding quality matters; Katz-err used lambda-max = 1 and produced imprecise or erroneous encodings despite higher K-NN Label Homophily and improved performance.The authors propose exploring learnable and other better-suited positional encodings.Source: §6.4 · p. 21, Table 9 · p. 21
  • The FiLM ablation tests integration of positional and feature information; without FiLM, subsequent computations use feature information only.The ablation uses GAT+ with offset-num set to 4.Source: §6.4 · pp. 21–22, Table 10 · p. 22
  • With Katz encoding, Actor's 20.41% K-NN Label Homophily accompanies only modest VStr improvement when spatial information is added, unlike Texas's substantial improvement.The gating ablation compares single-branch and gated dual-branch settings on Actor and Texas.Source: §6.4 · p. 22, Table 11 · p. 22

6.5. Supplementary Notes

  • Corrected directed-graph Laplacian PE preserves the asymmetric adjacency information, and the paper's core conclusions remain unchanged across Laplacian and corrected-Laplacian PE.PyG's unfixed random ARPACK initial vector makes repeated Laplacian encodings differ, causing fluctuations in K-NN Label Homophily and Overlap Ratio.Source: §6.5 · p. 23

7. Discussion

The discussion links positional-encoding quality and fixed neighbor counts to performance boundaries, especially for large graphs and datasets with noisy or redundant positional neighbors.

7. Discussion

  • Citeseer combines 53.98% K-NN Label Homophily with 14.76% Overlap Ratio, which the authors identify as reasons PEBSAM performs poorly there.Cora's K-NN Label Homophily is 23.59%.Source: §7 · p. 23
  • On Squirrel, Laplacian and corrected-Laplacian PE differ markedly in K-NN Label Homophily and final performance, whereas comparable homophily values on two other datasets accompany close results.Table 12 reports GAT+ results with offset-num = 4.Source: Table 12 · p. 24
  • On large graphs, PEBSAM-Speed's required pe = 1 has limited encoding capacity and yields suboptimal metrics and results slightly below the baseline, while higher-dimensional encodings are costly.The authors suggest combining multiple one-dimensional encodings, potentially with attention, as a computationally simpler direction.Source: §7 · p. 24
  • The fixed k = 2 may provide too little information for high-degree large graphs, while increasing k adds information but also noise; adaptive per-node k remains future work.The authors also question whether one shared neighbor count suits nodes with different degrees.Source: §7 · p. 24

8. Conclusion

The conclusion reports that the deformable mechanism did not take effect, motivating a simplified module and further work on positional encodings.

8. Conclusion

  • Diagnostic experiments found that PEBDSAM's deformable mechanism did not take effect, prompting analysis of the failure and the model's continued satisfactory performance.Source: §8 · p. 25
  • The authors present PEBSAM as a simplified version developed from their diagnostic analysis.Source: §8 · p. 25
  • The design relies heavily on positional encoding; better-suited schemes may improve K-NN Label Homophily, make offsets effective, strengthen VSpa, and potentially remove VStr.Source: §8 · p. 25

Related papers

Loading 2609.13712v1…