本文總結(jié)之日CS224W Winter 2021只更新到了第四節(jié)，所以下文會參考2021年課程的PPT并結(jié)合2019年秋季課程進行總結(jié)以求內(nèi)容完整
課程主頁：CS224W: Machine Learning with Graphs
視頻鏈接：【斯坦福】CS224W：圖機器學(xué)習(xí)( 中英字幕 | 2019秋)
1 引言
工作中， 我們因為所處的崗位不同，公司中扮演的角色（Role）也不盡相同。而在網(wǎng)絡(luò)中，節(jié)點的拓撲結(jié)構(gòu)，決定了節(jié)點的角色也是不一樣的。這就是本節(jié)要研究的內(nèi)容——Structural Roles。
2 一些新概念（what）
-
角色（Role）：具有相似結(jié)構(gòu)特征的節(jié)點集合，不要求彼此相連。
-
-
社區(qū)（communities ）：結(jié)構(gòu)上，內(nèi)部連通，內(nèi)部可達的子圖。
-
角色（Roles） 和 社區(qū)（communities ）之間還是有明顯區(qū)別。兩者概念上是互補。
例如，對于計算機學(xué)院的社交網(wǎng)絡(luò)而言：
- 角色Roles：有教員、工作人員、學(xué)生
- 社區(qū)：有AI研究室、信息研究室、理論研究室等
-
結(jié)構(gòu)等價（Structural equivalence）：若節(jié)點u和節(jié)點v與所有其他節(jié)點擁有相同的關(guān)系，則稱節(jié)點u和節(jié)點v結(jié)構(gòu)等價。
-
換句話說：對所有的其他節(jié)點集 ??, 當且僅當（iff/if and only）節(jié)點 ?? 和 ??之間的連接，等同于節(jié)點 ?? 和 ??之間的連接。如下圖的 結(jié)構(gòu)等價的節(jié)點4和節(jié)點5（6/7也是一組）：
2.1 為什么Roles很重要？（why）
因為有用！且應(yīng)用廣泛！
2.2 怎么找到Structural Roles？（how）
2.2.1 通過 RolX 方法[1]
簡單來說，就是遞歸抽取節(jié)點特征，然后做無監(jiān)督的聚類。
該方法有以下特點：
- 無監(jiān)督學(xué)習(xí)方法
- 無需先驗知識
- 為每個節(jié)點分配不同Roles混合而成的成員關(guān)系
- 復(fù)雜度隨著網(wǎng)絡(luò)中的邊的數(shù)量
線性增長
2.2.2 流程說明：
RolX 方法具體流程圖如下：大致兩個階段：
- 遞歸特征抽?。≧ecursive feature extraction）
- 角色抽取（Role Extraction）
2.2.2.1 遞歸特征抽取
目的是將節(jié)點轉(zhuǎn)化為特征向量，該特征向量包含了該節(jié)點本身、節(jié)點的鄰居節(jié)點的向量的信息，然后使用它遞歸生成新的特征。
基礎(chǔ)特征
（自身和鄰居）基礎(chǔ)特征特征工程思路總結(jié)
- 對有向圖，包括入度、出度、總度數(shù)
- 對加權(quán)圖：包括加權(quán)的各個度特征，即權(quán)重聚合
- 鄰居的平均聚類系數(shù)
- egonet的內(nèi)部邊數(shù)，指向egonet邊數(shù)，指出邊數(shù)，總邊數(shù)等。
egonet: 某節(jié)點和它的鄰居，以及這些節(jié)點之間的所有邊構(gòu)成的誘導(dǎo)子圖。
2.2.2.2 算法步驟
以基礎(chǔ)特征集作為開始
使用當前節(jié)點特征集生成新特征
尋找高度相關(guān)的特征對
當兩個特征的相關(guān)性超過用戶定義的閾值時，刪除其中一個特征
使用mean和sum兩種聚合函數(shù)
-
剪枝操作
隨著每次遞歸迭代，生成特征的數(shù)量呈指數(shù)增長 (
)。故需要使用
剪枝來減少特征數(shù)量 重復(fù)2
2.2.2.3 角色抽取
RolX 對特征矩陣進行非負矩陣分解，得到最終結(jié)果。
- 最小描述長度進行特征篩選（MDL：principle of minimum description length）。
- KL散度評估相似度。
2.3 應(yīng)用舉例
老師舉了論文合作者網(wǎng)絡(luò)角色挖掘的例子。
3 總結(jié)
本節(jié)，介紹的RolX思想上雖然比較好理解，但是知和行之間還是有不小的差距。計劃通過代碼運行，加深理解，同時看能不能在實際業(yè)務(wù)中運用。論文為資料5，供參考。
4 參考文章
- https://blog.csdn.net/lssx0817/article/details/106195822
- 《網(wǎng)絡(luò)科學(xué)引論》郭世澤 陳哲譯
- https://snap-stanford.github.io/cs224w-notes/preliminaries/motifs-and-structral-roles_lecture
- Automatic discovery of nodes’ structural roles in networks [Henderson, et al. 2011b]
- http://web.eecs.umich.edu/~dkoutra/papers/12-kdd-recursiverole.pdf
