Answers.Body: <p>The essence of the reason, why this approach works for graphs with a different number of nodes is the locality and node order permutation invariance.</p>
  <p>The typical form of the layer-wise signal propagation rule is:
  <span class="math-container">$$
  H^{(l+1)} = f(H^{(l)}, A) = \sigma (A H^{(l)} W^{(l)})
  $$</span></p>
  <p>Here <span class="math-container">$H^{(k)}$</span> are the activations of the <span class="math-container">$k$</span>-th later, <span class="math-container">$W^{(k)}$</span> is the weight matrix, <span class="math-container">$A$</span> is the adjacency matrix and <span class="math-container">$\sigma$</span> is the activation function.</p>
  <p>Activation function <span class="math-container">$\sigma$</span> and <span class="math-container">$W^{(k)}$</span>  is the same on any graph, and the difference is only in the choice of adjacency matrix <span class="math-container">$A$</span>.</p>
  <p>Aggregation of the information from the neighborhood is done in permutation-invariant way, and the only way to do this is to assign the same weight for every member in neightboorhood, and (probably) some other weight to the node itself.</p>
  <p>For <a href="https://tkipf.github.io/graph-convolutional-networks/" rel="nofollow noreferrer">Graph Convolutional Neural Networks</a> (GCNN's) this works as follows:
  <span class="math-container">$$
  h_{v_i}^{(l+1)} = \sigma (\sum_{j \in N(i)} \frac{1}{c_{ij}} h_{v_j}^{(l)} W^{(l)})
  $$</span></p>
  <p>Regardless of whether the node is isolated or has many neighbors procedure is unchanged.</p>
  <p>Older approaches, the spectral for example, had to calculate the Graph Laplacian and perform its eigendecomposition. They did not generalize to other graphs.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-12-06T23:46:52.657Z
Answers.Text: A follow-up question: in your activation function, why do you not include bias vectors? Is it because bias matrices—not vectors—are needed for graph neural networks (and thus including a bias matrix is equivalent to just using a weight matrix)?
Answers.UserDisplayName: Mathews24
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-10-20T07:32:25.107Z
Answers.Text: So the dimension of the weight matrix is actually given by $ W \in R^{d_k*d_{k-1}} $?
Answers.UserDisplayName: tangolin
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-10-20T08:18:05.477Z
Answers.Text: @tangolin - yes, there is no any spatial index, as would be for regular convolution. Say $i, j$ - denoting the $i$-th row and $j$-th column inside the kernel.
Answers.UserDisplayName: spiridon_the_sun_rotator
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-10-20T09:04:45.013Z
Answers.Text: but in the paper Graph Attention Network, they mentioned `...which define convolutions directly on the graph, operating on groups of spatially close neighbors. One of the challenges ... In some cases, this requires learning a specific weight matrix for each node degree, using the powers of a transition matrix to define the neighborhood while learning weights for
  each input channel and neighborhood degree , or extracting and normalizing neighborhoods containing a fixed number of nodes`, why would they have this problem if the weight matrix is same for any node?
Answers.UserDisplayName: tangolin
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-10-20T17:40:41.483Z
Answers.Text: @tangolin specific weights for each possible node degree is a more expressive option - since it can be the case, that vertices with a different number of neighbors require a different treatment. However, this architecture is still applicable to different graphs, since the weights are shared for the neighborhoods of the same kind. If in a given graph there is no vertex with 5 neighbors and there is such a weight in GCNN - this weight will not participate in computation.
Answers.UserDisplayName: spiridon_the_sun_rotator
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-10-21T08:57:54.060Z
Answers.Text: got it! Thanks a lot for the explanation.
Answers.UserDisplayName: tangolin
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-10-20T06:18:02.950Z
Answers.LastActivityDate: 2021-10-20T06:18:02.950Z
Answers.UserDisplayName: spiridon_the_sun_rotator
Body: <p>I have recently been studying GNN, and the fundamental idea seems to be the aggregation and transfer of information from a node's neighborhood to update the node's internal state. However, there are few sources that mention the implementation of GNN in code, specifically, how do GNNs adapt to the differing number of nodes and connections in a dataset.</p>
  <p>For example, say we have 2 graph data that looks like this:</p>
  <p><img src="https://i.sstatic.net/Tb7HX.jpg" alt="enter image description here" /></p>
  <p>It is clear that the number of weights required in the two data points would be different.</p>
  <p>So, how would the model adapt to this varying number of weight parameters?</p>
  
Tags: <implementation><geometric-deep-learning><graph-neural-networks>
Title: How do graph neural networks adapt to different number of nodes and connections of different graphs?
UserDisplayName: tangolin
ThreadText: # How do graph neural networks adapt to different number of nodes and connections of different graphs?
  
  (Asked by: username_0 on 2021-10-20)
  
  I have recently been studying GNN, and the fundamental idea seems to be the aggregation and transfer of information from a node's neighborhood to update the node's internal state. However, there are few sources that mention the implementation of GNN in code, specifically, how do GNNs adapt to the differing number of nodes and connections in a dataset.
  
  For example, say we have 2 graph data that looks like this:
  
  ![enter image description here](https://i.sstatic.net/Tb7HX.jpg)
  
  It is clear that the number of weights required in the two data points would be different.
  
  So, how would the model adapt to this varying number of weight parameters?
  
  **Tags:** implementation, geometric-deep-learning, graph-neural-networks
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2021-10-20. Score: 3 | Accepted answer
  
  The essence of the reason, why this approach works for graphs with a different number of nodes is the locality and node order permutation invariance.
  
  The typical form of the layer-wise signal propagation rule is:
  $$
  H^{(l+1)} = f(H^{(l)}, A) = \sigma (A H^{(l)} W^{(l)})
  $$
  
  Here $H^{(k)}$ are the activations of the $k$-th later, $W^{(k)}$ is the weight matrix, $A$ is the adjacency matrix and $\sigma$ is the activation function.
  
  Activation function $\sigma$ and $W^{(k)}$ is the same on any graph, and the difference is only in the choice of adjacency matrix $A$.
  
  Aggregation of the information from the neighborhood is done in permutation-invariant way, and the only way to do this is to assign the same weight for every member in neightboorhood, and (probably) some other weight to the node itself.
  
  For [Graph Convolutional Neural Networks](https://tkipf.github.io/graph-convolutional-networks/) (GCNN's) this works as follows:
  $$
  h\_{v\_i}^{(l+1)} = \sigma (\sum\_{j \in N(i)} \frac{1}{c\_{ij}} h\_{v\_j}^{(l)} W^{(l)})
  $$
  
  Regardless of whether the node is isolated or has many neighbors procedure is unchanged.
  
  Older approaches, the spectral for example, had to calculate the Graph Laplacian and perform its eigendecomposition. They did not generalize to other graphs.
  
  > **Comments:**
  > **username_0**: So the dimension of the weight matrix is actually given by $ W \in R^{d_k*d_{k-1}} $?  
  > **username_1**: @username_0 - yes, there is no any spatial index, as would be for regular convolution. Say $i, j$ - denoting the $i$-th row and $j$-th column inside the kernel.  
  > **username_0**: but in the paper Graph Attention Network, they mentioned `...which define convolutions directly on the graph, operating on groups of spatially close neighbors. One of the challenges ... In some cases, this requires learning a specific weight matrix for each node degree, using the powers of a transition matrix to define the neighborhood while learning weights for each input channel and neighborhood degree , or extracting and normalizing neighborhoods containing a fixed number of nodes`, why would they have this problem if the weight matrix is same for any node?  
  > **username_1**: @username_0 specific weights for each possible node degree is a more expressive option - since it can be the case, that vertices with a different number of neighbors require a different treatment. However, this architecture is still applicable to different graphs, since the weights are shared for the neighborhoods of the same kind. If in a given graph there is no vertex with 5 neighbors and there is such a weight in GCNN - this weight will not participate in computation.  
  > **username_0**: got it! Thanks a lot for the explanation.  
  > **username_2**: A follow-up question: in your activation function, why do you not include bias vectors? Is it because bias matrices—not vectors—are needed for graph neural networks (and thus including a bias matrix is equivalent to just using a weight matrix)?  
  
  ---
  
  