[論文閱讀筆記] Are Meta-Paths Necessary, Revisiting Heterogeneous Graph Embeddings
[論文閱讀筆記] Are Meta-Paths Necessary? Revisiting Heterogeneous Graph Embeddings
本文結構
- 解決問題
- 主要貢獻
- 算法原理
- 參考文獻
(1) 解決問題
傳統的異構網絡中的隨機遊走常常偏向於採樣節點數比較多的節點類型。為了克服該問題，metapath2vec提出了基於元路徑的隨機遊走，然而使用元路徑策略要麼要求先驗知識，要麼需要通過額外的操作來結合所有短的元路徑到一個預定義的序列長度（如多元路徑的情況，如何取捨，哪個更重要？）。本文基於該以上傳統隨機遊走存在的偏向性問題出發，提出了不使用元路徑策略的另外一種解決方法。
(2) 主要貢獻
Contribution： 本篇論文提出了一種基於隨機遊走的異構網絡嵌入算法JUST（不使用元路徑），設計了JUmp和STay兩個策略來以一種更有效的方式克服上述提出的傳統異構網絡隨機遊走偏差的問題。
(3) 算法原理
JUST算法框架主要包含兩個部分：首先在圖上做基於JUMP和STAY策略的隨機遊走，其次將得到的節點序列輸入Skip-Gram模型學習節點表示向量嵌入(不再贅述)。
基於JUMP和STAY策略的隨機遊走
相比於同構網絡，異構網絡中的存在多種節點類型，該論文在傳統異構圖網絡隨機遊走的基礎之上，設計了兩種策略來選擇隨機遊走中下一跳節點的類型，即Jump和Stay策略。
1. Jump（跳轉策略）： 即隨機遊走下一跳跳轉到其他節點類型上去，假設下一跳節點類型為q，則所有與當前節點有邊的且屬於節點類型q的鄰居節點都是下一跳節點的候選集。
2. Stay（停留策略）： 即隨機遊走下一跳停留在當前節點的節點類型上，則所有與當前節點有連邊且與當前節點同類型的鄰居節點為下一跳節點的候選集。
基於以上兩種策略，我們需要確定以下細節來控制隨機遊走：何時jump何時stay？jump的時候，要jump到哪個節點類型合適？
1. 何時jump何時stay？： stay和jump的概率設計如下，
一共包括三種情況：
（1）如果沒有與當前節點同類型的鄰居節點，那stay不了，就jump。
（2）如果沒有與當前節點不同類型的鄰居節點，那jump不了，就stay。
（3）如果既有與當前節點同類型的鄰居又有不同類型的鄰居，那以α的L次方確定stay和Junp的概率。α為初始的stay概率（超參數），L為到目前為止連續訪問同一類型節點的次數（為了防止隨機遊走連續使用停留策略採樣同一類型的節點，因此設計以指數概率衰減）。
2. jump的時候，要jump到哪個節點類型合適？： 以如下方式構造待選節點類型集合：
一共包含兩種情況：
（1）節點類型q在最近沒被選擇過（構造一個m大小的隊列來存儲最近被選擇跳轉過的節點類型）並且當前節點的q類型節點鄰居非空，滿足該要求節點類型的為待選節點類型。以下為一個m=2的例子 (Q_hist存儲最近被選擇跳轉的m=2個節點類型，下一跳節點類型跳轉就選不到P和A兩個類型了)：
（2）如果由上述要求構造出來的待選節點類型集合是空的（即沒有滿足上述條件的節點類型），那就放鬆條件重新構造該集合。即不和當前節點的節點類型相同的其他節點類型都作為待選節點類型。
構造完待選節點類型之後，下一跳待轉移的節點類型從該集合中隨機採樣即可，選完節點類型之後選擇具體節點也是隨機的。
通過以上方式生成異構網絡上的隨機遊走序列之後，採用Skip-Gram模型訓練節點向量即可。
(4) 參考文獻
Hussein R, Yang D, Cudré-Mauroux P. Are Meta-Paths Necessary? Revisiting Heterogeneous Graph Embeddings[A]. Proceedings of the 27th ACM International Conference on Information and Knowledge Management[C]. 2018: 437–446.
