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

Streaming Network Embedding with Memory Refreshing

陳璽文(Hsi-Wen Chen)

指導教授 ： 王勝德

共同指導教授 ： 楊得年(De-Nian Yang)

國立臺灣大學/電機資訊學院/電機工程學研究所/碩士(2019年)

https://doi.org/10.6342/NTU201901324

摘要

網路嵌入 (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.

並列關鍵字

Network Embedding ； Streaming Network ； Online Learning

參考文獻

[1] C. Aggarwal and K. Subbian. Evolutionary network analysis: A survey. ACM Computing Surveys (CSUR), 47(1):10, 2014.

[2] A. Ahmed, N. Shervashidze, S. Narayanamurthy, V. Josifovski, and A. J. Smola. Distributed large-scale natural graph factorization. In Proceedings of the 22nd international conference on World Wide Web, pages 37–48. ACM, 2013.

[3] L. Backstrom and J. Leskovec. Supervised random walks: predicting and recommending links in social networks. In Proceedings of the fourth ACM WSDM, pages 635–644. ACM, 2011.

[4] M. Belkin and P. Niyogi. Laplacian eigenmaps and spectral techniques for embedding and clustering. In Advances in neural information processing systems, pages 585–591, 2002.

[5] J. Benesty. Adaptive eigenvalue decomposition algorithm for passive acoustic source localization. the Journal of the Acoustical Society of America, 107(1):384–391, 2000.