1 of 19

We can use classical Logic �to understand the power of

Graph Neural Networks

2 of 19

GNNs based �on local features capture a logic �heavily used in Knowledge Representation.

GNNs mixing�local + global features can express�First Order Logic �with 2 variables �and counting.

Theorem

Theorem

3 of 19

AC-GNNs:�Aggregate & Combine

4 of 19

5 of 19

6 of 19

Simple AC-GNN

7 of 19

Logical Classifiers

8 of 19

not connected with v

First Order logic with counting (FOC)

​

v is red, and

there is a node

that has at least two

blue neighbors

FOC-k: FOC with only k variables in every formula.

9 of 19

WL-test�(Graph Isomorphism)

FOC-2

AC-GNNs

?

Morris et al.’19 (AAAI)�Xu et al.’19 (ICLR)

Cai et al.’92 (Combinatorica)

10 of 19

Proposition

There are (infinitely many) FOC-2 formulas

that cannot be captured by AC-GNNs

​

11 of 19

Which logic is captured �by AC-GNNs?

12 of 19

ALCQ: a Description Logic to define concepts

​

13 of 19

Theorem

A formula is captured by an AC-GNN �if and only if it is expressible in ALCQ

14 of 19

GNNs for FOC-2?

ALCQ FOC-2

15 of 19

ACR-GNNs:

Aggregate & Combine�+ Readouts

16 of 19

17 of 19

Theorem

Every formula expressed in FOC-2 �can be captured by an ACR-GNN

18 of 19

Other results:

  • Single readout
  • Experiments

Future work:

  • Explainability

19 of 19

The Logical Expressiveness �of Graph Neural Networks

Pablo Barceló

Egor V. Kostylev

Mikaël�Monet

Jorge�Pérez

Juan L.

Reutter

Juan-P.

Silva