Efficient Tree-SVD for Subset Node Embedding over Large Dynamic Graphs

Subset embedding is the task to learn low-dimensional representations for a subset of nodes according to the graph topology. It has applications when we focus on a subset of users, e.g., young adults, and aim to make better recommendations for these target users. In real-world scenarios, graphs are dynamically changing. Thus, it is more desirable to dynamically maintain the subset embeddings to reflect graph updates. The state-of-the-art methods, e.g., DynPPE, still adopt a hashing-based method, while hashing-based solutions are shown to be less effective than matrix factorization (MF)-based methods in existing studies. At the same time, MF-based methods in the literature are too expensive to update the embedding when the graph changes, making them inapplicable on dynamic graphs.

Motivated by this, we present Tree-SVD, an efficient and effective MF-based method for dynamic subset embedding. If we simply maintain the whole proximity matrix, then we need to re-do the MF, e.g., truncated Singular Value Decomposition (SVD), on the whole matrix after graph updates, which is prohibitive. To tackle this issue, our main idea is to do hierarchical SVD (HSVD) on the proximity matrix of the given subset, which vertically divides the proximity matrix into multiple sub-matrices, and then repeatedly do SVD on sub-matrices and merge the intermediate results to obtain the final embedding. We first present Tree-SVD, which combines a sparse randomized SVD with an HSVD. Our theoretical analysis shows that our Tree-SVD gains the efficiency of sparse randomized SVD and the flexibility of the HSVD with theoretical guarantees. To further reduce update costs, we present a lazy-update strategy. In this strategy, we only update sub-matrices that changes remarkably in terms of the Frobenius norm. We present theoretical analysis to show the guarantees with our lazy-update strategy. Extensive experiments show the efficiency and effectiveness of Tree-SVD on node classification and link prediction tasks.