Towards Tight Bounds for Estimating Degree Distribution in Streaming and Query Models
Arijit Bishnu, Debarshi Chanda, Gopinath Mishra · 2025
Read Towards Tight Bounds for Estimating Degree Distribution in Streaming and Query Models by Arijit Bishnu, Debarshi Chanda, Gopinath Mishra (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-21784.txt.
Introduction
Arijit Bishnu, Debarshi Chanda, and Gopinath Mishra bound the cost of reading a graph's degree spread in a 2025 paper. The spread counts how many nodes reach each link count. Two error knobs tune how loose the read may be in value and in rank.
Their method mixes sampled nodes and edges and works in both stream and query settings. Cost lands at a rate set by the graph's edge count over its h-index, and matching lower bounds prove it tight. Even multi-pass stream methods cannot beat it. The result settles an open problem in sublinear graph work. Tests on real graphs back the counts.
Catalog record
| CREATOR | Arijit Bishnu, Debarshi Chanda, Gopinath Mishra |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 82 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-21784
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Towards Tight Bounds for Estimating Degree Distribution in Streaming and Query Models Arijit Bishnu, Debarshi Chanda, Gopinath Mishra Abstract The degree distribution of a graph G = ( V , E ) G=(V,E) , | V | = n \left|{V}\right|=n , | E | = m \left|{E}\right|=m is one of the most fundamental objects of study in the analysis of graphs as it embodies relationship among entities. In particular, an important derived distribution from degree distribution is the complementary cumulative degree histogram (ccdh). The ccdh is a fundamental summary of graph structure, capturing, for each threshold d d , the number of vertices with degree at least d d . For approximating ccdh, we consider the ( ε 𝒟 , ε ℛ ) (\varepsilon_{\mathcal{D}},\varepsilon_{\mathcal{R}}) -BiCriteria Multiplicative Approximation, which allows for controlled multiplicative slack in both the domain and the range. There are only two works in sublinear models prior to us that considered ccdh – one in streaming setup [Simpson et al. (ICDM 2015)] and the other in property testing setup with query models [Eden et al. (WWW 2018)]. However, the exact complexity of the problem, including lower bounds, was not known and had been posed as an open problem in WOLA 2019 [Sublinear.info, Problem 98]. In this work, we first design an algorithm that can approximate ccdh if a suitable vertex sample and an edge sample can be obtained and thus, the algorithm is independent of any sublinear model. Next, we show that in the streaming and query models such samples can be obtained, and (almost) settle the complexity of the problem across both the sublinear models. Our upper bound results are the following where h h is the h h -index of G G : • For the non-adaptive and adaptive query setup, our algorithms make O ~ ( n / ε R 2 h + m / ε D 2 h ) \widetilde{O}\left(\nicefrac{{n}}{{\varepsilon_{R}^{2}h}}+\nicefrac{{m}}{{\varepsilon_{D}^{2}h}}\right) and O ~ ( m / h ( 1 / ε R 2 CLOSE CLOSE \widetilde{O}(\nicefrac{{m}}{{h}}(\nicefrac{{1}}{{\varepsilon_{R}^{2}}} OPEN OPEN + 1 / ε D 2 ) ) +\nicefrac{{1}}{{\varepsilon_{D}^{2}}})) local and random edge queries, respectively, where O ~ ( ⋅ ) \widetilde{O}(\cdot) hides polynomial in log n \log n . • For the one-pass and two-pass streaming setup, our algorithms use O ~ ( n / ε R 2 h + m / ε D 2 h ) \widetilde{O}\left(\nicefrac{{n}}{{\varepsilon_{R}^{2}h}}+\nicefrac{{m}}{{\varepsilon_{D}^{2}h}}\right) and O ~ ( m / h ( 1 / ε R 2 + CLOSE CLOSE \widetilde{O}(\nicefrac{{m}}{{h}}(\nicefrac{{1}}{{\varepsilon_{R}^{2}}}+ OPEN 1 / ε D 2 ) \nicefrac{{1}}{{\varepsilon_{D}^{2}}}) space, respectively. Prior to our work, there were no known lower bounds for ccdh across sublinear models. In terms of lower bounds, we first show that the problem does not have a sublinear solution for all graphs through a Ω ( n ) \Omega(n) lower bound on both query and space. Furthermore, we establish a Ω ( m / h ) \Omega\left(\nicefrac{{m}}{{h}}\right) lower bound for the adaptive query and multi-pass streaming setup, (almost) matching our upper bounds. A consequence of our lower bound results is that the SADDLES algorithm of [Eden et al. (WWW 2018)] is almost tight. 1 Introduction Degree sequence in graphs has been of theoretical interest for a long time West et al. 2001 ; Bollobás 2001 . Degree distribution, which can be derived from degree sequences, was also of theoretical interest for researchers studying random networks like Erdős-Rényi graphs. The problem of degree distribution received renewed attention with the advent of massive graphs. These massive graphs are ubiquitous wherever there are entities and relationships among those entities like in web-pages and hyperlinks between web-pages, IP addresses and connection links between addresses, social network entitites and their friendships, etc. The degree distribution of a graph embodies relationship among entities across domains as varied as biology Pržulj 2007 , social networks Golbeck 2013 ; Seshadhri et al. 2012 ; Ebbes et al. 2008 , network robustness Yuan et al. 2015 , web graphs Cohen et al. 2000 ; Pennock et al. 2002 ; Aksoy et al. 2017 , graph mining Chakrabarti and Faloutsos 2006 , study of algorithms Durak et al. 2013 ; Mitzenmacher 2004 etc. This explosion in the practical usage of massive graphs generated a new field of network science Barabási 2013 ; Barabási and Albert 1999 ; Broder et al. 2000 ; Faloutsos et al. 1999 ; Newman 2003 . The way these massive graphs are stored and processed are also varied giving rise to the study of massive graph algorithms under different computation models. They can be stored in a distributed fashion Fu et al. 2017 ; Buragohain et al. 2020 ; Yan et al. 2017 , they can be presented as massive graph streams McGregor 2014 ; Gou et al. 2023 , they can be accessed only through some graph samples obtained through some particular query accesses Faloutsos et al. 1999 ; Eden et al. 2018 to the graph. Almost parallely in time frame, and also fueled by the paradigm of massive data , two new areas of study – sub-linear space (streaming) and sub-linear time (property testing) algorithms – started gaining attention Goldreich and Ron 1997 ; Goldreich et al. 1998 ; Goldreich 1999 ; Alon et al. 1999 . It was only natural that fundamental problems of network science will also be of interest to the sub-linear algorithms community. Degree distribution is one such fundamental problem that drove the study of network science Barabási 2013 . The problem of degree distribution is characterized by scale freeness and heavy tail. The sub-linear algorithms community considered the problem of degree distribution from sublinear-space Simpson et al. 2015 and sublinear-time Eden et al. 2018 perspectives. As a comprehensive theoretical solution, including a lower bound, was eluding the community, the problem found its way into the open problem list Seshadri 2019 of the sub-linear community in 2019. Since then, it seems that no sublinear solution has been proposed for this problem. We revisit this open problem both in terms of streaming and property testing. Given complete access to the graph in the RAM model, degree distribution can be solved in linear time and space. In massive graph scenario, such an access is almost ruled out. Graph parameters, including degree distribution, are estimated from small sized graph subsamples. There is a vast literature on estimating the degree distribution using a small subsample Ribeiro and Towsley 2012 ; Zhang et al. 2015 ; Dasgupta et al. 2014 ; Stewart 2025 ; Antunes et al. 2021 ; Eden et al. 2018 . Ideally, the sublinear community wants this subsample size to be o(n) but classical works in the graph sampling framework used 10-30\% of the vertices as a subsample that was improved to about 1\% in Eden et al. 2018 . The same work highlighted the need of a theoretical guarantee for the estimation of the degree distribution from graph subsamples. Moreover, to the best of our knowledge, there were no known lower bounds for the estimation of degree distribution. Against this backdrop, we contextualize our work. The next section sets up the problem, the machine models and highlights our results and also places our work