Identity-aware Graph Neural Networks

Abstract/Contents

Abstract

Message passing Graph Neural Networks (GNNs) provide a powerful modeling framework for relational data. However, the expressive power of existing GNNs is upper-bounded by the 1-Weisfeiler-Lehman (1-WL) graph isomorphism test, which means GNNs that are not able to predict node clustering coefficients and shortest path distances, and cannot differentiate between different d-regular graphs. Here we develop a class of message passing GNNs, named Identity-aware Graph Neural Networks (ID-GNNs), with greater expressive power than the 1-WL test. ID-GNN offers a minimal but powerful solution to limitations of existing GNNs. ID-GNN extends existing GNN architectures by inductively considering nodes’ identities during message passing. To embed a given node, ID-GNN first extracts the ego network centered at the node, then conducts rounds of heterogeneous message passing, where different sets of parameters are applied to the center node than to other surrounding nodes in the ego network. We further propose a simplified but faster version of ID-GNN that injects node identity information as augmented node features. Altogether, both versions of ID-GNN represent general extensions of message passing GNNs, where experiments show that transforming existing GNNs to ID-GNNs yields on average 40% accuracy improvement on challenging node, edge, and graph property prediction tasks; 3% accuracy improvement on node and graph classification benchmarks; and 15% ROC AUC improvement on real-world link prediction tasks. Additionally, ID-GNNs demonstrate improved or comparable performance over other task-specific graph networks.

Description

Type of resource	text
Date created	2020

Creators/Contributors

Author	Gomes-Selman, Jonathan Michael
Degree granting institution	Stanford University, Department of Electrical Engineering
Primary advisor	Leskovec, Jure
Advisor	Ermon, Stefano
Contributing author	You, Jiaxuan

Subjects

Subject	Computer Science
Subject	Artificial Intelligence
Subject	Deep Learning
Subject	Graph Neural Networks
Subject	School of Engineering
Subject	Machine Learning
Subject	Graph-based Machine Learning
Subject	ML: Relational Learning
Subject	ML: Representation Learning
Subject	ID-GNN
Subject	GNNs
Subject	GNN Expressive Power
Genre	Thesis

Bibliographic information

Related item	Title Proceedings of the AAAI Conference on Artificial Intelligence Title Arxiv
Location	https://purl.stanford.edu/gp940rz7480

Access conditions

Use and reproduction

User agrees that, where applicable, content will not be used to identify or to otherwise infringe the privacy or confidentiality rights of individuals. Content distributed via the Stanford Digital Repository may be subject to additional license and use restrictions applied by the depositor.

License

This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).

Preferred citation

Preferred Citation

Gomes-Selman, Jonathan Michael. (2020). Identity-aware Graph Neural Networks. Stanford Digital Repository. Available at: https://purl.stanford.edu/gp940rz7480

Collection

Undergraduate Theses, School of Engineering

View other items in this collection in SearchWorks

Contact information

Contact

jgs8@cs.stanford.edu

Also listed in

View in SearchWorks

Loading usage metrics...