The Logic of Graph Neural Networks

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

paper · pdf · doi:10.48550/arxiv.2104.14624

arxiv created 2022/01/09 · arxiv updated 2022/01/11

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
• A Game for Counting Logic Formula Size and an Application to Linear Orders
• The Logical Expressiveness of Temporal GNNs via Two-Dimensional Product Logics
• Halting Recurrent GNNs and the Graded μ-Calculus
• Going deep and going wide: Counting logic and homomorphism indistinguishability over graphs of bounded treedepth and treewidth
• Repetition Makes Perfect: Recurrent Graph Neural Networks Match Message-Passing Limit
• Separation and Definability in Fragments of Two-Variable First-Order Logic with Counting

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