Accelerating Dynamic Network Embedding with Billions of Parameter
  Updates to Milliseconds
Haoran Deng Yang Yang Jiahe Li Haoyang Cai Shiliang Pu Weihao Jiang
Network embedding, a graph representation learning method illustrating
network topology by mapping nodes into lower-dimension vectors, is challenging
to accommodate the ever-changing dynamic graphs in practice. Existing research
is mainly based on node-by-node embedding modifications, which falls into the
dilemma of efficient calculation and accuracy. Observing that the embedding
dimensions are usually much smaller than the number of nodes, we break this
dilemma with a novel dynamic network embedding paradigm that rotates and scales
the axes of embedding space instead of a node-by-node update. Specifically, we
propose the Dynamic Adjacency Matrix Factorization (DAMF) algorithm, which
achieves an efficient and accurate dynamic network embedding by rotating and
scaling the coordinate system where the network embedding resides with no more
than the number of edge modifications changes of node embeddings. Moreover, a
dynamic Personalized PageRank is applied to the obtained network embeddings to
enhance node embeddings and capture higher-order neighbor information
dynamically. Experiments of node classification, link prediction, and graph
reconstruction on different-sized dynamic graphs suggest that DAMF advances
dynamic network embedding. Further, we unprecedentedly expand dynamic network
embedding experiments to billion-edge graphs, where DAMF updates billion-level
parameters in less than 10ms.