Position-aware Graph Neural Networks

By Jiaxuan You, Rex Ying, Jure Leskovec. 2019

580 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Information Systems, Model Architectures, Graph Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Information Systems

In Model Architectures

In Graph Learning

Citations in the corpus

Strategies for Pre-training Graph Neural Networks (2019, background): “This, however, can be sub-optimal for graph-level prediction tasks, where capturing structural similarity of local neighborhoods is often more important than capturing the positional information of nodes within a graph (You et al., 2019; Rogers & Hahn, 2010; Yang et al., 2014).”
Parameter Prediction for Unseen Deep Architectures (2021, methodology): “Instead we adopt simple graph-based heuristics in line with recent works [64, 65].”
Utilizing graph machine learning within drug discovery and development (2021, methodology): “using contrastive approaches [31, 237], by augmenting the framework with relative positioning to anchor nodes [238, 239], or by”
A Generalization of Transformer Networks to Graphs (2020, background): “…et al. 2020), or node Laplacian position eigenvectors (Belkin and Niyogi 2003; Dwivedi et al. 2020), or relative learnable positional information (You, Ying, and Leskovec 2019), virtual nodes (Li et al. 2015), etc. Zhang et al. (2020) propose Graph-BERT with an emphasis on pre-a training and…”
Principal Neighbourhood Aggregation for Graph Nets (2020, background): “The graph property tasks consist of a range of individual properties for each node and global properties of the entire graph.”
AM-GCN: Adaptive Multi-channel Graph Convolutional Networks (2020, background): “Recently, Graph Convolutional Networks (GCNs), a class of neural networks designed to learn graph data, have shown great popularity in tackling graph analytics problems, such as node classification [1, 31], graph classification [7, 37], link prediction [13, 36] and recommendation [6, 34].”
Machine Learning on Graphs: A Model and Comprehensive Taxonomy (2020, background): “While these data-driven methods are still outperformed by existing solvers, promising results show that GNNs can generalize to larger problem instances [85].”
Structure-Aware Transformer for Graph Representation Learning (2022, methodology): “, 2022), while distance-based methods include distances to a predefined set of nodes (You et al., 2019) and shortest path distances between pairs of nodes (Zhang et al.”
How Powerful are Spectral Graph Neural Networks (2022, background): “Since then, various works attempt to analyze GNNs with the WL tests and graph isomorphism testing (Morris et al., 2019; Maron et al., 2019a; Chen et al., 2019; You et al., 2019; Li et al., 2020; Sato et al., 2019; Zhang & Chen, 2018; Sato et al., 2021).”
Graph Information Bottleneck (2020, unknown): “Recently, many works have been focusing on developing more powerful GNNs [8–13], in a sense that they can fit more complex graph-structured data.”
GNNExplainer: Generating Explanations for Graph Neural Networks (2019, background): “…Convolutional Networks [21], Gated Graph Sequence Neural Networks [26], Jumping Knowledge Networks [36], Attention Networks [33], Graph Networks [4], GNNs with various node aggregation schemes [7, 5, 18, 16, 40, 39, 35], Line-Graph NNs [8], position-aware GNN [42], and many other GNN architectures.”
Language-Agnostic Representation Learning of Source Code from Structure and Context (2021, methodology): “On the other hand, models leveraging the structure representations are typically based on graph neural networks (GNNs) (Kipf & Welling, 2017; Xu et al., 2019; Veliˇckovi´c et al., 2018; You et al., 2019; Hamilton et al., 2017; Li et al., 2015; Klicpera et al., 2020).”
Open Graph Benchmark: Datasets for Machine Learning on Graphs (2020, background): “The poor training performance of GNNs suggests that positional information, which cannot be captured by GNNs alone (You et al., 2019), might be crucial to ﬁt training edges and obtain meaningful node embeddings.”
HGNN+: General Hypergraph Neural Networks (2022, background): “Spatial-based approaches [1], [3], [15], [16] are formulated as aggregating messages from neighbor vertices, and the convolution operation is deﬁned in groups of spatially closed vertices.”
GraphSAIL: Graph Structure Aware Incremental Learning for Recommender Systems (2020, background): “This is a general limitation of the majority of GNN models [21, 30].”
MAGNN: Metapath Aggregated Graph Neural Network for Heterogeneous Graph Embedding (2020, background): “Node2vec is expected to perform strongly in the node clustering task because, being a random-walk-based approach, it forces nodes that are close in the graph also to be close in the embedding space [33], and thereby encodes node positional information.”