How rotational invariants are learned with Chebyshev algorithm ?

[pinkfloyd06]

Hello,

I'm wondering if the first order approximation of algorithm Chebyshev ( Weisfeiler-Lehman ) allows the convolutional features to learn rotation invariants of graphs ?

Thank you

[tkipf]

All these graph neural net algorithms considered here are invariant to local reordering of neighbors. This corresponds to rotational invariance of filters if you consider, e.g., a 2D regular grid graph of infinite size embedded in 2D Euclidean space. Is that what you mean?

Note that it is easy to "fix" this invariance by assigning specific meaning to neighbors in a specific direction (as done in regular CNNs). Relational GCNs support this, for example https://arxiv.org/abs/1703.06103 - they can recover regular CNNs on grids.

[pinkfloyd06]

 @tkipf thank you for your answer. My question is about rotational invariance in the case of irregular graphs (not a grid)

[tkipf]

What is a rotation on irregular graphs? :)

[pinkfloyd06]

In the context of graph classification, l mean the following :

For the same graph G. A rotation of G with angle u results a graph G'.

G and G' has the same topology and vertices connexion. However, nodes position are not the same . It can be seen as isomorphism graph problem where we look at the bijection. Hence, we need to get invariance to permutation.

Hope it's clear

[tkipf]

Oh ok, so assuming you embed this graph in some Euclidean space, you rotate the position of the vertices? This has little to do with the graph structure, I'm afraid. Have a look at Group-Equivariant nets (https://arxiv.org/abs/1602.07576) if you want to be equivariant to transformations such as rotation in a Euclidean space. Invariance is easy, just ignore the node positions and then your model will be invariant to them ;-)

[pinkfloyd06]

Ok, so the idea is just to embed the graph in Euclidean space without taking into consideration their position , then by construction they are invariant to rotation ?

[tkipf]

Yes, but that might ultimately not be what you want. A typical approach is to move to relative, internal coordinates, defined by angles and distances in a local frame of reference. This is by construction invariant to rotation but still keeps the information about the spatial structure of the component.

[pinkfloyd06]

Hello @tkipf,

l come back to you for some clarification about invariance to translation, rotation and permutation in the context of full graph classification (irregular graphs).

1) In this context , the actual Chebyshev implementation is only invariant to translation (and not to rotation and permutation) ? 2) If we want to be invariant to rotation or more in general to permutation, we need to come up with a pooling algorithm which is invariant to permutation. However : 2-A) If we apply pooling by taking into consideration nodes positions . Invariance to permutation will not be respected , since it depends on the nodes position (which vary from a graph to another) 2-B) If we come up with a pooling that ignores nodes position . I'm wondering how can fully connected layer distinguish between two graphs of the same classs, since the position of nodes is a discriminant features. Otherwise, fully connected layer act randomly on graphs since it doesn't have any prior about nodes position. For the sake of clarification let's take a simple example:

Given two graph G and G' such that G' is obtained by permuting the vertices of G. Obviously, the graph neural network should learn that G and G' are coming from the same class. However if the network is not invariant to permutation (convolutional/pooling layers), the fully connected layer will act randomly , because there is no structure on these graphs.

Hope it's clear.

Thank you for your answer

[tkipf]

What do you mean by invariance w.r.t. translation and rotation in the context of graphs? Do you mean the graph is embedded into e.g. 3D Euclidean space? Graph neural nets only give you equivariance w.r.t. permutation, they do not necessarily give you translation or rotation in-/equivariance.

In terms of graph classification: it often makes sense to use a global pooling layer that is permutation invariant, like a sum or an average (or max). In this case, the overall model is also invariant to permutation.

[pinkfloyd06]

1) Invariance to translation : We have two graphs G and G' such that G' is the result of translation on G. Translation on graph can be seen as just removing some nodes and connections on the graph. Let's say we apply translation by shifting right by 3 units, hence we get a new adjacency matrix. G' here is a subgraph of graph G. 2) Invariance to rotation (can be seen as in grid) : if we apply rotation on graph G with 90° we obtain graph G'. Graphs G and G' have the same topology, it changes only the position of nodes (nodes relabeling ) but the connexions remains the same. It's just a permutation of indexes in the adjacency matrix. Permutation is more general than rotation

3) "Graph neural nets only give you equivariance w.r.t. permutation" How this permutation is learnt ? since the order/position of nodes is note known at the fully connected layer

4) In the latter case. Using global pooling allows to map features from the conv layer to softmax layer (without the use of fully connected layer which lose information about the graph structure). But l'm wondering how global pooling is invariant to permutation in the context of graphs.

[tkipf]

I see. In general these types of models (GNNs for classification with a permutation-invariant pooling layer) are invariant to permutations of indices in the adjacency matrix, so this should cover the symmetries you're describing if I understand this correctly.

Not sure what you mean by 3), but hopefully what I said above helps. Sum/average are by design permutation invariant operations, so permutation invariance doesn't need to be "learned" (it's in there by design ;-) ).

4): Same as 3), but maybe I'm still misunderstanding the question.

[pinkfloyd06]

Thank you @tkipf for all these clarifications.

Let's take an example :

output from the last convolutional layer :

conv_2_output=(145,32,10) # 145 number of nodes , 32 : number of convolution features map , 10 represents the features of each node.
x=global_average_pooling(conv_2_output) 
x.shape=(145,1)

Let's suppose that we have 5 classes

predictions=Softmax(x)
predictions.shape= (5,145)

In order to make my third question clear: when applying global_pooling

x=global_average_pooling(conv_2_output) 
x.shape=(145,1)

How these representation (x) is invariant to permutations.

if l feed a network with the same graph permuted , l come up with a vector x' such that x'.shape=(145,1) How it can differentiate between the values of x and x' for instance x[0] after permutation is x'[78]

Thank you

[tkipf]

I think the source of our misunderstanding is that by global pooling, I mean pooling over all nodes (0-th dimension in your example) whereas you seem to be pooling over the feature dimension, which doesn't make a lot of sense to me...