Answers.Body: <p>In the introduction, the authors write</p>
  <blockquote>
  <p>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 <strong>label information is smoothed over the graph via some form of explicit graph-based regularization</strong> (Zhu et al., 2003; Zhou et al., 2004; Belkin et al., 2006; Weston et al., 2012), e.g. by using a <strong>graph Laplacian regularization term</strong> in the loss function:
  <span class="math-container">$$
  \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)
  $$</span>
  Here, <span class="math-container">$\mathcal{L}_{0}$</span> denotes the supervised loss w.r.t. the labeled part of the graph, <span class="math-container">$f(\cdot)$</span> can be a neural network-like differentiable function, <span class="math-container">$\lambda$</span> is a weighing factor and <span class="math-container">$X$</span> is a matrix of node feature vectors <span class="math-container">$X_{i}$</span>. <span class="math-container">$\color{blue}{\Delta}=D-\color{red}{A}$</span> denotes the unnormalized graph Laplacian of an undirected graph <span class="math-container">$\mathcal{G}=(\mathcal{V}, \mathcal{E})$</span> with <span class="math-container">$N$</span> nodes <span class="math-container">$v_{i} \in \mathcal{V}$</span>, edges <span class="math-container">$\left(v_{i}, v_{j}\right) \in \mathcal{E}$</span>, an adjacency matrix <span class="math-container">$\color{red}{A} \in \mathbb{R}^{N \times N}$</span> (binary or weighted) and a degree matrix <span class="math-container">$D_{i i}=\sum_{j} \color{red}{A}_{i j} .$</span> The formulation of Eq. 1 relies on the <strong>assumption that connected nodes in the graph are likely to share the same label</strong>. This assumption, however, <strong>might restrict modeling capacity, as graph edges need not necessarily encode node similarity, but could contain additional information</strong>.</p>
  </blockquote>
  <p>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, <span class="math-container">$\mathcal{L}$</span>, which is the sum of <span class="math-container">$L_0$</span> and a <strong>regularisation term</strong>, where</p>
  <ul>
  <li><p><span class="math-container">$L_0$</span> 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</p>
  </li>
  <li><p><span class="math-container">$\mathcal{L}_{\text {reg }}$</span> 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 <span class="math-container">$\color{red}{A}$</span> (the adjacency matrix) or <span class="math-container">$\color{blue}{\Delta}$</span> (the Laplacian).</p>
  </li>
  </ul>
  <p>However, this approach, as they claim, can be limiting, and the explanation is above (the last sentences <strong>in bold</strong> of the quoted excerpt).</p>
  <p>To overcome this limitation, they decide to pass the adjacency matrix <span class="math-container">$\color{red}{A}$</span> to the neural network <span class="math-container">$f$</span>, or, as they claim, to condition <span class="math-container">$f$</span> on <span class="math-container">$\color{red}{A}$</span>. The idea is that, by doing this, the neural network <span class="math-container">$f$</span> will learn the graph structure. They write</p>
  <blockquote>
  <p>In this work, we encode the graph structure directly using a neural network model <span class="math-container">$f(X, \color{red}{A})$</span> and train on a supervised target <span class="math-container">$\mathcal{L}_{0}$</span> <strong>for all nodes with labels</strong>, thereby <strong>avoiding explicit graph-based regularization in the loss function</strong>. Conditioning <span class="math-container">$f(\cdot)$</span> on the adjacency matrix of the graph will allow the model to <strong>distribute gradient information from the supervised loss <span class="math-container">$\mathcal{L}_{0}$</span></strong> and will enable it to <strong>learn representations of nodes both with and without labels</strong>.</p>
  </blockquote>
  <p>So, their graph neural network is defined as follows (equation 9)</p>
  <p><span class="math-container">$$
  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),
  $$</span>
  where <span class="math-container">$Z$</span> are the predictions (i.e. labels for the nodes <span class="math-container">$X$</span>).</p>
  <p>Their loss function is then defined only for <span class="math-container">$X$</span> that have labels</p>
  <p><span class="math-container">$$\mathcal{L}=-\sum_{l \in \mathcal{Y}_{L}} \sum_{f=1}^{F} Y_{l f} \ln Z_{l f},$$</span></p>
  <p>where <span class="math-container">$\mathcal{Y}_{L}$</span> is the set of node indices that have labels. However, note that <span class="math-container">$Z_{l f}$</span> is still computed as a function of <span class="math-container">$\color{red}{A}$</span>, which contains information about all nodes (labeled and unlabelled).</p>
  <p><strong>To conclude</strong>, 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 <span class="math-container">$f$</span> that also takes as an input <span class="math-container">$\color{red}{A}$</span>, <span class="math-container">$f(X, \color{red}{A})$</span>, which, supposedly, is what makes this approach work.</p>
  <p>(<strong>Disclaimer</strong>: 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.)</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-10-23T22:59:09.200Z
Answers.LastActivityDate: 2021-10-25T14:25:58.480Z
Answers.LastEditDate: 2021-10-25T14:25:58.480Z
Answers.UserDisplayName: nbro
Body: <p>In <a href="https://arxiv.org/abs/1609.02907" rel="nofollow noreferrer">Semi-Supervised Classification with Graph Convolutional Networks</a>, the authors say that GCN is an approach for <em>semi-supervised learning</em> (SSL).</p>
  <p>But a GCN is making predictions using only the graph Laplacian. The single place where I find the labels is in its loss function.</p>
  <p><span class="math-container">$$\mathcal{L}=-\sum_{l \in \mathcal{Y}_{L}} \sum_{f=1}^{F} Y_{l f} \ln Z_{l f}$$</span></p>
  <p>How does it make GCN a SSL approach?</p>
  
Tags: <papers><graph-neural-networks><semi-supervised-learning><spectral-clustering>
Title: How are GCN doing semi-supervised learning?
UserDisplayName: willtryagain
ThreadText: # How are GCN doing semi-supervised learning?
  
  (Asked by: username_0 on 2021-10-22)
  
  In [Semi-Supervised Classification with Graph Convolutional Networks](https://arxiv.org/abs/1609.02907), 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?
  
  **Tags:** papers, graph-neural-networks, semi-supervised-learning, spectral-clustering
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2021-10-23. Score: 3 | Accepted answer
  
  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.)
  
  
  ---
  
  