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 contributionpeer-review

    6 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
    Country/TerritoryUnited 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