Graph Embedding：SDNE演算法的原理，實現和應用
- 2019 年 11 月 21 日
- 筆記
文章作者：沈偉臣 內容來源：作者授權發布 出品社區：DataFun 註：歡迎轉載，轉載請註明出處。
SDNE（Structural Deep Network Embedding ）是和node2vec並列的工作，均發表在2016年的KDD會議中。可以看作是基於LINE的擴展，同時也是第一個將深度學習應用於網路表示學習中的方法。 不清楚LINE的同學可以參考：
SDNE使用一個自動編碼器結構來同時優化1階和2階相似度(LINE是分別優化的)，學習得到的向量表示能夠保留局部和全局結構，並且對稀疏網路具有魯棒性。
SDNE 演算法原理
相似度定義
SDNE中的相似度定義和LINE是一樣的。簡單來說，1階相似度衡量的是相鄰的兩個頂點對之間相似性。2階相似度衡量的是，兩個頂點他們的鄰居集合的相似程度。
2階相似度優化目標
這裡我們使用圖的鄰接矩陣進行輸入，對於第
個頂點，有
，每一個
都包含了頂點i的鄰居結構資訊，所以這樣的重構過程能夠使得結構相似的頂點具有相似的embedding表示向量。
這裡存在的一個問題是由於圖的稀疏性，鄰接矩陣S中的非零元素是遠遠少於零元素的，那麼對於神經網路來說只要全部輸出0也能取得一個不錯的效果，這不是我們想要的。
文章給出的一個方法是使用帶權損失函數，對於非零元素具有更高的懲罰係數。 修正後的損失函數為
其中
為逐元素積，
，若
，則
，否則
1階相似度優化目標
對於1階相似度，損失函數定義如下
該損失函數可以讓圖中的相鄰的兩個頂點對應的embedding vector在隱藏空間接近。
還可以表示為
其中L是圖對應的拉普拉斯矩陣，
，D是圖中頂點的度矩陣，S是鄰接矩陣，
。
整體優化目標
聯合優化的損失函數為
是正則化項，
為控制1階損失的參數，
為控制正則化項的參數。
模型結構
先看左邊，是一個自動編碼器的結構，輸入輸出分別是鄰接矩陣和重構後的鄰接矩陣。通過優化重構損失可以保留頂點的全局結構特性(論文的圖畫錯了，上面應該是Global structure preserved cost)。
再看中間一排，
就是我們需要的embedding向量，模型通過1階損失函數使得鄰接的頂點對應的embedding向量接近，從而保留頂點的局部結構特性(中間應該是 Local structure preserved cost)
實現
文章提出使用深度信念網路進行預訓練來獲得較好的參數初始化，這裡我就偷個懶省略這個步驟了~
損失函數定義
l_2nd是2階相似度對應的損失函數，參數beta控制著非零元素的懲罰項係數。y_true和y_pred分別是輸入的鄰接矩陣和網路重構出的鄰接矩陣。
l_1st是1階相似度對應的損失函數，參數alpha控制著其在整體損失函數中的佔比。
def l_2nd(beta): def loss_2nd(y_true, y_pred): b_ = np.ones_like(y_true) b_[y_true != 0] = beta x = K.square((y_true - y_pred) * b_) t = K.sum(x, axis=-1, ) return K.mean(t) return loss_2nd def l_1st(alpha): def loss_1st(y_true, y_pred): L = y_true Y = y_pred batch_size = tf.to_float(K.shape(L)[0]) return alpha * 2 * tf.linalg.trace(tf.matmul(tf.matmul(Y, L, transpose_a=True), Y)) / batch_size return loss_1st
模型定義
create_model函數創建SDNE模型，l1和l2分別為模型的正則化項係數，模型的輸入A為鄰接矩陣，L為拉普拉斯矩陣。輸出A_為重構後的鄰接矩陣，Y為頂點的embedding向量。
函數中兩個for循環分別對應encoder和decoder結構。
def create_model(node_size, hidden_size=[256, 128], l1=1e-5, l2=1e-4): A = Input(shape=(node_size,)) L = Input(shape=(None,)) fc = A for i in range(len(hidden_size)): if i == len(hidden_size) - 1: fc = Dense(hidden_size[i], activation='relu',kernel_regularizer=l1_l2(l1, l2),name='1st')(fc) else: fc = Dense(hidden_size[i], activation='relu',kernel_regularizer=l1_l2(l1, l2))(fc) Y = fc for i in reversed(range(len(hidden_size) - 1)): fc = Dense(hidden_size[i], activation='relu',kernel_regularizer=l1_l2(l1, l2))(fc) A_ = Dense(node_size, 'relu', name='2nd')(fc) model = Model(inputs=[A, L], outputs=[A_, Y]) return model
應用
使用SDNE在wiki數據集上進行節點分類任務和可視化任務(感興趣的同學可以試試別的數據集，我比較懶就選了個很小的數據集)。 wiki數據集包含 2,405 個網頁和17,981條網頁之間的鏈接關係，以及每個網頁的所屬類別。
本例中的訓練，評測和可視化的完整程式碼在下面的git倉庫中：
https://github.com/shenweichen/GraphEmbedding
分類任務
micro-F1: 0.6341 macro-F1: 0.4962
可視化
這個貌似某些類別的點的向量都聚集在一起了，可能和超參的設置還有網路權重的初始化有關，我懶得調了~
參考資料：
Wang D, Cui P, Zhu W. Structural deep network embedding[C]//Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2016: 1225-1234.
https://www.kdd.org/kdd2016/papers/files/rfp0191-wangAemb.pdf
作者介紹：
沈偉臣，阿里巴巴演算法工程師，碩士畢業於浙江大學電腦學院。對機器學習，強化學習技術及其在推薦系統領域內的應用具有濃厚興趣。
識別下圖二維碼，瀏覽作者github主頁：
