傳統的圖嵌入(graph embedding)方法一般隻針對同構的圖，但是實際的圖往往都是異構的。隻包含異構節點的圖的嵌入學習已經被廣泛研究，例如 metapath2vec[1] 提出了異構的 random walk 和 skip gram。而包含異構邊的圖的嵌入學習近來開始被大家所關注，比如 MNE[2] 通過引入對于每種 edge type 的 embedding 來處理異構邊的情形。在阿裡電商場景下，由使用者和商品構成的圖就是異構的，并且不僅包含異構的節點（使用者和商品），而且包含異構的邊（使用者和商品的多種互動行為，比如點選、購買等）。不僅如此，圖中的節點還包含着豐富的屬性。本文處理的就是這種包含異構節點和異構邊的圖的嵌入學習。
根據圖結構(同構/異構)以及是否包含節點特征，我們将圖分為如下六類：_HO_mogeneous _N_etwork(HON), _A_ttributed _HO_mogeneous _N_etwork(AHON), _HE_terogeneous _N_etwork(HEN), _A_ttributed _HE_terogeneous _N_etwork(AHEN), _M_ultiplex _HE_terogeneous _N_etwork(MHEN), _A_ttributed _M_ultiplex _HE_terogeneous _N_etwork(AMHEN)。
同時我們也在下表中列出了處理各種類型的圖的方法(其中GATNE-T/I是我們提出的方法)：
模型
由于有多種類型的邊(比如點選、購買)，這裡我們考慮給每個節點在每種邊類型下都學一個表示。比如我們給使用者和商品在點選場景下學一種表示，在購買場景下學一種表示。但是這兩種表示之間并不是完全獨立的，是通過某種機制互相影響的。我們主要考慮的就是如何來模組化不同類型的表示之間互相影響的方式：
模型的大緻結構如上圖所示。對于GATNE-T(T for transductive)來說，每個節點在每種edge type 下的 embedding 由兩個部分組成，分别是 base embedding 和 edge embedding。base embedding 是每個節點在每種 edge type下共享的，而 edge embedding 是通過相鄰節點的 edge embedding 計算得到的。具體來說，類似于 GraphSAGE[3]，這裡的 edge embedding 的計算方式如下：
其中 i, j 表示節點編号，r 表示某種 edge type，k 表示第 k 層的 edge embedding(1<=k<=K)，aggregator function 可以是 mean aggregator 或者 max-pooling aggregator。我們将第 K 層的 edge embedding 拼起來記為矩陣U：
其中，m 表示 edge type 的數量。由于我們不知道每個節點在每種 edge type 下的表示之間的關系，是以我們通過 self-attention[4] 的機制來模組化這種互相關系，并得到每種 edge type 下的表示對于各個 edge type 的權重：
其中是模型需要訓練得到的參數，是計算得到的權重向量。最後我們就能得到每個節點i在某種 edge type r 下的向量表示：
由于實際問題中會遇到冷啟動等問題，需要給沒有在訓練集中出現過的節點也求得 embedding。而 transductive model 不具備這種能力。是以我們引入了節點的特征提出了相應的 inductive model，記為 GATNE-I。具體來說，原先在 GATNE-T 中和都是随機初始化的。但是在 GATNE-I，這兩個 embedding 都是基于節點的特征，也就是通過節點的特征經過某種變換(比如線性變換或者神經網絡等)得到的。那麼節點i在某種 edge type r 下的向量表示就可以表達成：
其中
表示節點 i 的特征。
接下來介紹模型的訓練方式。GATNE-T/I 模型的訓練方式基于 meta-path-based random walk 和 heterogeneous skip gram。具體來說，我們預先設定 meta-path schem，
，(比如 User-Item-User)，那麼 random walk 的轉移機率即為：.
其中表示類型為 r 的邊集。給定一個節點與其在某個 random walk 上的 context C，我們的目标是最小化如下的負對數似然函數：
其中右側的每一項的機率通過 heterogeneous softmax function 來計算：
其中 c 表示節點的 context embedding。最後我們通過 heterogeneous negative sampling 來近似負對數似然：
整體的算法流程如下：
實驗
我們在3個公開資料集 Amazon、YouTube、Twitter 和阿裡資料集（user-item通路、購買、點選、加購關系）進行了實驗，驗證了我們所提出的模型的有效性，同時也說明了異構邊的資訊對如何學到更好的 graph embedding 能帶來較大的幫助。用到的資料集的規模如下（3個公開資料集從原始資料集中進行了采樣）：
如下表所示，在3個公開資料集和阿裡小資料集上，我們提出的 GATNE-T/I 取得了最好的效果。Amazon 資料集上由于商品的特征比較弱，是以 GATNE-I 的效果會稍差于GATNE-T；而在阿裡資料集上，因為節點的特征非常豐富，是以 GATNE-I 的效果會好于 GATNE-T。YouTube 和 Twitter 資料集不包含節點特征，是以我們把 DeepWalk 跑出來的200維向量作為初始的節點特征。由于 DeepWalk 生成的特征也隻利用了圖的結構，沒有引入額外的資訊，是以兩種方法 GATNE-T/I 的結果差别不大。
我們實作了3個 baseline(DeepWalk, MVE, MNE)和 GATNE-T/I 的分布式版本，運作在PAI Tensorflow 上，并在阿裡大資料集上進行了測試。如下表所示，相比于 baseline 來說，GATNE-I 取得了非常顯著的提高。
我們對模型的 convergence 和 scalability 進行了測試。在阿裡大資料集上，相比GATNE-T 來說，GATNE-I 能夠更快地達到比較好的效果。并且，随着模型所使用的worker 數量的增加，GATNE-T/I 模型的訓練時間都能顯著降低。
參考文獻
[1] Yuxiao Dong, Nitesh V Chawla, and Ananthram Swami. 2017. metapath2vec: Scalable representation learning for heterogeneous networks. In KDD’17. ACM, 135–144.
[2] Hongming Zhang, Liwei Qiu, Lingling Yi, and Yangqiu Song. 2018. Scalable Multiplex Network Embedding. In IJCAI’18. 3082–3088.
[3] Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017. Inductive representation learning on large graphs. In NIPS’17. 1024–1034.
[4] Zhouhan Lin, Minwei Feng, Cicero Nogueira dos Santos, Mo Yu, Bing Xiang, Bowen Zhou, and Yoshua Bengio. 2017. A structured self-attentive sentence embedding. ICLR’17.