In Semi-Supervised Classification with Graph Convolutional Networks, the authors say that GCN is an approach for semi-supervised learning (SSL).
But a GCN is making predictions using only the graph Laplacian. The single place where I find the labels is in its loss function.
$$\mathcal{L}=-\sum_{l \in \mathcal{Y}_{L}} \sum_{f=1}^{F} Y_{l f} \ln Z_{l f}$$
How does it make GCN a SSL approach?
In the introduction, the authors write
We consider the problem of classifying nodes (such as documents) in a graph (such as a citation network), where labels are only available for a small subset of nodes. This problem can be framed as graph-based semi-supervised learning, where label information is smoothed over the graph via some form of explicit graph-based regularization (Zhu et al., 2003; Zhou et al., 2004; Belkin et al., 2006; Weston et al., 2012), e.g. by using a graph Laplacian regularization term in the loss function: $$ \mathcal{L}=\mathcal{L}_{0}+\lambda \mathcal{L}_{\text {reg }}, \quad \text { with } \quad \mathcal{L}_{\text {reg }}=\sum_{i, j} \color{red}{A}_{i j}\left\|f\left(X_{i}\right)-f\left(X_{j}\right)\right\|^{2}=f(X)^{\top} \color{blue}{\Delta} f(X) $$ Here, $\mathcal{L}_{0}$ denotes the supervised loss w.r.t. the labeled part of the graph, $f(\cdot)$ can be a neural network-like differentiable function, $\lambda$ is a weighing factor and $X$ is a matrix of node feature vectors $X_{i}$. $\color{blue}{\Delta}=D-\color{red}{A}$ denotes the unnormalized graph Laplacian of an undirected graph $\mathcal{G}=(\mathcal{V}, \mathcal{E})$ with $N$ nodes $v_{i} \in \mathcal{V}$, edges $\left(v_{i}, v_{j}\right) \in \mathcal{E}$, an adjacency matrix $\color{red}{A} \in \mathbb{R}^{N \times N}$ (binary or weighted) and a degree matrix $D_{i i}=\sum_{j} \color{red}{A}_{i j} .$ The formulation of Eq. 1 relies on the assumption that connected nodes in the graph are likely to share the same label. This assumption, however, might restrict modeling capacity, as graph edges need not necessarily encode node similarity, but could contain additional information.
So, if you want to solve a node classification problem, where labels are available only for a small subset of the nodes, you can solve it by framing it with a specific loss function, $\mathcal{L}$, which is the sum of $L_0$ and a regularisation term, where
$L_0$ is the term of the loss function that takes care of the nodes that have labels (i.e. it's computed as a function of the nodes that have labels), while
$\mathcal{L}_{\text {reg }}$ is supposed to take care of the nodes without (and with) labels. Why? I don't know exactly, but I suspect this is due to the fact that it uses the information contained in $\color{red}{A}$ (the adjacency matrix) or $\color{blue}{\Delta}$ (the Laplacian).
However, this approach, as they claim, can be limiting, and the explanation is above (the last sentences in bold of the quoted excerpt).
To overcome this limitation, they decide to pass the adjacency matrix $\color{red}{A}$ to the neural network $f$, or, as they claim, to condition $f$ on $\color{red}{A}$. The idea is that, by doing this, the neural network $f$ will learn the graph structure. They write
In this work, we encode the graph structure directly using a neural network model $f(X, \color{red}{A})$ and train on a supervised target $\mathcal{L}_{0}$ for all nodes with labels, thereby avoiding explicit graph-based regularization in the loss function. Conditioning $f(\cdot)$ on the adjacency matrix of the graph will allow the model to distribute gradient information from the supervised loss $\mathcal{L}_{0}$ and will enable it to learn representations of nodes both with and without labels.
So, their graph neural network is defined as follows (equation 9)
$$ Z=f(X, \color{red}{A})=\operatorname{softmax}\left(\hat{\color{red}{A}} \operatorname{ReLU}\left(\hat{\color{red}{A}} X W^{(0)}\right) W^{(1)}\right), $$ where $Z$ are the predictions (i.e. labels for the nodes $X$).
Their loss function is then defined only for $X$ that have labels
$$\mathcal{L}=-\sum_{l \in \mathcal{Y}_{L}} \sum_{f=1}^{F} Y_{l f} \ln Z_{l f},$$
where $\mathcal{Y}_{L}$ is the set of node indices that have labels. However, note that $Z_{l f}$ is still computed as a function of $\color{red}{A}$, which contains information about all nodes (labeled and unlabelled).
To conclude, their approach is a semi-supervised learning approach because they train the neural network with a training dataset, which is only partially labeled, to perform node classification. Their approach is different from previous approaches (which include a regularisation term to account for the part of the graph without labels) by defining the graph neural network as a function $f$ that also takes as an input $\color{red}{A}$, $f(X, \color{red}{A})$, which, supposedly, is what makes this approach work.
(Disclaimer: I've only quickly read a few other parts of the paper, and it had been a while since I extensively read something about graph neural networks.)
