Answers.Body: <p>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.</p>
  <p>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.</p>
  <p>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.</p>
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-06-28T12:28:56.497Z
Answers.Text: You're right, my graph filter for any given node collects information from itself and its neighboring nodes, and applies a graph convolution operator. It seems that they way it is defined, it is shift invariant over the input features, but not permutation equivariance. But permutation equivariance would be preserved if the graph structure is also permuted accordingly.
Answers.UserDisplayName: Acad
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-06-22T16:05:57.793Z
Answers.LastActivityDate: 2023-06-22T16:05:57.793Z
Answers.UserDisplayName: michael williams
Body: <p>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 <a href="https://github.com/unstable-zeros/grnn-comms-codesign" rel="nofollow noreferrer">https://github.com/unstable-zeros/grnn-comms-codesign</a>):</p>
  <pre><code> 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)
  </code></pre>
  <p>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.</p>
  <p>I have read that graph neural networks are permutation equivariant, so if the input is permuted, then the output must be accordingly permuted.</p>
  <p>Now, I am working with the following graph adjacency matrix:</p>
  <pre><code>S= [1,1,0,1 ; 1,1,1,0 ; 0,1,1,1 ; 1,0,1,1]
  
  </code></pre>
  <p>This means that every node is connected to two nodes that are adjacent to it in a circular fashion.</p>
  <p>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</p>
  <p><code>x=torch.tensor([1,2,3,4])</code>
  if I get the following output:</p>
  <p><code>tensor([20.7212, 20.7212, 20.5522, 20.2472])</code></p>
  <p>for
  <code>x=torch.tensor([2,1,3,4])</code></p>
  <p>I should get:
  <code>tensor([20.7212, 20.7212, 20.2472, 20.5522])</code></p>
  <p>But this is the output I actually get:</p>
  <p><code>tensor([20.7212, 20.7212, 20.5715, 20.2280])</code></p>
  <p>I do not understand this behavior, or whether I'm missing something or making a mistake. Any help will be appreciated.</p>
  
Tags: <neural-networks><pytorch><graph-neural-networks><graph-theory>
Title: Why is the output of my graph neural network not permutation equivariant?
UserDisplayName: Acad
ThreadText: # Why is the output of my graph neural network not permutation equivariant?
  
  (Asked by: username_0 on 2023-06-22)
  
  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.
  
  **Tags:** neural-networks, pytorch, graph-neural-networks, graph-theory
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2023-06-22. Score: 2
  
  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.
  
  > **Comments:**
  > **username_0**: You're right, my graph filter for any given node collects information from itself and its neighboring nodes, and applies a graph convolution operator. It seems that they way it is defined, it is shift invariant over the input features, but not permutation equivariance. But permutation equivariance would be preserved if the graph structure is also permuted accordingly.  
  
  ---
  
  