Faster algorithms for sampling connected induced subgraphs

Marco Bressan

Abstract

Analyzing the distribution of small, connected, induced subgraphs—known as graphlets—is a cornerstone of network science, with applications ranging from bioinformatics to social network analysis. However, uniform sampling of these structures has historically been computationally expensive. This paper introduces the first efficient algorithms for this task. By employing a novel vertex-sorting technique to "regularize" the graph, the author provides a truly uniform sampling method (UGS) and the first sublinear-time algorithm for approximately uniform sampling (APX-UGS). These methods break long-standing efficiency barriers, offering provable complexity bounds that significantly improve upon prior work.

Introduction

In complex systems, graphlets like triangles, stars, or cliques serve as essential building blocks. Understanding their frequency and distribution helps researchers uncover the underlying principles of network formation and function. Despite their importance, sampling graphlets uniformly at random is a non-trivial challenge. While selecting an arbitrary set of $k$ vertices is straightforward, ensuring that the selected set is connected and that every possible connected set has an equal probability of being chosen is computationally demanding.

Existing methods often suffer from high per-sample costs, sometimes proportional to the entire graph size, or provide only "approximately uniform" results with poorly understood convergence rates. This research addresses these gaps by providing near-optimal, provably efficient algorithms for both uniform and $\epsilon$-uniform graphlet sampling.

Methodological Advancements

The paper contributes three primary algorithmic innovations:

  1. Refined Random Walks (RWGS): The author establishes a new, tighter bound on the mixing time for the $k$-graphlet walk. This is achieved by proving a technical connection between the relaxation times of a graph and its line graph, providing a more direct path to tight bounds than traditional methods like Cheeger’s inequality.
  2. Uniform Graphlet Sampler (UGS): This is the central contribution. To achieve truly uniform sampling, the author introduces a preprocessing step that "regularizes" the graph. By sorting vertices into a 1-dominating order—a process of repeatedly removing the highest-degree vertex—the algorithm ensures that local neighborhoods behave similarly to regular graphs. This structure enables an efficient rejection sampling scheme where the probability of rejection is mathematically controlled.
  3. Sublinear-Time Sampler (APX-UGS): For massive graphs where linear-time preprocessing is prohibitive, the author proposes APX-UGS. This version utilizes graph sketching and cut-size estimation to achieve $\epsilon$-uniform sampling. Its preprocessing time is sublinear in the number of edges ($m$), making it suitable for extremely large or streaming datasets.

Key Insights

The core innovation lies in using vertex sorting as a form of regularization. By organizing the graph's vertices in a specific topological order, the sampling problem becomes significantly more manageable. This allows the algorithm to "bucket" graphlets such that sampling probabilities within each bucket are balanced, effectively circumventing the "curse of rejection" that plagues standard connectivity-constrained sampling.

Results and Performance Comparison

The theoretical performance of these algorithms represents a significant leap forward. The UGS algorithm is the first to break the $\Theta(n+m)$ per-sample barrier for uniform sampling, achieving an expected sampling time of $k^{O(k)} \log \Delta$. Furthermore, APX-UGS is the first to offer $\epsilon$-uniform sampling with preprocessing time independent of the number of edges $m$ (specifically $O(n \log n)$).

Comparison of the proposed algorithms (UGS, APX-UGS, RWGS) against prior state-of-the-art methods.

As shown in the table above, the proposed methods offer superior complexity bounds across preprocessing time, space, and per-sample time compared to existing literature. Notably, UGS provides truly uniform output with significantly reduced per-sample complexity compared to previous uniform samplers.

Limitations and Future Work

While these algorithms mark a major advancement, they still face an exponential dependence on the subgraph size $k$ ($k^{O(k)}$). This limits their practical application to relatively small graphlets (typically $k \le 10$). Additionally, the efficiency of the sublinear results depends on the availability of specific graph access models, such as neighbor and degree queries. Future research may explore whether $\Omega(|G|)$ operations are strictly necessary for uniform sampling in very sparse graphs and seek to further reduce the dependence on $k$.

Conclusion

By bridging the gap between theoretical complexity and practical graph mining needs, this work provides a robust framework for efficient graphlet analysis. The introduction of vertex-sorting-based regularization offers a powerful new tool for tackling the connectivity constraints inherent in network subgraph sampling.

Summary updated

BibTeX
@article{bressan2023faster,
  author = {Marco Bressan},
  title = {{Faster algorithms for sampling connected induced subgraphs}},
  journal = {ACM Trans. Algorithms},
  year = {2023},
  doi = {10.1145/3596495},
}
Figure