2021

Identity-aware Graph Neural Networks

You, Jiaxuan, Gomes-Selman, Jonathan, Ying, Rex et al.

Understand

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.

Built on

Spline-fitting with a genetic algorithm: A method for developing classification structure- activity relationships
Sutherland, J. J.; O’brien, L. A.; and Weaver, D. F. 2003 · 1915
Earlier work this paper cites.
Multilayer feedforward networks are universal approximators
Hornik, K.; Stinchcombe, M.; White, H.; et al. 1989 · 1989
Earlier work this paper cites.
Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds. correlation with molecular orbital energies and hydrophobicity
Debnath, A. K.; Lopez de Compadre, R. L.; Debnath, G.; Shusterman, A. J.; and Hansch, C. 1991 · 1991
Earlier work this paper cites.
Collective dynamics of ‘small-world’networks
Watts, D. J.; and Strogatz, S. H. 1998 · 1998
Earlier work this paper cites.
A survey of the predictive toxicology challenge 2000–2001
Helma, C.; and Kramer, S. 2003 · 2001
Earlier work this paper cites.
Growing scale-free networks with tunable clustering
Holme, P.; and Kim, B. J. 2002 · 2002
Earlier work this paper cites.
BRENDA, the enzyme database: updates and major new developments
Schomburg, I.; Chang, A.; Ebeling, C.; Gremse, M.; Heldt, C.; Huhn, G.; and Schomburg, D. 2004 · 2004
Earlier work this paper cites.
Protein function prediction via graph kernels
Borgwardt, K. M.; Ong, C. S.; Schönauer, S.; Vishwanathan, S.; Smola, A. J.; and Kriegel, H.-P. 2005 · 2005
Earlier work this paper cites.
Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting
Original
Bouritsas, G.; Frasca, F.; Zafeiriou, S.; and Bronstein, M. M. 2020 · 2006
Earlier work this paper cites.
The graph neural network model
Scarselli, F.; Gori, M.; Tsoi, A. C.; Hagenbuchner, M.; and Monfardini, G. 2008 · 2008
Earlier work this paper cites.
Collective classification in network data
Sen, P.; Namata, G.; Bilgic, M.; Getoor, L.; Galligher, B.; and Eliassi-Rad, T. 2008 · 2008
Earlier work this paper cites.
Opinion fraud detection in online reviews by network effects
Akoglu, L.; Chandy, R.; and Faloutsos, C. 2013 · 2013
Earlier work this paper cites.
Anomaly, event, and fraud detection in large network datasets
Akoglu, L.; and Faloutsos, C. 2013 · 2013
Earlier work this paper cites.

Similar

Gated graph sequence neural networks
Li, Y.; Tarlow, D.; Brockschmidt, M.; and Zemel, R. 2016 · 2016
Cited alongside, same era.
Residual gated graph convnets
Original
Bresson, X.; and Laurent, T. 2017 · 2017
Cited alongside, same era.
Inductive representation learning on large graphs
Hamilton, W.; Ying, Z.; and Leskovec, J. 2017 · 2017
Cited alongside, same era.
Semi-supervised classification with graph convolutional networks
Kipf, T. N.; and Welling, M. 2017 · 2017
Cited alongside, same era.
Antisocial behavior on the web: Characterization and detection
Kumar, S.; Cheng, J.; and Leskovec, J. 2017 · 2017
Cited alongside, same era.
Geometric deep learning on graphs and manifolds using mixture model cnns
Monti, F.; Boscaini, D.; Masci, J.; Rodola, E.; Svoboda, J.; and Bronstein, M. M. 2017 · 2017
Cited alongside, same era.
Predicting multicellular function through multi-layer tissue networks
Zitnik, M.; and Leskovec, J. 2017 · 2017
Cited alongside, same era.
Relational inductive biases, deep learning, and graph networks
Original
Battaglia, P. W.; Hamrick, J. B.; Bapst, V.; Sanchez-Gonzalez, A.; Zambaldi, V.; Malinowski, M.; Tacchetti, A.; Raposo, D.; Santoro, A.; Faulkner, R.; et al. 2018 · 2018
Cited alongside, same era.
Junction tree variational autoencoder for molecular graph generation
Jin, W.; Barzilay, R.; and Jaakkola, T. 2018 · 2018
Cited alongside, same era.
Covariant compositional networks for learning graphs
Original
Kondor, R.; Son, H. T.; Pan, H.; Anderson, B.; and Trivedi, S. 2018 · 2018
Cited alongside, same era.
Graph attention networks
Velickovic, P.; Cucurull, G.; Casanova, A.; Romero, A.; Lio, P.; and Bengio, Y. 2018 · 2018
Cited alongside, same era.
Graph Convolutional Neural Networks for Web-Scale Recommender Systems
Ying, R.; He, R.; Chen, K.; Eksombatchai, P.; Hamilton, W. L.; and Leskovec, J. 2018 · 2018
Cited alongside, same era.

Then

Retgk: Graph kernels based on return probabilities of random walks
Zhang, Z.; Wang, M.; Xiang, Y.; Huang, Y.; and Nehorai, A. 2018 · 2018
Later among the works it cites.
On the equivalence between graph isomorphism testing and function approximation with gnns
Chen, Z.; Villar, S.; Chen, L.; and Bruna, J. 2019 · 2019
Later among the works it cites.
Graph neural networks for social recommendation
Fan, W.; Ma, Y.; Li, Q.; He, Y.; Zhao, E.; Tang, J.; and Yin, D. 2019 · 2019
Later among the works it cites.
Weisfeiler and leman go neural: Higher-order graph neural networks
Morris, C.; Ritzert, M.; Fey, M.; Hamilton, W. L.; Lenssen, J. E.; Rattan, G.; and Grohe, M. 2019 · 2019
Later among the works it cites.
Relational pooling for graph representations
Murphy, R. L.; Srinivasan, B.; Rao, V.; and Ribeiro, B. 2019 · 2019
Later among the works it cites.
How Powerful are Graph Neural Networks?
Xu, K.; Hu, W.; Leskovec, J.; and Jegelka, S. 2019 · 2019
Later among the works it cites.
GNNExplainer: Generating explanations for graph neural networks
Ying, Z.; Bourgeois, D.; You, J.; Zitnik, M.; and Leskovec, J. 2019 · 2019
Later among the works it cites.
Position-aware graph neural networks
You, J.; Ying, R.; and Leskovec, J. 2019 · 2019
Later among the works it cites.
Open Graph Benchmark: Datasets for Machine Learning on Graphs
Hu, W.; Fey, M.; Zitnik, M.; Dong, Y.; Ren, H.; Liu, B.; Catasta, M.; and Leskovec, J. 2020 · 2020
Later among the works it cites.
Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning
Li, P.; Wang, Y.; Wang, H.; and Leskovec, J. 2020 · 2020
Later among the works it cites.
Neural execution of graph algorithms
Veličković, P.; Ying, R.; Padovano, M.; Hadsell, R.; and Blundell, C. 2020 · 2020
Later among the works it cites.
What Can Neural Networks Reason About?
Xu, K.; Li, J.; Zhang, M.; Du, S. S.; Kawarabayashi, K.-i.; and Jegelka, S. 2020 · 2020
Later among the works it cites.
Design Space for Graph Neural Networks
You, J.; Ying, R.; and Leskovec, J. 2020 · 2020
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…