Why is the output of my graph neural network not permutation equivariant?

Question

I am using Pytorch to train a graph neural network on a 4x4 graph. Each node has one feature, and the output has one feature. Essentially, the architecture of my GNN looks like this (I'm training the networks using the pre-defined modules in https://github.com/unstable-zeros/grnn-comms-codesign):

 LocalGNN_t(
  (GFL): Sequential(
    (0): GraphFilter_t(in_features=1, out_features=1, filter_taps=2, edge_features=1, bias=True, GSO stored)
    (1): ReLU()
  )
  (Readout): Sequential(
    (0): Linear(in_features=1, out_features=10, bias=True)
    (1): ReLU()
    (2): Linear(in_features=10, out_features=10, bias=True)
    (3): ReLU()
    (4): Linear(in_features=10, out_features=1, bias=True)
    (5): Hardtanh(min_val=-1e+16, max_val=1e+16)

So I have one graph filter layer that takes information from the immediate neighbors for every node, and applies ReLU nonlinearity. The output of this is given to an MLP, node-wise.

I have read that graph neural networks are permutation equivariant, so if the input is permuted, then the output must be accordingly permuted.

Now, I am working with the following graph adjacency matrix:

S= [1,1,0,1 ; 1,1,1,0 ; 0,1,1,1 ; 1,0,1,1]

This means that every node is connected to two nodes that are adjacent to it in a circular fashion.

After training the neural network on PyTorch, I find that the output is not permuted according to the graph structure. I would assume that for the input

x=torch.tensor([1,2,3,4]) if I get the following output:

tensor([20.7212, 20.7212, 20.5522, 20.2472])

for x=torch.tensor([2,1,3,4])

I should get: tensor([20.7212, 20.7212, 20.2472, 20.5522])

But this is the output I actually get:

tensor([20.7212, 20.7212, 20.5715, 20.2280])

I do not understand this behavior, or whether I'm missing something or making a mistake. Any help will be appreciated.

Answer 1

It seems that the graph filter layer in your GNN takes information from the immediate neighbors for every node and applies a ReLU nonlinearity. However, the architecture you've shown does not explicitly consider the graph structure or utilize any permutation equivariance properties.

Permutation equivariance in graph neural networks refers to the property that the output of the network should remain unchanged when the input nodes are permuted while keeping the graph structure intact. In your case, it appears that the network does not explicitly enforce permutation equivariance.

To achieve permutation equivariance, you can incorporate graph convolutional layers or graph attention layers into your network architecture. These layers are designed to capture the graph structure and propagate node information accordingly. By using these layers, the network can learn to output results that are invariant to the ordering of the input nodes.

If your goal is to enforce permutation equivariance, you might need to modify the network architecture or consider different graph neural network models that explicitly account for the graph structure and permutation equivariance.