Abstract
Link prediction, personalized graph search, fraud detection, and many such graph mining problems revolve around the computation of the most "similar" $k$ nodes to a given query node. One widely used class of similarity measures is based on random walks on graphs, e.g., personalized pagerank, hitting and commute times, and simrank. There are two fundamental problems associated with these measures. First, existing online algorithms typically examine the local neighborhood of the query node which can become significantly slower whenever high-degree nodes are encountered (a common phenomenon in real-world graphs). We prove that turning high degree nodes into sinks results in only a small approximation error, while greatly improving running times. The second problem is that of computing similarities at query time when the graph is too large to be memory-resident. The obvious solution is to split the graph into clusters of nodes and store each cluster on a disk page; ideally random walks will rarely cross cluster boundaries and cause page-faults. Our contributions here are twofold: (a) we present an efficient deterministic algorithm to find the $k$ closest neighbors (in terms of personalized pagerank) of any query node in such a clustered graph, and (b) we develop a clustering algorithm (RWDISK) that uses only sequential sweeps over data files. Empirical results on several large publicly available graphs like DBLP, Citeseer and Live-Journal (~ 90 M edges) demonstrate that turning high degree nodes into sinks not only improves running time of RWDISK by a factor of 3 but also boosts link prediction accuracy by a factor of 4 on average. We also show that RWDISK returns more desirable (high conductance and small size) clusters than the popular clustering algorithm METIS, while requiring much less memory. Finally our deterministic algorithm for computing nearest neighbors incurs far fewer page-faults (factor of 5) than actually simulating random walks.
Introduction
Finding the most similar nodes to a query node is a foundational task in graph mining, supporting applications from recommendation engines to fraud detection. Similarity measures based on random walks, such as Personalized PageRank (PPR), are particularly effective but face two significant scaling challenges. First, the presence of high-degree "hub" nodes in real-world graphs can cause local search algorithms to stall as they process massive neighborhoods. Second, as graphs grow to millions or billions of edges, they exceed the capacity of main memory (RAM), forcing reliance on disk-resident storage where random access is prohibitively slow due to page faults.
This paper addresses these challenges by introducing a framework that optimizes both the computational complexity of random walks and the I/O efficiency of searching disk-resident graphs.
Methodology
Handling High-Degree "Hub" Nodes
A primary bottleneck in graph search is the "hub" problem. High-degree nodes act as computational sinks in terms of processing time but often add noise to similarity measures by connecting unrelated communities. The authors propose turning these high-degree nodes into actual sinks—nodes where a random walk terminates.
They provide a theoretical proof that this transformation results in only a small approximation error, which is inversely proportional to the degree of the sink node. By removing the need to propagate walks through these hubs, the algorithm avoids the "neighborhood explosion" that typically slows down search.
RWDISK: External-Memory Clustering
To handle graphs that do not fit in RAM, the authors developed RWDISK, a clustering algorithm designed for external memory. Unlike traditional algorithms like METIS, which require the entire graph structure to be memory-resident, RWDISK operates via sequential sweeps over data files.
Key features of RWDISK include:
- Epsilon-rounding: Setting very small probabilities to zero to maintain manageable intermediate file sizes.
- Sequential I/O: By prioritizing sequential sweeps over random lookups, RWDISK avoids the latency of disk seek times.
- Locality Optimization: The algorithm produces clusters designed to ensure that random walks stay within the same disk page for as long as possible, thereby minimizing page faults.
Deterministic Top-k Search
Rather than relying on Monte Carlo simulations, which can be noisy and require many disk accesses, the paper proposes a deterministic algorithm for finding the $k$ nearest neighbors. This algorithm maintains upper and lower bounds on similarity scores, allowing it to prune the search space and identify the top-$k$ results while fetching significantly fewer clusters from the disk.
Experimental Evaluation
The framework was evaluated on three large-scale datasets: Citeseer (~100K nodes, 700K edges), DBLP (~1.4M nodes, 12M edges), and LiveJournal (~4.8M nodes, 86M edges).
Key Findings
- Efficiency: Turning high-degree nodes into sinks sped up the RWDISK algorithm by a factor of 3.
- Accuracy: Link prediction accuracy improved by an average factor of 4 across the tested datasets. This suggests that hubs often act as "shortcuts" that obscure local community structures.
- Reduced I/O: The deterministic search algorithm incurred 5x fewer page faults than traditional random walk simulations.
- Memory Scalability: RWDISK successfully processed the 86-million-edge LiveJournal graph on a standard PC using only 2–4 GB of RAM. In contrast, the METIS algorithm required 80 GB of RAM to handle the same task, making it impractical for most commodity hardware.
Conclusion
This work demonstrates that massive graph search can be made both faster and more accurate by strategically simplifying the graph structure and optimizing for sequential disk access. By treating high-degree hubs as sinks and employing the RWDISK clustering method, researchers can perform complex similarity queries on commodity hardware that would otherwise require high-end servers with massive RAM. Future work includes further optimizing implementation for specific hardware page sizes and extending the analysis to directed graph structures.
Summary updated