【CS224W課程筆記】Message Parsing and Node Classification

Outline

Main question today：給定一個(gè)部分節(jié)點(diǎn)有標(biāo)簽的網(wǎng)絡(luò)骨坑，如何為網(wǎng)絡(luò)中的剩余節(jié)點(diǎn)分配標(biāo)簽？

Collective classification：為網(wǎng)絡(luò)中所有節(jié)點(diǎn)分配標(biāo)簽的思想，直覺上是利用網(wǎng)絡(luò)中存在的關(guān)聯(lián)（Correlations）。本次課程將討論以下三類方法：

Relation Classification
Iterative Classification
Belief Propagation

有三種類型的依賴將導(dǎo)致關(guān)聯(lián)：

Homophily（Individual Characteristics -> Social Connections): 個(gè)體與相似的其他個(gè)體交往和聯(lián)系的趨勢妆毕。這種相似性可以體現(xiàn)在年齡、性別贮尖、組織角色等多種屬性上笛粘。例如：喜歡相同音樂類型的人更可能建立社交聯(lián)系（在音樂會(huì)上見面，在音樂論壇上互動(dòng)等）
Infuence (Social Connections -> Individual Characteristics): 社會(huì)關(guān)聯(lián)將影響到個(gè)人特性湿硝。
Confounding (Environment -> Individual Characteristics; Environment -> Social Connections)

Classification with Network Data

Problem：給定一個(gè)圖和少數(shù)帶有標(biāo)簽的節(jié)點(diǎn)薪前，如何利用網(wǎng)絡(luò)中觀察到的關(guān)聯(lián)幫助預(yù)測其它節(jié)點(diǎn)的標(biāo)簽？

Motivation：相似的節(jié)點(diǎn)往往離得很近或直接相連关斜。

Guilt-by-association：如果我與一個(gè)帶有標(biāo)簽X的節(jié)點(diǎn)相連示括，我的標(biāo)簽很有可能也是X。
網(wǎng)絡(luò)中對象O的類別標(biāo)簽可能取決于：O的特性蚤吹、O鄰居的標(biāo)簽例诀、O鄰居的特性。

Fomulation：令 $W$ 表示一個(gè) $n$ 個(gè)節(jié)點(diǎn)上的 $n \times n$ 的帶權(quán)鄰接矩陣裁着。令 $Y=\{-1, 0, 1\}^n$ 表示標(biāo)簽向量繁涂，其中1表示正類節(jié)點(diǎn)，-1表示負(fù)類節(jié)點(diǎn)二驰，0表示無標(biāo)簽節(jié)點(diǎn)扔罪。目標(biāo)是預(yù)測哪些無標(biāo)簽節(jié)點(diǎn)可能是正類的。

Collective Classification

Markov Assumption: 節(jié)點(diǎn) $i$ 的標(biāo)簽 $Y_i$ 取決于其鄰居 $N_i$ 的標(biāo)簽
$P(Y_i|i) = P(Y_i|N_i)$

Collective Classification涉及三個(gè)步驟：

Local Classifier：（bootstrap step）分配初始標(biāo)簽桶雀。根據(jù)節(jié)點(diǎn)屬性或特性預(yù)測標(biāo)準(zhǔn)矿酵，這是一個(gè)標(biāo)準(zhǔn)的分類任務(wù)唬复，不涉及網(wǎng)絡(luò)信息。
Relational Classifier：捕捉節(jié)點(diǎn)之間的相關(guān)性全肮。學(xué)習(xí)一個(gè)基于鄰居標(biāo)簽屬性對各節(jié)點(diǎn)進(jìn)行分類的分類器敞咧，這里用到了網(wǎng)絡(luò)的信息。
Collective Inference：通過網(wǎng)絡(luò)傳播相關(guān)性辜腺。將relational classification迭代的用于每個(gè)節(jié)點(diǎn)休建，直到相鄰標(biāo)簽之間的非一致性最小化。網(wǎng)絡(luò)的結(jié)構(gòu)將嚴(yán)重影響最終的預(yù)測結(jié)果评疗。

注意：如今所介紹的所有分類方法都是Approximate Inference测砂，Exact Inference對于任意網(wǎng)絡(luò)而言都是一個(gè)NP-hard問題，只有當(dāng)網(wǎng)絡(luò)滿足特定條件時(shí)百匆，才可以進(jìn)行Exact Inference砌些。此外接下來介紹的所有算法都是迭代算法。

Probabilistic Relational Classifier

Basic Idea： $Y_i$ 類別的可能性是其鄰居類別可能性的加權(quán)平均加匈。對于有標(biāo)簽節(jié)點(diǎn)存璃，使用groud-truth的 $Y$ 標(biāo)簽進(jìn)行初始化；對于無標(biāo)簽節(jié)點(diǎn)矩动，對 $Y$ 進(jìn)行統(tǒng)一初始化有巧。以任意順序更新節(jié)點(diǎn)，直到收斂或達(dá)到最大次數(shù)悲没。

對每個(gè)節(jié)點(diǎn) $i$ 和標(biāo)簽 $c$ 重復(fù)進(jìn)行如下計(jì)算（其中 $N_i$ 表示節(jié)點(diǎn)i的鄰居數(shù)篮迎， $W(i,j)$ 表示從 $i$ 到 $j$ 的邊的權(quán)重）：
$P(Y_i = c) = \frac{1}{|N_i|} \sum_{(i,j)\in E} W(i,j)P(Y_j=c)$

該方法的困難在于無法保證收斂以及模型無法用到節(jié)點(diǎn)的特征信息。

Iterative classification

Main idea：克服Relational Classifier未使用節(jié)點(diǎn)屬性的缺點(diǎn)示姿，基于節(jié)點(diǎn) $i$ 的屬性和鄰居節(jié)點(diǎn) $N_i$ 的標(biāo)簽對節(jié)點(diǎn) $i$ 進(jìn)行分類甜橱。為每個(gè)節(jié)點(diǎn) $i$ 創(chuàng)建一個(gè)平面向量 $a_i$ ，然后使用 $a_i$ 訓(xùn)練一個(gè)分類器栈戳；每個(gè)節(jié)點(diǎn)具有不同數(shù)量的鄰居岂傲，因此可以使用以下方法進(jìn)行匯總（aggregate）：計(jì)數(shù)（有多少鄰居節(jié)點(diǎn)擁有某種特性）、模式子檀、比例镊掖、均值、存在等褂痰。

Basic architechture：

Bootstrap phase：將每個(gè)節(jié)點(diǎn) $i$ 轉(zhuǎn)換為平面向量 $a_i$ 亩进，使用local classifier $f(a_i)$ ，如SVM缩歪、kNN計(jì)算 $Y_i$ 的最佳值归薛；
Iteration phase：對每個(gè)節(jié)點(diǎn) $i$ 重復(fù)以下過程：根據(jù)迭代結(jié)果更新節(jié)點(diǎn)向量 $a_i$ ，重新計(jì)算 $f(a_i)$ ，迭代該過程直到類標(biāo)簽穩(wěn)定或達(dá)到最大迭代次數(shù)主籍。

Belief Propagation

Belief Propagation是一種用于回答圖形模型中的條件概率查詢的動(dòng)態(tài)編程方法习贫，鄰居變量在其迭代過程中彼此傳遞信息，在達(dá)成共識(shí)后千元，將計(jì)算最終的belief苫昌。

Message Passing
Task: 計(jì)算圖中的節(jié)點(diǎn)數(shù)
Condition: 每一個(gè)節(jié)點(diǎn)只能與鄰居節(jié)點(diǎn)傳遞信息
Solution: 每一個(gè)節(jié)點(diǎn)接收其鄰居節(jié)點(diǎn)傳遞的信息，更新自己的信息然后繼續(xù)傳遞

Message Passing

注意：在一個(gè)有環(huán)圖中該過程無法正確運(yùn)作幸海。

Loopy BP algorithm
What message will i send to j蜡歹？取決于i從它的鄰居k接收到的信息，每一個(gè)鄰居將會(huì)傳遞給i對i狀態(tài)的belief信息涕烧。

Notion：

Label-label potential matrix $\psi$ : 節(jié)點(diǎn)和其鄰居之間的依賴關(guān)系。 $\psi(Y_i, Y_j)$ 等于給定節(jié)點(diǎn) $j$ 處于狀態(tài) $Y_i$ 下的鄰居節(jié)點(diǎn) $i$ 汗洒，其狀態(tài)為 $y_j$ 的可能性议纯。
Prior belief $/phi$ : 節(jié)點(diǎn) $i$ 處于狀態(tài) $Y_i$ 下的概率 $\phi_i(Y_i)$ 。
$m_{i \rightarrow j}(Y_j)$ 表示 $i$ 對 $j$ 處于狀態(tài) $Y_j$ 的估計(jì)溢谤。
$\mathcal{L}$ 是所有的狀態(tài)集合瞻凤。

Process：

初始化所有的消息為1；
對每個(gè)結(jié)點(diǎn)重復(fù)如下操作：
$m_{i \rightarrow j}(Y_j) = \alpha \sum_{Y_i \in \mathcal{L}} \psi(Y_i, Y_j) \phi_i(Y_i) \prod_{k \in \mathcal{N}_i \backslash j} m_{k \rightarrow i}(Y_i)$
收斂后世杀，令 $b_i(Y_i)$ 表示 $i$ 處于狀態(tài) $Y_i$ 的belief阀参，其計(jì)算如下：
$b_i(Y_i) = \alpha \phi_i(Y_i) \prod_{j \in \mathcal{N}_i} m_{j \rightarrow i}(Y_i), \forall Y_i \in \mathcal{L}$

Advantages:

很容易進(jìn)行編程和并行計(jì)算
容易泛化到其它圖模型

Challenges:
不能保證收斂，尤其是在有很多閉環(huán)的情況下