A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling
A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling
复制标题
一种通过边缘采样计算任意子图的简单次线性时间算法
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
S. Khanna
中科院分区：
文献类型：
--
作者：
Sepehr Assadi;M. Kapralov;S. Khanna
在子图计数问题中，我们得到一个输入图$G(V，E)$和一个目标图$H$；目标是估计$H$在$G$中出现的次数。这里我们的重点是设计次线性时间算法，在该算法被授予对$G$的查询访问权限的设置中，近似计算$H$在$G$中的出现次数。这个问题已经在最近的几篇论文中进行了研究，这些论文主要集中在特定的图族$H$上，如三角形、团和星。然而，对任意图$H$的近似计数知之甚少。这与密切相关的子图枚举问题形成了鲜明的对比，在数据库社区中，子图枚举问题作为数据库连接问题受到了极大的关注。AGM界表明，具有$m$边的图$G$中任意子图$H$的最大出现次数为$O(m^{\Rho(H)})$，其中$\Rho(H)$是$H$的分数边覆盖，并且对于任何$H$都知道具有匹配运行时的计数算法.
我们通过设计一个次线性时间算法来弥合子图计数和子图计数之间的差距，该算法可以估计$G$中任意子图$H$的数目，以$#H$表示，在$(1\pm\epsilon)$-近似W.H.P.在$O(\frac{m^{\rho(H)}}{\#H})\CDOT Poly(\log{n}，1/\epsilon)$time中。我们的算法允许一般图的标准查询集，即度查询、配对查询和邻接查询，加上一个额外的边样本查询，返回随机选择的边。我们算法的性能与Eden等人的算法相当。[Focs 2015，STEC 2018]，用于计算三角形和团，并在边样本查询的附加假设下将其扩展到子图$H$的所有选择。我们进一步证明了我们的算法适用于更一般的数据库连接大小估计问题，并证明了该问题的匹配下界。
In the subgraph counting problem, we are given a input graph $G(V, E)$ and a target graph $H$; the goal is to estimate the number of occurrences of $H$ in $G$. Our focus here is on designing sublinear-time algorithms for approximately counting occurrences of $H$ in $G$ in the setting where the algorithm is given query access to $G$. This problem has been studied in several recent papers which primarily focused on specific families of graphs $H$ such as triangles, cliques, and stars. However, not much is known about approximate counting of arbitrary graphs $H$. This is in sharp contrast to the closely related subgraph enumeration problem that has received significant attention in the database community as the database join problem. The AGM bound shows that the maximum number of occurrences of any arbitrary subgraph $H$ in a graph $G$ with $m$ edges is $O(m^{\rho(H)})$, where $\rho(H)$ is the fractional edge-cover of $H$, and enumeration algorithms with matching runtime are known for any $H$.
We bridge this gap between subgraph counting and subgraph enumeration by designing a sublinear-time algorithm that can estimate the number of any arbitrary subgraph $H$ in $G$, denoted by $\#H$, to within a $(1\pm \epsilon)$-approximation w.h.p. in $O(\frac{m^{\rho(H)}}{\#H}) \cdot poly(\log{n},1/\epsilon)$ time. Our algorithm is allowed the standard set of queries for general graphs, namely degree queries, pair queries and neighbor queries, plus an additional edge-sample query that returns an edge chosen uniformly at random. The performance of our algorithm matches those of Eden et.al. [FOCS 2015, STOC 2018] for counting triangles and cliques and extend them to all choices of subgraph $H$ under the additional assumption of edge-sample queries. We further show that our algorithm works for the more general database join size estimation problem and prove a matching lower bound for this problem.
通过边缘采样计算星子图的次线性时间算法
影响因子：
1.1
作者：
Aliakbarpour, Maryam;Biswas, Amartya Shankha;Gouleakis, Themis;Peebles, John;Rubinfeld, Ronitt;Yodpinyanee, Anak
通讯作者：
Yodpinyanee, Anak
用于计算图流中的三角形和其他子结构的更紧密的空间界限
DOI：
--
发表时间：
2017
期刊：
34th Symposium on Theoretical Aspects of Computer Science
影响因子：
--
作者：
Bera, Suman K;Chakrabarti, Amit
通讯作者：
Chakrabarti, Amit