Quick questions to see whether I understand GCNs correctly.
Is it correct that, if I have trained a GCN, it can take arbitrary graphs as input, assuming the feature size is the same?
I can't seem to find explicit literature on this.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Graph neural networks, of which GCNs are a specific type, are able to handle arbitrary graphs as input. GNNs operate first over "neighborhoods" of nodes to compute individual node representations and then optionally apply a pooling function to reduce these to a single graph-level representation that can be used in classification. This means that GNNs work "locally" and do not contain implicit assumptions about the graph topology.
For example, the update equation for a given node's representation in a GCN can be written as
$$h_v^{t+1} = \sigma\left({\bf W}^{t+1} \sum_{u \in \mathcal{N}_v} {\bf L}_{uv}~ h_u^t \right) $$
where $h_v^l$ is the representation of node $v$ at update $t$, $\sigma$ is an activation function, ${\bf W^{t}}$ is a weight matrix, ${\bf L_{uv}}$ is the value of the graph Laplacian (which is a matrix) at nodes $u$ and $v$, and finally $\mathcal{N}_v$ is the neighborhood of $v$. Looking at this expression it becomes clear that the value of the summation is always of the same dimension as $h$, no matter how you define the neighborhood $\mathcal{N}_v$. So you are correct that as long as the node representation size is static, the network can take arbitrary graphs as input.
I highly recommend this tutorial paper on GNNs, which I used when first learning about them. Section 2.3 specifically answers your question and discusses how things like cycles and non-positional graphs are handled.
