Real-time streaming graph embedding through local actions

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations

Abstract

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.

Original languageEnglish
Title of host publicationThe Web Conference 2019 - Companion of the World Wide Web Conference, WWW 2019
PublisherAssociation for Computing Machinery, Inc
Pages285-293
Number of pages9
ISBN (Electronic)9781450366755
DOIs
StatePublished - 13 May 2019
Event2019 World Wide Web Conference, WWW 2019 - San Francisco, United States
Duration: 13 May 201917 May 2019

Publication series

NameThe Web Conference 2019 - Companion of the World Wide Web Conference, WWW 2019

Conference

Conference2019 World Wide Web Conference, WWW 2019
CountryUnited States
CitySan Francisco
Period13/05/1917/05/19

Fingerprint Dive into the research topics of 'Real-time streaming graph embedding through local actions'. Together they form a unique fingerprint.

  • Cite this

    Liu, X., Chen, R., Hsieh, P-C., Xie, M., Duffield, N., & Wen, X. (2019). Real-time streaming graph embedding through local actions. In The Web Conference 2019 - Companion of the World Wide Web Conference, WWW 2019 (pp. 285-293). (The Web Conference 2019 - Companion of the World Wide Web Conference, WWW 2019). Association for Computing Machinery, Inc. https://doi.org/10.1145/3308560.3316585