The Logic of Graph Neural Networks

2021/04/29 by Grohe, Martin · 10 citations
#Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Machine Learning (cs.LG)

paper · doi:10.48550/arxiv.2104.14624

Abstract

Graph neural networks (GNNs) are deep learning architectures for machine learning problems on graphs. It has recently been shown that the expressiveness of GNNs can be characterised precisely by the combinatorial Weisfeiler-Leman algorithms and by finite variable counting logics. The correspondence has even led to new, higher-order GNNs corresponding to the WL algorithm in higher dimensions. The purpose of this paper is to explain these descriptive characterisations of GNNs.

Cited by

• Learning General Policies with Policy Gradient Methods
• A Logical View of GNN-Style Computation and the Role of Activation Functions
• Homomorphism Indistinguishability, Multiplicity Automata Equivalence, and Polynomial Identity Testing
• Vejde: A Framework for Inductive Deep Reinforcement Learning Based on Factor Graph Color Refinement
• Learning General Policies From Examples
• Weisfeiler-Leman Features for Planning: A 1,000,000 Sample Size Hyperparameter Study
• Graph Learning via Logic-Based Weisfeiler-Leman Variants and Tabularization
• MILP-SAT-GNN: Yet Another Neural SAT Solver
• Understanding Generalization in Node and Link Prediction
• Relational GNNs Cannot Learn C₂ Features for Planning

Related

• A Theoretical Comparison of Graph Neural Network Extensions
• Graph Neural Networks with Local Graph Parameters
• Theory of Graph Neural Networks: Representation and Learning
• Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks
• On the Computational Capability of Graph Neural Networks: A Circuit Complexity Bound Perspective