3
$\begingroup$

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

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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 (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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ So the dimension of the weight matrix is actually given by $ W \in R^{d_k*d_{k-1}} $? $\endgroup$
    – tangolin
    Oct 20, 2021 at 7:32
  • $\begingroup$ @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. $\endgroup$
    – spiridon_the_sun_rotator
    Oct 20, 2021 at 8:18
  • $\begingroup$ 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? $\endgroup$
    – tangolin
    Oct 20, 2021 at 9:04
  • $\begingroup$ @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. $\endgroup$
    – spiridon_the_sun_rotator
    Oct 20, 2021 at 17:40
  • $\begingroup$ got it! Thanks a lot for the explanation. $\endgroup$
    – tangolin
    Oct 21, 2021 at 8:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .