PaperlayerView exact revision on arXiv

Source-linked AI summary

Graph Neural Networks with Learnable Structural and Positional Representations

Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, Xavier Bresson

arXiv:2110.07875v2cs.LG

TL;DR

GNNs can struggle to distinguish nodes with similar local structure because arbitrary graphs lack canonical positional information. The paper introduces LSPE, which decouples and jointly learns structural and positional representations, and reports gains across sparse and Transformer-based GNNs on molecular benchmarks.

  • Problem

    Message-passing GNNs depend on local structure, limiting their ability to distinguish positionally different nodes with similar neighborhoods.

  • Method

    LSPE decouples structural and positional representations, updates positional features within GNN layers, and fuses them with structural features.

  • Results

    1.79% to 64.14%: learnable positional encodings improve performance across sparse and fully connected GNNs on molecular benchmarks.

  • Takeaways & Limitations

    LSPE is presented as a generic architecture applicable to diverse MP-GNNs, including sparse GNNs and Transformer-based GNNs.

  • Takeaways & Limitations

    The baseline architecture that merges positional and structural representations does not allow positional representations to change and adjust to the task.

Abstract

from arXiv · show

Graph neural networks (GNNs) have become the standard learning architectures for graphs. GNNs have been applied to numerous domains ranging from quantum chemistry, recommender systems to knowledge graphs and natural language processing. A major issue with arbitrary graphs is the absence of canonical positional information of nodes, which decreases the representation power of GNNs to distinguish e.g. isomorphic nodes and other graph symmetries. An approach to tackle this issue is to introduce Positional Encoding (PE) of nodes, and inject it into the input layer, like in Transformers. Possible graph PE are Laplacian eigenvectors. In this work, we propose to decouple structural and positional representations to make easy for the network to learn these two essential properties. We introduce a novel generic architecture which we call LSPE (Learnable Structural and Positional Encodings). We investigate several sparse and fully-connected (Transformer-like) GNNs, and observe a performance increase for molecular datasets, from 1.79% up to 64.14% when considering learnable PE for both GNN classes.

1 INTRODUCTION

GNNs build node representations from local structure, which can leave structurally identical but positionally distinct nodes indistinguishable. The proposed MPGNNs-LSPE framework learns structural and positional representations together to improve expressiveness while retaining linear complexity.

  • Message-passing GNNs aggregate local neighborhoods, so nodes with identical neighborhoods can receive similar representations despite different molecular roles.
  • Positional encoding and deeper or higher-order architectures are proposed ways to distinguish nodes whose relevant differences lie beyond local neighborhoods.
  • MPGNNs-LSPE learns structural and positional representations simultaneously while targeting linear complexity for large-scale applications.
  • 1.79% to 64.14%: the proposed architecture improves performance when learnable positional encodings are used with sparse and Transformer-based GNNs.

2 RELATED WORK

Related work identifies limits in GNN expressivity, positional information, and long-range message passing. These limitations motivate architectures that can improve expressivity while maintaining scalable graph computation.

  • Theoretical expressivity and Weisfeiler-Leman GNNs: Message-passing GNN expressivity is bounded by the 1-WL test, limiting performance on graphs with symmetries or insufficiently discriminative message functions.
  • Graph Positional Encoding: Graph positional encoding is challenging because arbitrary graphs lack a canonical node positioning, despite positional information being central to prominent neural architectures.
  • Transformer-based GNNs: Sparse message-passing GNNs are efficient but can suffer information bottlenecks, vanishing gradients, and limited long-range interactions.
  • The paper addresses these limitations with a novel architecture reporting consistent performance gains.

3 PROPOSED ARCHITECTURE

MP-GNNs-LSPE separates structural and positional representations so both can be learned within sparse or fully connected GNNs. It initializes positional features with LapPE or RWPE, updates them across layers, and fuses them with structural features for prediction.

  • Model classes: The framework instantiates both sparse MP-GNNs and fully connected Transformer GNNs, including GatedGCN, PNA, SAN, and GraphiT variants.The generic formulation supports edge features and can specialize message passing to fully connected graphs.
  • Motivation: Existing PE-based MP-GNNs concatenate positional and structural inputs, preserving linear complexity but preventing task-adaptive positional updates.The positional representation is transformed only at initialization and then merged with node features.
  • Architecture: MP-GNNs-LSPE decouples positional and structural representations and concatenates their learned features during node updates.The architecture adds a positional update alongside the structural update, then fuses both representations.
  • Positional initialization: LapPE provides distance-sensitive node representations but requires random sign flipping because its eigenvectors have sign ambiguity.The paper embeds either LapPE or RWPE into a d-dimensional feature vector for initialization.
  • Positional initialization: RWPE uses k-step random-walk self-landing probabilities, offering a low-complexity positional representation without LapPE’s sign ambiguity.The random-walk operator is RW = AD^-1, and RWPE retains only RWii rather than the full pairwise matrix.
  • Training objective: The LSPE objective combines task loss with a Laplacian eigenvector loss that constrains final positional vectors using graph topology.The final positional vectors are centered and unit norm, with α > 0 weighting the positional loss.

4 NUMERICAL EXPERIMENTS

The experiments evaluate LSPE across sparse and Transformer GNNs on three molecular benchmarks, finding that learnable positional representations improve performance and that updating them throughout the network is beneficial.

  • Experimental setup: The evaluation covers sparse and Transformer GNNs on ZINC, OGBG-MOLTOX21, and OGBG-MOLPCBA molecular benchmarks.The datasets contain 12K, 7.8K, and 437.9K graphs, respectively.
  • Experimental setup: Models are compared under a fixed 500k-parameter protocol on ZINC, while larger model sizes are used for the OGB datasets.The reported parameter counts and layer numbers are provided with the experiments.
  • Results: No PE results in the lowest performance across all three datasets.The performance gap between models without PE and those using LapPE or LSPE is larger on ZINC than on the OGBG-MOL* datasets.
  • Architecture coverage: The LSPE architecture is demonstrated with four diverse GNNs and is presented as applicable to any MP-GNN in practice.The comparison includes both sparse and Transformer-based GNN instances.
  • Ablation studies: 0.202 to 0.122 is the performance change when replacing LapPE with first-layer random-walk positional features in the GatedGCN ablation.Injecting random-walk features at the final layer performs poorly, whereas learning positional representations at every layer gives the best performance.
  • Ablation studies: 0.093 MAE is achieved on ZINC when learned positional features are fused with structural features at the final layer.Updating positional representations reduces overfitting and improves the test score to 0.100 before final fusion.
  • Ablation studies: The best random-walk initialization step counts are k=20 for ZINC with GatedGCN-LSPE and k=16 for OGBG-MOLTOX21 with PNA-LSPE.The same k sets the final dimension of the learned positional representation.

5 CONCLUSION

LSPE separately learns structural and positional representations, combines them for graph prediction, and is presented as a generic architecture for sparse and Transformer GNNs. The work also highlights efficient learnable positional encoding and reports consistent performance increases across evaluated molecular benchmarks.

  • Conclusion: LSPE learns structural and positional representations separately and fuses them into hybrid features for the learning task.Its design uses random-walk positional features for initialization and decouples positional representations at every GNN layer.
  • Conclusion: The architecture is demonstrated with two sparse GNNs and two fully connected Transformer-based GNNs.The authors describe it as simple and universal across these GNN classes.
  • Conclusion: The experiments report consistent performance increases across several LSPE model instances on the benchmark datasets.The evaluated benchmarks are molecular datasets.
  • Conclusion: Learnable positional encoding improves graph models while preserving linear complexity with respect to the number of nodes.The paper contrasts this with approaches requiring higher-order tensor computation.
  • Scope and ethics: The proposed architecture can also be used in malicious applications because internet processes can be represented as graphs.The paper recommends setting and enforcing ethical guidelines to constrain such usage.

A.1 DISTINGUISHING NON-ISOMORPHIC GRAPHS USING RANDOM WALK FEATURES

Random-walk positional encodings (RWPE) assign node features from self-landing probabilities, helping distinguish structurally different nodes and non-isomorphic graphs that message-passing methods may conflate. The examples show this benefit for regular, symmetric, and non-regular molecular graphs.

  • RWPE initializes node i with a k-dimensional vector of its self-landing probabilities from random walks of steps 1 through k.The vector is pre-computed before model training.
  • Four random-walk steps assign distinguishable vectors to structurally different nodes in an 8-node 3-regular graph.The assigned vectors are consistent with the nodes’ structural roles.
  • Four-step RWPE gives different node features across the two symmetric CSL graphs, enabling graph distinction after pooling.The graphs use skip-links 2 and 3, respectively.
  • Five random-walk steps distinguish the non-isomorphic Decalin and Bicyclopentyl graphs that MPGNNs fail to distinguish.Both graphs are non-regular and their nodes share the same Carbon-atom attribute.
  • Unlike pairwise distance encoding, RWPE uses self-landing probabilities and avoids computing pairwise scores between nodes or node subsets.This makes the random-walk initialization less computationally demanding.

A.2 RANDOM WALK PE FEATURE AND GRAPH ISOMORPHISM TEST

RWPE can serve as a node-coloring procedure for detecting non-isomorphic graphs, including examples that 1-WL cannot distinguish. The procedure returns a definitive non-isomorphic result or otherwise reports that the graphs are possibly isomorphic.

  • RWPE node coloring compares random-walk self-landing probabilities to decide whether two graphs are non-isomorphic.It cannot guarantee that graphs reported as possibly isomorphic are truly isomorphic.
  • The procedure returns “non-isomorphic” when the graph colorings differ and “possibly isomorphic” otherwise.The input consists of two graphs with matching node and edge counts, adjacency matrices, and degree matrices.

A.3 STUDY OF LAPPE AND RWPE AS INITIAL PE

The study compares LapPE and RWPE as initial positional encodings on 1,000 ZINC validation molecules. LapPE uniquely represents every node, while RWPE gives unique representations for many, but not all, nodes and remains useful despite this limitation.

  • Figure 5 plots graph node count against unique positional-encoding count for 1,000 ZINC validation graphs.Point intensity indicates how many graphs share each node-count and unique-PE pair; LapPE uses 36 dimensions and RWPE uses 24.
  • LapPE places every graph on the diagonal because its Laplacian eigenvectors guarantee unique node coordinates in the transformed Euclidean space.The diagonal represents a unique positional encoding for every node.
  • 87.5% of nodes have unique RWPE in 30 ZINC graphs with 24 nodes and 21 unique RWPEs.Many other graphs also lie close to the diagonal, indicating substantial RWPE uniqueness.
  • Sample ZINC graphs show completely unique RWPEs in two cases and partially unique RWPEs of 71.43% and 72.22% in two others.Node colors represent unique RWPE representations.
  • RWPE uniqueness requires sufficiently large k and unique k-hop topological neighborhoods, a condition that is not always satisfied.Despite this approximation, the paper reports benefits from capturing global higher-order node positioning.

A.5 FIGURE FOR THE STUDY OF k STEPS IN RWPE (SECTION 4.3)

The cited figure studies how the choice of k affects RWPE, linking k to both random-walk depth and the learned positional-encoding dimension at the final layer.

  • The figure reports test scores for different values of k used in RWPE.
  • In RWPE, k determines the number of iterative random-walk steps.
  • The same k also determines the dimension of the learned positional encoding at the final layer.This dimension is specified by Equation 12.

C.2.1 SAN-LSPE

SAN-LSPE extends full-graph Spectral Attention Networks with learnable positional representations and separate treatment of existing and non-existing edges. Its attention balance parameter is made learnable, while GraphiT provides a related diffusion-based full-graph design.

  • SAN-LSPE: SAN operates on full graphs while separating parameters for existing and non-existing edges.An additive positive scalar γ weights the contributions from the two edge types.
  • SAN-LSPE: SAN-LSPE uses a Learnable Positional Encoding module that transforms Laplacian eigenvectors.
  • SAN-LSPE: SAN-LSPE makes the balance parameter γ learnable and clips it to the range [0, 1].This differs from SAN, where the optimal γ is computed by grid search.
  • GraphiT-LSPE: GraphiT captures topology-dependent short- and long-range interactions using a multiplicative diffusion-distance weight.Its diffusion distance is based on a p-step random-walk kernel K = (I_n − β∆)^p, with β between 0.25 and 0.50.
  • GraphiT-LSPE: GraphiT-LSPE adds learnable positional features and separate parameters for existing and complementary edges.It otherwise uses the SAN-LSPE update equation while redefining the weight score with the diffusion kernel.

D EXPERIMENTS ON NON-MOLECULAR GRAPHS

The paper evaluates LSPE with GatedGCN on three non-molecular graph-classification datasets spanning social-network and image-superpixel domains. Across all three datasets, GatedGCN-LSPE consistently outperforms the corresponding baseline models.

  • D EXPERIMENTS ON NON-MOLECULAR GRAPHS: Three non-molecular graph datasets evaluate LSPE with GatedGCN for graph classification.The datasets cover actor-collaboration social networks and CIFAR10 image superpixels.
  • D EXPERIMENTS ON NON-MOLECULAR GRAPHS: IMDB-BINARY contains 1,000 graphs with 2 genre classes, while IMDB-MULTI contains 1,500 graphs with 3 genre classes.Both are egonetworks extracted from actor collaboration graphs.
  • D EXPERIMENTS ON NON-MOLECULAR GRAPHS: CIFAR10 is a 60,000-graph superpixel dataset with 10 classes, where nodes represent image superpixels and edges encode connectivity.
  • D EXPERIMENTS ON NON-MOLECULAR GRAPHS: GatedGCN-LSPE consistently gains performance on IMDB-MULTI, IMDB-BINARY, and CIFAR10.Results are averaged over four runs with four different seeds, following the referenced evaluation protocols.

E ADDITIONAL MODEL CONFIGURATION DETAILS

The additional configuration details specify hardware, positional-encoding dimensions, diffusion-kernel hyperparameters, and learning-rate schedules for the reported models.

  • E ADDITIONAL MODEL CONFIGURATION DETAILS: Experiments used Intel Xeon E5-2690 v4 servers with four Nvidia 1080Ti GPUs, running four parallel experiments.Each GPU ran one experiment.
  • E ADDITIONAL MODEL CONFIGURATION DETAILS: The positional-encoding dimension k, or random-walk steps for RWPE, is specified among the model hyperparameters.
  • E ADDITIONAL MODEL CONFIGURATION DETAILS: For GraphiT, β and p configure the diffusion kernel, while initial and minimum learning rates define the decay schedule.The schedule uses a reduction factor and patience interval when validation performance does not improve.
  • E ADDITIONAL MODEL CONFIGURATION DETAILS: α and λ are applicable when the positional loss is used.
Loading 2110.07875v2…