Real-time streaming graph embedding through local actions

Xi Liu, Rui Chen, Ping-Chun Hsieh, Muhe Xie, Nick Duffield, Xidao Wen

研究成果: Conference contribution同行評審

23 引文 斯高帕斯(Scopus)


Recently, considerable research attention has been paid to graph embedding, a popular approach to construct representations of vertices in latent space. Due to the curse of dimensionality and sparsity in graphical datasets, this approach has become indispensable for machine learning tasks over large networks. The majority of the existing literature has considered this technique under the assumption that the network is static. However, networks in many applications, including social networks, collaboration networks, and recommender systems, nodes, and edges accrue to a growing network as streaming. A small number of very recent results have addressed the problem of embedding for dynamic networks. However, they either rely on knowledge of vertex attributes, suffer high-time complexity or need to be re-trained without closed-form expression. Thus the approach of adapting the existing methods designed for static networks or dynamic networks to the streaming environment faces non-trivial technical challenges. These challenges motivate developing new approaches to the problems of streaming graph embedding. In this paper, we propose a new framework that is able to generate latent representations for new vertices with high efficiency and low complexity under specified iteration rounds. We formulate a constrained optimization problem for the modification of the representation resulting from a stream arrival. We show this problem has no closed-form solution and instead develop an online approximation solution. Our solution follows three steps: (1) identify vertices affected by newly arrived ones, (2) generating latent features for new vertices, and (3) updating the latent features of the most affected vertices. The new representations are guaranteed to be feasible in the original constrained optimization problem. Meanwhile, the solution only brings about a small change to existing representations and only slightly changes the value of the objective function. Multi-class classification and clustering on five real-world networks demonstrate that our model can efficiently update vertex representations and simultaneously achieve comparable or even better performance compared with model retraining.

主出版物標題The Web Conference 2019 - Companion of the World Wide Web Conference, WWW 2019
發行者Association for Computing Machinery, Inc
出版狀態Published - 13 5月 2019
事件2019 World Wide Web Conference, WWW 2019 - San Francisco, United States
持續時間: 13 5月 201917 5月 2019


名字The Web Conference 2019 - Companion of the World Wide Web Conference, WWW 2019


Conference2019 World Wide Web Conference, WWW 2019
國家/地區United States
城市San Francisco


深入研究「Real-time streaming graph embedding through local actions」主題。共同形成了獨特的指紋。