CS224W-圖神經(jīng)網(wǎng)絡(luò) 筆記6.2：Message Passing and Node Classification - 三類主要的節(jié)點(diǎn)分類算法介紹

本文總結(jié)之日CS224W Winter 2021只更新到了第四節(jié)，所以下文會參考2021年課程的PPT并結(jié)合2019年秋季課程進(jìn)行總結(jié)以求內(nèi)容完整

課程主頁：CS224W: Machine Learning with Graphs

視頻鏈接：【斯坦福】CS224W：圖機(jī)器學(xué)習(xí)( 中英字幕 | 2019秋)

[toc]

引言

前面，接著上文節(jié)點(diǎn)分類的協(xié)作分類算法思想介紹。這節(jié)具體看看細(xì)分的三類算法。

關(guān)系分類 relational classification
迭代分類 iterative classification
信念傳播 belief propagation

1. 概率關(guān)系分類(Probabilistic Relational Classifier)

1.1 算法過程

基本思想：每個節(jié)點(diǎn)類別的概率是其鄰接節(jié)點(diǎn)的加權(quán)平均。過程如下：

給已知和未知標(biāo)簽的節(jié)點(diǎn)分概率
- 未知的可初始化為0，或者其他先驗的概率值
隨機(jī)選擇節(jié)點(diǎn)更新其概率值為其鄰居的類別概率的加權(quán)平均值。
- 直到達(dá)到收斂或最大迭代次數(shù)

圖片

模型存在問題：

模型不一定收斂；
該模型并沒有使用到節(jié)點(diǎn)的特征信息；

為什么采用隨機(jī)選擇節(jié)點(diǎn)？

選擇節(jié)點(diǎn)的順序會影響最終結(jié)果，尤其是對于較小的圖（較大的圖對順序不敏感）。從經(jīng)驗上看，隨機(jī)選取在大多數(shù)情況下都達(dá)到較好的效果。

2. Iterative Classification

2.1 算法過程

因為上述方法沒有利用節(jié)點(diǎn)的特征，Iterative Classification 對這一點(diǎn)進(jìn)行完善。整個過程分為兩步：

Bootstrap Phase：
- 為每個節(jié)點(diǎn)分配一個向量.
- 創(chuàng)建一分類器(local classifier） $f(a_i)$ ：使用節(jié)點(diǎn)自身特征，去預(yù)測每個節(jié)點(diǎn)的標(biāo)簽 $Y_i$ .；分類器可以是 SVM, kNN或者其他
Iteration Phase：
- 通過計數(shù)、眾數(shù)、占比、均值等方式聚合鄰居特征。并更新每個節(jié)點(diǎn)的特征向量 $a_i$ 。
- 用分類器預(yù)測并更新新的標(biāo)簽 $Y_i$ 。
- 重復(fù)過程直到標(biāo)簽穩(wěn)定（收斂）或者達(dá)到最大迭代次數(shù)。

模型存在問題：模型不一定收斂；

3. Belief Propagation

信念傳播（Belief Propagation）通過消息傳遞(passing message)的方式，解決概率圖模型中的條件概率問題。這涉及了概率圖的相關(guān)知識。算法將變量消去法中的求和操作看作一個消息傳遞過程，較好地解決了求解多個邊際分布時的重復(fù)計算問題。

3.1 什么是消息傳遞？

看到 Propagation，部分朋友也會聯(lián)想到深度學(xué)習(xí)訓(xùn)練中的正向傳播和反向傳播（back Propagation）。對于信念傳播（Belief Propagation）涉及信息傳遞（message passing）。對于圖上的每個節(jié)點(diǎn)僅與它的鄰居進(jìn)行信息的收集（collect）和傳遞（distribute）。也就是當(dāng)前節(jié)點(diǎn)的狀態(tài)（state）不光取決于自身還與其鄰居相關(guān)。在消息傳遞時，每個節(jié)點(diǎn)只能從其鄰接接受消息。

借用課上的例子理解。如何基于消息傳遞機(jī)制統(tǒng)計圖的節(jié)點(diǎn)數(shù)？或者說如何讓圖上每個節(jié)點(diǎn)都直到圖中的節(jié)點(diǎn)數(shù)。

對于鏈圖:通過向左向右分別進(jìn)行消息傳遞，對于中間節(jié)點(diǎn)將左邊傳遞的消息和和右邊傳遞的消息的進(jìn)行匯總，并加上自身的1，實(shí)現(xiàn)圖上節(jié)點(diǎn)數(shù)的統(tǒng)計。
對于樹圖；通過加選中節(jié)點(diǎn)作為根節(jié)點(diǎn)（root node），其余節(jié)點(diǎn)分別向根節(jié)點(diǎn)傳遞消息，最終根節(jié)點(diǎn)，匯總不同鄰居傳遞的消息，并加上自身的1，實(shí)現(xiàn)圖上節(jié)點(diǎn)數(shù)的統(tǒng)計。

圖片

當(dāng)圖上有環(huán)（loop/circle）時，傳統(tǒng)的BP算法不適用，這時可以采用Loopy Belief Propagation。

3.2 Loopy Belief Propagation

在闡述具體算法前需要，先做一些符號定義。（可將下面的狀態(tài)替換為標(biāo)簽更好理解）。

Label-Label potential matrix $\psi$ ：其中 $\psi(Y_i, Y_j)$ 表示節(jié)點(diǎn) $i$ 是類別 $Y_i$ 的條件下，其鄰接節(jié)點(diǎn) $j$ 為類別 $Y_j$ 的概率;這反映的就是上面介紹的相鄰節(jié)點(diǎn)間的相關(guān)性correlation。
prior belief $\phi$ ： $\phi_i(Y_i)$ 表示節(jié)點(diǎn) $i$ 為類別 $Y_i$ 的先驗概率；
message $m_{i->j}(Y_j)$ : 節(jié)點(diǎn)預(yù)測其鄰接節(jié)點(diǎn) $j$ 為狀態(tài) $Y_j$ 的概率
stats $\mathcal{L}$ : 表示所有的狀態(tài)