2020

Can Graph Neural Networks Count Substructures?

Chen, Zhengdao, Chen, Lei, Villar, Soledad et al.

Understand

The ability to detect and count certain substructures in graphs is important for solving many tasks on graph-structured data, especially in the contexts of computational chemistry and biology as well as social network analysis.

Inspired by this, we propose to study the expressive power of graph neural networks (GNNs) via their ability to count attributed graph substructures, extending recent works that examine their power in graph isomorphism testing and function approximation.
We distinguish between two types of substructure counting: induced-subgraph-count and subgraph-count, and establish both positive and negative answers for popular GNN architectures.
Specifically, we prove that Message Passing Neural Networks (MPNNs), 2-Weisfeiler-Lehman (2-WL) and 2-Invariant Graph Networks (2-IGNs) cannot perform induced-subgraph-count of substructures consisting of 3 or more nodes, while they can perform subgraph-count of star-shaped substructures.

Built on

On the universality of invariant networks
Original
Maron, H., Fetaya, E., Segol, N., and Lipman, Y. (2019c) · 1901
Earlier work this paper cites.
A comprehensive survey on graph neural networks
Original
Wu, Z., Pan, S., Chen, F., Long, G., Zhang, C., and Yu, P. S. (2019) · 1901
Earlier work this paper cites.
Relational pooling for graph representations
Original
Murphy, R. L., Srinivasan, B., Rao, V., and Ribeiro, B. (2019) · 1903
Earlier work this paper cites.
Gnn explainer: A tool for post-hoc explanation of graph neural networks
Original
Ying, R., Bourgeois, D., You, J., Zitnik, M., and Leskovec, J. (2019) · 1903
Earlier work this paper cites.
Universal invariant and equivariant graph neural networks
Original
Keriven, N. and Peyré, G. (2019) · 1905
Earlier work this paper cites.
What graph neural networks cannot learn: depth vs width
Original
Loukas, A. (2019) · 1907
Earlier work this paper cites.
The generation of a unique machine description for chemical structures-a technique developed at chemical abstracts service
Morgan, H. L. (1965) · 1965
Earlier work this paper cites.
The reduction of a graph to canonical form and the algebra which appears therein
Weisfeiler, B. and Leman, A. (1968) · 1968
Earlier work this paper cites.
Random graph isomorphism
Babai, L., Erdos, P., and Selkow, S. M. (1980) · 1980
Earlier work this paper cites.
An optimal lower bound on the number of variables for graph identification
Cai, J.-Y., Fürer, M., and Immerman, N. (1992) · 1992
Earlier work this paper cites.
Long short-term memory
Hochreiter, S. and Schmidhuber, J. (1997) · 1997
Earlier work this paper cites.
Generating random regular graphs quickly
Steger, A. and Wormald, N. C. (1999) · 1999
Earlier work this paper cites.
Automated approaches for classifying structures
Deshpande, M., Kuramochi, M., and Karypis, G. (2002) · 2002
Earlier work this paper cites.
Composing molecules with multiple property constraints
Original
Jin, W., Barzilay, R., and Jaakkola, T. (2020) · 2002
Earlier work this paper cites.
Benchmarking graph neural networks
Original
Dwivedi, V. P., Joshi, C. K., Laurent, T., Bengio, Y., and Bresson, X. (2020) · 2003
Earlier work this paper cites.
Review of organic functional groups: introduction to medicinal organic chemistry
Lemke, T. L. (2003) · 2003
Earlier work this paper cites.
An efficient algorithm for detecting frequent subgraphs in biological networks
Koyutürk, M., Grama, A., and Szpankowski, W. (2004) · 2004
Earlier work this paper cites.
Open graph benchmark: Datasets for machine learning on graphs
Original
Hu, W., Fey, M., Zitnik, M., Dong, Y., Ren, H., Liu, B., Catasta, M., and Leskovec, J. (2020) · 2005
Earlier work this paper cites.
From graph low-rank global attention to 2-fwl approximation
Original
Puny, O., Ben-Hamu, H., and Lipman, Y. (2020) · 2006
Earlier work this paper cites.
Neural subgraph matching
Original
Lou, Z., You, J., Wen, C., Canedo, A., Leskovec, J., et al. (2020) · 2007
Earlier work this paper cites.
Biomolecular network motif counting and discovery by color coding
Alon, N., Dao, P., Hajirasouliha, I., Hormozdiari, F., and Sahinalp, S. C. (2008) · 2008
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.

Similar

The rise of fragment-based drug discovery
Murray, C. W. and Rees, D. C. (2009) · 2009
Cited alongside, same era.
Small molecule subgraph detector (smsd) toolkit
Rahman, S. A., Bashton, M., Holliday, G. L., Schrader, R., and Thornton, J. M. (2009) · 2009
Cited alongside, same era.
Efficient graphlet kernels for large graph comparison
Shervashidze, N., Vishwanathan, S., Petri, T., Mehlhorn, K., and Borgwardt, K. (2009) · 2009
Cited alongside, same era.
Finding frequent subgraphs in longitudinal social network data using a weighted graph mining approach
Jiang, C., Coenen, F., and Zito, M. (2010) · 2010
Cited alongside, same era.
From local measurements to network spectral properties: Beyond degree distributions
Preciado, V. M. and Jadbabaie, A. (2010) · 2010
Cited alongside, same era.
Zinc: a free tool to discover chemistry for biology
Irwin, J. J., Sterling, T., Mysinger, M. M., Bolstad, E. S., and Coleman, R. G. (2012) · 2012
Cited alongside, same era.
Structural analysis of viral spreading processes in social and communication networks using egonets
Preciado, V. M., Draief, M., and Jadbabaie, A. (2012) · 2012
Cited alongside, same era.
Spectral networks and locally connected networks on graphs
Original
Bruna, J., Zaremba, W., Szlam, A., and LeCun, Y. (2013) · 2013
Cited alongside, same era.
Adam: A method for stochastic optimization
Original
Kingma, D. P. and Ba, J. (2014) · 2014
Cited alongside, same era.
Quantum chemistry structures and properties of 134 kilo molecules
Ramakrishnan, R., Dral, P. O., Rupp, M., and Von Lilienfeld, O. A. (2014) · 2014
Cited alongside, same era.
Convolutional networks on graphs for learning molecular fingerprints
Duvenaud, D. K., Maclaurin, D., Iparraguirre, J., Bombarell, R., Hirzel, T., Aspuru-Guzik, A., and Adams, R. P. (2015) · 2015
Cited alongside, same era.
Batch normalization: Accelerating deep network training by reducing internal covariate shift
Original
Ioffe, S. and Szegedy, C. (2015) · 2015
Cited alongside, same era.

Then

Deep sets
Zaheer, M., Kottur, S., Ravanbakhsh, S., Poczos, B., Salakhutdinov, R. R., and Smola, A. J. (2017) · 2017
Later among the works it cites.
On weisfeiler-leman invariance: Subgraph counts and related graph properties
Original
Arvind, V., Fuhlbrück, F., Köbler, J., and Verbitsky, O. (2018) · 2018
Later among the works it cites.
Graph neural networks for icecube signal classification
Choma, N., Monti, F., Gerhardt, L., Palczewski, T., Ronaghi, Z., Prabhat, P., Bhimji, W., Bronstein, M., Klein, S., and Bruna, J. (2018) · 2018
Later among the works it cites.
Junction tree variational autoencoder for molecular graph generation
Original
Jin, W., Barzilay, R., and Jaakkola, T. S. (2018) · 2018
Later among the works it cites.
N-gram graph, A novel molecule representation
Original
Liu, S., Chandereng, T., and Liang, Y. (2018) · 2018
Later among the works it cites.
Invariant and equivariant graph networks
Maron, H., Ben-Hamu, H., Shamir, N., and Lipman, Y. (2018) · 2018
Later among the works it cites.
Motifnet: a motif-based graph convolutional network for directed graphs
Original
Monti, F., Otness, K., and Bronstein, M. M. (2018) · 2018
Later among the works it cites.
Discovering molecular functional groups using graph convolutional neural networks
Original
Pope, P., Kolouri, S., Rostrami, M., Martin, C., and Hoffmann, H. (2018) · 2018
Later among the works it cites.
Moleculenet: a benchmark for molecular machine learning
Wu, Z., Ramsundar, B., Feinberg, E. N., Gomes, J., Geniesse, C., Pappu, A. S., Leswing, K., and Pande, V. (2018) · 2018
Later among the works it cites.
Hierarchical graph representation learning with differentiable pooling
Original
Ying, R., You, J., Morris, C., Ren, X., Hamilton, W. L., and Leskovec, J. (2018) · 2018
Later among the works it cites.
Link prediction based on graph neural networks
Zhang, M. and Chen, Y. (2018) · 2018
Later among the works it cites.
Graph neural networks: A review of methods and applications
Original
Zhou, J., Cui, G., Zhang, Z., Yang, C., Liu, Z., Wang, L., Li, C., and Sun, M. (2018) · 2018
Later among the works it cites.
Cognitive graph for multi-hop reading comprehension at scale
Ding, M., Zhou, C., Chen, Q., Yang, H., and Tang, J. (2019) · 2019
Later among the works it cites.
Strategies for pre-training graph neural networks
Hu, W., Liu, B., Gomes, J., Zitnik, M., Liang, P., Pande, V., and Leskovec, J. (2019) · 2019
Later among the works it cites.
Hierarchical graph-to-graph translation for molecules
Jin, W., Barzilay, R., and Jaakkola, T. (2019) · 2019
Later among the works it cites.
Neural subgraph isomorphism counting
Liu, X., Pan, H., He, M., Song, Y., and Jiang, X. (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.
Experimental performance of graph neural networks on random instances of max-cut
Yao, W., Bandeira, A. S., and Villar, S. (2019) · 2019
Later among the works it cites.
G2sat: Learning to generate sat formulas
You, J., Wu, H., Barrett, C., Ramanujan, R., and Leskovec, J. (2019) · 2019
Later among the works it cites.
Generalization and representational limits of graph neural networks
Garg, V. K., Jegelka, S., and Jaakkola, T. (2020) · 2020
Closest in time.
A deep learning approach to antibiotic discovery
Stokes, J. M., Yang, K., Swanson, K., Jin, W., Cubillos-Ruiz, A., Donghia, N. M., MacNair, C. R., French, S., Carfrae, L. A., Bloom-Ackerman, Z., et al. (2020) · 2020
Closest in time.
Quartic graph
Weisstein, E. W. (2020) · 2020
Closest in time.

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…