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

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

課程主頁(yè)：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 算法過程

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

1. 給已知和未知標(biāo)簽的節(jié)點(diǎn)分概率

2. • 未知的可初始化為0冶忱，或者其他先驗(yàn)的概率值

3. 隨機(jī)選擇節(jié)點(diǎn)更新其概率值為其鄰居的類別概率的加權(quán)平均值庆揪。

4. • 直到達(dá)到收斂或最大迭代次數(shù)

圖片

模型存在問題：

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

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

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

2. Iterative Classification

2.1 算法過程

因?yàn)樯鲜龇椒]有利用節(jié)點(diǎn)的特征，Iterative Classification 對(duì)這一點(diǎn)進(jìn)行完善前计。整個(gè)過程分為兩步：

1. Bootstrap Phase：

2. • 為每個(gè)節(jié)點(diǎn)分配一個(gè)向量.
   • 創(chuàng)建一分類器(local classifier）：使用節(jié)點(diǎn)自身特征胞谭，去預(yù)測(cè)每個(gè)節(jié)點(diǎn)的標(biāo)簽.；分類器可以是 SVM, kNN或者其他

3. Iteration Phase：

4. • 通過計(jì)數(shù)男杈、眾數(shù)丈屹、占比、均值等方式聚合鄰居特征伶棒。并更新每個(gè)節(jié)點(diǎn)的特征向量 旺垒。
   • 用分類器 預(yù)測(cè)并更新新的標(biāo)簽。
   • 重復(fù)過程直到標(biāo)簽穩(wěn)定（收斂）或者達(dá)到最大迭代次數(shù)肤无。

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

3. Belief Propagation

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

3.1 什么是消息傳遞业岁？

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

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

• 對(duì)于鏈圖:通過向左向右分別進(jìn)行消息傳遞姚垃，對(duì)于中間節(jié)點(diǎn)將左邊傳遞的消息和和右邊傳遞的消息的進(jìn)行匯總念链，并加上自身的1，實(shí)現(xiàn)圖上節(jié)點(diǎn)數(shù)的統(tǒng)計(jì)积糯。
• 對(duì)于樹圖掂墓；通過加選中節(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)計(jì)吃嘿。

圖片

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

3.2 Loopy Belief Propagation

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

1. Label-Label potential matrix ：其中表示節(jié)點(diǎn)是類別的條件下嘱支，其鄰接節(jié)點(diǎn)為類別的概率;這反映的就是上面介紹的相鄰節(jié)點(diǎn)間的相關(guān)性correlation。
2. prior belief ：表示節(jié)點(diǎn)為類別的先驗(yàn)概率挣饥；
3. message : 節(jié)點(diǎn)預(yù)測(cè)其鄰接節(jié)點(diǎn)為狀態(tài)的概率
4. stats : 表示所有的狀態(tài)

有了上面的定義斗塘，可以得出節(jié)點(diǎn)向其鄰接節(jié)點(diǎn)發(fā)送的消息為：

對(duì)

整個(gè)過程如下：

圖片

模型優(yōu)點(diǎn)：

• 實(shí)現(xiàn)簡(jiǎn)單，極易并行化亮靴；

• 普適性強(qiáng)，適用所有圖模型于置；對(duì)于有環(huán)的圖茧吊，也可以使用LBP算法，因?yàn)樵趯?shí)踐中

• • a：環(huán)的回路較長(zhǎng)八毯，
  • b：環(huán)的某些邊的相關(guān)性correlation較小

使得傳播過程中其影響被削弱搓侄。

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

3.3 舉例

課上老師給了一個(gè)將LBP用于在線拍賣網(wǎng)絡(luò)的欺詐識(shí)別（NetProbe）话速。論文如下

http://www.cs.cmu.edu/~christos/PUBLICATIONS/netprobe-www07.pdf

總結(jié)

說實(shí)話讶踪，對(duì)于BP算法的理解還很表面，希望后面通過數(shù)據(jù)和代碼加深理解泊交。

參考資料

1. https://zhuanlan.zhihu.com/p/279561894
2. [PRML]圖模型推論(四)--循環(huán)信念傳播
3. https://www.cnblogs.com/Leo_wl/p/3506242.html