基於記憶更新機制的串流網路嵌入學習

Abstract

網路嵌入 (Network embedding) 是一個已經廣泛應用的表示學習方法，其目的是將稀疏的圖 (Graph) 資訊降維到一個低維的隱空間 (latent space)，然而傳統的方法多是專注於靜態網路 (static network) 的嵌入學習，然而在實際的應用中，網路的結構是持續變動的。由於當有新的資訊進入網路時，重新運行靜態的網路嵌入算法的時間複雜度是非常高的，因此，本論文提出一個針對串流網路嵌入 (streaming network embedding) 的算法以解決下列問題：1) 在多型態更新的條件下，有效率的選擇應該更新的點 2) 決定被選更新的點的更新幅度，以及基於拓樸 (topology)，來調整相鄰的點。本論文填補了此領域之不足，我們提出名為 Graph Memory Refreshing (GMR) 的算法,來保留圖上的結構資訊並且維持住嵌入向量 (embedding vector) 的一致性。除了理論分析上，我們證明 GMR 擁有更好的一致性和時間複雜度，實驗結果也顯示 GMR 不論在準確率和執行時間上都明顯優於先前的嵌入算法。

Static network embedding has been widely studied to convert the sparse structure information to a dense latent space for various applications. However, real networks are continuously evolving, and deriving the whole embedding for every snapshot is computationally intensive. In this paper, therefore, we explore streaming network embedding to 1) efficiently identify the nodes required to update the embeddings under multi-type network changes and 2) carefully revise the embeddings to maintain transduction over different parts of the network. Specifically, we propose a new representation learning framework, named Graph Memory Refreshing (GMR), to preserve both structural information and embedding consistency for streaming network embedding. We prove that GMR is more consistent than other state-of-the-art methods. Experimental results manifest that GMR outperforms the baselines in both the accuracy and the running time.