網路嵌入(6)GraphGAN
論文名稱：GraphGAN: Graph Representation Learning with Generative Adversarial Nets
Introduction
這篇文章將NE方法按照另一種角度分成了兩類：生成模型和判別模型。
生成模型：網路中節點和邊並不是隨機的，生成模型的目的是在找網路中一個節點鄰居的概率分布，也就是一個節點的連接偏好。給定一個 ，想找到一個
的鄰居服從的分布
。比如DeepWalk、noce2vec。
判別模型：判別模型並不考慮節點與鄰居的分布，它以網路中的邊為出發點，衡量兩個節點之間是否有邊關係。給定兩個節點 、
，判別模型給出兩個節點有邊的概率
。
Graph Generative Adversarial Nets
首先是一些符號：
表示
的直接鄰居；
表示
的鄰居服從的真實分布，也就是
的連接偏好。從採樣的角度來看，
就是概率分布
的採樣結果。
表示G所做的工作就是模擬出
的分布，模型的參數由
控制。
衡量
和
之間有邊的概率， 即
。它的輸出是一個常量。
具體的優化細節：
D量化兩個節點之間有邊的概率，文中給的公式是：
其中d分別代表兩個節點的表示向量。如果v是通過 採樣得到的，那麼D應該給出一個高分，如果v是G生成的，那麼D應該給一個低分。用梯度上升更新兩個節點表示。
G衡量節點的鄰居分布，文中的公式是：
就是一個softmax函數，輸出鄰居是每個節點的概率。
到這裡G和D的模型和優化目標都確定了，但是還有一個最大的問題，這個G和D的定義並沒有反映任何網路的特徵。
解決方案：Graph Softmax
D的定義並沒有問題，有問題的是G中的softmax函數，它的問題有兩個：
- 並沒有反映任何網路特徵。
- 每個節點都要算一遍，複雜度太高。
那麼這個重定義的softmax有怎樣的特點呢？
- Normalized：畢竟是概率，加一起要等於1，即
。
- Graph-structure-aware：網路特徵特現在什麼方面，比如兩個節點相距越遠，連接的可能性越低。
- computationally efficient：計算
的時候最好只用到一部分節點，而不用把所有節點都算一遍。
解決辦法就是對於每一個節點 ，以它為根節點BFS遍歷形成一棵生成樹，樹中兩個節點之間的邊對應的概率由以下公式給出。
從根開始自頂向下，每個節點和它子節點之間的邊都對應一個概率，如果要計算 ，只要找到一條從根
到
的路徑，將路徑經過的邊對應的概率相乘就算出來了。
那麼G應該怎麼生成鄰居節點呢？一種簡單的方法就是把每個節點對應的概率都算出來，然後根據每個節點的概率大小採樣。文中給出了另一種採樣方法：從根開始一條隨機遊走，按照之前算的概率選擇下一個節點，直到某次選擇的下一個節點是它的父節點，這個節點就是被採樣的節點。
Experiments
鏈接預測任務在效果上並沒有提升太多，比DeepWalk好，跟node2vec差不多。
Reference
GraphGAN: Graph Representation Learning with GAN - Xullll的文章 - 知乎 https://zhuanlan.zhihu.com/p/47622003
推薦閱讀：