Body: <p>In the <a href="https://arxiv.org/pdf/1805.10002.pdf" rel="nofollow noreferrer">label propagation algorithm</a> in section 3.2.3, we know the label of some nodes and we want to predict the label for the rest of the nodes whose labels we don't know. The update formula for this is the following:
  <span class="math-container">$$F(t+1) = \alpha SF(t) + (1-\alpha)Y $$</span>
  where <span class="math-container">$F(t)$</span> is predicted label from timestep t and <span class="math-container">$S$</span> can be considered as an adjacency matrix, <span class="math-container">$Y$</span> is the label for both the unlabeled data and labeled data. In the case of labeled data, we initialize <span class="math-container">$Y$</span> with ground truth and for the unlabeled data, we randomly initialize their label and assign it to <span class="math-container">$Y$</span>.
  Now, the most problematic part is I think the <span class="math-container">$Y$</span> matrix. Since I do not know the label of some nodes, so we initialize with some random value and keep Y as a constant throughout this iterative process.
  We can calculate the optimal value of F directly using:
  <span class="math-container">$$F^{*} = (I - \alpha S)^{-1}Y$$</span>
  But my question is, if we keep Y as a constant ( assign random numbers to unknown nodes as labels) what kind of sense does it make?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-08-06T15:15:34.497Z
Comments.Text: Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/111506/discussion-on-question-by-swakshar-deb-how-to-make-sense-of-label-propagation-fo).
Comments.UserDisplayName: Dennis Soemers
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-03-02T00:31:14.537Z
Comments.Text: One question is: why is $S$ considered to be an adjacency matrix when the formula $\Delta = I - S$ implies that $S = D^{-1} A $ or a symmetric-normalized version? Is it just because we don't care about the constants?
Comments.UserDisplayName: Rocky the Owl
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-03-02T00:32:57.583Z
Comments.Text: Sorry, one other question is: why did we drop the $ (1 - \alpha) $ from the front of the expression for $F^{*}$? Is it just because it is a constant?
Comments.UserDisplayName: Rocky the Owl
Tags: <deep-learning><computer-vision><graph-theory><probabilistic-graphical-models>
Title: How to make sense of label propagation formula in graph neural networks?
UserDisplayName: Swakshar Deb
ThreadText: # How to make sense of label propagation formula in graph neural networks?
  
  (Asked by: username_0 on 2020-08-03)
  
  In the [label propagation algorithm](https://arxiv.org/pdf/1805.10002.pdf) in section 3.2.3, we know the label of some nodes and we want to predict the label for the rest of the nodes whose labels we don't know. The update formula for this is the following:
  $$F(t+1) = \alpha SF(t) + (1-\alpha)Y $$
  where $F(t)$ is predicted label from timestep t and $S$ can be considered as an adjacency matrix, $Y$ is the label for both the unlabeled data and labeled data. In the case of labeled data, we initialize $Y$ with ground truth and for the unlabeled data, we randomly initialize their label and assign it to $Y$.
  Now, the most problematic part is I think the $Y$ matrix. Since I do not know the label of some nodes, so we initialize with some random value and keep Y as a constant throughout this iterative process.
  We can calculate the optimal value of F directly using:
  $$F^{\*} = (I - \alpha S)^{-1}Y$$
  But my question is, if we keep Y as a constant ( assign random numbers to unknown nodes as labels) what kind of sense does it make?
  
  **Tags:** deep-learning, computer-vision, graph-theory, probabilistic-graphical-models
  > **Comments:**
  > **username_1**: Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/111506/discussion-on-question-by-swakshar-deb-how-to-make-sense-of-label-propagation-fo).  
  > **username_2**: One question is: why is $S$ considered to be an adjacency matrix when the formula $\Delta = I - S$ implies that $S = D^{-1} A $ or a symmetric-normalized version? Is it just because we don't care about the constants?  
  > **username_2**: Sorry, one other question is: why did we drop the $ (1 - \alpha) $ from the front of the expression for $F^{*}$? Is it just because it is a constant?  
  
  ---
  
  ## 0 answers
  
  