Identity-aware Graph Neural Networks

ID-GNNs are the first class of message passing GNNs that have greater expressive power than 1-Weisfeiler-Lehman (1-WL) graph isomorphism test. ID-GNNs offer consistent performance gains over existing GNNs on node, edge and graph level tasks.

Motivation

Messaging passing GNNs (MP-GNNs), such as GCN, GraphSAGE, and GAT, are dominantly used today due to their simplicity, efficiency and strong performance in real-world applications. The central idea behind message passing GNNs is to learn meaningful node embeddings via the repeated aggregation of information from local node neighborhoods using non-linear transformations.
However, it has been shown that the expressive power of existing MP-GNNs is upper-bounded by the 1-Weisfeiler-Lehman (1-WL) test. Concretely, a fundamental limitation of existing MP-GNNs is that two nodes with different neighborhood structure can have the same computational graph, thus appearing indistinguishable. As is shown in the figure below, such failure cases are abundant: in node classification tasks, existing GNNs fail to distinguish nodes that reside in $d$-regular graphs of different sizes; in link prediction tasks, they cannot differentiate node candidates with the same neighborhood structures but different shortest path distance to the source node; and in graph classification tasks, they cannot differentiate $d$-regular graphs.




Figure 1: Overview of the proposed ID-GNN model. Across all examples, the task requires an embedding that allows for the differentiation of the label $A$ vs. $B$ nodes in their respective graphs. However, across all tasks, existing GNNs, regardless of depth, will always assign the same embedding to both classes of nodes, because for all tasks the computational graphs are identical. In contrast, the colored computation graphs provided by ID-GNNs allows for clear differentiation between the nodes of class $A$ and class $B$

Method

We propose two versions of ID-GNNs.


Key Results

We compare ID-GNNs against GNNs across 8 datasets and 6 different tasks.

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

Code and Datasets

We implement ID-GNN using the GraphGym platform on GitHub. The datasets are included in the code repository.

Contributors

The following people contributed to P-GNNs:
Jiaxuan You
Jonathan Gomes-Selman
Rex Ying
Jure Leskovec

References

Identity-aware Graph Neural Networks. J. You, J. Gomes-Selman, R. Ying, J. Leskovec. AAAI Conference on Artificial Intelligence (AAAI), 2021.