Faster Estimation of the Average Degree of a Graph Using Random Edges and Structural Queries

We revisit the problem of designing sublinear algorithms for estimating the average degree of an n-vertex graph. The standard access model for graphs allows for the following queries: sampling a uniform random vertex, the degree of a vertex, sampling a uniform random neighbor of a vertex, and "pair queries" which determine if a pair of vertices form an edge. In this model, original results [Goldreich-Ron, RSA 2008; Eden-Ron-Seshadhri, SIDMA 2019] on this problem prove that the complexity of getting (1+ε)-multiplicative approximations to the average degree, ignoring ε-dependencies, is Θ( √ n). When random edges can be sampled, it is known that the average degree can estimated in O(n 1/3 ) queries, even without pair queries [Motwani-Panigrahy-Xu, ICALP 2007; Beretta-Tětek, TALG 2024].

We give a nearly optimal algorithm in the standard access model with random edge samples. Our algorithm makes O(n 1/4 ) queries exploiting the power of pair queries. We also analyze the "full neighborhood access" model wherein the entire adjacency list of a vertex can be obtained with a single query; this model is relevant in many practical applications. In a weaker version of this model, we give an algorithm that makes O(n 1/5 ) queries. Both these results underscore the power of structural queries, such as pair queries and full neighborhood access queries, for estimating the average degree. We give nearly matching lower bounds, ignoring ε-dependencies, for all our results.