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