Efficiently counting bicliques in large bipartite graphs is a fundamental problem with applications in network analysis, bioinformatics, and social sciences. However, existing exact algorithms do not scale well to large graphs, and current approximation algorithms lack formal accuracy guarantees. In this paper, we present the first approximation algorithm for the (p,q)-biclique counting problem that offers formal accuracy guarantees. Our approach introduces a novel sampling framework, termed BC-Shadow, which refines the sample space using edge-oriented techniques to strategically balance computational costs across algorithmic stages. This refinement increases the density of bicliques in the sample space, reducing the number of samples required for accurate estimation. Our algorithm adaptively determines the number of successful samples that are needed to satisfy predefined error and failure probability, enabling real-time adjustment to graph properties. We further enhance sampling efficiency with a new sampling structure, named zstar, which establishes a one-to-one correspondence with (p,q)-bicliques, eliminating redundancies and improving accuracy. Comprehensive theoretical analyses confirm the algorithm's accuracy and running time guarantees, while extensive experiments on large real-world datasets demonstrate its scalability and effectiveness.

Counting and enumerating all occurrences of k -cliques, i.e., complete subgraphs with k vertices, in a large graph G is a fundamental problem with many applications. However, exact solutions are often infeasible due to the exponential growth in the number of k -cliques when k increases. Thus, a more practical approach is approximately counting and uniformly sampling k -cliques. Turán-Shadow and DPColorPath are two state-of-the-art algorithms for approximately counting k -cliques. The general idea is first constructing a sample space that is a superset of all k -cliques in G , and then sampling t elements uniformly-at-random (u.a.r.) from the sample space for a pre-determined t ; the k -clique count is estimated as the sample space size multiplied by the ratio of k -cliques among the t samples. Although techniques have been proposed in Turán-Shadow for setting t to ensure the estimation accuracy, the theoretically chosen t is often too large to be practical. As a result, both of the existing algorithms used a fixed t in their implementations and thus do not offer accuracy guarantee. In this paper, we propose the first randomized algorithm that achieves the theoretical estimation accuracy and the practical efficiency at the same time. Different from the existing algorithms, we pre-determine the number s of k-clique samples that are required to achieve the estimation accuracy. Consequently, we can estimate the running time of the sampling stage (i.e., time taken to sample sk -cliques), for a given sample space. Then, we propose to balance the time of constructing/refining the sample space and the time of the sampling stage, by stopping the refinement of the sample space once the elapsed time is comparable to the estimated time of the sampling stage. Extensive empirical studies on large real graphs show that our algorithm SR-kCCE provides an accurate k -clique count estimation and also runs efficiently. As a by-product, our algorithm can also be used for efficiently sampling a certain number of k -cliques u.a.r. from G.