Homogeneous Network Embedding for Massive Graphs via Reweighted Personalized PageRank

Renchi Yang, Jieming Shi, Xiaokui Xiao, Yin Yang, Sourav S. Bhowmick

Abstract

Homogeneous Network Embedding (HNE) is a fundamental task in graph machine learning, yet existing methods often struggle to balance scalability with embedding quality. This paper introduces Node-Reweighted PageRank (NRP), a novel approach that leverages Personalized PageRank (PPR) to generate high-quality embeddings for massive graphs. By identifying and correcting an inherent "local bias" in PPR, NRP achieves state-of-the-art performance on graphs with billions of edges using only a single CPU core.

Introduction

In graph-structured data, such as social networks or web links, HNE maps nodes into low-dimensional vector spaces while preserving topological properties. These embeddings are critical for downstream tasks like link prediction and node classification. However, current techniques face a trade-off: deep learning models and random-walk simulations (e.g., DeepWalk) offer high accuracy but are computationally prohibitive for massive graphs, while faster heuristic methods often sacrifice embedding quality.

Methodology

The researchers propose a "Goldilocks" solution using Personalized PageRank (PPR). PPR summarizes an infinite number of random walks into a single proximity value, capturing the importance of a target node from a source node's perspective.

Overcoming Local Bias

A significant challenge identified is that PPR is a local measure. In nodes with high degrees (many connections), PPR values are naturally diluted, making them incomparable across the global graph. To address this, NRP introduces two innovations:

  1. Iterative Factorization: Instead of computing a full $N \times N$ proximity matrix, NRP uses an iterative approach to approximate the PPR matrix, starting from a low-rank adjacency matrix.
  2. Node-Reweighted PageRank (NRP): The method introduces learnable forward and backward weights for each node. These weights are optimized to ensure that the total connection strength in the embedding space aligns with the actual physical degrees of the nodes, transforming local PPR values into a unified global coordinate system.

Key Insights: The PPR Paradox

The authors demonstrate that vanilla PPR can be counter-intuitive due to its local nature. Consider the graph in Figure 1.

Example graph illustrating the local bias of Personalized PageRank.

In this structure, the probability "leaks" out of high-degree nodes more rapidly. As shown in the corresponding PPR table (Figure 3), the proximity values are heavily influenced by node degree rather than just topological distance. For instance, the proximity from a low-degree node to its neighbor is often higher than the inverse, creating a global inconsistency.

PPR values for the example graph, demonstrating how high-degree nodes dilute proximity scores.

By reweighting these embeddings based on node degrees, NRP bridges the gap between local proximity and global network structure. Furthermore, the authors reduced the optimization complexity from $O(N^2)$ to $O(m)$, where $m$ is the number of edges, ensuring extreme efficiency.

Experimental Results

NRP was evaluated against 16 competing methods on datasets ranging from small (Wiki, 4.7K nodes) to massive (Twitter, 41.6M nodes and 1.2B edges).

  • Efficiency: On the billion-edge Twitter graph, NRP completed its task in under 4 hours on a single CPU core. Other scalable methods either exceeded memory limits or were significantly slower.
  • Accuracy: NRP consistently outperformed competitors in link prediction and graph reconstruction. In node classification, it improved upon state-of-the-art results by over 3% on several datasets.
  • Versatility: Unlike many factorization methods limited to undirected graphs, NRP natively supports directed graphs by generating distinct forward and backward embedding vectors.

Conclusion

NRP provides a mathematically rigorous and highly scalable framework for network embedding. While currently optimized for homogeneous graphs, future work aims to extend this reweighting logic to attributed graphs, incorporating node features alongside topology. Its ability to handle massive datasets on standard hardware makes it a potent tool for real-world industrial applications.

Summary updated

BibTeX
@article{yang2020homogeneous,
  author = {Renchi Yang and Jieming Shi and Xiaokui Xiao and Yin Yang and Sourav S. Bhowmick},
  title = {{Homogeneous Network Embedding for Massive Graphs via Reweighted Personalized PageRank}},
  journal = {Proc. VLDB Endow.},
  year = {2020},
  url = {https://openreview.net/forum?id=n9Sz48rOE49},
}

Loading related content...

Figure