Source-linked AI summary
Position-aware Graph Neural Networks
Jiaxuan You, Rex Ying, Jure Leskovec
TL;DR
Existing GNNs have limited ability to capture nodes’ positions within the broader graph, despite positional information being important for graph prediction. P-GNNs address this by aggregating distance-weighted information from sampled anchor-sets while retaining inductive and feature-aware capabilities, and they consistently outperform existing GNNs across varied tasks and datasets.
Problem
Existing GNN embeddings may fail to recover shortest-path distances and therefore cannot reliably capture global node position when local neighborhoods are structurally equivalent.
Method
P-GNNs sample anchor-sets, compute target-to-anchor-set distances, and learn nonlinear distance-weighted aggregation of information from those sets.
Results
P-GNNs consistently outperform existing GNNs across varied tasks and datasets, with up to 66% AUC score improvement.
Takeaways & Limitations
P-GNNs provide position-aware node embeddings while retaining inductive capability and the ability to use node features.
Takeaways & Limitations
Structure-aware embeddings may not generalize to new graphs when their mapping memorizes shortest-path distances for nodes with unique local neighborhoods.
Abstract
from arXiv · showhide
Learning node embeddings that capture a node's position within the broader graph structure is crucial for many prediction tasks on graphs. However, existing Graph Neural Network (GNN) architectures have limited power in capturing the position/location of a given node with respect to all other nodes of the graph. Here we propose Position-aware Graph Neural Networks (P-GNNs), a new class of GNNs for computing position-aware node embeddings. P-GNN first samples sets of anchor nodes, computes the distance of a given target node to each anchor-set,and then learns a non-linear distance-weighted aggregation scheme over the anchor-sets. This way P-GNNs can capture positions/locations of nodes with respect to the anchor nodes. P-GNNs have several advantages: they are inductive, scalable,and can incorporate node feature information. We apply P-GNNs to multiple prediction tasks including link prediction and community detection. We show that P-GNNs consistently outperform state of the art GNNs, with up to 66% improvement in terms of the ROC AUC score.
1. Introduction
Existing GNNs capture local structure but can miss a node’s broader graph position, motivating P-GNNs, which use anchor-set distances for position-aware embeddings. Across eight datasets and multiple tasks, P-GNNs consistently outperform state-of-the-art GNN variants, with up to 66% AUC improvement.
- Motivation: GNNs aggregate neighborhood information efficiently and inductively, but their local focus can assign identical embeddings to nodes in different graph regions.Nodes with isomorphic neighborhoods remain indistinguishable without node features.
- Contribution: P-GNNs compute node embeddings that incorporate positional information relative to all other nodes while retaining inductive capability and node features.The approach extends GNNs with position-aware aggregation rather than relying only on local neighborhoods.
- Method: P-GNN samples k anchor-sets and learns nonlinear aggregation of node features weighted by distances from the target node to those sets.Bourgain’s theorem indicates that k = O(log2 n) anchor-sets can preserve graph distances with low distortion.
- Scalability: P-GNNs support inductive computation across node orderings and graphs, and P-GNN-Fast retains P-GNN benefits with traditional GNN computational complexity.Approximate node-distance computation addresses the cost of distances in large-scale applications.
- Empirical results: 66% AUC score improvement is achieved at most as P-GNNs consistently outperform state-of-the-art GNN variants across eight datasets and several prediction tasks.Evaluated tasks include link prediction and community detection.
2. Related Work
Prior node-embedding methods include GNN, matrix-factorization, random-walk, and graph-kernel approaches. GNNs are efficient and inductive, whereas common positional heuristics may sacrifice scalability or generalization to unseen graphs.
- Approaches: Node-embedding approaches include GNNs, matrix factorization, random walks, and graph kernels.
- Positional heuristics: Unique-node-identifier heuristics are not scalable and cannot generalize to unseen graphs without a canonical node ordering.P-GNNs are presented as capturing positional information without sacrificing GNN advantages.
- Graph kernels: Graph kernels capture structural properties or shortest-path relationships by mapping graphs or shared walks into kernel spaces.
3. Preliminaries
The paper distinguishes structure-aware embeddings, derived from local neighborhoods, from position-aware embeddings, which preserve shortest-path information. Structure-aware embeddings cannot generally recover position unless local neighborhoods uniquely identify all nodes, a condition often violated in real-world graphs.
- Notation: A graph is represented as G = (V, E), optionally augmented with node features X = {x1, ..., xn}.
- Notation: Node embedding models map nodes to low-dimensional vectors that can be supplied to a classifier for graph prediction.
- Position-aware embeddings: Position-aware embeddings allow a function to recover shortest-path distance dsp(vi, vj) from embeddings zi and zj.
- Structure-aware embeddings: Structure-aware embeddings depend on a node’s q-hop neighborhood, as in message-passing GNNs that aggregate local information.
- Limitation: Structure-aware embeddings are insufficient for positional tasks because they cannot generally be mapped to embeddings that recover node positions.Such tasks include link prediction and community detection.
- Limitation: A mapping from structure-aware to position-aware embeddings exists if and only if no pair of nodes has isomorphic local q-hop neighborhood graphs.
- Limitation: In real-world graphs, common structural equivalences make node identification difficult, and a learned mapping may fail to generalize to new graphs.
4. Proposed Approach
P-GNNs extend GNNs by aggregating feature-aware messages from shared, randomly sampled anchor-sets, using node-to-anchor distances to produce position-aware embeddings. The framework uses stacked layers, permutation-invariant aggregation, and Bourgain-theorem-guided anchor selection to preserve graph distances with low distortion.
- Framework: P-GNNs aggregate messages from randomly chosen anchor-sets rather than only a node’s local neighborhood, coupling aggregation across nodes through shared anchors.Anchor-sets are resampled on each forward pass.
- Framework: Each anchor-set message combines two nodes’ feature information with their network distance, then aggregation functions transform messages within and across anchor-sets.The framework defines AGGM for within-anchor-set aggregation and AGGS for aggregation across anchor-sets.
- Framework: P-GNN layers compute one embedding dimension per anchor-set by applying F, AGGM, a learned projection vector w, and a non-linear transformation.The resulting structure-aware message hv is passed to the next P-GNN layer, while zv is the position-aware output.
- Position-aware embeddings: P-GNN embeddings encode positional information relative to anchor-sets, allowing structurally equivalent nodes in different graph locations to be distinguished.Embedding dimensions may be permuted globally without changing the positional information they carry.
- Anchor-set selection: Bourgain-theorem-based selection uses k = O(log2 n) anchor-sets to obtain low-distortion distance representations.The constructive strategy uses random anchor-sets and generalizes the distance metric through F and AGGM to incorporate node features.
- Design decisions: P-GNNs use q-hop shortest-path distance to reduce the cost of position computation, transforming distance with s(v, u) = 1/(d_sp(v,u)+1).One-hop distance can be obtained directly from the adjacency matrix; feature information can be combined with position information through F.
5. Theoretical Analysis of P-GNNs
The theoretical analysis places P-GNNs in a more general inductive framework than traditional GNNs by coupling node representations through distances to shared anchors. This supports greater expressive power for learning both structure-aware and position-aware embeddings, while incurring higher communication complexity.
- Generalization: P-GNNs generalize existing GNNs by using shared random anchor-sets, whereas traditional GNNs rely on local-neighborhood aggregation or independently sampled size-1 anchor-sets.Deterministic GNNs correspond to individual-node anchor-sets with q-hop aggregation, and GraphSAGE corresponds to independently sampled size-1 anchor-sets.
- Expressive power: P-GNNs provide a more general inductive bias for learning both structure-aware and position-aware node embeddings.The framework is motivated by pairwise relation prediction, including links and community membership as possible target similarities.
- Expressive power: P-GNNs learn node embeddings from the joint distribution of distances to common anchors, yielding greater expressive power than existing GNNs.The analysis states I(Y; X_joint) ≥ I(Y; X_marginal) for the target pairwise relation variable Y.
- Complexity: P-GNN communication requires O(mn log2 n) messages when anchor-sets average m nodes, compared with O(n + e) for existing GNNs.Following exact anchor-set selection gives O(n2 log2 n) complexity.
6. Experiments
Experiments evaluate P-GNNs against GNN baselines across link prediction and pairwise node classification in transductive and inductive settings. P-GNNs generally achieve stronger performance, especially when positional information is important.
- Datasets and tasks: Experiments use synthetic and real datasets for link prediction, community detection, and role-equivalence prediction.The datasets include Grid, Communities, PPI, Emails, and Protein graphs.
- Evaluation settings: P-GNNs are evaluated in both transductive and inductive learning settings, with order-invariant attributes used for inductive evaluation.Inductive experiments use separate graphs for training and testing when multiple graphs are available.
- Baseline models: P-GNN variants are compared fairly with GCN, GraphSAGE, GAT, and GIN using similar parameter counts, training epochs, and fixed configurations.The P-GNN variants differ by layer count and by truncated versus exact shortest-path distances.
- Link prediction: 66% AUC improvement is achieved by P-GNNs over the best GNN on inductive link prediction in the Grid dataset.Across link-prediction datasets and variants, P-GNNs significantly outperform GNNs; transductive performance is comparable.
- Results: P-GNN-F, which truncates shortest-distance computation at 2 hops, achieves comparable results in many datasets.This provides a faster variant while retaining similar empirical performance in many settings.
- Pairwise node classification: 56% relative ROC AUC improvement is achieved on Communities, where P-GNN variants nearly perfectly detect memberships while the best GNN reaches 0.620 ROC AUC.Improvements are also reported on Email and Protein, at 18% and 39%, respectively.
7. Conclusion
The paper proposes P-GNNs for position-aware node embeddings while retaining inductive capability and using node features. Across varied tasks and datasets, P-GNNs consistently outperform existing GNNs.
- P-GNNs compute node embeddings that incorporate positional information while retaining inductive capability and utilizing node features.
- P-GNNs consistently outperform existing GNNs across a variety of tasks and datasets.