Efficient and near-optimal algorithms for sampling connected subgraphs

We study the graphlet sampling problem: given an integer $k \ge 3$ and a simple graph $G=(V,E)$, sample a connected induced $k$-node subgraph of $G$ (also called $k$-graphlet) uniformly at random. This is a fundamental graph mining primitive, with applications in social network analysis and bioinformatics. In this work, we give the following results. (1) A near-tight bound for the classic $k$-graphlet random walk, as a function of the mixing time of $G$. In particular, ignoring $k^{O(k)}$ factors, we show that the random walk mixes in time $\tilde{\Theta}(t(G) \cdot \rho(G)^{k-1})$, where $t(G)$ is the mixing time of $G$ and $\rho(G)$ is the ratio between its maximum and minimum degree. (2) The first efficient algorithm for uniform graphlet sampling. The algorithm has a preprocessing phase that uses time ${O}(n k^2 \ln k + m)$ and space $O(n)$, and a sampling phase that uses $k^{O(k)} O(\log \Delta)$ time per sample. (3) A near-optimal algorithm for $\epsilon$-uniform graphlet sampling. The preprocessing takes time $O\big(\frac{k^6}{\epsilon}\, n \log n \big)$ and space $O(n)$, and the sampling takes $k^{O(k)}O\big((\frac{1}{\epsilon})^{10}\log \frac{1}{\epsilon} \big)$ expected time per sample.