PaperlayerView exact revision on arXiv

Source-linked AI summary

Equivariant and Stable Positional Encoding for More Powerful Graph Neural Networks

Haorui Wang, Haoteng Yin, Muhan Zhang, Pan Li

arXiv:2203.00199v5cs.LGcs.SI

TL;DR

GNNs can struggle with predictions over sets of nodes, and existing fixes raise concerns about generalization, stability, or efficiency. The paper proposes PEG, which processes node and positional features in separate channels with equivariance guarantees. Across eight real-world link-prediction networks, PEG compares favorably with baselines, including under domain shift.

  • Problem

    GNNs can give the same representation to automorphic nodes and often perform poorly on node-set tasks; using positional features raises unresolved equivariance and stability challenges.

    Source: §1 · pp. 1–2

  • Method

    PEG uses separate channels to update node and positional features, imposing permutation equivariance on node features and orthogonal equivariance on positional features.

    Source: §1 · p. 2

  • Results

    Across eight real-world networks, PEG achieved performance comparable to strong distance-encoding baselines with lower training and inference complexity, beat baselines without distance encoding, and showed larger performance gaps under domain shift.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The paper supports PEG's effectiveness for link prediction and identifies broader positional-encoding techniques and other graph tasks as future extensions.

    Source: §5 · p. 10

    Full characterization of PE-equivariance and PE-stability for general positional-encoding techniques is left for future study.

    Source: §3.3 · p. 7

Abstract

from arXiv · show

Graph neural networks (GNN) have shown great advantages in many graph-based learning tasks but often fail to predict accurately for a task-based on sets of nodes such as link/motif prediction and so on. Many works have recently proposed to address this problem by using random node features or node distance features. However, they suffer from either slow convergence, inaccurate prediction, or high complexity. In this work, we revisit GNNs that allow using positional features of nodes given by positional encoding (PE) techniques such as Laplacian Eigenmap, Deepwalk, etc. GNNs with PE often get criticized because they are not generalizable to unseen graphs (inductive) or stable. Here, we study these issues in a principled way and propose a provable solution, a class of GNN layers termed PEG with rigorous mathematical analysis. PEG uses separate channels to update the original node features and positional features. PEG imposes permutation equivariance w.r.t. the original node features and imposes $O(p)$ (orthogonal group) equivariance w.r.t. the positional features simultaneously, where $p$ is the dimension of used positional features. Extensive link prediction experiments over 8 real-world networks demonstrate the advantages of PEG in generalization and scalability.

1 INTRODUCTION

GNNs often struggle with node-set predictions because automorphic nodes receive indistinguishable representations, while common fixes can compromise generalization, stability, or efficiency. PEG uses separate channels for node and positional features, with equivariance guarantees and link-prediction results across eight real-world networks.

1 INTRODUCTION

  • Automorphic nodes receive the same GNN representation, making them indistinguishable for node-set predictions; one-hot features can break permutation equivariance and impair transferability or stability.The paper identifies this ambiguity as a reason GNNs can underperform on link prediction and other node-set tasks.Source: §1 · p. 1
  • Random features may make training hard to converge and predictions noisy, distance encoding is costly because computations are sample-specific, and randomized spectral PE can lose equivariance for repeated eigenvalues or become unstable for close eigenvalues.Distance encoding can share fewer intermediate computations across node-set samples than the canonical GNN pipeline.Source: §1 · pp. 1–2
  • PEG updates node and positional features in separate channels, preserving permutation equivariance for node features and orthogonal equivariance for positional features; its Laplacian Eigenmap stability bound uses the pth-to-(p + 1)th eigengap.This replaces dependence on the smallest gap between any consecutive eigenvalues among those considered by earlier methods.Source: §1 · p. 2
  • PEG achieved performance comparable to strong distance-encoding baselines with much lower training and inference complexity, outperformed baselines without distance encoding, and showed larger gaps under domain shift.The evaluation covered link prediction on eight real-world networks.Source: §1 · p. 2

1.1 OTHER RELATED WORKS

  • Alternative GNNs that directly represent node sets have high complexity and were studied only for graph-level tasks, while prior GNN stability analyses did not address positional features.Source: §1.1 · p. 3

2 NOTATIONS AND PRELIMINARIES

The preliminaries establish graph, matching, and positional-encoding notation used in the paper. They also explain why eigenvector representations may be non-unique and define distances that account for node permutations and orthogonal changes to positional features.

2 NOTATIONS AND PRELIMINARIES

  • A graph is represented as G = (A, X), with adjacency matrix A and node-feature matrix X whose vth row gives node v's feature vector.Source: §2 · p. 3
  • Graph matching aligns graph structure and node features with a permutation, and graph distance sums the Frobenius differences between the matched Laplacians and features.Source: §2 · p. 3
  • Eigenvalue decomposition is non-unique: distinct eigenvalues allow eigenvector sign flips, while repeated eigenvalues allow orthogonal transformations within the corresponding eigenspace.Source: §2 · p. 3
  • Positional encoding maps a graph to a positional vector for each node; PE-matching aligns two such feature collections by minimizing their Frobenius distance over orthogonal transformations.The resulting distance is the Frobenius norm after applying the optimal orthogonal match.Source: §2 · pp. 3–4

3 EQUIVARIANT AND STABLE POSITIONAL ENCODING FOR GNN

The section formalizes equivariance and stability for GNN layers using positional encodings, then gives conditions for Laplacian Eigenmap and other matrix-factorization encodings. It also identifies eigengap and training-setting constraints on stability.

3.1 OUR GOAL: BUILDING PERMUTATION EQUIVARIANT AND STABLE GNN LAYERS

  • PE-stability bounds matched output discrepancies by graph distance and is stronger than permutation equivariance; PE-based layers may update both node and positional features.The layer's output includes updated node features and positional features, with the latter compared as sets.Source: §3.1 · p. 4

3.2 PE-STABLE GNN LAYERS BASED ON LAPLACIAN EIGENMAP AS POSITIONAL ENCODING

  • ρ_p is extremely large on Citeseer and mostly greater than 10 on Twitch(PT).The ratio compares eigenspace-based sensitivity with the largest inverse eigengap among the first p eigenpairs.Source: §3.2 · pp. 5–6
  • Small eigengaps can make individual eigenvectors change sharply under tiny graph perturbations, challenging stability in settings with few large training graphs.The paper contrasts prior experiments with at least 1,000 graphs of at most 100–200 nodes against its focus on at most 10 graphs of at least 1,000 nodes.Source: §3.2 · p. 5
  • For Laplacian Eigenmap, permutation equivariance over all features and O(p) equivariance over positional features yield PE-equivariance when λ_p ≠ λ_(p+1).O(p) equivariance makes the layer insensitive to the choice of basis within the eigenspace.Source: §3.2 · p. 6
  • PEG's simplified layer uses a GCN weighted by distances between positional vectors, leaves positional features unchanged, and satisfies PE-stability.A different O(p)-equivariant design performs similarly but slightly worse than Eq. 6 in link prediction.Source: §3.2 · p. 6
  • PE-stability requires bounded initial features and weights, Lipschitz activations, and a gap between λ_p and λ_(p+1); larger gaps improve stability.The authors report that instability becomes more severe for larger graphs and smaller training sets.Source: §3.2 · pp. 6–7

3.3 GENERALIZED TO OTHER PE TECHNIQUES: DEEPWALK AND LINE

  • For matrix-factorization encodings such as Deepwalk, Node2vec, and LINE, a unique rank-p optimum and permutation-covariant objectives make layers satisfying the two equivariance conditions PE-equivariant.The result assumes the objective's f+ and f− functions transform consistently under node permutations.Source: §3.3 · p. 7
  • For general positional encodings, PE-stability depends on the smallest nonzero singular value of the factorized optimum, and its full characterization is left for future work.The low-rank optimization may not yield a guaranteed optimum in practice because its constraint is non-convex.Source: §3.3 · p. 7

4 EXPERIMENTS

PEG is evaluated on traditional and domain-shift link prediction, using positional encodings with GNN layers across eight real-world graphs. It performs comparably to SEAL in domain shift with lower training and testing complexity, and outperforms other baselines.

4.1 THE EXPERIMENTAL PIPELINE OF PEG FOR LINK PREDICTION

  • The link-prediction pipeline computes positional features, stacks PEG layers, then predicts each link from the final representations of its two nodes.The tested encodings are Laplacian Eigenmap and Deepwalk; PEG is also applied to GraphSAGE.Source: §4.1 · p. 8
  • For small graphs where labeled links also generate positional features, the authors use 10-fold training-link partitions to reduce overfitting and generalization gaps.Fold-specific positional encodings can be precomputed; the partition is not needed at testing.Source: §4.1 · p. 8

4 EXPERIMENTS

  • The experiments cover traditional link prediction on eight real graphs and domain-shift prediction across citation, user-interaction, and biological networks.The paper describes domain shift as training and testing on different graphs and evaluates results over 10 random tests.Source: §4 · p. 7, §4.2 · p. 8, §4.3 · p. 10

4.2 TASK 1 — TRADITIONAL LINK PREDICTION

  • On small datasets, node-feature VGAE performs best on Cora, CiteSeer, and Pubmed, while one-hot and positional features achieve nearly the same performance.Combining node and positional features beats positional features alone but can underperform node features alone.Source: §4.2 · pp. 8–9
  • On traditional link prediction, PEG significantly outperforms all baselines except SEAL, while PEG+ achieves comparable or better performance than SEAL.PEG also performs comparably in most cases with constant features, and positional encodings without GNNs perform poorly.Source: §4.2 · p. 9
  • On the OGB datasets, PEG achieves the best results on DDI and performs competitively with SEAL on COLLAB.PEG's complexity is comparable to canonical GNNs and its test-time speed is significantly faster than SEAL's.Source: §4.2 · p. 9, Table 2 · p. 9

4.3 TASK 2 —DOMAIN-SHIFT LINK PREDICTION

  • In domain-shift link prediction, PEG and SEAL outperform other baselines significantly and achieve comparable performance, while PEG has much lower training and testing complexity.The experiments train and test on graphs from different domains.Source: Table 3 · p. 10, §4.3 · p. 10

5 CONCLUSION

The paper proposes PEG under conditions intended to preserve permutation equivariance and stability when GNNs use positional encodings. Link-prediction experiments demonstrate PEG's effectiveness, while extending the theory and testing other graph tasks remain future work.

5 CONCLUSION

  • The paper proposes conditions for GNNs using positional encodings to remain permutation equivariant and stable, and introduces PEG to satisfy them.The conditions address the node-ambiguity issue.Source: §5 · p. 10
  • Extensive link-prediction experiments demonstrate the effectiveness of PEG.Source: §5 · p. 10
  • Future work will generalize the theory to more positional-encoding techniques and test PEG on other graph-learning tasks.Source: §5 · p. 10

A PROOF OF LEMMA 3.4

The proof considers Laplacian-style positional encodings formed from the first p eigenvectors of a positive semidefinite matrix. It perturbs the matrix near a pair of eigenvalues and relates the resulting encodings.

A PROOF OF LEMMA 3.4

  • The positional encoding PE(B) is defined as the first p eigenvectors of the positive semidefinite matrix B.The passage orders eigenvectors by their corresponding eigenvalues.Source: A PROOF OF LEMMA 3.4 · p. 14
  • The proof chooses k where adjacent eigenvalues have minimum gap, then perturbs the corresponding eigenvectors.Source: A PROOF OF LEMMA 3.4 · p. 14
  • After perturbation, the vectors are still an orthogonal basis, and the perturbed positional encoding may differ by a transformation from S′ in S_N(p).Source: A PROOF OF LEMMA 3.4 · p. 14

B PROOF OF LEMMA 3.5

The proof invokes a Davis–Kahan eigenspace perturbation result to relate positional encodings of nearby matrices. It also uses permutation invariance of eigenvalues to obtain a bound after node reindexing.

B PROOF OF LEMMA 3.5

  • The proof derives the lemma using the Davis–Kahan theorem and a variant that characterizes eigenspace perturbation.It applies Theorem 2, Equation 3 of Yu et al. (2015) to two positive semidefinite matrices.Source: B PROOF OF LEMMA 3.5 · p. 14
  • The cited theorem supplies an orthogonal matrix Q relating the matrices' orthonormal eigenvector columns.Source: B PROOF OF LEMMA 3.5 · p. 15
  • Permuting a matrix's rows and columns preserves its eigenvalues and permutes its eigenvectors, enabling the proof to bound the reordered encodings.The resulting bound is expressed using the operator or Frobenius norm of the matrix difference.Source: B PROOF OF LEMMA 3.5 · p. 15

C PROOF OF THEOREM 3.6

The proof establishes PE-equivariance by aligning positional features across perfectly matched graphs through an orthogonal transformation, then showing the layer outputs preserve the node matching and positional-feature agreement.

C PROOF OF THEOREM 3.6

  • Under a perfect node matching and the stated eigenvalue-gap condition, the two Laplacian positional-feature matrices differ only by an orthogonal transformation.The proof uses this alignment to account for non-unique eigenvector choices.Source: C PROOF OF THEOREM 3.6 · p. 15
  • The proof applies the layer conditions in Eqs. 4 and 5 to the matched inputs and aligned positional features.It considers the outputs of a GNN layer satisfying those conditions on both graphs.Source: C PROOF OF THEOREM 3.6 · p. 15
  • The resulting node features follow the graph matching, while the positional-feature discrepancy is zero, establishing PE-equivariance.The proof concludes that the layer satisfies PE-equivariance.Source: C PROOF OF THEOREM 3.6 · p. 15

D PROOF OF THEOREM 3.7

The proof bounds changes in a PEG layer by handling positional-feature variation and graph-dependent terms separately, using eigenspace stability, Lipschitz continuity, and matrix norm inequalities.

D PROOF OF THEOREM 3.7

  • The proof first bounds the positional-feature output discrepancy by the discrepancy between matched graphs’ Laplacians, using the eigenspace perturbation lemma.The bound is expressed using both operator- and Frobenius-norm Laplacian differences.Source: D PROOF OF THEOREM 3.7 · p. 16
  • The proof separately bounds graph-dependent terms involving masked adjacency and Ξ using matrix norm inequalities and properties of normalized adjacency eigenvalues.It also uses that an edge indicator is nonzero exactly when the node pair is an edge.Source: D PROOF OF THEOREM 3.7 · pp. 16–17
  • Lipschitz continuity and triangle inequalities propagate the component-wise feature-function bounds through the stability argument.The proof invokes the Lipschitz property of the component-wise function φ.Source: D PROOF OF THEOREM 3.7 · p. 17

E PROOF OF THEOREM 3.8

The appendix proves PE-equivariance for the optimization-derived positional features, reviews E-GNN, and gives optimization forms for several positional-encoding techniques alongside supplementary experiment details.

E PROOF OF THEOREM 3.8

  • A unique rank-constrained optimization solution yields positional features that transform under a graph permutation up to an orthogonal change of basis, enabling the layer proof of PE-equivariance.The proof combines this alignment with the layer conditions to show node-feature outputs follow the permutation and positional-feature discrepancy is zero.Source: E PROOF OF THEOREM 3.8 · pp. 17–18

F REVIEW OF THE E-GNN LAYER

  • E-GNN is reviewed as a layer that updates node embeddings and physical coordinates, with coordinate equivariances that include translation, rotation, and reflection.The text notes that its stronger translation-equivariance requirement can also satisfy the conditions used for PE-equivariance.Source: F REVIEW OF THE E-GNN LAYER · p. 18

G THE OPTIMIZATION FORM FOR GENERAL PE TECHNIQUES

  • LINE and Deepwalk are expressed through graph- and degree-dependent matrix functions that satisfy the permutation conditions of Theorem 3.8.For LINE, f+(A)=A; for Deepwalk, the functions use random-walk powers and a degree-based negative-sampling term.Source: G THE OPTIMIZATION FORM FOR GENERAL PE… · pp. 19–20
  • Node2vec uses a second-order random walk to collect node-id strings before training an SGNS model.The text refers readers to prior work for its more involved optimization form.Source: G THE OPTIMIZATION FORM FOR GENERAL PE… · p. 20

H SUPPLEMENT FOR EXPERIMENTS

  • The supplement reports further experiments addressing generalization, stability, and the theory and PEG layer’s wider applicability.These experiments are described as appearing in Sections H.6–H.8.Source: H SUPPLEMENT FOR EXPERIMENTS · p. 20

H.1 DATASETS

The supplementary section describes the datasets, baselines, and tuning used in the experiments, and reports stability and positional-dimension sensitivity findings.

H.1 DATASETS

  • Experiments cover citation networks Cora, Citeseer, and Pubmed; Twitch gamer-friendship networks across countries; Chameleon Wikipedia links; 24 human-tissue PPI graphs; and OGB drug-interaction and author-collaboration networks.OGB uses more realistic train/validation/test splits, by time for ogbl-collab and by drug target in the body for ogbl-ddi.Source: §H.1 · p. 20
  • Across Pubmed, Twitch(RU), and Chameleon, ρp is mostly larger than 5 even without multiple eigenvalues; on Cora it is extremely large because eigenvalues repeat.The text describes the proposed approach as far more stable than previous methods under the stated sensitivity measure.Source: §H.1 · p. 21

H.2 BASELINE DETAILS

  • The baseline set includes four GNN-based methods and two network-embedding methods, with LE and Deepwalk embeddings evaluated using pairwise inner products and an MLP.GNN baselines include VGAE, P-GNN, a GNN transformer, and SEAL; the methods are tuned and their best results reported.Source: §H.2 · p. 21
  • AUC sensitivity to positional-feature dimension varies by technique: DW is generally more stable than LE, PEG-DW+ is stable, and larger dimensions tend to improve PEG performance but take longer.The comparison covers PEG-DW, PEG-LE, PEG-DW+, and PEG-LE+ on Cora, Pubmed, and Twitch(RU).Source: §H.2 · p. 21, Figure 4 · p. 22

H.3 HYPERPARAMETERS TUNING FOR PEG

  • PEG hyperparameters are selected by grid search, and reported models are the best from ten runs after training until loss convergence.The authors note that PEG was only slightly tuned and more extensive tuning may yield better results.Source: §H.3 · p. 22

H.4 FURTHER ANALYSIS

PEG performs strongly on random-graph link prediction and under input perturbations. Further analyses report PE-dimension trade-offs and nonlinear edge-weight transformations.

H.4 FURTHER ANALYSIS

  • Fig. 3 supplements Lemmas 3.4 and 3.5 with inverse-eigengap ratios; across three datasets, DW seems more stable than LE, while larger dimensions may improve PEG performance but take more time.PEG-DW+ achieves stable performance.Source: §H.4 · p. 22

H.5 EDGE WEIGHT VISUALIZATION

  • With DW positional embeddings, PEG’s edge weights increase nonlinearly with node-representation distance; most weights are near 1 and a few are much smaller.Figure 5 plots curves for each dataset, with 500 selected edges represented as red points.Source: §H.5 · p. 22, Figure 5 · p. 23

H.6 LINK PREDICTION OVER RANDOM GRAPHS

  • AUC around 0.98 with one training graph, PEG slightly improves with more graphs and outperforms all three GAE variants trained on 50 graphs.The comparison is shown for link prediction on random graphs.Source: Figure 6 · p. 23, §H.6 · p. 23

H.7 THE STUDY OF PE STABILITY BY PERTURBING THE INPUT GRAPHS

  • Under all four perturbation scenarios, PEG significantly outperforms PE-based GAE/VGAE; edge removal is more destructive on small Cora graphs, but PEG remains resilient.GAE/VGAE models using constant and positional features generally collapse when many edges are removed.Source: Figure 7 · p. 24, §H.7 · p. 24

H.8 PRELIMINARY RESULTS FOR NODE CLASSIFICATION BASED ON PE

The preliminary citation-network evaluation finds that PEG-LE and PEG-DW outperform GCN and are comparable to GAT on node classification.

H.8 PRELIMINARY RESULTS FOR NODE CLASSIFICATION BASED ON PE

  • The model was kept at hyperparameters selected for traditional link prediction rather than specifically tuned for node classification.Source: §H.8 · pp. 24–25
  • PEG-LE and PEG-DW significantly outperform GCN and provide results comparable to GAT on node classification.The reported Table 6 scope is accuracy on Cora, Citeseer, and Pubmed; the model was not specifically tuned for this task.Source: §H.8 · pp. 24–25, Table 6 · p. 25
  • PEG uses structure-derived edge weights, whereas GAT’s neighbor-attention weights are based on node features.The paper describes these as orthogonal information sources and leaves combining them for future work.Source: §H.8 · p. 25
Loading 2203.00199v5…