REFINE: Random RangE FInder for Network Embedding

Abstract

Network embedding approaches have recently attracted considerable interest as they learn low-dimensional vector representations of nodes. Embeddings based on the matrix factorization are effective but they are usually computationally expensive due to the eigen-decomposition step. In this paper, we propose a Random RangE FInder based Network Embedding (REFINE) algorithm, which can perform embedding on one million of nodes (YouTube) within 30 seconds in a single thread. REFINE is 10x faster than ProNE, which is 10-400x faster than other methods such as LINE, DeepWalk, Node2Vec, GraRep, and Hope. Firstly, we formulate our network embedding approach as a skip-gram model, but with an orthogonal constraint, and we reformulate it into the matrix factorization problem. Instead of using randomized tSVD (truncated SVD) as other methods, we employ the Randomized Blocked QR decomposition to obtain the node representation fast. Moreover, we design a simple but efficient spectral filter for network enhancement to obtain higher-order information for node representation. Experimental results prove that REFINE is very efficient on datasets of different sizes (from thousand to million of nodes/edges) for node classification, while enjoying a good performance.

References in corpus (5)

• 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
• NetSMF: Large-Scale Network Embedding as Sparse Matrix Factorization

Cited by in corpus (5)

• COSTA: Covariance-Preserving Feature Augmentation for Graph Contrastive Learning
• Tensor Representations for Action Recognition
• Graph-adaptive Rectified Linear Unit for Graph Neural Networks
• Understanding and Mitigating Hyperbolic Dimensional Collapse in Graph Contrastive Learning
• Graph Self-Supervised Learning with Learnable Structural and Positional Encodings