How GCN can be an inductive method?

[aure_bnp]

Hi everyone,

I am currently diving into Graph Convolutional Network which is the method of this paper : Semi-Supervised Classification with Graph Convolutional Networks (arxiv.org)([1609.02907] Semi-Supervised Classification with Graph Convolutional Networks).
I have seen that the GCN model takes as input the adjacency matrix and the features matrix (which is a graph, let say our graph as n nodes). From this remark, I am wondering how GCN can generate an embedding for a node which appears after the training and was totally unseen during the training. We have now n+1 nodes and the adjacency matrix and the features matrix have new size.
Hence, my question, How GCN can be inductive ?

Thanks !

[czkkkkkk]

Hi @aure_bnp, we say GraphSAGE is inductive because it can use sampling methods to predict the label of unseen nodes. On the contrary, GCN is transductive because the graph structure is fixed.

[aure_bnp]

Hi @czkkkkkk and thanks for your fast reply !

Okay I’m confused… Why is there many articles stating that GCN is an inductive learning framework ?

And, even two of you collaborators think it is inductive, check this post How to carry out the batch-wise training while using layer defined in DGL? - Questions - Deep Graph Library (neo and mufeili).
You can also see on this website : Graph Neural Networks (snap-stanford.github.io) which comes from Stanford university and where Jure Leskovec teaches this course, that GCN has an inductive capacity.

From my point of view, I think we can use GCN as an inductive method because it does not change the shape of weight matrixes when we add a new node to the graph. We just need to do get the node’ neighbors times their features times the learned weight matrixes. In the wend we just have to pass GCN(A[new_nodes], X, W_learned), with A[new_nodes] the line allowing to get the node’ neighbors, X the feature matrix and W_learned all the matrixes learned during the training of the model.

I am really confused as you can see, beacause some say it is transductive, others say it is inductive. I know that originally it was tested in an transductive setting, but many sources accord to say it can be used inductively. Maybe it is because everyone does not have the same definition of transductive and inductive, yet they are straightforward definitions…

In the end, I just want to know if a GCN model can, from a node totally unseen (not masked, really unseen) during the training, generate an embedding for this unseen node ?
At the end of my GCN, I want to classify my node as 1 or 0, so I just put a linear layer with a sigmoid activation function.

Thank you for your clarification.

[czkkkkkk]

Thanks for your interest in such a discussion. My understand may not be totally correct since I am not a GNN algorithm expertise. Here are my thoughts. Full graph GCN is not inductive because it only is applied for the whole graph and makes predictions for nodes that can be seen during training. Sampling-based GraphSAGE is inductive because it is able to apply sampling on unseen nodes. So the difference is whether sampling is applied or not. If sampling is available, both GCN and SAGE models can conduct inductive learning.

[aure_bnp]

Thanks for your reply !
So, for you, the main difference and what make GraphSAGE inductive and not GCN is that GraphSAGE can sample node neighbors and not GCN …
For me, if GCN is not inductive is because it uses the adjacency matrix rather than the neighborhood sampling. In the end, it is what you think.
I might have found an explication on why GCN is only transductive : for one layer
GCN(A,X) = ReLU(A x X x W0 + b0)
The shapes for A, X and W0 and b0 are, for a graph with N nodes?
A : N x N, X : N x nb of features, W0 : nb of features x embedding dimension, b0 : N x embedding dimension
Hence GCN(A,X) is of shape (N x embedding dimension)
If we add a node, we have now N+1 node, hence, the shape of b0 is not applicable anymore with the addition in A x X x W0 + b0.

But a lot of people seem to disagree on this inductive/transductive issue about GCN. Nevertheless, if Standford university states that it is inductive, it mights exist something to make it inductive. From what I see, if we do not use biases, it should be fine, but again, it’s just an hypothesis.

[czkkkkkk]

Actually the shape of bias in GNN is normally equal to the number of features. So it would not be affected by the number of nodes.

[aure_bnp]

Sorry, I wanted to put b0 : N x embedding dimension. I have edited the comment above so it could be written correctly.

Nevertheless, the statement remains the same. Because if we add a node on the graph, we will have N+1 nodes and we have to add a line on b0 at the end, to have a shape of (N+1 x embedding dimension). Those biases will not have been learn during the training. Hence, can’t be applied and it can’t be inducitve.