打卡筆記-Stanford CS224W-Ch2
1.3
圖的基本表示
Objects：nodes（節(jié)點(diǎn)）、vertices（頂點(diǎn)）表示為NN
Interactions（關(guān)系）：links、edges表示為EE
System：network、graph表示為G(N,E)G(N,E)
設(shè)計(jì)本體圖
如何設(shè)計(jì)本體圖，取決于將來(lái)想解決什么樣的問(wèn)題
有些時(shí)候，本體圖是唯一的、無(wú)歧義的
圖的類(lèi)型
無(wú)向圖：連接是無(wú)方向的
有向圖：連接是有方向的
異質(zhì)圖：節(jié)點(diǎn)和連接都存在不同的類(lèi)型
二分圖（Bipartite Graph）
節(jié)點(diǎn)只有兩類(lèi)
展開(kāi)二分圖：將連接了另一類(lèi)的節(jié)點(diǎn)進(jìn)行分別連接
節(jié)點(diǎn)連接數(shù)
無(wú)向圖：平均度為
有向圖：平均度為
鄰接矩陣Adjacency Matrix
無(wú)向圖：
鄰接矩陣是對(duì)稱(chēng)陣
，主對(duì)角線(xiàn)為0，A_{ii} = 0Aii=0
連接總數(shù)：
沿行或列求和均可：
有向圖
鄰接矩陣是非對(duì)稱(chēng)矩陣，
連接總數(shù)：
2.6 連接列表、鄰接列表
連接列表：只記錄存在連接的節(jié)點(diǎn)對(duì)
鄰接列表：只記錄相關(guān)連接的節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)占用一行
2.1總結(jié)：
2.1
圖數(shù)據(jù)挖掘任務(wù)分類(lèi)：
節(jié)點(diǎn)層面：信用卡欺詐用戶(hù)的挖掘
連接層面：Facebook預(yù)測(cè)可能認(rèn)識(shí)的人，預(yù)測(cè)某兩個(gè)節(jié)點(diǎn)之間是否有連接以及連接的種類(lèi)；
全圖層面：與非一個(gè)蛋白質(zhì)分子的功能
傳統(tǒng)機(jī)器學(xué)習(xí)（人工特征+機(jī)器學(xué)習(xí)）
節(jié)點(diǎn)屬性特征；
連接特征，節(jié)點(diǎn)和其他節(jié)點(diǎn)之間連接的特征；結(jié)構(gòu)信息
本節(jié)主要討論無(wú)向圖；
特征非常重要，
Eigenvector centrality：
，這是一個(gè)遞歸的求解；等價(jià)于
，A是鄰接矩陣，c 是A的eigenvectors；
Betweenness centrality：
Closeness centrality：
u和v之間最短路徑長(zhǎng)度累加；
Node Feature: Clustering Coefficient：
Graphlet Degree Vector (GDV)：
A count vector of graphlets rooted at a given node;（因?yàn)槭莡節(jié)點(diǎn)鄰域的信息，不包括u節(jié)點(diǎn)）
2.2總結(jié)
2.2 連接層面的特征工程
the task is to predict new links based on the existing links；
at test time, node pairs (with no existing links) are ranked, and top K pairs are predicted.
the key is to design features for a pair of nodes.
方法：
For each pair of nodes (x, y) compute score c(x ,y) (例如 x 和 y 的共有鄰居)；
Link-Level Features: Overview
Distance-based feature
Shortest-path distance between two nodes; 但是這樣忽略了例如多條路徑的信息
Local neighborhood overlap
Common neighbors （共同好友個(gè)數(shù)）
jaccard's coefficient:
（交互比）;
Adamic-Adar index:
（共同好友是不是社牛）
缺點(diǎn)：如果兩個(gè)節(jié)點(diǎn)沒(méi)有共同節(jié)點(diǎn)
Global neighborhood overlap
Katz index: count the number of walks of all lengths between a given pair of nodes. 節(jié)點(diǎn)u和節(jié)點(diǎn)v之間長(zhǎng)度為K的路徑個(gè)數(shù)
兩節(jié)點(diǎn)之間 walks 計(jì)算方法：計(jì)算 adjacency matrix (鄰接矩陣) 的冪；
2.3 總結(jié)
2.3 全圖層面的特征工程
把整張圖變成d維向量，能反映全圖的結(jié)構(gòu)特點(diǎn)；
Goal: design graph feature vector
Key idea:
Bag-of-Words (BoW) for a graph
Bag of node degrees; Bag-of-*
Count the number of different graphlets in a graph
這里不是針對(duì) rooted 的圖，而是針對(duì)全圖視角的，區(qū)別于節(jié)點(diǎn)工程中的針對(duì)鄰域的graphlet
Graphlet Kernel:
，如果
和
size不同，那么用歸一化的方式進(jìn)行處理
子圖匹配非常消耗算力，枚舉；
可用于各種 kernel；
Weisfeiler-Lehman Kernel：
Goal: Design an efficient graph feature descriptor
，color reinforcement?
