論文閱讀“Adaptive Graph Auto-Encoder for General Data Clustering”

Li X, Zhang H, Zhang R. Adaptive Graph Auto-Encoder for General Data Clustering[J]. arXiv preprint arXiv:2002.08648, 2020.

摘要翻譯

基于圖的聚類在聚類領域具有重要的作用螺男。近年來棒厘，關于圖卷積神經(jīng)網(wǎng)絡的研究在圖形類型數(shù)據(jù)方面取得了令人矚目的成功。然而下隧，在一般的聚類任務中奢人，不存在數(shù)據(jù)的圖結構，因此構造圖的策略對性能至關重要淆院。因此何乎，如何將圖卷積網(wǎng)絡擴展到一般的聚類任務中是一個很有吸引力的問題。本文提出了一種用于一般數(shù)據(jù)聚類的圖自編碼器土辩，它根據(jù)圖的生成視角自適應地構造圖支救。自適應過程旨在誘導模型挖掘數(shù)據(jù)背后的高級信息，充分利用非歐幾里德結構脯燃。論文進一步設計了一種新的機制搂妻，并進行了嚴格的分析，以避免自適應結構造成的負面影響辕棚。通過將網(wǎng)絡嵌入的生成模型和基于圖的聚類相結合欲主，開發(fā)了一種基于圖的自動編碼器和解碼器，使其在加權圖的應用場景中表現(xiàn)良好逝嚎。大量的實驗證明了我們的模型的優(yōu)越性扁瓢。
GNNs extend classical neural networks into irregular data so that the deep information hidden in graphs is exploited sufficiently.[Scarselli F, Gori M, Tsoi A C, et al. The graph neural network model[J]. IEEE transactions on neural networks, 2008, 20(1): 61-80.]
GCNs have shown superiority compared with traditional network embedding models. []
Similarly, graph auto-encoder (GAE) is developed to extend GCN into unsupervised learning.[Kipf T N, Welling M. Variational graph auto-encoders[J]. arXiv preprint arXiv:1611.07308, 2016.]
切入點：為探索歐式數(shù)據(jù)域中的拓撲結構信息，論文從生成角度自適應的構造圖补君，并使用GCN更好的提升聚類性能引几。

主要貢獻點

為構建理想的圖結構信息，模型合并了網(wǎng)絡嵌入的生成模型挽铁∥拔Γ基于生成的觀點，進一步整合了表示學習叽掘，以使圖自然編碼自然地被用來學習嵌入楣铁。（基于生成的思想，更容易探索數(shù)據(jù)中各節(jié)點間的連接分布）
從生成的圖模型獲得的學習的連通性分布更扁，被用作圖自動編碼器重構的目標盖腕，這也啟發(fā)了我們?yōu)榻獯a器設計一種新穎的體系結構赫冬。
模型根據(jù)生成的嵌入內(nèi)容自適應地更新圖，從而可以利用深層信息并修改由原始特征導致的不良圖溃列。通過更改圖形的稀疏度劲厌，我們消除了自適應結構導致的崩潰。此外听隐，給出了相關的理論分析以了解該現(xiàn)象大渤。

相關工作結構
深度聚類（AE-based 和 CNN-based）
GAE相關

模型淺析

Probabilistic Perspective of Weighted Graphs

論文有個基礎假設绸罗，任意兩個節(jié)點之間的連通性被定義為條件概率 $p(v|v_i)$ ，并且在整張圖中有 $\sum_{j=1}^np(v_j|v_i)=1$ 。因此守呜，可以將這種連通性看做采樣結果欧引，這也是生成網(wǎng)絡嵌入的核心假設手趣。
當然這種采樣會由于連通性的差異導致 $p(v_i|v_j)\neq p(v_j|v_i)$ （有向加權圖）阁最。因此，加權圖的構造等效于找到基礎的連通性分布成玫。
為了找到近似的連通分布加酵，論文給出假設1：如果 $p(v_i|v_j)$ 值比較大，等價于節(jié)點 $v_i$ 和 $v_j$ 的特征表示是相似的哭当。

紅框中是代表為節(jié)點 $v_i$ 采樣的期望猪腕，即期望在該節(jié)點的所有鄰接節(jié)點中選出差異性 $d(v_i,v_j)$ 較小的節(jié)點集合。根據(jù)圖中連通性的稀疏性原則钦勘，在自主學習連通性的過程中添加了正則項（由于L0和L1都存在些缺陷陋葡，因此論文選擇使用L2正則項來保證節(jié)點連接的稀疏性）。通過對模型超參數(shù)的權衡彻采，論文為所有節(jié)點選擇相同的稀疏度腐缤，并被設置為控制參數(shù)的上界。

而 $p_i$ 作者將其定義為節(jié)點 $v_i$ 相對于每個節(jié)點的條件概率 $p_i=[p(v_1|v_i), p(v_2|v_i), ..., p(v_n|v_i)]$ 肛响，并且在初始化時將其看做最簡單的解決方案岭粤，即除自身節(jié)點外，其余節(jié)點的條件概率都等于0.

Graph Auto-Encoder for Weighted Graph

通過上述帶權節(jié)點的連通性學習特笋，我們其實得到的是有向帶權圖剃浇，在這一部分的運算中將其轉(zhuǎn)換為無向圖 $W_{ij}=(p(v_i|v_j)+p(v_j|v_i))/2$ ，并且 $W$ 鄰接矩陣被作為GAE的重構目標猎物。

Encoder
在普通GCN運算中鄰接信息的引入使用 $(A+I)$ 虎囚，通過自環(huán)的權重是自適應學習的，而不是原始的 $I$ 蔫磨，因此在Encoder中溜宽，作者將該部分替換為 $W$ ，其余算子未變质帅，因此有:
Decoder
不同于重建A的內(nèi)積，論文基于假設1來重建連通性分布 $p(v|v_i)$ 。

連通性分布計算