Towards a Decomposition-Optimal Algorithm for Counting and Sampling Arbitrary Motifs in Sublinear Time
Towards a Decomposition-Optimal Algorithm for Counting and Sampling Arbitrary Motifs in Sublinear Time
复制标题
DOI：
10.4230/lipics.approx/random.2021.55
复制
发表时间：
2021-07
期刊：
影响因子：
--
通讯作者：
Amartya Shankha Biswas;T. Eden;R. Rubinfeld
中科院分区：
文献类型：
--
作者：
Amartya Shankha Biswas;T. Eden;R. Rubinfeld
我们考虑采样的问题，并在图$ g $中大约计算出一个任意的图案$ h $，其中通过查询提供了$ g $的访问：学位，邻居和对以及统一的边缘样品查询。这些任务的先前算法基于$ h $的分解成奇数和星星的集合，表示为$ \ Mathcal {d}^*（h）= \ {o_ {o_ {k_1}，\ ldots，o_ {k_q}} ，s_ {p_1}，\ ldots，s_ {p_ \ ell} \} $。这些算法对于$ h $是集团或奇怪的循环的情况显示出最佳，但尚无其他下限。我们提出了一种用于采样的新算法和大约计算任意图案，该算法最多$ \ textrm {poly}（\ log n）$ castion始终与以前的结果一样好，对于大多数图表而言，$ g $的$ G $严格好。 。导致这种改进的主要成分是对采样星的改进统一算法，这可能引起独立的关注，因为它允许根据学位分布的$ p $ theminm skins进行对顶点进行采样。最后，我们证明，对于包含至少一个奇数循环的分解，该算法是\ emph {emph {emph {emph {emph {emph {emph}。这些是具有非平凡分解的图案$ h $的第一个下限，即分解中有一个不仅单个成分的图案。
We consider the problem of sampling and approximately counting an arbitrary given motif $H$ in a graph $G$, where access to $G$ is given via queries: degree, neighbor, and pair, as well as uniform edge sample queries. Previous algorithms for these tasks were based on a decomposition of $H$ into a collection of odd cycles and stars, denoted $\mathcal{D}^*(H)=\{O_{k_1}, \ldots, O_{k_q}, S_{p_1}, \ldots, S_{p_\ell}\}$. These algorithms were shown to be optimal for the case where $H$ is a clique or an odd-length cycle, but no other lower bounds were known. We present a new algorithm for sampling and approximately counting arbitrary motifs which, up to $\textrm{poly}(\log n)$ factors, is always at least as good as previous results, and for most graphs $G$ is strictly better. The main ingredient leading to this improvement is an improved uniform algorithm for sampling stars, which might be of independent interest, as it allows to sample vertices according to the $p$-th moment of the degree distribution. Finally, we prove that this algorithm is \emph{decomposition-optimal} for decompositions that contain at least one odd cycle. These are the first lower bounds for motifs $H$ with a nontrivial decomposition, i.e., motifs that have more than a single component in their decomposition.