Graph Inference Representation: Learning Graph Positional Embeddings with Anchor Path Encoding

Yuheng Lu, Jinpeng Chen, Chuxiong Sun, Jie Hu

Abstract

Learning node representations that incorporate information from graph structure benefits a wide range of tasks on graphs. The majority of existing graph neural networks (GNNs) have limited power in capturing position information for a given node. The idea of positioning nodes with selected anchors has been exploited, yet mainly relying on explicit labeling of distance information. Here we propose Graph Inference Representation (GIR), an anchor-based GNN model encoding path information related to pre-selected anchors for each node. Abilities to get position-aware embeddings are theoretically and experimentally investigated on GIR and its core variants. Further, the complementarity between GIRs and typical GNNs is demonstrated. We show that GIRs get outperformed results in position-aware scenarios, and performances on typical GNNs could be improved by fusing GIR embeddings.

Introduction

Standard Graph Neural Networks (GNNs) typically follow a message-passing paradigm where a node's representation is iteratively updated by aggregating features from its immediate neighborhood. While highly effective for capturing local structural patterns, this approach suffers from a fundamental "position-blind" limitation. Specifically, if two nodes reside in different parts of a graph but possess identical local neighborhood structures—a phenomenon known as topological symmetry—a standard GNN will assign them identical embeddings.

Illustration of the position-blind flaw in standard GNNs where nodes 3 and 4 have identical message passing trees.

As illustrated in the figure above, nodes 3 and 4 have isomorphic computation trees despite their distinct global positions. In real-world applications, such as identifying central hubs in transportation networks or predicting links in social graphs, global position is often as critical as local connectivity. Existing anchor-based methods attempt to address this by calculating distances to reference nodes, but these often require explicit distance labels and can be computationally expensive or unstable.

Methodology: Graph Inference Representation (GIR)

To overcome these limitations, we introduce Graph Inference Representation (GIR). Unlike traditional GNNs that aggregate from all neighbors indiscriminately, GIR explicitly encodes path information relative to a set of pre-selected anchor nodes.

Anchor Selection and Path Encoding

The model utilizes the GA-MPCA algorithm to select anchors based on degree centrality and graph coverage, ensuring they are both influential and well-distributed across the graph. The core innovation lies in the path-constrained message passing: the $k$-th layer of a GIR model only processes messages along edges that are exactly $k$ steps away from an anchor. This mechanism effectively "labels" nodes based on their distance and connectivity to specific anchors, breaking structural symmetries.

Model Variants

We explore several variants to enhance precision:

  • GIR-MIX: Employs multiple sets of anchors to establish a more robust, multi-dimensional coordinate system.
  • GIR-A: Incorporates one-hot labeling for anchors, enabling the model to distinguish the specific origin of each message.

Multi-modal Fusion (GCN-GIR)

Recognizing that standard GNNs excel at local structure while GIR excels at global positioning, we propose a "Mixture of Experts" (MoE) framework. A gating network dynamically weights the structural embeddings (from a GCN) and positional embeddings (from GIR) for each node, allowing the model to leverage the most relevant information for a given task.

Experiments and Results

The GIR framework was evaluated across diverse benchmarks, ranging from small position-sensitive graphs to large-scale citation networks.

Position-Aware Performance

On datasets where location is critical—such as Email (communication), Europe/USA (flight networks), and PB (political blogs)—GIR variants significantly outperformed standard GCNs. In tasks like link prediction on the PB dataset, GIR-A and GIR-O nearly doubled the accuracy of traditional models, demonstrating the power of explicit positional encoding.

Large-Scale Benchmarking

On the ogbn-arxiv dataset, a massive citation network with over 170,000 nodes, the fused GCN-GIR model achieved an accuracy of 72.72%. This result outperformed standalone 3-layer and 5-layer GCNs, validating that positional information remains valuable even in large, complex graphs.

Expert Complementarity

A key insight from our analysis is the "Expert Complementarity" (EC) between GIR and traditional Message Passing Neural Networks (MPNNs). Our metrics confirm that GIR learns fundamentally different features than standard GNNs. This diversity justifies the fusion strategy, as the two models provide complementary perspectives on the graph's topology.

Conclusion and Future Work

GIR provides a theoretically grounded method for incorporating positional awareness into GNNs without relying on explicit distance labels. By breaking symmetry through path truncation, it achieves superior performance on position-dependent tasks.

However, some challenges remain. Variants like GIR-A are currently transductive, making it difficult to generalize to new nodes added post-training. Additionally, performance is sensitive to the anchor selection heuristic. Future research will focus on developing inductive positional embeddings and exploring more sophisticated reachability metrics beyond simple shortest-path distances.

Summary updated

Abstract

Learning node representations that incorporate information from graph structure benefits wide range of tasks on graph. The majority of existing graph neural networks (GNNs) have limited power in capturing position information for a given node. The idea of positioning nodes with selected anchors has been exploited, yet mainly relying on explicit labeling of distance information. Here we propose Graph Inference Representation (GIR), an anchor based GNN model encoding path information related to pre-selected anchors for each node. Abilities to get position-aware embeddings are theoretically and experimentally investigated on GIR and its core variants. Further, the complementarity between GIRs and typical GNNs is demonstrated. We show that GIRs get outperformed results in position-aware scenarios, and performances on typical GNNs could be improved by fusing GIR embeddings.
BibTeX
@misc{lu2021graph,
  author = {Yuheng Lu and Jinpeng Chen and Chuxiong Sun and Jie Hu},
  title = {{Graph Inference Representation: Learning Graph Positional Embeddings with Anchor Path Encoding}},
  year = {2021},
  eprint = {2105.03821},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2105.03821},
}
Figure