PANE: scalable and effective attributed network embedding

Abstract

Given a graph G where each node is associated with a set of attributes, attributed network embedding (ANE) maps each node v in G to a compact vector Xv, which can be used in downstream machine learning tasks. Ideally, Xv should capture node v's affinity to each attribute, which considers not only v's own attribute associations, but also those of its connected nodes along edges in G. It is challenging to obtain high-utility embeddings that enable accurate predictions; scaling effective ANE computation to massive graphs pushes the difficulty of the problem to a whole new level. Existing solutions largely fail on such graphs, leading to prohibitive costs, low-quality embeddings, or both. This paper proposes PANE, an effective and scalable approach to ANE computation for massive graphs that achieves state-of-the-art result quality on multiple benchmark datasets. PANE obtains high scalability and effectiveness through 3 main algorithmic designs. First, it formulates the learning objective based on a novel random walk model for attributed networks. Second, PANE includes a highly efficient solver for the above optimization problem, whose key module is a carefully designed initialization of the embeddings, which drastically reduces the number of iterations required to converge. Finally, PANE utilizes multi-core CPUs through non-trivial parallelization of the above solver, which achieves scalability while retaining the high quality of the resulting embeddings. The performance of PANE depends upon the number of attributes in the input network. To handle large networks with numerous attributes, we further extend PANE to PANE++. Extensive experiments, comparing 10 existing approaches on 8 real datasets, demonstrate that PANE and PANE++ consistently outperform all existing methods in terms of result quality, while being orders of magnitude faster.

arXiv commentPaper published in VLDBJ 2023. Extended version of PVLDB Vol. 14 (VLDB 2021) paper titled "Scaling Attributed Network Embedding to Massive Graphs"

References in corpus (16)

• Efficient Estimation of Word Representations in Vector Space
• DeepWalk: Online Learning of Social Representations
• LINE: Large-scale Information Network Embedding
• PTE: Predictive Text Embedding through Large-scale Heterogeneous Text Networks
• Network Embedding as Matrix Factorization: Unifying DeepWalk, LINE, PTE, and node2vec
• Community Detection in Networks with Node Attributes
• Representation Learning for Attributed Multiplex Heterogeneous Network
• Attributed Social Network Embedding
• Scaling Graph Neural Networks with Approximate PageRank
• DynGEM: Deep Embedding Method for Dynamic Graphs
• VERSE: Versatile Graph Embeddings from Similarity Measures
• PyTorch-BigGraph: A Large-scale Graph Embedding System
• Easing Embedding Learning by Comprehensive Transcription of Heterogeneous Information Networks
• GraphVite: A High-Performance CPU-GPU Hybrid System for Node Embedding
• FREDE: Anytime Graph Embeddings
• Effective and Scalable Clustering on Massive Attributed Graphs

Cited by in corpus (1)

• Efficient Integration of Multi-View Attributed Graphs for Clustering and Embedding