圖神經網絡（GNN）的核心思想之一是通過信息傳播（Message Passing） 機制來學習節點表示，并進而完成節點分類等任務。本講重點探討如何利用圖中節點間的連接關系（即“法圖信息”，或更準確地稱為“圖結構信息”）來對未標記節點進行半監督分類。
1. 問題定義：半監督節點分類
在許多現實圖數據（如社交網絡、引用網絡）中，僅有部分節點擁有標簽（如用戶的興趣類別、論文的研究領域）。目標是利用這些少量標簽以及豐富的圖結構（連接關系），預測未標記節點的類別。這屬于典型的半監督學習場景。
關鍵假設：同質性（Homophily）。即相連的節點傾向于具有相似的屬性或標簽。“物以類聚，人以群分”是圖數據中普遍存在的規律，這構成了信息傳播的理論基礎。
2. 核心思想：基于集體分類的迭代算法
傳統方法不依賴節點特征，僅利用圖結構和已知標簽。基本框架是迭代式的集體分類（Collective Classification），包含三個主要步驟：
1. 局部分類器（Local Classifier）：初始時，僅使用節點自身的屬性（如果有）或給予未標記節點一個初始預測。
2. 關系分類器（Relational Classifier）：利用鄰居節點的標簽或預測結果來更新當前節點的預測。其核心公式常表示為：
\[ P(Yi = c) = \frac{1}{\mathcal{N}(i)} \sum{j \in \mathcal{N}(i)} P(Y_j = c) \]
即，節點 \(i\) 屬于類別 \(c\) 的概率是其所有鄰居 \(j\) 屬于該類別概率的平均。這直接體現了“鄰居影響我”的思想。
- 集體推理（Collective Inference）：迭代執行步驟2，讓標簽信息在整個圖中傳播，直至收斂或達到迭代次數。常用方法包括迭代分類、信念傳播等。
3. 典型算法：標簽傳播
標簽傳播算法（Label Propagation） 是上述思想的經典實現。
- 初始化：將所有已標記節點的標簽固定，未標記節點賦予一個統一的隨機分布或均勻分布。
- 迭代更新：每個節點將其標簽分布更新為其所有鄰居節點標簽分布的加權平均。對于未標記節點：
\[ \mathbf{Y}i^{(t+1)} = \sum{j \in \mathcal{N}(i)} \frac{1}{\deg(i)} \mathbf{Y}j^{(t)} \]
其中 \(\mathbf{Y}i\) 是節點 \(i\) 的標簽概率向量。
- 收斂：重復迭代直到標簽分布變化很小或達到最大迭代次數。未標記節點的標簽取其概率最大的類別。
該算法的核心是創建一個“標簽流”從已標記節點通過邊向未標記節點擴散的過程。
4. 與圖神經網絡的聯系
現代圖神經網絡（如GCN）本質上是帶參數、多層次、結合節點特征的信息傳播框架。
- GNN中的消息傳遞（Message Passing） 可以看作上述標簽傳播的可微、參數化、特征增強的擴展。
- 每一層，節點聚合來自其鄰居的消息（經過變換的特征），并結合自身信息更新其表示。
- 通過堆疊多層，信息可以傳播到多跳鄰居，捕獲更廣泛的圖結構上下文。
- 基于學習到的節點表示（而非直接的標簽分布）進行分類預測。
因此，傳統基于圖結構的標簽傳播算法可以視為一個簡單的、無參數、無特征的“單層GNN”。它驗證了純粹利用圖結構進行半監督學習的可行性，并為GNN的設計提供了直觀的動機。
5.
信息傳播與節點分類緊密相連。傳統方法（如標簽傳播）直接利用圖結構的同質性假設，通過迭代平均鄰居標簽來推斷未知節點類別。這些方法雖然簡單，但清晰地展示了圖結構本身蘊含的強大預測信號。現代圖神經網絡繼承了這一核心思想，但通過可學習的非線性變換、節點特征融合以及深度架構，極大地增強了模型的表達能力和適用性，成為處理圖數據半監督學習任務的主流工具。理解這一演進脈絡，有助于我們更深刻地把握GNN的設計原理與優勢。
