本文總結(jié)之日CS224W Winter 2021只更新到了第四節(jié)蔓纠，所以下文會參考2021年課程的PPT并結(jié)合2019年秋季課程進(jìn)行總結(jié)以求內(nèi)容完整
課程主頁：CS224W: Machine Learning with Graphs
視頻鏈接：【斯坦福】CS224W：圖機(jī)器學(xué)習(xí)( 中英字幕 | 2019秋)
1 引言
工作中观游， 我們因?yàn)樗幍膷徫徊煌榔保局邪缪莸慕巧≧ole）也不盡相同卵贱。而在網(wǎng)絡(luò)中滥沫，節(jié)點(diǎn)的拓?fù)浣Y(jié)構(gòu)，決定了節(jié)點(diǎn)的角色也是不一樣的键俱。這就是本節(jié)要研究的內(nèi)容——Structural Roles兰绣。
2 一些新概念（what）
-
角色（Role）：具有相似結(jié)構(gòu)特征的節(jié)點(diǎn)集合，不要求彼此相連编振。
-
-
社區(qū)（communities ）：結(jié)構(gòu)上缀辩，內(nèi)部連通，內(nèi)部可達(dá)的子圖踪央。
-
角色（Roles） 和 社區(qū)（communities ）之間還是有明顯區(qū)別臀玄。兩者概念上是互補(bǔ)。
例如畅蹂，對于計(jì)算機(jī)學(xué)院的社交網(wǎng)絡(luò)而言：
- 角色Roles：有教員健无、工作人員、學(xué)生
- 社區(qū)：有AI研究室液斜、信息研究室累贤、理論研究室等
-
結(jié)構(gòu)等價(jià)（Structural equivalence）：若節(jié)點(diǎn)u和節(jié)點(diǎn)v與所有其他節(jié)點(diǎn)擁有相同的關(guān)系，則稱節(jié)點(diǎn)u和節(jié)點(diǎn)v結(jié)構(gòu)等價(jià)旗唁。
-
換句話說：對所有的其他節(jié)點(diǎn)集 ??, 當(dāng)且僅當(dāng)（iff/if and only）節(jié)點(diǎn) ?? 和 ??之間的連接畦浓，等同于節(jié)點(diǎn) ?? 和 ??之間的連接。如下圖的 結(jié)構(gòu)等價(jià)的節(jié)點(diǎn)4和節(jié)點(diǎn)5（6/7也是一組）：
2.1 為什么Roles很重要检疫？（why）
因?yàn)橛杏茫∏覒?yīng)用廣泛祷嘶！
2.2 怎么找到Structural Roles屎媳？（how）
2.2.1 通過 RolX 方法[1]
簡單來說，就是遞歸抽取節(jié)點(diǎn)特征论巍，然后做無監(jiān)督的聚類烛谊。
該方法有以下特點(diǎn)：
- 無監(jiān)督學(xué)習(xí)方法
- 無需先驗(yàn)知識
- 為每個節(jié)點(diǎn)分配不同Roles混合而成的成員關(guān)系
- 復(fù)雜度隨著網(wǎng)絡(luò)中的邊的數(shù)量
線性增長
2.2.2 流程說明：
RolX 方法具體流程圖如下：大致兩個階段：
- 遞歸特征抽忍逃场（Recursive feature extraction）
- 角色抽日窦帷（Role Extraction）
2.2.2.1 遞歸特征抽取
目的是將節(jié)點(diǎn)轉(zhuǎn)化為特征向量，該特征向量包含了該節(jié)點(diǎn)本身危融、節(jié)點(diǎn)的鄰居節(jié)點(diǎn)的向量的信息鞋怀，然后使用它遞歸生成新的特征双泪。
基礎(chǔ)特征
（自身和鄰居）基礎(chǔ)特征特征工程思路總結(jié)
- 對有向圖，包括入度密似、出度焙矛、總度數(shù)
- 對加權(quán)圖：包括加權(quán)的各個度特征，即權(quán)重聚合
- 鄰居的平均聚類系數(shù)
- egonet的內(nèi)部邊數(shù)残腌，指向egonet邊數(shù)村斟，指出邊數(shù)贫导，總邊數(shù)等。
egonet: 某節(jié)點(diǎn)和它的鄰居蟆盹，以及這些節(jié)點(diǎn)之間的所有邊構(gòu)成的誘導(dǎo)子圖孩灯。
2.2.2.2 算法步驟
以基礎(chǔ)特征集作為開始
使用當(dāng)前節(jié)點(diǎn)特征集生成新特征
尋找高度相關(guān)的特征對
當(dāng)兩個特征的相關(guān)性超過用戶定義的閾值時，刪除其中一個特征
使用mean和sum兩種聚合函數(shù)
-
剪枝操作
隨著每次遞歸迭代逾滥，生成特征的數(shù)量呈指數(shù)增長 (
)钱反。故需要使用
剪枝來減少特征數(shù)量 重復(fù)2
2.2.2.3 角色抽取
RolX 對特征矩陣進(jìn)行非負(fù)矩陣分解，得到最終結(jié)果匣距。
- 最小描述長度進(jìn)行特征篩選（MDL：principle of minimum description length）面哥。
- KL散度評估相似度。
2.3 應(yīng)用舉例
老師舉了論文合作者網(wǎng)絡(luò)角色挖掘的例子毅待。
3 總結(jié)
本節(jié)尚卫，介紹的RolX思想上雖然比較好理解，但是知和行之間還是有不小的差距尸红。計(jì)劃通過代碼運(yùn)行吱涉，加深理解，同時看能不能在實(shí)際業(yè)務(wù)中運(yùn)用外里。論文為資料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
