如何把節(jié)點(diǎn)映射成D維向量：（先對(duì)節(jié)點(diǎn)進(jìn)行分析是非常必要的）

• 人工特征工程：節(jié)點(diǎn)重要度、集群系數(shù)、Graphlet

• 圖表示學(xué)習(xí)：通過隨機(jī)游走構(gòu)造自監(jiān)督學(xué)習(xí)任務(wù)，DeepWalk、Node2Vec

• 矩陣分解

• 深度學(xué)習(xí)：圖神經(jīng)網(wǎng)絡(luò)

• 圖表示學(xué)習(xí)：

• 不需要特征工程，將各個(gè)模態(tài)輸入轉(zhuǎn)為向量，自動(dòng)學(xué)習(xí)特征

• 將節(jié)點(diǎn)映射為d維向量，向量具有低維（向量維度遠(yuǎn)小于節(jié)點(diǎn)數(shù)）、連續(xù)（每個(gè)元素都是實(shí)數(shù)）、稠密（每個(gè)元素都不為0），與下游任務(wù)無關(guān)

• 嵌入d維空間：

• 向量相似度反映節(jié)點(diǎn)相似度

• 嵌入向量包含網(wǎng)絡(luò)連接信息

1 基本框架（編碼器+解碼器）

• 編碼器：輸入一個(gè)節(jié)點(diǎn)，輸出這個(gè)節(jié)點(diǎn)的D維向量，

• 解碼器：輸入這個(gè)節(jié)點(diǎn)的dd維向量，輸出節(jié)點(diǎn)相似度，向量點(diǎn)乘數(shù)值反映節(jié)點(diǎn)的相似度（需要人為定義）

• 優(yōu)化目標(biāo)：迭代優(yōu)化每個(gè)節(jié)點(diǎn)的dd維向量，使得圖中相似節(jié)點(diǎn)向量數(shù)量積大，不相似節(jié)點(diǎn)向量數(shù)量積小 ==> 對(duì)于每一個(gè)相似的節(jié)點(diǎn)對(duì)(u, v)最大化

1.1 編碼器

• 最簡單的編碼器：查表（淺編碼器），采用獨(dú)熱編碼，

• Z表示一個(gè)矩陣，每一列表示一個(gè)節(jié)點(diǎn)，行數(shù)表示向量的維度

• 優(yōu)化Z矩陣的方法：DeepWalk、Node2Vec

1.2 解碼器

• 基于節(jié)點(diǎn)相似度（key：定義相似度的計(jì)算方法）

• 目標(biāo)：對(duì)

• 進(jìn)行優(yōu)化迭代每個(gè)節(jié)點(diǎn)的D維向量，使得使得圖中相似節(jié)點(diǎn)向量數(shù)量積大，不相似節(jié)點(diǎn)向量數(shù)量積小

• 直接優(yōu)化嵌入向量，使用隨機(jī)游走方式，如果兩個(gè)節(jié)點(diǎn)出現(xiàn)在同一個(gè)隨機(jī)游走序列中，就反映了這兩個(gè)節(jié)點(diǎn)是相似的，并與下游任務(wù)無關(guān)

2 基于隨機(jī)游走的方法

2.1 隨機(jī)游走的概念

• 隨機(jī)游走：可以定義具體的策略，在圖中進(jìn)行游走

• 圖機(jī)器學(xué)習(xí)可以和NLP對(duì)應(yīng)：

• 圖：文章

• 隨機(jī)游走序列：句子

• 節(jié)點(diǎn)：單詞

• DeepWalk：Skip-Gram

• Node Embedding：Word Embedding

2.2 隨機(jī)游走的方法步驟

• P(v|z_u)P(v∣zu)：從uu節(jié)點(diǎn)觸發(fā)的隨機(jī)游走序列經(jīng)過vv節(jié)點(diǎn)的概率

• 使用softmax方法計(jì)算P(v|z_u)P(v∣zu)：

• 具體步驟：

1. 采樣得到若干隨機(jī)游走序列，計(jì)算條件概率

1. 迭代優(yōu)化每個(gè)節(jié)點(diǎn)的D維，使得序列中共現(xiàn)節(jié)點(diǎn)向量數(shù)量積大，不共現(xiàn)節(jié)點(diǎn)向量數(shù)量積小

• 優(yōu)點(diǎn)：表示能力、計(jì)算便捷、無監(jiān)督/自監(jiān)督學(xué)習(xí)問題

• 使用極大似然估計(jì)，優(yōu)化目標(biāo)函數(shù)

• 其中

• 表示從uu節(jié)點(diǎn)出發(fā)的隨機(jī)游走序列的所有鄰域節(jié)點(diǎn)

• 整個(gè)優(yōu)化的目標(biāo)函數(shù)：

• 其中

• 遍歷所有節(jié)點(diǎn)，并遍歷從uu節(jié)點(diǎn)出發(fā)的隨機(jī)游走序列的所有鄰域節(jié)點(diǎn)，計(jì)算節(jié)點(diǎn)uu和節(jié)點(diǎn)vv在該隨機(jī)游走序列中共現(xiàn)。

2.3 計(jì)算優(yōu)化

• 負(fù)采樣：

• 其中

• （非均勻分布采樣），

• 梯度下降：

• 全局梯度下降（Gradient Descent）：求所有節(jié)點(diǎn)uu總梯度

• ，并迭代更新

• 隨機(jī)梯度下降（Stochastic Gradient Descent）：每次隨機(jī)游走優(yōu)化一次

• ，并迭代更新

3 Node2Vec

• 有偏二階隨機(jī)游走

• 通過兩個(gè)超參數(shù)pp和qq控制隨機(jī)游走的方向，其中概率\displaystyle \frac{1}{p}p1表示退回上一個(gè)節(jié)點(diǎn)，概率\displaystyle \frac{1}{q}q1表示走向更遠(yuǎn)的節(jié)點(diǎn)，1表示走向上一個(gè)節(jié)點(diǎn)距離相等的節(jié)點(diǎn)

• 設(shè)置不同的超參數(shù)：

• pp大qq小：DFS深度優(yōu)先（探索遠(yuǎn)方），應(yīng)用于同質(zhì)社群（homophily community）

• pp小qq大：BFS廣度優(yōu)先（探索近鄰），應(yīng)用于節(jié)點(diǎn)功能角色（中樞、橋接、邊緣）（structural equivalence）

• Node2Vec算法：

1. 計(jì)算每條邊的隨機(jī)游走概率

2. 以uu節(jié)點(diǎn)為出發(fā)點(diǎn)，長度為ll，生成rr個(gè)隨機(jī)游走序列

3. 用隨機(jī)梯度下降優(yōu)化目標(biāo)函數(shù)

4 隨機(jī)游走的圖嵌入的討論與總結(jié)

• 基于隨機(jī)游走的圖嵌入的缺點(diǎn)：

• 隨機(jī)游走的圖嵌入方法都是對(duì)圖中已有的節(jié)點(diǎn)計(jì)算特征，無法立刻泛化到新加入的節(jié)點(diǎn)，其實(shí)是某種程度的過擬合

• 只是探索相鄰局部信息，只能采樣出地理上相近的節(jié)點(diǎn)

• 僅利用圖本身的連接信息，并沒有使用屬性信息

• DeepWalk：

• 首個(gè)將深度學(xué)習(xí)和自然語言處理的思想用于圖機(jī)器學(xué)習(xí)

• 在稀疏標(biāo)注節(jié)點(diǎn)分類場景下，嵌入性能卓越

• 均勻隨機(jī)游走，沒有偏向的游走方向

• 需要大量隨機(jī)游走序列訓(xùn)練

• 基于隨機(jī)游走，管中窺豹，距離較遠(yuǎn)的兩個(gè)節(jié)點(diǎn)無法相互影響。看不到全圖信息。

• 無監(jiān)督，僅編碼圖的連接信息，沒有利用節(jié)點(diǎn)的屬性特征。

• 沒有真正用到神經(jīng)網(wǎng)絡(luò)和深度學(xué)習(xí)

• Node2Vec：

• 解決圖嵌入問題，將圖中的每個(gè)節(jié)點(diǎn)映射為一個(gè)向量（嵌入）

• 向量（嵌入）包含了節(jié)點(diǎn)的語義信息（相鄰社群和功能角色）

• 語義相似的節(jié)點(diǎn)，向量（嵌入）的距離也近

• 向量（嵌入）用于后續(xù)的分類、聚類、Link Prediction、推薦等任務(wù)

• 在DeepWalk完全隨機(jī)游走的基礎(chǔ)上，Node2Vec增加參數(shù)p和q，實(shí)現(xiàn)有偏隨機(jī)游走。不同的p、q組合，對(duì)應(yīng)了不同的探索范圍和節(jié)點(diǎn)語義

• DFS深度優(yōu)先探索，相鄰的節(jié)點(diǎn)，向量（嵌入）距離相近

• BFS廣度優(yōu)先探索，相同功能角色的節(jié)點(diǎn)，向量（嵌入）距離相近

• DeepWalk是Node2Vec在p=1，q=1的特例

• 結(jié)

5 全圖嵌入

• 所有節(jié)點(diǎn)的D維向量求和：

• 引入虛擬節(jié)點(diǎn)，并求出虛擬節(jié)點(diǎn)嵌入，作為整個(gè)子圖的嵌入

• 匿名隨機(jī)游走