The Sketching Complexity of Graph and Hypergraph Counting
The Sketching Complexity of Graph and Hypergraph Counting
复制标题
图和超图计数的草图复杂性
DOI：
10.1109/focs.2018.00059
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Eric Price
中科院分区：
文献类型：
--
作者：
John Kallaugher;M. Kapralov;Eric Price
子图计数是图形处理中的基本原始性，并具有社交网络分析中的应用程序（例如，估计图形的群集系数），数据库处理和其他领域。在文献中已经对子图计数的空间复杂性进行了广泛的研究，但是许多自然设置仍然不太了解。在本文中，我们在草图模型中重新访问了子图（和超图）计数问题，在该模型中，算法的状态在处理到图的更新流是流的线性函数。该模型最近在文献中引起了很多关注，并已成为解决动态图流问题的标准模型。在本文中，我们对素描的复杂性进行了紧密的限制，即计算一个小子h的出现数量，在一个边界图G中以边缘更新流呈现。具体而言，我们表明，问题的空间复杂性受图H的分数顶点覆盖号。位于一组新的傅立叶分析工具，我们开发了这些工具来分析同时通信模型中的多人通信协议，从而使我们能够证明一个紧密的下限。我们认为，我们的技术可能会在其他设置中找到应用。除了给所有图H给出紧密的界限外，我们的算法和下限都扩展到了超图设置，尽管空间复杂性有所损失。
Subgraph counting is a fundamental primitive in graph processing, with applications in social network analysis (e.g., estimating the clustering coefficient of a graph), database processing and other areas. The space complexity of subgraph counting has been studied extensively in the literature, but many natural settings are still not well understood. In this paper we revisit the subgraph (and hypergraph) counting problem in the sketching model, where the algorithm's state as it processes a stream of updates to the graph is a linear function of the stream. This model has recently received a lot of attention in the literature, and has become a standard model for solving dynamic graph streaming problems. In this paper we give a tight bound on the sketching complexity of counting the number of occurrences of a small subgraph H in a bounded degree graph G presented as a stream of edge updates. Specifically, we show that the space complexity of the problem is governed by the fractional vertex cover number of the graph H. Our subgraph counting algorithm implements a natural vertex sampling approach, with sampling probabilities governed by the vertex cover of H. Our main technical contribution lies in a new set of Fourier analytic tools that we develop to analyze multiplayer communication protocols in the simultaneous communication model, allowing us to prove a tight lower bound. We believe that our techniques are likely to find applications in other settings. Besides giving tight bounds for all graphs H, both our algorithm and lower bounds extend to the hypergraph setting, albeit with some loss in space complexity.
用于估计平面图及其他区域中的匹配大小的流算法
DOI：
10.1145/3230819
发表时间：
2015
期刊：
ACM Transactions on Algorithms (TALG)
影响因子：
--
作者：
Hossein Esfandiari;Mohammad Taghi Hajiaghayi;Vahid Liaghat;Morteza Monemizadeh;Krzysztof Onak
通讯作者：
Krzysztof Onak