1 of 27

The Logic of Graph Neural Network

Paper by: Martin Grohe

RWTH Aachen University, Germany

Presented by: Hritam Basak

Some slides borrowed from the author’s original presentation

2 of 27

Motivation: Neuro-symbolic Integration

Part I: Logic for GNNs

We characterise the logical expressiveness of graph neural network (GNN)

Part II: GNNs for Logic

We propose a generic architecture for compiling GNN-based solvers for constraint satisfaction problems

So the motivation for this talk is something called neuro-symbolic integration, or actually it has many different names.

What is meant by this is the integration, the combination of traditional logic-based reasoning that we use in AI with the statistical type of reasoning used by machine learning. And when we say neural, maybe in particular deep

learning these days. Now this is a very important goal.

I think it's also extremely difficult. So I would fully subscribe to this goal. I just don't think we’ve come very far with it really. So what I'm trying to do here is maybe somewhat simpler.

I'm trying to explain what the interface between logic and neural networks might be. And I think graph neural networks, which I'll talk about, offer a particularly nice interface. And this is basically witnessed by two results I want to talk about today.

So the talk will have two parts. And the first is I use logic to describe graph neural networks or rather the functions they compute. So we characterize the logical expressiveness of graph neural networks. And the second part goes the other way around.

I'm trying to use graph neural networks to express logic. And the first part is theory. The second is a bit more practical. What I will talk about there is an architecture, a very generic architecture for solving constraint satisfaction problems using GNNs.

And let's keep it there for the moment. And well, I'll tell you more about this in a while.

3 of 27

Graph Neural Networks

4 of 27

Graph Neural Networks

Graph Neural Networks (GNNs) are deep learning architectures for machine learning problems on graphs.

They can be viewed as a generalization of convolutional neural networks from a rigid grid structure to more flexible structured data.

GNNs have wide range of applications, for example, in computational biology, chemical engineering, physics, etc.

By now, there are large varieties of GNN architectures. We consider the core GNN architecture known as message passing graph neural network or aggregate-combine graph neural network

So graph neural networks are deep learning architectures for machine learning problems on graphs. And we can view them as a generalization of convolutional neural networks.

---- Next ----

For convolutional neural networks, we basically look at a grid structure or just at a line, a one-dimensional structure. Whereas for graph neural networks, we don't have this restriction so we can look at more flexibly structured data.

---- Next ----

They have a wide range of applications. So for example, there are applications in computational biology and chemical engineering, physics, and so on.

---- Next ----

Now there's a large variety of GNN architectures by now. And it's, I guess it's even hopeless to keep track of all the papers that appear. The graph neutral networks I'll talk about here are really the core architecture. They are sometimes called message passing graph neural networks or aggregate-combine graph neural networks.

5 of 27

Graph Neural Networks

6 of 27

Graph Neural Networks

7 of 27

Graph Neural Networks

8 of 27

Graph Neural Networks

9 of 27

Graph Neural Networks

10 of 27

Graph Neural Networks

11 of 27

Graph Neural Networks

12 of 27

Graph Neural Networks

13 of 27

Graph Neural Networks

14 of 27

Computation of GNNs

GNN N with d layers maps graph G to sequence of functions

Initialization: encodes node level of v

Aggregation:

Sufficient to use summation as aggregation (Xu et al.,19)

Function computed by a feedforward neural network or some more complex neural network architecture

let me describe this a bit more technically. So a GNN, a graph neural network N, with d layers maps graphs to sequences of functions defined on the vertex set of the graph and mapping vertices to real vectors. That's the state functions we have at every iteration. And I'm starting at iteration zero with an initialization. I go on, do d iterations. So in the end I have a function zeta-d.

--- Next ---

The initialization certainly should encode the node label. And other than that, it’s just some default value, or as we'll discuss later, it's just a random value.

----Next----

And then, well, all the nodes receive messages and they aggregate the message in some way. And the interesting part here is that, as I said before, all nodes basically have the same type of message functions. So there is no order between the neighbors, all the messages that are coming in look the same from the perspective of node v. So this is a function of the multiset of messages the node receives. So that's a set where certain entries may appear several times.

---Next---

So typically, as aggregation, we take symmetric functions like sum or mean, or the maximum applied either directly to the states of the neighbors (then we just think the neighbors sent their states) or to some function of these states. And typically it's enough to take a linear function here. It usually doesn't buy us anything in practice to take more complicated functions, although we could.

--Next—

And there are some theoretical results saying that it's sufficient to use summation as aggregation. So the aggregation function is just the sum of the states of the neighbors, that's good enough, that's completely general.

Next –

And then we need a combination function that computes the new state from the old states and the aggregated values of the messages. So that's just some function computed by a feedforward neural network or some more complex neural network architecture. And the parameters of this function, of this neural network, are learned. That's the main thing we learn when we train a graph neural network. Possibly it's also these linear functions that have learned parameters.

15 of 27

Functions computed by GNNs

So these are the functions as I've just described. So we update the states, taking the aggregated values of the states of the neighbors, combining them with the old states and then we get the new states. And now, okay, here I am. Now we want some outputs. So we have two options. We can compute a function that is defined on the nodes of our graph. Sometimes we want that. So we just apply some readout function to the final state of the nodes. And this is again, a learned function,

again, a feedforward neural network that computes this function. And the idea here is that to do the computation, of course we need more information.

So the state is typically larger than what we actually need in the end. Maybe in the end, we just need one truth value. So one bit for the nodes.

Next –

The second option is that I compute a graph-level function. And for that, I aggregate the states of all nodes and then apply some readout function. And what I can do here is typically sum up all the states. And then again, use some feed forward neural network. So that's the basic architecture.

16 of 27

Recurrent GNNs

Recurrent GNNs: Instead, we can take a single layer and apply it repeatedly. That is, we have a single aggregation function agg and combination function comb and let:

So far I've described GNNs as having a fixed number of iterations. And each of the layers of such a GNN has its own aggregation and combination functions. So we can set it up this way. This is what is sometimes called graph convolutional neural network. But we can also say we apply the same functions over and over again. And the advantage of doing this is we can do it as long as we want to.

Next –

And that's what we would call recurrent GNN. So we take a single layer and apply it repeatedly. So we have a single aggregation function and combination function, and then update the states in the same way, apply the aggregation function

to the states of the neighbors, then combine it with the old states. And we can run this for as long as we want to.

--Next –

In particular, we can determine the number of iterations at runtime, for example, depending on the size of the input graph or something more fancy, maybe the diameter of the input graph to make sure that all the vertices can communicate with one another. Or we can also make it depend on the evolution of the sequence. So we can say if this sequence of states converges, or if the states get close together, we stop. Although that's something we usually not have, let me emphasize this,

we do not require any convergence. We just decide we stop after d rounds and it's up to us how to decide this. So that's the basic setup. And then after we have stopped, we apply the readout function to the layer where we have stopped, or if we want, we can also take the average of all layers.

17 of 27

Part I

The Expressiveness of Graph Neural Network

The Weisfeiler-Leman Algorithm

18 of 27

A simple combinatorial algo.

The color refinement algorithm iteratively computed a coloring of the vertices of graph G

Initialization: All vertices get a same color

Refinement Step: Two nodes v, w get different colors if there is some color c such that v and w have different numbers of neighbors of color c.

Refinement is repeated until coloring stays stable

Color refinement demo

The stable coloring of a given graph with n nodes and m edges can be computed in time O((n + m) log n).

It's a very simple combinatorial algorithm. And what it does is it colors the vertices of the graph. And the goal, when you use this as an isomorphism test, at least, is to distinguish vertices that are structurally different.

--Next–

And the way we do this is as follows. Initially all vertices have the same color. And then if two vertices have different degrees, then they get different colors or in a refinement step, more precisely, when we have two nodes that have different numbers of neighbors in some other color, then these nodes will get different colors now in one iteration of the algorithm.

--Next—

And we iterate until the coloring stays stable. And that means the partitioning used by the colors is no longer refined. And let me just show you how this works,

--Next—

So one nice thing about this algorithm is that it's very efficient. It runs almost in linear time, n log n, and there are also no large constants or anything so it's really efficient in practice.

19 of 27

WL distinguishes two graphs G, H if their color histograms differ, that is, some color appears a different number of times in G and H.

Thus 1-WL can be used as an incomplete isomorphism test.

works on almost all graphs (Babai, Erdös, Selkow 1980)

fails on some very simple graphs:

And the way we can use it as an isomorphism test, as a standalone isomorphism test, is to say, okay, it distinguishes two graphs. If their color patterns in the ends are different, that means some color appears more oftenin graph G than in H

or the other way round. If that happens, since the coloring we compute is isomorphism invariant, or maybe I should say equivariant, we know that the, if the color patterns are different, the graphs cannot be isomorphic.

Well, if the color patterns are the same, then we know nothing so it’s an incomplete isomorphism test.

On the other hand, it fails on very simple graphs. So look at these two, a cycle of lengths six versus two triangles. They are obviously not isomorphic, but color refinement does nothing. Initially all vertices are blue and all have two blue neighbors

so nothing happens if we stop the coloring iteration. So this is already the stable coloring and it really tells us nothing.

20 of 27

Higher-Dimensional Weisfeiler-Leman

The k-dimensional Weisfeiler-Leman algorithm (k-WL) iteratively colours k-tuples of nodes (Weisfeiler and Leman 1968, Babai ∼1980)

Running time: O(n^k⁺¹log n)

k-WL is much more powerful than 1-WL, but still not a complete isomorphism test.

Theorem (Cai, Fürer, Immerman 1992)

For every k there are non-isomorphic graphs G_k, H_kof size O(k)

not distinguished by k-WL.

So now this we call the k-dimensional Weisfeiler-Leman Algorithm and what it does is it colors k-tuples of nodes in a very similar way as color refinements colors nodes. So the running time of this is now n to the k plus 1 times log n. And as I said before, the one-dimensional version is essentially the same as color refinement, although there’s a small difference. Now this k-dimensional version is much more powerful than color refinement. It's really difficult to find two graphs that are not isomorphic, but cannot be distinguished by say three-dimensional Weisfeiler-Leman. And it really k-dimensional Weisfeiler-Leman somehow is stronger than most of the combinatorial graph isomorphism tests we know. But it's still not a complete isomorphism test.. So that's a very important, nice result by Cai, Fürer and Immerman.

21 of 27

22 of 27

Part II

GNN for Constraint Satisfaction Problems

23 of 27

Constraint Satisfaction Problem

Constraint satisfaction problem (CSP) provide a general framework for combinatorial search problems:

The task is to assign values to variables subject to constraints

A specific CSP is given by its constraint language specifying which kinds of constraints can be used

In the maximization version (MAX-CSP) the objective is to satisfy as many constraints as possible

24 of 27

RUN-CSP

RUN-CSP (Tönshoff, Ritzert, Wolf, G. 2020+)

(Recurrent Unsupervised NN for Max-CSPs)

MPNN architecture for solving binary binary Max-CSPs

Applicable to all binary CSPs: constraint language compiled into loss function

training unsupervised

scales from small training examples to inference on large examples

So here's our architecture. So basically it's a graph neural network architecture applied to this constraint graph I just described and the readout function in the end will give us values for all the variables for all the nodes of the network.

Now, one thing we do for the updates of the states, we use a more complicated neural network architecture than just feedforward neural networks. We use LSTM cells there.

So we have this GNN architecture that we apply to the max CSPs. What is also nice is the training is unsupervised. Essentially we can train such neutral network by just generating random instances of the CSPs, and we don't need to solve them.

What the network tries to achieve is to satisfy as many constraints as it can. In this sense, we only look at the maximization problem. We have no guarantees whatsoever.

What it also does is, the training examples can be fairly small, say a couple of hundred nodes, and we can still do inference on much larger examples, several thousands of nodes. So that scales fairly well. And that's a nice feature of this architecture. We just have to learn the different state update functions and message functions, and then we can apply them to graphs of any size.

So this is all nice.

25 of 27

Loss Function

So how do we compute the loss functions? So let's say we have an instance with variables X, constraints C, domain D. And then our readout function is a softmax or gives us a soft assignment for every node or every variable, a d-dimensional vector, and the way we interpret these numbers, well, they are just numbers between 0 and 1 of course.

And so now imagine we draw values for all the variables by using this probability.

So the value is one specific of the d possible values, well, by just drawing from the distribution. Anyway, so then the probability that we satisfy a constraint is this sum. It's basically the sum over all possible value pairs of the probabilities,

all possible value pairs in the relation of the probabilities we get. So we want to maximize this probability, it's convenient to take logarithms, well, we can maximize the logarithm, or since it's a loss function, we minimize minus log.

And then we sum over all constraints and normalize.

That's essentially what we do.

26 of 27

Concluding Remarks

GNNs are a very flexible learning architecture which allows us to adapt them to logical formalism such as CSPs

We have a good understanding of their expressiveness. Yet many interesting questions remain open

Expressiveness results only tell half story, because they ignore learning. However, most of the results have good experimental support.

27 of 27

References

Slides on GNN by the author himself
YouTube presentation by the author
Grohe M. The logic of graph neural networks. In2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) 2021 Jun 29 (pp. 1-17). IEEE.
Toenshoff J, Ritzert M, Wolf H, Grohe M. Graph neural networks for maximum constraint satisfaction. Frontiers in artificial intelligence. 2021 Feb 25;3:580607.