2020

Evaluating Logical Generalization in Graph Neural Networks

Sinha, Koustuv, Sodhani, Shagun, Pineau, Joelle et al.

Understand

Recent research has highlighted the role of relational inductive biases in building learning agents that can generalize and reason in a compositional manner.

However, while relational learning algorithms such as graph neural networks (GNNs) show promise, we do not understand how effectively these approaches can adapt to new tasks.
In this work, we study the task of logical generalization using GNNs by designing a benchmark suite grounded in first-order logic.
Our benchmark suite, GraphLog, requires that learning algorithms perform rule induction in different synthetic logics, represented as knowledge graphs.

Built on

On the role of scientific thought
Dijkstra, E. W · 1982
Earlier work this paper cites.
Applications of machine learning and rule induction
Langley, P. and Simon, H. A · 1995
Earlier work this paper cites.
Wordnet: a lexical database for english
Miller, G. A · 1995
Earlier work this paper cites.
Long short-term memory
Hochreiter, S. and Schmidhuber, J · 1997
Earlier work this paper cites.
The role of relational reasoning in children’s addition concepts
Farrington-Flint, L., Canobi, K. H., Wood, C., and Faulkner, D · 2007
Earlier work this paper cites.
Yago: a core of semantic knowledge
Suchanek, F. M., Kasneci, G., and Weikum, G · 2007
Earlier work this paper cites.
The graph neural network model
Scarselli, F., Gori, M., Tsoi, A. C., Hagenbuchner, M., and Monfardini, G · 2008
Earlier work this paper cites.
Curriculum learning
Bengio, Y., Louradour, J., Collobert, R., and Weston, J · 2009
Earlier work this paper cites.
Relational knowledge: the foundation of higher cognition
Halford, G. S., Wilson, W. H., and Phillips, S · 2010
Earlier work this paper cites.
Young children’s analogical reasoning across cultures: Similarities and differences
Richland, L. E., Chan, T.-K., Morrison, R. G., and Au, T. K.-F · 2010
Earlier work this paper cites.
Yago2: exploring and querying world knowledge in time, space, context, and many languages
Hoffart, J., Suchanek, F. M., Berberich, K., Lewis-Kelham, E., De Melo, G., and Weikum, G · 2011
Earlier work this paper cites.
A hierarchy for relational reasoning in the prefrontal cortex
Krawczyk, D. C., McClelland, M. M., and Donovan, C. M · 2011
Earlier work this paper cites.
Connecting instances to promote children’s relational reasoning
Son, J. Y., Smith, L. B., and Goldstone, R. L · 2011
Earlier work this paper cites.
The Oxford handbook of thinking and reasoning
Holyoak, K. J. and Morrison, R. G · 2012
Earlier work this paper cites.
Learning to learn
Thrun, S. and Pratt, L · 2012
Earlier work this paper cites.
Translating embeddings for modeling multi-relational data
Bordes, A., Usunier, N., Garcia-Duran, A., Weston, J., and Yakhnenko, O · 2013
Earlier work this paper cites.
Yago3: A knowledge base from multilingual wikipedias
Mahdisoltani, F., Biega, J., and Suchanek, F. M · 2013
Earlier work this paper cites.

Similar

Never ending language learning
Mitchell, T. and Fredkin, E · 2014
Cited alongside, same era.
Knowledge base completion via search-based question answering
West, R., Gabrilovich, E., Murphy, K., Sun, S., Gupta, R., and Lin, D · 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
Cited alongside, same era.
Relational thinking and relational reasoning: harnessing the power of patterning
Alexander, P. A · 2016
Cited alongside, same era.
Interaction networks for learning about objects, relations and physics
Battaglia, P., Pascanu, R., Lai, M., Rezende, D. J., et al · 2016
Cited alongside, same era.
Convolutional neural networks on graphs with fast localized spectral filtering
Defferrard, M., Bresson, X., and Vandergheynst, P · 2016
Cited alongside, same era.
Jointly embedding knowledge graphs and logical rules
Guo, S., Wang, Q., Wang, L., Wang, B., and Guo, L · 2016
Cited alongside, same era.
Semi-supervised classification with graph convolutional networks
Original
Kipf, T. N. and Welling, M · 2016
Cited alongside, same era.
Learning Explanatory Rules from Noisy Data
Evans, R. and Grefenstette, E · 2017
Cited alongside, same era.
Neural message passing for quantum chemistry
Gilmer, J., Schoenholz, S. S., Riley, P. F., Vinyals, O., and Dahl, G. E · 2017
Cited alongside, same era.
Clevr: A diagnostic dataset for compositional language and elementary visual reasoning
Johnson, J., Hariharan, B., van der Maaten, L., Fei-Fei, L., Lawrence Zitnick, C., and Girshick, R · 2017
Cited alongside, same era.
Generalization without systematicity: On the compositional skills of sequence-to-sequence recurrent networks
Original
Lake, B. M. and Baroni, M · 2017
Cited alongside, same era.

Then

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
Later among the works it cites.
Textworld: A learning environment for text-based games
Côté, M.-A., Kádár, Á., Yuan, X., Kybartas, B., Barnes, T., Fine, E., Moore, J., Hausknecht, M., El Asri, L., Adada, M., et al · 2018
Later among the works it cites.
Dynamic task prioritization for multitask learning
Guo, M., Haque, A., Huang, D.-A., Yeung, S., and Fei-Fei, L · 2018
Later among the works it cites.
Embedding logical queries on knowledge graphs
Hamilton, W., Bajaj, P., Zitnik, M., Jurafsky, D., and Leskovec, J · 2018
Later among the works it cites.
Relational recurrent neural networks
Santoro, A., Faulkner, R., Raposo, D., Rae, J., Chrzanowski, M., Weber, T., Wierstra, D., Vinyals, O., Pascanu, R., and Lillicrap, T · 2018
Later among the works it cites.
Modeling relational data with graph convolutional networks
Schlichtkrull, M., Kipf, T. N., Bloem, P., Van Den Berg, R., Titov, I., and Welling, M · 2018
Later among the works it cites.
How powerful are graph neural networks?
Original
Xu, K., Hu, W., Leskovec, J., and Jegelka, S · 2018
Later among the works it cites.
Are powerful graph neural nets necessary? a dissection on graph classification
Original
Chen, T., Bian, S., and Sun, Y · 2019
Later among the works it cites.
Continual learning: A comparative study on how to defy forgetting in classification tasks
Original
De Lange, M., Aljundi, R., Masana, M., Parisot, S., Jia, X., Leonardis, A., Slabaugh, G., and Tuytelaars, T · 2019
Later among the works it cites.
Graph neural tangent kernel: Fusing graph neural networks with graph kernels
Du, S. S., Hou, K., Salakhutdinov, R. R., Poczos, B., Wang, R., and Xu, K · 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., Lenssen, J., Rattan, G., and Grohe, M · 2019
Later among the works it cites.
Continual lifelong learning with neural networks: A review
Parisi, G. I., Kemker, R., Part, J. L., Kanan, C., and Wermter, S · 2019
Later among the works it cites.
Pytorch: An imperative style, high-performance deep learning library
Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., Desmaison, A., Kopf, A., Yang, E., DeVito, Z., Raison, M., Tejani, A., Chilamkurthy, S., Steiner, B., Fang, L., Bai, J., and Chintala, S · 2019
Later among the works it cites.
Enhancing the transformer with explicit relational encoding for math problem solving
Original
Schlag, I., Smolensky, P., Fernandez, R., Jojic, N., Schmidhuber, J., and Gao, J · 2019
Later among the works it cites.
Clutrr: A diagnostic benchmark for inductive reasoning from text
Original
Sinha, K., Sodhani, S., Dong, J., Pineau, J., and Hamilton, W. L · 2019
Later among the works it cites.
On training recurrent neural networks for lifelong learning
Sodhani, S., Chandar, S., and Bengio, Y · 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
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…