Position-aware Graph Neural Networks

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.Source: §1 · p. 1

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.Source: §1 · p. 1

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.Source: §1 · p. 2

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.Source: §1 · p. 2

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.Source: §1 · p. 2

Approaches

• Node-embedding approaches include GNNs, matrix factorization, random walks, and graph kernels.Source: §2 · p. 2

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.Source: §2 · p. 2

Graph kernels

• Graph kernels capture structural properties or shortest-path relationships by mapping graphs or shared walks into kernel spaces.Source: §2 · pp. 2–3

Notation

• A graph is represented as G = (V, E), optionally augmented with node features X = {x1, ..., xn}.Source: §3.1 · p. 3
• Node embedding models map nodes to low-dimensional vectors that can be supplied to a classifier for graph prediction.Source: §3.1 · p. 3

Position-aware embeddings

• Position-aware embeddings allow a function to recover shortest-path distance dsp(vi, vj) from embeddings zi and zj.Source: §3.2 · p. 3

Structure-aware embeddings

• Structure-aware embeddings depend on a node’s q-hop neighborhood, as in message-passing GNNs that aggregate local information.Source: §3.2 · p. 3

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.Source: §3.2 · p. 3
• 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.Source: §3.2 · p. 3
• In real-world graphs, common structural equivalences make node identification difficult, and a learned mapping may fail to generalize to new graphs.Source: §3.2 · p. 3

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.Source: §4.1 · p. 3, §4 · p. 3
• 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.Source: §4.1 · p. 3, §4.3 · p. 5
• 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.Source: §4.1 · p. 4, Figure 2 · p. 4

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.Source: §4.1 · p. 4

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.Source: §4.2 · pp. 4–5

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.Source: §4.3 · p. 5

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.Source: §5.1 · p. 6, §5.2 · p. 6

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.Source: §5.2 · p. 6
• 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.Source: §5.2 · pp. 6–7

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.Source: §5.3 · p. 7

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.Source: §6.1 · p. 7

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.Source: §6.2 · p. 7

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.Source: §6.3 · pp. 7–8

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.Source: §6.4 · p. 8

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.Source: §6.4 · p. 8

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.Source: §6.4 · p. 8

• P-GNNs compute node embeddings that incorporate positional information while retaining inductive capability and utilizing node features.Source: §7 · p. 8
• P-GNNs consistently outperform existing GNNs across a variety of tasks and datasets.Source: §7 · p. 8