Computing (1+epsilon)-Approximate Degeneracy in Sublinear Time

Valerie King, Alex Thomo, Quinton YongIJCAI 2023 · DOI

TL;DR

This paper introduces a novel algorithm for computing the degeneracy of large graphs with a guaranteed approximation factor of (1+ε) in sublinear time (specifically O(n log n)). This is a significant improvement over previous methods, offering a faster and more scalable solution for a fundamental graph property with broad applications.

What Problem Does This Paper Address?

The degeneracy of a graph is a fundamental property that measures its "sparseness" and is closely related to the k-core decomposition problem. Finding the exact degeneracy is computationally expensive, especially for massive real-world graphs. While existing algorithms can compute degeneracy, they often require processing every edge or are limited in their scalability. This paper tackles the challenge of efficiently approximating graph degeneracy for extremely large graphs, aiming for a solution that is faster than exact methods and more accurate than previous approximation algorithms, all while operating in sublinear time with respect to the number of edges.

Methods

The core of the paper's contribution is a new algorithm, dubbed NESD (Neighbor Sampling for Degeneracy). The key insight is that the degeneracy of a graph is often determined by high-degree nodes that are densely connected to other high-degree nodes. NESD leverages this by focusing on a subgraph induced by these high-degree nodes.

The algorithm works iteratively:

  1. Thresholding: It starts with a high threshold l for node degrees and partitions nodes into two sets: H (nodes with degree ≥ l) and L (nodes with degree < l).
  2. Sampling: For each node v in H, it samples a fraction of its neighbors. The number of samples is proportional to p * deg(v), where p is a probability parameter.
  3. Peeling (Approximate): It then performs a modified peeling process. If a node v in H hasn't sampled a sufficient number of its neighbors that are also in H (indicating it might not be part of a high-degree core), it's moved from H to L. This process is repeated.
  4. Iteration and Refinement: If all nodes are moved to L, it means the current threshold l is likely too high, and the algorithm reduces l and increases p for the next iteration. If some nodes remain in H, the current l is considered a potential approximation of the degeneracy.

The algorithm is proven to provide a (1+ε)-approximation with high probability and runs in O(n log n) time. Optimizations are also proposed, including a lower starting threshold, larger "leaps" in threshold reduction when H becomes empty, and reusing random number generation to improve practical performance.

Datasets

The paper evaluates its algorithm on several large-scale real-world web graph datasets:

  • clueweb12
  • uk-2014
  • gsh-2015
  • sk-2005
  • twitter-2010

These datasets are characterized by having billions of edges and hundreds of millions to billions of nodes, making them suitable for testing sublinear time algorithms.

Key Insights and Ideas

  • High-degree nodes are key: The degeneracy is heavily influenced by the densest parts of the graph, which are characterized by high-degree nodes connected to each other. This insight allows for focusing on a subset of nodes rather than the entire graph.
  • Sampling as a proxy for connectivity: Instead of examining all edges, sampling a fraction of neighbors provides a probabilistic way to infer connectivity within the high-degree subgraph. This is the core of the sublinear time complexity.
  • Iterative refinement with probabilistic guarantees: The algorithm iteratively refines its estimate of the degeneracy by adjusting a threshold and sampling strategy. The use of Chernoff bounds is crucial for proving the probabilistic guarantees of the approximation.
  • Practical optimizations matter: The paper demonstrates that simple optimizations like adjusting the initial threshold and reusing random numbers can significantly improve the practical performance of the algorithm on massive datasets.

Key Results

  • Sublinear Time Complexity: The algorithm achieves a running time of O(n log n), which is sublinear in the number of edges for dense graphs.
  • Approximation Guarantee: It provides a (1+ε)-approximation of the graph degeneracy with high probability.
  • Significant Speedup: Experiments show that NESD is orders of magnitude faster than previous approximation algorithms (like the one from Farach-Colton and Tsai, 2016) on massive webgraphs. It also outperforms the state-of-the-art exact degeneracy algorithm (SemiDeg+) by a significant margin, achieving speedups of 2.21x to 4.43x on some datasets.
  • NESD+ Performance: A variant that uses NESD to provide tighter bounds for the exact algorithm (NESD+) also shows competitive performance, sometimes outperforming SemiDeg+.
  • Error Factors: The experimental results demonstrate that the error factors of NESD are well within the theoretical bounds, with values ranging from 0.869 to 1.023 across different datasets and ε values.

Limitations and Future Work

  • Approximation vs. Exact: The primary limitation is that the algorithm provides an approximation, not an exact degeneracy value, although the approximation is very tight.
  • Extension to k-Core: The paper mentions that the algorithm can be extended to compute approximate k-core decomposition in O(n log n) time, which is a promising direction for future work.
  • Parameter Sensitivity: While the paper states that the parameter c had little impact, the choice of ε directly affects the approximation quality and potentially the running time. Further exploration of parameter tuning could be beneficial.
  • Specific Graph Structures: While tested on webgraphs, the performance on other types of massive graphs (e.g., social networks with different degree distributions) could be an area for further investigation.

Summary updated

BibTeX
@inproceedings{king2023computing,
  author = {Valerie King and Alex Thomo and Quinton Yong},
  title = {{Computing (1+epsilon)-Approximate Degeneracy in Sublinear Time}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.24963/ijcai.2023/240},
}
Figure