本文總結(jié)之日CS224W Winter 2021只更新到了第四節(jié)，所以下文會參考2021年課程的PPT并結(jié)合2019年秋季課程進行總結(jié)以求內(nèi)容完整
課程主頁：CS224W: Machine Learning with Graphs
視頻鏈接：【斯坦?！緾S224W：圖機器學(xué)習(xí)( 中英字幕 | 2019秋)
1 引言
這篇是CS224W 圖機器學(xué)習(xí)筆記的第一篇，本筆記主要梳理課程的關(guān)鍵點，以及一些圖相關(guān)的基本概念。
1.1 為什么要研究網(wǎng)絡(luò)
- 圖/網(wǎng)絡(luò) 無處不在。
- 跨領(lǐng)域。圖在不同研究領(lǐng)域都有應(yīng)用，如計算機科學(xué)、社會學(xué)、經(jīng)濟學(xué)等等。
- 數(shù)據(jù)豐富。
- 有前景。社交網(wǎng)絡(luò)分析，藥物開發(fā)，AI推理等
1.2 網(wǎng)絡(luò)分析主要研究方向（場景）
- 對節(jié)點的類型/屬性進行預(yù)測。如：節(jié)點分類。
- 預(yù)測兩個節(jié)點是否相連。如：鏈路預(yù)測（link prediction）。
- 識別緊密相連的節(jié)點群。例如：社區(qū)挖掘（Community detection），節(jié)點聚類。
- 計算兩個節(jié)點或者網(wǎng)絡(luò)的相似性 。node embedding / graph embedding
老師在課程中ppt中給了很多現(xiàn)實例子。總之，學(xué)了很有用就對了！！
2 圖的基礎(chǔ)知識
為了研究這些，需要有系統(tǒng)(system) -> 圖(Graph)的建模的過程。
先需要一些網(wǎng)絡(luò)/圖論基本知識
2.1 圖的定義
- A network is a collection of objects where some pairs of objects are connected by links
- 網(wǎng)絡(luò)是互連成對的節(jié)點的集合。
網(wǎng)絡(luò)是一種描述復(fù)雜系統(tǒng)中實體關(guān)聯(lián)的通用語言。是一種通用的數(shù)據(jù)結(jié)構(gòu)。它表示了成分之間的聯(lián)系.
圖的數(shù)據(jù)表示G(N,E) G是圖，V是節(jié)點，E是邊。上面既有圖，又有網(wǎng)絡(luò)，那它們之間的區(qū)別是什么呢？
2.2 網(wǎng)絡(luò)(Network)與圖(Graph)之間區(qū)別
- Network：表示現(xiàn)實世界的系統(tǒng)。舉例：互聯(lián)網(wǎng)（Web）、社交網(wǎng)絡(luò)（ Social network ）等 對應(yīng)描述：網(wǎng)絡(luò)（Network）, 點（node）, 邊（link）
- Graph：是 Network 的數(shù)學(xué)表示。舉例：、社交圖（ Social graph）、知識圖譜（ Knowledge Graph ）等 對應(yīng)描述：圖（Graph）,點（ vertex）, 邊（edge）
很多時候，并不太嚴格區(qū)分。
2.3 網(wǎng)絡(luò)的粗分類（不嚴格）
網(wǎng)絡(luò)大致可分為兩類，有時它們的界線并不那么明顯。
- Networks (Natural Graphs)
第一類可以看做是自然網(wǎng)絡(luò)，比如社會網(wǎng)絡(luò)、社交網(wǎng)絡(luò)、蛋白質(zhì)圖譜、基因圖譜等。
- Information Graphs
第二類就是各種信息匯聚成為的網(wǎng)絡(luò)，如知識圖譜，相似網(wǎng)絡(luò)（similarity netoworks）等等。如基于地址相似度構(gòu)建的地址網(wǎng)路。
2.4 圖論中圖的分類
圖的分類：
2.4.1 根據(jù)邊的方向
- 無向圖，如：同事關(guān)系，論文合作關(guān)系
- 有向圖，如：B站用戶關(guān)注與被關(guān)注關(guān)系
補充概念——度(degree)
定義：連接節(jié)點i的邊的數(shù)量，稱為節(jié)點i的度(數(shù))。
上左圖的無向圖中節(jié)點a的度為4.
對于有向圖，節(jié)點i的度分為
入度in-degree：指向自身邊的邊的數(shù)量。上圖c點的入度是2出度out-degree：指向其他節(jié)點邊的數(shù)量.c點的出度是1
平均度 avg degree:衡量圖的稠密性。等于所有節(jié)點度的平均。
從圖的鄰接矩陣來看
2.4.2 根據(jù)邊是否有權(quán)重
- 無權(quán)圖，權(quán)重為1**
- 加權(quán)圖
2.4.3 根據(jù)節(jié)點連接方式
- 補充概念——二部圖的折疊 （Projection/Folded）
也就是將異質(zhì)的二部圖圖，變成同質(zhì)圖。
- 二部圖（Bipartite graph）：圖可分為兩類內(nèi)部不相連的節(jié)點集。如：作者和論文構(gòu)成的圖，電影和演員構(gòu)成的圖以及用戶和商品之間構(gòu)成的圖等等。
-
圖片
- 完全圖（complete graph）。任意兩點都有邊相連
- 自環(huán)圖（Self-edges (self-loops)）。自己與自己相連。鄰居矩陣的對角線不為0.
- 多重圖 （ Multigraph ）。存在兩點之間大于一條邊。
-
圖片
現(xiàn)實中系統(tǒng)繁多，數(shù)學(xué)中的圖很多，因此，正確建模很關(guān)鍵??！
2.3 圖數(shù)學(xué)的表示
這部分在代碼篇再詳細展示。這里只做簡單介紹。雖然課程老師推薦使用官方的SNAP包，進行實操。但是因為之前主要用的還是networkx，為了降低學(xué)習(xí)成本。動手部分就采用 networkx了，這些部分代碼，可以在下面的github鏈接獲得。
鄰接矩陣（Adjacency matrix） 現(xiàn)實中大部分的網(wǎng)絡(luò)的鄰接矩陣是非常稀疏的，通常采用稀疏矩陣or鄰接列表存儲。
鄰接列表（Adjacency list）
邊列表（Edge list）
- 如 [(1,4),(2,1),(4,2),(4,3)]
2.4 圖的連通性
2.4.1 對于無向圖
連通圖（無向圖）：任意兩節(jié)點間存在直接或間接的鏈路關(guān)系。子概念：
- Bridge edge: 去掉該邊，圖變成菲連通圖。下圖中綠色邊
- Articulation node：去掉該點，，圖變成菲連通圖。下圖中藍色節(jié)點
- 圖片
2.4.2 對于有向圖
強連通有向圖：圖內(nèi)部對于任意兩個節(jié)點，存在路徑，彼此之間相互觸達。
弱連通有向圖：忽略方向時才連通的圖
-
強連通分量（Strongly connected components (SCCs)）
子圖內(nèi)部任意兩個節(jié)點，存在路徑，彼此之間相互觸達
最后放一張，現(xiàn)實中的不同系統(tǒng)中網(wǎng)絡(luò)的統(tǒng)計信息再次，說明網(wǎng)絡(luò)的稀疏性！
