CS224W-圖神經(jīng)網(wǎng)絡(luò) 筆記6.1：Message Passing and Node Classification - 節(jié)點分類方法簡介

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

課程主頁：CS224W: Machine Learning with Graphs

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

[toc]

引言

如何在給定一個網(wǎng)絡(luò)上某些節(jié)點的標(biāo)簽毅否，為所有其他無標(biāo)簽的節(jié)點分配標(biāo)簽？ 這類任務(wù)在現(xiàn)實生活中很常見妻顶。本節(jié)要介紹的協(xié)作分類(Collective Classification)是一種解決方案队贱。

協(xié)作分類(Collective Classification)

協(xié)作分類(Collective Classification)是一種有效的網(wǎng)絡(luò)數(shù)據(jù)分類方法,它利用網(wǎng)絡(luò)數(shù)據(jù)中節(jié)點間的關(guān)聯(lián)關(guān)系，結(jié)合部分節(jié)點標(biāo)簽和屬性兔朦，推斷未知標(biāo)簽的節(jié)點的標(biāo)簽。它是一種半監(jiān)督的節(jié)點分類方法磨确。

ps:其實從經(jīng)驗來看沽甥，當(dāng)有標(biāo)簽節(jié)點數(shù)量足夠時，應(yīng)當(dāng)優(yōu)先考慮有監(jiān)督的節(jié)點分類算法乏奥。

1 算法思想

1.1 為什么可以利用關(guān)聯(lián)關(guān)系摆舟，推斷節(jié)點標(biāo)簽?

因為，網(wǎng)絡(luò)中蘊含著相關(guān)性信息邓了。

網(wǎng)絡(luò)環(huán)境使得個體行為產(chǎn)生關(guān)聯(lián)恨诱。具體相關(guān)性原因（形式）有三種：

1. homophily：“物以類聚，人以群分”骗炉，有相同性質(zhì)的節(jié)點間可能存在更密切的聯(lián)系.比如：有相同喜好的人照宝，更傾向于產(chǎn)生聯(lián)系。
2. influence：“近朱者赤句葵，近墨者黑”厕鹃，一個個體有可能會受其它個體的影響而具有某種性質(zhì)兢仰。如因為朋友的推薦，也會產(chǎn)生相同的喜好
3. confounding：大環(huán)境可能會對個體性質(zhì)和個體間的聯(lián)系產(chǎn)生影響剂碴“呀可以看做非前兩種原因的其他原因。
   圖片

這三種形式忆矛，在現(xiàn)實網(wǎng)絡(luò)的觀察中都得到驗證察蹲。如種族網(wǎng)絡(luò)：

圖片

1.2 如何利用關(guān)聯(lián)關(guān)系，推斷節(jié)點標(biāo)簽?

Guilt-by-association

(我將其直譯為 連累法).如果一個節(jié)點連接到具有特定標(biāo)簽的另一個節(jié)點催训，則該節(jié)點很可能有相同標(biāo)簽递览。換句話說：相似的節(jié)點通常距離很近或者直接相連。

基于這樣的假設(shè)可以進行如區(qū)分惡意網(wǎng)站識別頁等任務(wù)瞳腌。因為通常惡意網(wǎng)頁往往會相互鏈接绞铃，以提高知名度，使得看起來可信嫂侍，以提高在搜索引擎中排名儿捧。

課上老師說，Guilt-by-association法要求 網(wǎng)絡(luò)節(jié)點有同質(zhì)性（homophily）挑宠。

如何進行節(jié)點分類

具體可利用信息有

圖片

但是菲盾，如果只使用這些信息，而不使用網(wǎng)絡(luò)結(jié)構(gòu)屬性各淀，那么我們只會在這些特征上訓(xùn)練簡單的分類器懒鉴。為了使我們能夠進行集體分類，我們還需要考慮網(wǎng)絡(luò)拓撲結(jié)構(gòu)碎浇。這就是我們要介紹的協(xié)作分類（Collective Classification）临谱。

2. 協(xié)作分類的步驟

需要以下三個組成部分：

圖片

1. local classifier：本地分類器

• 目的：預(yù)測初始標(biāo)簽：

  僅依據(jù)節(jié)點自身屬性和特征，不涉及網(wǎng)絡(luò)信息奴璃。這里可以用很多常見的分類器悉默，甚至是kNN。其實苟穆，如果這一步效果足夠好抄课，是沒有必要進行后續(xù)的操作，但通常有標(biāo)簽的數(shù)量非常少雳旅，這一步的效果跟磨，不會太好。

1. Relational Classifier：關(guān)系分類器

• 目的：基于網(wǎng)絡(luò)捕捉節(jié)點相關(guān)性（如：homophily 和 influence）

  根據(jù)節(jié)點鄰接的標(biāo)簽和特征預(yù)測該節(jié)點標(biāo)簽攒盈。運用了網(wǎng)絡(luò)信息抵拘。

1. collective inference：協(xié)作推斷

• 目的：基于網(wǎng)絡(luò)傳遞相關(guān)性信息

  不想僅使用鄰居的信息，而是希望通過多次迭代沦童，能夠獲取其他節(jié)點的信息仑濒。

  具體的叹话，是將關(guān)系分類器迭代運用到每個節(jié)點上，迭代直到收斂（節(jié)點與鄰居的標(biāo)簽差異程度inconsistency最卸胀）驼壶。另外，網(wǎng)絡(luò)的結(jié)構(gòu)會影響最終的預(yù)測結(jié)果喉酌。

2.1 協(xié)作分類的種類

它有三種代表性的近似推斷的方法热凹，都是迭代型算法。分別：

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

近似推斷有個前提假設(shè)——馬爾可夫假設(shè)（Markov Assumption）泪电，即節(jié)點的類別只取決于它的鄰接節(jié)點 . 用條件概率表示

關(guān)于條件概率的精確推斷和近似推斷

從概率圖模型角度看般妙，如果我們將每個節(jié)點表示為離散的隨機變量，其類成員的聯(lián)合質(zhì)量函數(shù)為相速，則節(jié)點的邊沿分布為所有其他節(jié)點上的的總和碟渺。

• 精確推斷（exact inferance） 精確推斷 需要是節(jié)點數(shù)的指數(shù)級，是一個np-hard的問題突诬。
• 近似推斷（approximate inferance） 通過縮小傳播范圍（例如苫拍，僅鄰居）和變量的數(shù)量，通過聚合來近似解決推斷問題旺隙。并且大多數(shù)情況下可以取得不錯的結(jié)果绒极。

總結(jié)

各類方法的介紹放在下一節(jié)，同時結(jié)合具體案例蔬捷，進一步加深理解垄提，敬請期待。

參考文章

• https://snap-stanford.github.io/cs224w-notes/machine-learning-with-networks/message-passing-and-node-classification
• https://zhuanlan.zhihu.com/p/279561894
• https://blog.csdn.net/New2World/article/details/105410276