Triangle Estimation using Polylogarithmic Queries

Anup Bhattacharya, Arijit Bishnu, Arijit Ghosh, Gopinath MishraarXiv 2018 · OpenReview

TL;DR

This paper introduces a new query oracle called Tripartite Independent Set (TIS) to efficiently estimate the number of triangles in a graph. They developed an algorithm that achieves this estimation using only a polylogarithmic number of TIS queries, provided that the number of triangles sharing any given edge is bounded. This work extends previous research on graph property estimation using sublinear algorithms.

What Problem Does This Paper Address?

Counting triangles in a graph is a fundamental problem in computer science, with applications in social network analysis, recommendation systems, and more. Traditional methods for counting triangles often require examining a significant portion of the graph, which can be computationally expensive for very large graphs. Sublinear algorithms aim to solve these problems by making a limited number of queries to the graph, without needing to read the entire dataset.

The challenge this paper addresses is how to efficiently estimate the total number of triangles in a graph using a novel query model, specifically the Tripartite Independent Set (TIS) oracle. This oracle, given three disjoint sets of vertices A, B, and C, can tell us if there's any triangle with one vertex in A, one in B, and one in C. The authors aim to leverage this oracle to count all triangles in the graph with a limited number of queries, under a specific condition: the number of triangles incident to any single edge (denoted as $\Delta_E$) must be polylogarithmically bounded. This condition is crucial for their algorithm's efficiency.

Methods

The core of this paper is the development of an algorithm that uses the Tripartite Independent Set (TIS) oracle to estimate triangle counts. The approach is inspired by prior work on estimating edge counts using a Bipartite Independent Set (BIS) oracle.

The algorithm employs a sparsification technique. This involves repeatedly breaking down the graph into smaller, disjoint tripartite subgraphs. The key idea is that these subgraphs, when appropriately scaled, collectively represent the original graph's triangle count.

The algorithm proceeds in several steps:

  1. Threshold Estimation: It first checks if the total number of triangles is below a certain threshold. If so, it directly estimates the count.
  2. General Sparsification: If the triangle count is above the threshold, the graph is sparsified into tripartite subgraphs. This step uses a novel "properly colored" triangle concept and a random vertex coloring scheme.
  3. Iterative Refinement: For each resulting tripartite subgraph, the algorithm recursively applies threshold checks and further sparsification if necessary.
  4. Coarse Estimation and Sampling: For subgraphs that remain "dense" (many triangles), a coarse estimation technique is used, followed by sampling to manage the complexity.
  5. Exact Counting: For "sparse" subgraphs (few triangles), the exact number of triangles is computed.

The algorithm relies heavily on probabilistic tools and concentration inequalities to bound errors and ensure high probability of success. The TIS oracle is the fundamental query primitive used throughout.

Datasets

Not discussed in the paper. The paper focuses on theoretical algorithm design and query complexity, not on empirical evaluation with specific datasets.

Key Insights and Ideas

  • The Tripartite Independent Set (TIS) Oracle: This is a novel query primitive that allows checking for the existence of a triangle spanning three disjoint vertex sets. Its introduction is a key contribution, enabling a new approach to triangle counting.
  • Sparsification via "Properly Colored" Triangles: The algorithm cleverly uses a concept of "properly colored" triangles, derived from a random coloring of vertices. This allows them to analyze the behavior of triangles under random partitions and bound the error introduced by sparsification.
  • Leveraging Bounded $\Delta_E$: The assumption that the number of triangles incident to any edge ($\Delta_E$) is bounded is critical. This assumption simplifies the analysis and allows for the polylogarithmic query complexity. The paper highlights that removing this assumption is a significant open challenge.
  • Extending BIS to TIS: The work builds upon the success of Bipartite Independent Set (BIS) oracles for edge estimation, demonstrating how a similar framework can be adapted for triangle estimation.

Key Results

The main result is an algorithm that estimates the number of triangles in a graph $G$ with $|V(G)| = n$ and $\Delta_E < d$ using $O(\frac{1}{\epsilon^4} d^2 \log^{18} n)$ Tripartite Independent Set (TIS) queries, achieving a $(1 \pm \epsilon)$-multiplicative approximation with high probability.

  • Query Complexity: The algorithm achieves a polylogarithmic query complexity in terms of $n$, which is a significant improvement over algorithms that might require reading a larger portion of the graph. The complexity depends on $\epsilon$, $d$ (the bound on $\Delta_E$), and $\log n$.
  • Approximation Guarantee: The algorithm provides a $(1 \pm \epsilon)$-multiplicative approximation, meaning the estimated count is close to the true count within a factor of $\epsilon$.
  • High Probability: The approximation guarantee holds with high probability, typically $1 - n^{-c}$ for some constant $c$.

Limitations and Future Work

  • Bounded $\Delta_E$ Assumption: The most significant limitation is the requirement that the number of triangles on any edge ($\Delta_E$) must be polylogarithmically bounded. The authors acknowledge that removing this assumption is a major open problem. They note that recent work by Dell et al. and Bhattacharya et al. has addressed this for generalized hypergraphs, suggesting that a similar breakthrough might be possible for triangle counting.
  • Query Oracle Dependency: The algorithm's efficiency is tied to the TIS oracle. While TIS is a natural extension of BIS, its practical implementation and availability might be a consideration.
  • Future Work: The authors explicitly mention the challenge of removing the $\Delta_E$ bound. They also suggest that their work can be generalized to $c$-uniform hypergraphs, building on concurrent research. Further exploration of the TIS oracle's capabilities and its application to other graph problems could also be fruitful.

Summary updated

Abstract

Estimating the number of triangles in a graph is one of the most fundamental problems in sublinear algorithms. In this work, we provide an algorithm that approximately counts the number of triangles in a graph using only polylogarithmic queries when \emph{the number of triangles on any edge in the graph is polylogarithmically bounded}. Our query oracle {\em Tripartite Independent Set} (TIS) takes three disjoint sets of vertices $A$, $B$ and $C$ as inputs, and answers whether there exists a triangle having one endpoint in each of these three sets. Our query model generally belongs to the class of \emph{group queries} (Ron and Tsur, ACM ToCT, 2016; Dell and Lapinskas, STOC 2018) and in particular is inspired by the {\em Bipartite Independent Set} (BIS) query oracle of Beame {\em et al.} (ITCS 2018). We extend the algorithmic framework of Beame {\em et al.}, with \tis replacing \bis, for approximately counting triangles in graphs.
BibTeX
@misc{bhattacharya2018triangle,
  author = {Anup Bhattacharya and Arijit Bishnu and Arijit Ghosh and Gopinath Mishra},
  title = {{Triangle Estimation using Polylogarithmic Queries}},
  year = {2018},
  eprint = {1808.00691},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1808.00691},
}
Figure