Position-aware Graph Neural Networks

P-GNNs are a family of models that are provably more powerful than GNNs in capturing nodes' positional information with respect to the broader context of a graph. It can achieve superior performance in link prediction and pairwise node classification tasks.

Motivation

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.

For example, if two nodes reside in very different parts of the graph but have topologically the same (local) neighbourhood structure, they will have identical GNN structure. Therefore, GNNs will embed them to the same point in the embedding space (we ignore node attributes for now). This issue of GNNs is illustrated in the figure below.


The key insight of P-GNN is that node position can be captured by quantifying the distance between a given node and a set of "anchor-sets". Specifically, P-GNN uses a sampling strategy with theoretical guarantees to choose k random subsets of nodes called anchor-sets. To compute a node’s embedding, P-GNN first samples multiple anchor-sets in each forward pass, then learns a non-linear aggregation scheme that combines node feature information from each anchor-set and weighs it by the distance between the node and the anchor-set. Such aggregations can be naturally chained and combined into multiple layers to enhance model expressiveness. The framework of P-GNN is illustrated in the figure below.


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. An illustrative exmaple of embedding 2 graphs is shown below.


Please refer to our paper for detailed explanations and more results.

Code

A reference implementation of P-GNNs in Python is available on GitHub.

Datasets

The datasets used by P-GNNs are included in the code repository.

Contributors

The following people contributed to node2vec:
Jiaxuan You
Rex Ying
Jure Leskovec

References

Position-aware Graph Neural Networks. J. You, R. Ying, J. Leskovec. International Conference on Machine Learning (ICML), 2019.