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