How large is your graph?
Varun Kanade∗1,2, Frederik Mallmann-Trenn†3,4, and Victor Verdugo‡3,5
1

arXiv:1702.03959v1 [cs.DS] 13 Feb 2017

Department of Computer Science, University of Oxford
2
The Alan Turing Institute
3
Départment d’Informatique, École normale supérieure
4
Department of Computer Science, Simon Fraser University
5
Departmento de Ingenierı́a Industrial, Universidad de Chile
February 15, 2017

Abstract
We consider the problem of estimating the graph size, where one is given only local access to
the graph. We formally define a query model in which one starts with a seed node and is allowed
to make queries about neighbours of nodes that have already been seen. In the case of undirected
graphs,
an estimator
of Katzir et al. (2014) based on a sample from the stationary distribution π uses



1
O kπk
+davg queries; we prove that this is tight. In addition, we establish this as a lower bound
2
even when the algorithm is allowed to crawl the graph arbitrarily; the results of Katzir et al. give
an upper bound that is worse by a multiplicative factor tmix ·log(n).
The picture becomes significantly different in the case of directed graphs. We show that without
strong assumptions on the graph structure, the number of nodes cannot be predicted to within a
constant multiplicative factor without using a number of queries that are at least linear in the number
of nodes; in particular, rapid mixing and small diameter, properties that most real-world networks
exhibit, do not suffice. The question of interest is whether any algorithm can beat breadth-first search.
We introduce a new parameter, generalising the well-studied conductance, such that if a suitable
bound on it exists and is known to the algorithm, the number of queries required is sublinear in the
number of edges; we show that this is tight.

∗

varunk@cs.ox.ac.uk
frederik.mallmann-trenn@ens.fr
‡
vverdugo@dii.uchile.cl
†

1

Introduction

Networks contain a wealth of information and studying properties of networks may yield important insights.
However, most networks of interest are very large and ordinary users may have rather restricted access to
them. One of most basic questions about networks is the number of nodes contained in them. For example,
the number of pages on the world wide web (WWW) is estimated to be just shy of 50 billion at the time of
writing.1 Facebook currently reports having about one and three quarter billion users;2 Twitter reports having about 300 million active users. It is undesirable to rely on a small number of sources for such information.
At times we might be interested in more specific graphs for which there is no public information available
at all. Is there a way to estimate the total number of nodes using rather limited access to these graphs?
Our model is motivated by the kind of access ordinary users may have to graphs of interest. For
example, most social network companies provide some sort of an application programming interface
(API). In the case of the world wide web, one option is to simply crawl. The graph query access models
we use are formally defined in Section 2.1. For now, we mention four specific networks, each of which
captures an important modelling aspect. First, Facebook is an undirected graph of friendships, and as
long as privacy settings allow it, it is possible to request the number of friends for a given user and the
identity of the friends. Second, the world wide web, which is a directed graph—it is possible to extract
out-links on a given webpage; however, there is no obvious method to access all in-links. The third is what
we refer to as the “fan” network—for a specific user it is possible to query who she is a fan of, however
in terms of her fans only the number is revealed.3 And finally, the fourth is the twitter network, which is
directed, however both the followers and followees of a given user are accessible, as far as privacy settings
allow. Obviously, the method to estimate the number of nodes may be rather different in each case. It
is worth mentioning that the twitter network can essentially be treated as an undirected graph, however
it still leaves open the possibility that differentiating in-links and out-links leads to better estimators.
While memory and computational requirements do act as constraints when dealing with large graphs,
possibly the most important one is the rate limits set on queries made using the API. Even when crawling
the web, there is the risk of simply being blocked if large volumes of requests are sent to the same server.
Thus, the most scarce resource in this instance is the number of queries made about the graph. Our
query model counts these costs strictly—essentially every time a new node is discovered, its degree is
revealed at unit cost and a unit cost is incurred for every neighbour requested.

1.1

Related Work

There is a large body of literature on estimating statistical properties of graphs, reflecting the relevance
of and interest in studying complex networks. Much of this work is in the more applied literature and in
particular, we were unable to pin down a precisely defined query model. The work most closely related
to ours is that of Katzir et al. [12]. They consider a model where a random sample drawn from the
stationary distribution of the random walk is available. If the random walk mixes rapidly and a suitable
bound
on the mixing time is known, this can be simulated in the models we consider. They show that

1
O kπk +davg queries suffice, where π is the stationary distribution and davg is the average degree.
2
We show that this is tight when given access to a sample from the stationary distribution. When only
neighbour queries are allowed, we show that this bound is tight up to a multiplicative factor of the mixing
1

www.worldwidewebsize.com
Here, billion refers to one thousand million, not a million million.
3
Although it is not obvious which of the extant networks has this property, there are close approximations such as
Blogger. In any case, it is a very natural intermediate model between the second and the fourth.
2

1

time and other polylogarithmic factors. It is worth mentioning what this bound actually yields in graphs
where the average degree is small, something common to most real world networks. It is always the case
√
that kπk−1
2 ≤ n, where equality holds in the case of regular graphs. Thus, the number of queries required
is significantly sublinear in the number of nodes. For graphs with power law degree distributions with
1/4 logn). See Section 3.1 for further discussion.
parameter β =2, Katzir et al. calculated that kπk−1
2 =O(n
In more recent work, Hardiman and Katzir give another estimator based on counting shared neighbours [11]. They give a slightly better bound on the number of nodes sampled than the earlier work
of Katzir et al. [12]. However, it is unclear that this can be implemented efficiently in the query model
in our paper. Cooper et al. [4] obtain estimators for the number of edges, triangles and nodes. The
estimators are based on random walks over the graph, but in particular, for estimating the number of
nodes, the transition probabilities are not inversely proportional to the degree. Their estimator relies
on counting the time required for the kth return to a particular vertex. It seems unlikely that either
their random walk or their estimator can be implemented in a query efficient manner. Musco et al. [17]
develop a distributed collision based approach where several random walks traverse the graph and counts
the number of collisions with other random walks. Dasgupta et al. [6] provide an estimator of the
average degree that uses O(logUloglogU) samples, where U is an upper bound on the maximum degree.
Somewhat surprisingly, this seems to be an easier task than estimating the number of nodes.
Cooper and Frieze [3] estimate the graph size in a dynamic setting where the graph grows over time
and there exists an agent that is allowed to move through the network every time a new node arrives.
They prove that this agent visits asymptotically a constant fraction of the vertices. If one has access to
the complete neighbourhood of a node when it is visited, it is shown by Mihail et al. that the expected
time in which a walk discovers a power law random graph is sublinear [16]. There has been some older
theoretical work on estimating the size of graphs motivated primarily by search algorithms [13, 15].
However the model of graph access is unrelated and they do not present bounds on the estimates.
Related to the question of estimating graph properties is that of testing whether graphs have specific
properties. Property testing has received much attention in the last two decades with properties of
undirected graphs being one of the important areas of focus (see e.g., [9]). Directed graphs have received
somewhat less attention; there are two main query models, unidirectional where only out-neighbours may
be queried, and bidirectional where both in and out-neighbours may be queried [1]. Bender and Ron showed
that there exist properties such as strong connectivity, where the query complexity may be either O(1) or
√
Ω( n) depending on the model used, even when allowing two-sided error. More recently, Czumaj et al.
have shown that if a property can be tested with constant query complexity in the bidirectional setting,
it can be tested with sublinear query complexity in the unidirectional model [5]. Although, these query
models are closely related to the ones in this paper, a crucial aspect exploited by most property testing
algorithms is the ability to sample nodes uniformly at random, something that is not available in our setting.
A closely related line of work is that on estimating properties of distributions from samples; of most
interest, in our case is the support size. This problem has a long history going back at least to Good
and Turing [10]. We only mention a few recent relevant results here. Given access to uniformly sampled
√
elements from a set, O( n) samples suffice to derive a good estimate of the set size using the birthday
problem [8]. However, it is not clear how to sample from the uniform distribution over the nodes of the
graph in the query model we consider. Valiant and Valiant show that support size can be estimated to a
good accuracy using O(n/logn) samples for any distribution [18, 19]. However, their result requires that
any element in the support has Ω(1/n) probability mass, something that is not true for the stationary
distribution of a random walk on a graph. (In the case of directed graphs this problem becomes even
more severe, since some nodes may have exponentially small stationary probability mass.)

2

1.2

Our contributions

Firstly, our contribution is to express the problem of estimating graph properties formally. As discussed in
the introduction, networks of interest vary significantly in terms of what access might be easily available
to an ordinary user. Keeping in mind the examples of Facebook, the web, the fan-network and Twitter,
we introduce different types of oracles that provide access to the graph.
The focus of this work is on estimating the number of nodes. For any ε>0 and δ >0, we say that
an algorithm (with access to a query oracle) provides an ε-accurate estimate of the number of nodes,
if with probability at least 1−δ it outputs n
b, such that |n−b
n|≤εn. The main quantity to be optimised
is the number of oracle queries, though all algorithms considered in this paper are also computationally
highly efficient. Allowed queries are defined precisely in Section 2.1. Here, we point out that a unit cost
must be paid for every disclosed neighbour as well as to know the degree of a node. All algorithms have
access to the identifier of one seed node in the graph to begin with. Throughout we will assume that ε
and δ are constants and the use of O(·) and Ω(·) notation in this paper hides all dependence on ε and δ.
Undirected Graphs. Katzir et al. [12] implicitly
 assumethe ability to sample from the stationary
1
distribution. They show that in this setting O kπk
+davg samples from the stationary distribution
2
π suffice, where davg is the average degree. If the graph is connected and a suitable bound on the
mixing time exists which is known to the algorithm, O(tmixlogn) queries suffice to draw one node from
a distribution that is close (up to inverse polynomial factors in variation distance)
to 
the stationary


1
+davg
distribution using only neighbour queries. This gives an upper bound of O tmix ·logn· kπk
2
queries with a neighbour query oracle (Corollary 3.2). In terms of lower bounds, we establish that
• (Theorem 3.5) Any algorithm that has access to random samples from the stationary distribution π
and
 outputs a0.1-accurate estimate of the number of nodes with probability at least 0.99, requires
1
Ω kπk
+davg samples.
2

• (Theorem 3.8) Any algorithm that has access to neighbour queries and outputs a 0.1-accurate

1
+davg queries.
estimate of the number of nodes with probability at least 0.99, requires Ω kπk
2

We remark that there is a gap between the upper bound and lower bound when considering an oracle
with neighbour access. A question left open by our work is whether the multiplicative factor of tmixlogn
is required, or whether a more efficient estimator can be designed.
Directed Graphs. The estimator of Katzir et al. is not applicable in the setting when graphs are
directed, unless the query model allows in-neighbour queries as well as out-neighbour queries, in which case
all results in the undirected setting hold. The reason for this is that even if one did receive a sample drawn
from the stationary distribution, it is no longer the case that πv ∝deg(v), a crucial property exploited by
the estimator of Katzir et al.. In fact, unless strong assumptions are made on the relationship between the
in-degree and the out-degree (e.g., being Eulerian), no simple expression for π in terms of degrees exists.4
We provide constructions of graphs that demonstrate that low average degree, rapid mixing and
small diameter are not sufficient to design algorithms to estimate the graph size with sublinear (in
n) query complexity. In fact, we show that when only given access to a sample from the stationary
4

We mention that the distribution is closely related to the PageRank distribution. However, the PageRank random
walk jumps to a uniformly random node in the graph with a small probability; this is done to avoid problems when the
graph is not strongly connected.

3

distribution, a superpolynomially large sample may be required even for graphs with constant average
degree, logarithmic diameter and rapid mixing. The reason for this is that in the case of directed graphs
most of the stationary mass can be concentrated on a very small number of nodes.
In order to understand the query complexity when neighbour-queries are allowed, we define a new
parameter called generalized conductance. Roughly speaking a graph has ε-general conductance φε, if
every set containing at most (1−ε)n nodes has at least φε fraction of directed edges going out. If a
suitable bound on the value of φε is known, we show that a simple edge-sampling algorithm outputs
an estimate to within relative error ε while using O(n/φε) queries (Theorem 4.4) and that this is almost
tight, in the sense that any algorithm that outputs an estimate that is even slightly better than ε requires
at least Ω(n/φε) queries (Theorem 4.6). The algorithm only requires access to out-neighbours, while
the lower bound holds even with respect to an oracle that allows in-neighbour queries, which means that
it also applies in the case of undirected graphs.

1.3

Discussion

In terms of improvements to our results, the most interesting question is whether any reasonable subclass
of directed graphs are amenable to significantly improved query complexity (ideally sublinear) for the
problem of estimating the number of nodes. The constructions in Section 4 show that having low average
degree, small diameter and rapid mixing is not enough. For undirected graphs, it is an interesting question
whether the extra factor of mixing time tmix must be paid, when only neighbour queries are allowed. It
is conceivable that an improved estimator that can handle correlated pairs of nodes can be designed, so
as to not waste all but one query for every tmix queries. Finally, it’d be interesting to study the question
of estimating other properties of graphs, number of edges, number of triangles, etc. in this framework.
The model choices we made reflect the publicly available access to most extant networks; in particular,
we were very stringent with accounting—every neighbour query counts as unit cost. Many APIs return the
list of neighbours, although in chunks of a fixed size, e.g., 100. It is hard to argue that 100 should be treated
as constant in the context of social networks. Nevertheless, if we wanted a list of all followers of Barack
Obama, this would still result in a very large number of queries. A natural extension to the query model
in this paper is to allow the entire neighbourhood (possibly restricted to the out-neighbourhood in the case
of directed graphs) to be revealed at unit cost. Estimators such as the one involving common neighbours
of Hardiman and Katzir [11] can be implemented efficiently under such a model. Understanding the
query complexity of estimation in these more powerful models is an interesting question.

2

Model and Preliminaries

Graphs. Graphs G=(V,E) considered in this paper may be directed or undirected; typically we assume
|V |=n and |E|=m, though if there is scope for confusion we use |V | or |E| explicitly. For undirected
graphs, for a node v ∈ V , we denote by N(v) its neighbourhood, i.e., N(v) = {w | {v,w} ∈ E}, and its
degree by deg(v) := |N(v)|. In the case of directed graphs, we denote N +(v) := {w | (v,w) ∈ E} its
out-neighbourhood and by deg+(v):=|N +(v)| its out-degree. Similarly, N −(v):={u | (u,v)∈E} denotes
its in-neighbourhood
and deg−(v):=|N −(v)| its in-degree. Furthermore, davg denotes the average degree,
P
i.e, v∈V deg(v)/n. Whenever there is scope for confusion, we use the notations degG(u), NG(v), davg (G),
etc. to emphasise that the terms are with respect to graph G.
Random walks in graphs. A discrete-time lazy random walk (Xt)t≥0 on a graph G=(V,E) is defined by
a Markov chain with state space V and transition matrix P =(p(u,v))u,v∈V defined as follows: For every
4

u∈V , p(u,u)=1/2 (Laziness). In the undirected setting, for every v ∈N(u), p(u,v)=1/(2deg(u)). In the
directed setting, for every v ∈N +(u), p(u,v)=1/(2deg+(u)). The transition probabilities can be expressed
in matrix form as P =(I +D−1A)/2, where A is the adjacency matrix of G, D is the diagonal matrix of
node degrees (only out-degrees if G is directed), and I is the identity. Let pt(u,·) denote the distribution
over nodes of a random walk at time step t with X0 =u. For the most part, we will consider (strongly)
connected graphs. Together with laziness, this ensures that the stationary distribution of the random walk,
denoted by π, is unique and given by πP =π. In the undirected case, the form of the stationary distribution
is particularly simple, π(u)=deg(u)/(2|E|); furthermore, the random walk is reversible, i.e., π(u)p(u,v)=
π(v)p(v,u). As before, πG is used to emphasise that the stationary distribution is respect to graph G.
Mixing time. To measure how far pt(u,·) is from the stationary distribution we consider the totalX
variation
1
distance; for distributions µ,ν over sample space Ω the total variation distance is kµ−νkTV = 2
|µ(x)−
x∈Ω

ν(x)|. The mixing time of the random walk is defined as tmix :=maxu∈V min{t≥1 | pt(u,·)−π TV ≤e−1}.
Although the choice of e−1 is arbitrary, it is known that after tmix log(1/ε) steps, the total variation
distance is at most ε.

2.1

Query Model

In this section, we formally define the query model that allows us to access the graph. We consider four
→
− →
−
→
−
different neighbour query oracles, O, O, O(1) and O(2). We also assume that all oracles have graphs
stored as adjacency lists. In the case of directed graphs, there are two adjacency lists for every vertex,
one for in-neighbours and one for out-neighbours. No assumption is made regarding the order in which
the adjacency lists are stored.
All oracles also make use of labelling functions5 ; for some space L, a labelling function `:V →L used by
an oracle is an injection. We allow ` to be defined dynamically. The labelling function we use throughout
the paper is the consecutive labelling function defined as follows: The label set is L=N. If S denotes all
the vertices labelled by the oracle so far, for a new vertex v ∈
6 S picked by the oracle, the label is assigned
as follows: if S = ∅, `(v) = 1, else `(v) = max{`(u) | u ∈ S}+1. For these neighbour query oracles, any
algorithm can essentially make two types of queries, (i) init, and (ii) (l,i) for undirected graphs or (l,i,etype)
for directed graphs, where etype is either in, out. We assume that oracles use a labelling function `.
(i) init: The oracle initialises a set S :={v},
where v is chosen to be an arbitrary node in the graph. The different oracles respond as defined below.
→
−
• O responds with (`(v),deg(v)) for some v ∈V . O responds with (`(v),deg+(v)) for some v ∈V .
→
−
→
−
• O(1) and O(2) both respond with (`(v),deg+(v),deg−(v)).
(ii) (l,i)
or (l,i,etype): O only responds to query of type (l,i) and the remaining to queries of the type (l,i,etype).
• For query (l,i), if there is v ∈S such that `(v)=l and i≤deg(v), then O returns (`(u),deg(u)), where u
is the ith element in the adjacency list of v. The oracle updates S ←S∪{u}. Otherwise it returns null.
5

We do assume that there is unit cost in sending the label of a node to the algorithm, thus implicitly we may think
of every label having a bit-representation that is logarithmic in the size of the graph. However, the bit-length of the label
reveals minimal information, which we assume that the algorithm has access to anyway.

5

→
−
• For query (l,i,out), if there is v ∈S such that `(v)=l and i≤deg+(v), then O returns (`(u),deg+(u)),
→
−
→
−
while both O(1) and O(2) return (`(u),deg+(u),deg−(u)) where u is the ith element on the outneighbour adjacency list of v. The oracles all update S ←S∪{u}. Otherwise, all oracles return null.
→
−
→
−
• For query (l,i,in), O and O(1) always return null. If there exists v ∈S, such that `(v)=l and
→
−
i≤deg−(v), then O(2) returns (`(u),deg+(u),deg−(u)), where u is the ith element on the adjacency
→
−
list of in-neighbours of v; otherwise, it returns null. In the case of O(2), it updates S ←S∪{u}.
→
−
In words, O captures access to undirected graphs such as social networks like Facebook, O captures
→
−
directed graphs such as the world wide web, where only out-edges are available, O(1) captures directed
→
−
graphs such as fan-networks, where the in-degree but not in-neighbours may be available, and O(2)
captures directed graphs such as Twitter where access is available to both in-edges and out-edges.
It is worth pointing out that a response of null provides no new information to the algorithm. The
algorithm only knows that it hadn’t received l as a label before or that the degree of the node with label l is
strictly smaller than i, things it already knew. This is because the oracle maintains a history of past queries;
if this were not the case the algorithm could generate (random) labels and try to find out whether they
corresponded to nodes in the graph. However, even for oracles that don’t maintain such state explicitly,
by choosing ` to be collision-resistant hash function, essentially the same behaviour can be achieved.
In some of our proofs, we also allow oracles to return side information. These are denoted by a
superscript s, e.g., Os. Access to oracles with (truthful) side information can only help to reduce query
complexity, since an algorithm can choose to ignore any side information it receives. Finally, we say that
an algorithm is sensible if it does not make a query to which it already knows the answer. It is clear that
given any algorithm, there is a sensible algorithm that is at least as good as the original algorithm. The
sensible algorithm merely simulates the original algorithm and whenever the original algorithm made
a query to which the answer was known, the sensible algorithm simulates the oracle response.
Finally, we consider the stationary query oracle, Oπ , which when queried returns (`(v),deg(v)), where
v ∼π; π is the stationary distribution.

3

Undirected graphs

In this section, we focus on the question of estimating the number of nodes in undirected graphs. We show
that the results obtained by Katzir et al. [12] are essentially tight, up to a factor of the mixing time and
polylogarithmic terms in n. This suggests that rapid mixing is a critical condition for being able to estimate
the size of the graph. We begin by discussing very simple examples which show that this is indeed the case.
Some Simple Observations First we construct two simple graphs, one having twice as many nodes
as the other. No algorithm can distinguish between these two graphs with probability greater than 3/4
(say) unless Ω(m) queries to the oracle O are made. The graphs are shown in Figure 1. The first graph
is simply Gn,p with each node being connected to an additional node with degree 1. The second graph
is identical, except that for one randomly chosen node, instead of this additional edge to a degree 1
node, it is connected to a copy of Gn,p. Suppose p>log(n)/n so that the graphs are connected with high
probability and that m=Θ(n2p).
We don’t provide a formal proof here, which can be given along the lines of the proof of Theorem 3.5.
We outline a sketch here. Assuming the oracle O returns some v ∈ V in the part that is Gn,p with an
additional edge coming out of each node, how long will it take before we discover the edge to the copy
6

Kn

Figure 1: Example showing that Ω(m) samples
might be required if no assumption like rapid mixing
is made.

Kn

Figure 2: The sun graph and the bright sun.

of Gn,p, if it exists? Since we made no assumption on the order in which neighbours are stored in an
adjacency list, we have to query at least a constant fraction of neighbours of a given node to discover,
with constant probability, the edge that leads out of the Gn,p. However, most of these will just lead us
to a single vertex. Thus, unless we explore at least a constant fraction of the edges of a constant fraction
of the vertices, we don’t stand a significant chance of finding the edge that leads to the copy of the Gn,p.
Thus, Ω(m) queries to the oracle are required.
Clearly, if we’re in the second case, that is the graph with an additional copy of Gn,p connected to
the earlier one by a single edge, a random walk on this graph does not mix rapidly. What this example
shows is that if one wishes to do asymptotically better than breadth-first search, one needs additional
assumptions on the graph, such as rapid mixing.

3.1

Results of Katzir et al.

In this section, we discuss the result of Katzir et al. [12] regarding estimating the number of nodes in
a graph. Though, they don’t discuss this formally, their method essentially boils down to having access
to the stationary query oracle Oπ .
For the sake of completeness, we outline the estimator of Katzir et al. here. Let
X ={(`(x1),deg(x1)),(`(x2),deg(x2)),...,(`(xr ),deg(xr ))}
Pr
Pr
π . Let Ψ =
be drawn
from
the
stationary
query
oracle
O
)
and
Ψ
=
deg(x
i
1
−1
i=1
i=1 1/deg(xi ); let
P
C = i6=j 1(`(xi)=`(xj )) denote the random variable counting the number of collisions. Then, it is fairly


straightforward to see that E[Ψ1Ψ−1] = r +2n 2r kπk22 and E[C] = 2 2r kπk22. Katzir et al. use the the
following as an estimator for the number of nodes: n
b := Ψ1ΨC−1−r They prove the following result.
Theorem 3.1n (Katzir et
o al. [12]). Let ε > 0 and δ > 0. Suppose that the number of samples is
32
1
r ≥1+ ε2δ max kπk2 ,davg , where davg =2m/n. Then, P[|b
n −n|≥εn]≤δ.
Given a bound T on tmix and access to oracle O, the stationary query oracle Oπ can be approximately
simulated. (We assume that the graph is connected.) We simply perform a random walk on the graph for
T log(1/ρ) steps, if a sample from a distribution at most ρ far from π in total variation distance is desired.
Using the above theorem, we get the following straightforward corollary. The proof of the corollary follows
by simulating s random walks for O(T logs) time steps (queries) ensuring that each random walk has a total
variation distance of s−2 from π. Using the above theorem, we get the following straightforward corollary.
Corollary 3.2. Let ε > 0 and δ > 0. For a connected, undirected graph, G = (V,E) let T be such that
tmix ≤ T . Then there exists an algorithm that given T and access to oracle O, outputs n
b, such that,
7

P[|b
n −n|≥εn]≤δ.
the number of queries made by the algorithm to O is O(T slogs), where

n Furthermore,
o
1
1
s=O ε2δ ·max kπk ,davg .
2

The key question is, are these bounds tight? In Section 3.2, we give much stronger lower bounds,
where we show that for any valid degree sequence d=(d1,...,dn) on n nodes, there exists a sequence d0 on
0
2n nodes, such that any algorithm with access to
 a stationary
 oracle for either sequence d or d , cannot
1
distinguish between the two unless it makes Ω kπk
+davg queries. Here, we discuss simple instances
2
where the bound in Theorem 3.1 is tight; we don’t give formal proofs which are relatively straightforward.
• Let G1 and G2 be d-regular graphs on n and 2n nodes respectively, for d<n. Thus, samples from
the stationary distribution are essentially just uniformly chosen random nodes in the graph. As
the degrees are identical, they reveal no additional information. Thus, the algorithm has to query
√
√
1
until a collision is observed, which requires Ω( n) queries. Clearly for these graphs kπk
=Θ( n).
2

• We define the sun graph as a Kn with an additional edge out of each vertex to a node with degree
1. The bright sun graph is the same as the sun graph, except that there is a path of length 2 coming
out of each vertex, rather than just an edge (see Figure 2). Under the stationary oracle model,
Ω(n) queries are required before any degree 1 or 2 nodes are returned since the total probability
on these nodes is O(1/n). As can be seen for these graphs davg =Θ(n).
The above examples show that there are graphs for which the bound of Katzir et al. is tight. In this
paper, we show a significantly stronger statement—given any degree sequence d, there are graphs for
which the bound is almost tight.

3.2

Lower Bounds in the Stationary Query Model

In this section, we show that for any undirected, connected graph G=(V,E), there exists an undirected,
e such that any algorithm which has access to either the oracle Oπ (G) or Oπ (G),
e
connected graph G,
cannot distinguish between the two with significant probability without making a large number of queries.
Thus, it cannot output an estimate n
b satisfying |b
n −|V ||<|V |/2 with probability 2/3.
Lemma 3.3. Let G = (V,E) be an undirected, connected graph with |V | = n and |E| ≥ n. Then there
e Ve ,E),
e with |Ve |=2n, such that any algorithm given access to either Oπ (G) or Oπ (G)
e
exists a graph G=(
2
with equalprobability,
cannot distinguish between the two with probability greater than 3 , unless it makes


queries. As a consequence, no algorithm can output n
b satisfying |b
n −n∗|<n∗/2 w.p.
e
at least 2/3, where n∗ =n if the chosen graph is G and 2n if it is G.
at least Ω

1
kπG k2

e Ve ,E)
e by taking G=(V,E) and an identical copy, denoted G0 =(V 0,E 0), and
Proof. We construct G=(
connecting them arbitrarily in such a way that the degrees of the nodes remain unchanged. We note that
this can always be done. Since |E|≥n, the graph G is not a tree, and hence there is an edge {i,j}∈E
such that removing it does not disconnect G. Let {i0,j 0} be the corresponding edge in the copy of G,
e
then removing {i,j} and {i0,j 0} and adding the edges {i,j 0} and {i0,j} gives G.
s
e t)s be
For some s ∈ N, let (Xt)t=1 be s independent samples drawn from πG. Similarly, let (X
t=1
s
e s
independent samples from πG
e . We define a coupling between (Xt )t=1 and (Xt )t=1 . Suppose Xt =i, then
e t =i with probability 1 and X
e t =i0 (the copy of i in G0) with probability 1 . This ensures that
we define X
2
2

8

e t is drawn from the distribution π e . Note that the output of the oracle Oπ (G) (respectively Oπ (G))
e
X
G
e
e
is (`(Xt),degG(Xt)) (respectively (`(Xt),degG
e (Xt ))).
We assume the oracle simply uses a consecutive labelling scheme, i.e., when Xt is drawn from π, if there
is no t0 <t, such that Xt0 =Xt, then `(Xt)=max{`(Xt0 ) | t0 <t}+1. Note that this ensures that unless there
e would be identical.
exist t6= t0 and t,t0 ≤s, such that Xt =Xt0 , the outputs of oracles Oπ (G) and Oπ (G)
Finally, define
X
e t0 )
Cs =
1(Xt =
6 X
t0 <t≤s


The expectation of Cs is E[Cs]= 2s kπGk22. Then by Markov’s inequality, for a suitably chosen constant
e
c, if s≤ kπGc k , P[C ≥1]≤1/6. Thus, with probability at least 56 , the outputs of oracles Oπ (G) and Oπ (G)
2
can be coupled perfectly.
Lemma 3.4. Let G = (V,E) be an undirected, connected graph with |V | = n and |E| ≥ n. Then there
e Ve ,E),
e with |Ve |=2n, such that any algorithm given access to either Oπ (G) or Oπ (G)
e
exists a graph G=(
2
with equal probability, cannot distinguish between the two with probability greater than 3 , unless it makes
at least Ω(davg (G)) queries. As a consequence, no algorithm can output n
b satisfying |b
n −n∗|<n∗/2 w.p.
e
at least 2/3, where n∗ =n if the oracle chosen corresponds to G and n∗ =2n if it corresponds to G.
e = (Ve ,E)
e by taking G = (V,E) and a 3-regular expander on n nodes, denoted
Proof. We construct G
0
0
0
G = (V ,E ), and connecting them arbitrarily in such a way that the degrees of the nodes remain
unchanged. (If n is odd, we can use set |V 0| = |V |+1.) We note that this can always be done. Since
|E|≥n, the graph G is not a tree, and hence there is an edge {i,j}∈E such that removing it does not
disconnect G. Let {i0,j 0} be the corresponding edge in the copy of G, then removing {i,j} and {i0,j 0}
e
and adding the edges {i,j 0} and {i0,j} gives G.
s
e t)s a sample drawn
For s∈N, let (Xt)t=1 be s independent samples drawn from πG; similarly (X
t=1
0
s
e s
from πG
e . We define a coupling between (Xt )t=1 and (Xt )t=1 as follows. Let p=πG
e (V ), the probability
that a node sampled according to πG
e is one of the newly created ones. Let Zt = 1 with probability p
e
e t is chosen uniformly at random from V 0,
and 0 otherwise. Then we have Xt =Xt if Zt =0, otherwise X
the newly added nodes. To see that this is a valid coupling, observe that for any u ∼ πG
e , conditioned
0
on u6∈ V , u is distributed according to πG.
e returns (`(Xt),degG(Xt)) (respectively (`(X
e t),deg e (Xt))).
Note that the oracle Oπ (G) (respectively Oπ (G))
G
We assume that the oracles use a consecutive labelling function, i.e., every new node is given the smallest
as yet unused
Pnatural number.
Let C = st=1Zt, then E[C]=ps. Note that p=3|V 0|/(2|E|+3|V |0)≤3|V |/(2|E|)=3/davg (G). Thus,
for a suitably chosen constant c, if s ≤ c · davg (G), by Markov’s inequality P[C ≥1] ≤ 1/6. Note that
e can be coupled perfectly. Hence, no
conditioned on C =0, the outputs of the oracles Oπ (G) and Oπ (G)
e
algorithm can distinguish between G and G using fewer than c·davg (G) queries with probability greater
than or equal to 2/3.
As a consequence of Lemma 3.3 and Lemma 3.4, we get the following theorem.
e Ḡ with 2|V | nodes
Theorem 3.5. Given an undirected, connected graph G=(V,E), there exist graphs G,
π
π e
and a constant p<1, such that any algorithm that
 is given access to
 one of three oracles O (G), O (G) and
Oπ (Ḡ), chosen with equal probability, requires Ω kπG1 k +davg (G) queries to distinguish between them with
2
probability
at
least
p.
As
a
consequence,
any
algorithm
that outputs n
b, such that |b
n −n∗|<n∗/2 requires at


e or Ḡ.
least Ω kπG1 k +davg (G) queries, where n∗ =n if the graph is G and n∗ =2n if the graph is either G
2

9

3.3

Oracle Sampling from the Neighbour Query Model

In this section, we show that with access to the oracle O(G), anyalgorithm that
 predicts the number of
1
nodes in a graph G to within a small constant fraction requires Ω kπGk2 +davg queries. For proving the
lower bounds we use graphs generated according to the configuration model [2]. A vector d=(d1,d2,...,dn)
is said to be graphical if there exists an undirected graph on n nodes such that vertex i∈[n] has degree
di. We briefly describe here how graphs are generated in the configuration model:
1. Create disjoint sets Wi, for i∈{1,...n}, with |Wi|=di. The elements of Wi are called stubs.
2. Create a uniform random maximum matching in the set

n
[

Wi (note that

Pn

i=1 di

must be even

i=1

since d is graphical).
3. For a stub edge {x,y} in the matching, such that x ∈ Wi and y ∈ Wj , the edge {i,j} is added to
the graph.
The above procedure creates a graph where vertex i has degree exactly di. However, the graph may not be
simple, i.e., it may have multiple edges and self-loops. Also, this procedure does not necessarily produce
a uniform distribution over graphs having degree sequence d. The expected number of multi-edges and
self-loops in the graph is for many interesting graphs only a small fraction and in any graph with bounded
degree their expected number is a constant. We use G∼G(d) to denote that a graph G was generated
in the configuration model with degree sequence d.
Recall the definition of a sensible algorithm as one that never makes a query to which it already
knows the answer. A sensible algorithm has the following behaviour: (i) for every u∈V and i≤deg(u)
(deg+(u) and deg−(u), respectively) it makes the query (`(u),i) ((`(u),i,in) and (`(u),i,out), respectively)
at most once, and (ii) it never queries a (`(v),i) if it has not received `(v) as a valid label or if i6∈ [1,deg(v)].
Note that there exists for any algorithm a sensible implementation which needs at most as many queries
as the original algorithm. For technical reasons, in the proof of Lemma 3.6, we use an oracle Os with
side-information as an extension of O: Os returns, upon query, exactly the same information as O, but
can add additional truthful information. In particular, we allow the oracle when queried (`(v),i) to not
only return the corresponding node (`(u),deg(u)), where u is the ith element in the adjacency list of
v, but also the index, say j, in the adjacency list of u which corresponds to v. Clearly, any sensible
algorithm wouldn’t query (`(u),j) after querying (`(v),i).
P
Lemma 3.6. Let ε>0. Let d=(d1,...,dn) be an arbitrary graphical sequence and let D := ni=1di. Let
e be an arbitrary graph with degree sequence d. There exists an implementation of
G ∼ G(d), and let G
s
an oracle O (G) (with side-information) such that if (`(Xt),degG(Xt))Tt=1 is the sequence of responses
to a sensible algorithm, where
n
ε √ o
T :=min min{τ ≥0 | all neighbours of all known nodes are disclosed using τ queries}, · D ,
16
e t),deg e (X
e t))T is the sequence returned by oracle Oπ (G),
e then there exists a coupling so that
and if (`(X
t=1
G
e t),deg e (X
e t)))T are identical with probability at least 1−ε.
the sequences ((`(Xt),degG(Xt)))Tt=1 and ((`(X
t=1
G
Remark 3.7. Graphs G ∼ G are not necessarily connected. Thus, Lemma 3.6 uses stopping time T
where all edges in the connected component involving the starting node, i.e., the node sent in response
10

to the init are uncovered by the algorithm, either through query responses or through side information.
Clearly, at this point there is nothing left of the algorithm to do except return the number of observed
nodes as its estimate, which can be arbitrarily far off.
Proof of Lemma 3.6 . We consider the following implementation of Os(G), which generates the graph
G∼G(d) on the fly as it receives the queries. We assume that Os(G) uses a consecutive labelling function,
i.e., whenever it chooses a new node, it picks the smallest as yet unused natural number as the label.
In response to the init, it picks X1 ∼π, sets `(X1)=1 and returns (`(X1),degG(X1)).
It starts by creating sets Wu ={u1,u2,...,udu } for u=1,...,n. Let Ft be the filtration corresponding
to all the random choices made including the answer to the tth query (counting the init as the first one).
Let (l,i) be the (t+1)th query made by the algorithm, let v ∈V , such that `(v)=l. Since the algorithm is
sensible, it must be that (l,i) is queried for the first time and that the algorithm never learned, through
side-information of the oracle, to which node the stub vi connects; this means Os(G) has not fixed the
choice of partner for vi yet.
The oracle chooses a random unmatched stub, say vi00 and returns (`(v0),degG(v0)) as well as the side
information i0, indicating that v is the (i0)th neighbour of v0.
Let pt denote the distribution over choice of v0 made by Os(G) before responding to the (t+1)th
query. Let δu(t) denote number of edges of u that have been already disclosed
up to the answering of
P
th
the t query. This also includes possible side-information. Note that u δ(u) = 2(t−1), since every
query other than the init reveals information about the two end-points of the disclosed edge. Thus,
pt(u)=(du −δu(t))/(D−2(t−1)). Consider the variation distance between pt and π,
π−pt

=
TV

1 X du du −δu(t)
1 X −2(t−1)du +Dδu(t)
−
=
2
D D−2(t−1) 2
D(D−2t+2)
u∈V

u∈V

1 X Dδu(t)
1 X 2(t−1)du
+
≤
2 u∈v D(D−2t+2) 2
D(D−2t+2)
u∈V

1 2(t−1)
1 2(t−1)
2t−2
≤ ·
+ ·
=
2 D−2t+2 2 D−2t+2 D−2t+2
P
P
In the final step above, we used the fact that udu =D and uδu(t)=2t−2. Note that if the stopping
condition
in the definition of T has not occurred the above calculations are valid. Also, we know that T ≤
√
ε
D,
thus
summing up the variation distance π−pt TV for t∈{1,...,T } and observing that p0 −π TV =
16
0, since the response to the init is chosen from the stationary distribution, we get the desired result.
Theorem 3.8. Let d=(d1,...,dn) be a graphical vector satisfying minidi ≥3. Then there exists a graphical
e e
e there exists c>0, such that
e
d=(
d1,...,e
dn,e
dn+1,...,e
d2n) with minie
di ≥3, such that for G∼G(d) and G∼G(
d),
e
any algorithm with access to one of two oracles O(G) or O(G) chosen
 equal probability,
 cannot distinguish
1
between the two with probability greater than 1−c unless it makes Ω kπGk +davg (G) queries to the oracle.
2

√
√
P
Proof. First we notice that kπGk =O( D) and davg (G)=O( D) if D := ni=1di.
2
e = (d1,...,dn,d1,...,dn) as in the proof of
We first prove the lower bound of Ω(1/kπGk2). We set d
Lemma 3.3. Let G1 and G2 be an arbitrary graphs on n and 2n vertices with degree sequences d and
e respectively. Let E1 (resp. E2) be the event that the coupling of the sequences output by Os(G) (resp.
d
e and Oπ (G1) (reps. Oπ (G2)) holds for the first T queries using Lemma 3.6. Let E 0 and E 0 be
Os(G))
2
√ 1
the events that the stopping condition in the coupling in Lemma 3.6 happens due to ε D/16 queries
being made. Note that because of the condition mini di ≥ 3 (and minie
di ≥ 3) the graph G ∼ G(d) (and
1

11

e is connected with high probability. Thus, as n→∞, P[E 0 ]→1 (the same for P[E 0 ]). Finally,
e
G∼G(
d))
1
2
let E3 be the event that the coupling in Lemma 3.3 holds. By choosing ε in Lemma 3.6 appropriately,
we can bound the probability that at least one of the events E1, E2, E10 , E20 , and E3 does not occur, by
some constant c<1. Thus, we get the require result.
The lower bound of Ω(davg (G)) follows similarly using Lemma 3.4 instead of Lemma 3.3.

4

Directed Graphs

In this section, we consider the query complexity of estimating the number of nodes in directed graphs. We
first observe that estimating n using the approach of Katzir et al. [12] is not possible since the stationary
distribution of a node is in general not proportional to its degree. Another obstacle is that the stationary
distribution of a node can be exponentially small as the graphs in Figures 3 and 4 illustrate. In particular, it
takes an exponentially large sample drawn from the stationary distribution to distinguish between the line
graph of Figure 3 on n nodes and the line graph on 2n nodes, since the probability mass of the additional
→
−
nodes is 2−Ω(n). It is also not very difficult to show that even with access to one of the two oracles O or
→
−
O(1), Ω(n) queries are required to distinguish the line graph on n vertices from the line graph on 2n vertices.
As the example of the line graph reveals, unlike in the undirected case, rapid mixing and low average
degree are not sufficient conditions to design a good estimator of the number of nodes using sublinear
number of queries. The line graph shows that in the directed case, rapid mixing does not imply short
(directed) diameter. One might hope that if one throws small diameter into the mix, in addition to low
average degree and rapid mixing, a better estimator could be designed. In Section 4, we show that this is
→
−
not the case. The problem of estimation remains stubbornly hard, and Ω(n) queries to the oracle O, and
2Ω(n) queries to the stationary query oracle are required to achieve a good estimate of the number of nodes.
These observations suggest that exploring the graph, e.g., through breadth-first search, is much
faster than sampling from the stationary distribution. The question of interest is whether there is a
property, satisfied by graphs of interest, which yields a query complexity better than Ω(m). We answer
this positively in Section 4.1, where we introduce a parameter that generalises the conductance φε and
give almost tight bounds on the number of queries required to estimate n up to an ε relative error. Our
Algorithm EdgeSampling takes this parameter as an input and terminates after O(n/φε) queries which
can be much smaller than the sample complexity of breadth-first search.
Before delving into these results, it is worth pointing out that results in Section 3 can be used if
→
−
access to O(2) is provided. In this case, we can simply treat the graph as being undirected. However, it
is still interesting to understand whether the distinction between in-neighbours and out-neighbours allows
one to design better estimators. At present, we are unaware of any graphs where this might be the case.

Figure 3: The Line graph on 6 nodes.

12

v4

v3

v2

v1

Figure 4: The graph Comet(20,4).

v8

v7

v6

v4

v5

v3

v2

v1

Figure 5: The graph DoubleComet(40,8). DoubleComet(2n,2k) consists of two copies of Comet(n,k)
connected in the following way. First we remove all directed neighbours of vk+1 as well as the edge
(vk ,v1). Then we add (vk ,vk+1), (vk+1,vk+2) as well as (vk+1,v1).

The Comet Graph The Comet graph, Comet(n,k) is constructed as follows. Assume that k divides
n. There is a directed cycle on the vertices v1,v2,...,vk , with edges (vi,vi+1) for 1≤i<k and (vk ,v1). We
denote these k vertices as centres. For every `∈[k], there is a directed star S` ={(v`,v`,j ):j ∈[n/k−1]}
with centre in v` of degree n/k − 1. For each leaf v`,j in star S` with ` ∈ [k],j ∈ [n/k − 1], there is a
G
directed edge to the first star centre v1, that is, {(v`,j ,v1) : ` ∈ [1,k],j ∈ [n/k−1]}. We write v`G and v`,j
to emphasise that the nodes belong to graph G.
In the following lemma we obtain bounds on stationary distribution of the nodes, which will allow
us to obtain a bound on the query complexity w.r.t. Oπ (see Theorem 4.2).
Lemma 4.1. Let n be a multiple of k. Let π be the stationary distribution of the nodes in Comet(n,k).
k k−1
e
Then, for G=Comet(n,k) and G=Comet(2n,2k)
it holds that πG −πG
).
e TV =O(( n )
P
Proof. Note that for u ∈ V we have π(v) = u∈V p(u,v)π(u). Let ` ∈ [k], u ∈ N +(v`)\{v1} and d = n/k.
We have that
π(u)=π(v`)/2d+π(u)/2.

(1)

This implies that π(v`)=dπ(u) for every u∈N +(v`). In particular, for u=v`+1 (consider vk+1 =v1) it
follows that
π(v`+1)=π(v`)/d.
(2)
Therefore, π(v`)=π(v1)/d`−1. Furthermore,
π(v`,j )=π(v`+1)=π(v1)/d`

13

(3)

for every `∈[k], j ∈[d−1]. Summing up everything,


k
d−1
X
X
π(v`)+ π(v`,j )
1 =
`=1

j=1

k
X

k X
d−1
X

π(v1)
π(v1)
+
`−1
d
d`
`=1 j=1
`=1


1−1/dk
1/d−1/dk+1
,
= π(v1)
+(d−1)
1−1/d
1−1/d
!
2d−1− 2d+1
dk
= π(v1)
.
d−1
=

Rearranging the terms yields
π(v1)=

d−1
.
2d−1− 2d+1
dk

We proceed by establishing a bound on πG −πG
e

TV

.

k

πG −πG
e

(4)

k d−1

1 XX
1X
e
e
G
G
G
G
)
+
)−π(v
)
π(v
)−π(v`,j
=
π(v`,j
`
`
TV
2
2
`=1 j=1

`=1

1
+
2
≤

k
X

2k
X

e
0−π(v`G)

2k d−1
1 XX
e
G
+
)
0−π(v`,j
2
`=k+1 j=1

`=k+1

2k
X

π(v`G)−π(v`G) +
e

π(v`G)
e

`=k+1

`=1

≤ π(v1G)−π(v1G)
e

k
X
`=1

≤2 π(v1G)−π(v1G) +
e

1

+
d`−1
1
dk

1− d1

2k
X
`=k+1

1
d`−1

.

By triangle inequality,
π(v1G)−π(v1G) ≤ π(v1G)−
e

d−1
d−1
d−1
2d+1
d−1
e
+ π(v1G)−
≤2
−
≤4 k .
2d+1
2d−1
2d−1
2d−1
d
2d−1− dk

Putting everything together yields πG −πG
e

=O
TV




k k−1
n


.

To establish the mixing time of Comet(n,k), we will make use of the result of Levin, Peres and Wilmer
[14] which relates the mixing time of a Markov chain to the probability that two copies of the chain meet.

14

Theorem 4.2. Let n be a multiple of k. Then Comet(n,k) has mixing time tmix =O(1) and diameter
→
−
k. Furthermore, any algorithm requires at least Ω(( nk )k−1) queries to Oπ and Ω(n) queries to O to
e
distinguish between G=Comet(n,k) and G=Comet(2n,2k).
Proof. Observe that the diameter of the graph is indeed k. Let (Xt)t≥0, (Yt)t≥0 be random walks on
Comet(n,k) with X0 = x and Y0 = y, where x,y ∈ V . Whenever Xs = Ys, then we can couple Xt = Yt
for t ≥ s. Let T = min{t ≥ 0 | Xt = Yt}. Starting from any vertex u ∈ V , with constant probability at
least p>0, the random walk is at v1 after 2 steps, i.e., P[X2 =v1 | X0 =u]≥p for u∈V . In particular,
using independence, P[X2 =Y2 | X0 =u,Y0 =v] ≥ P[X2 =v1 | X0 =u]·P[Y2 =v1 | Y0 =v] ≥ p2 for u,v ∈ V .
Iterating this and using independence shows
P[T >2t]≤P[X2t =
6 Y2t | X0 =u,Y0 =v]≤(1−p2)t ≤e−1.
For some large enough constant t. From Theorem A.1 ([14]) and using the definition of the mixing time
we derive tmix =O(1).
Wenow consider the query complexity
Oπ . By Lemma 4.1 we have that
 k−1
  w.r.t.

k−1
k
πG −πG
samples can be coupled with constant
. This implies that the first Ω nk
e TV =O
n
  
e on 2n nodes one requires Ω n k−1
probability. Thus, in order to distinguish between G on n nodes and G
k
→
−
→
−
samples. We now consider the query complexity w.r.t. O. In response to the init query, both oracles O(G)
→
− e
and O(G)
pick v1, set `(v1)=1 and return (`(v1),deg+(v1)). Any algorithm has to reach at least node vk
−
→
− e
e We assume that the oracles →
in order to distinguish between G and G.
O(G) and O(G)
use independent
random adjacency lists at all nodes. But we couple them to be the same for the nodes that are common
to both graphs. Clearly, unless Ω(n/k) queries are made to the out-neighbour lists of each of v1,v2,...,vk−1,
the node vk cannot be discovered, which in turn means that it is impossible to distinguish between the
→
−
→
− e
oracles O(G) and O(G).
Thus, Ω(k·n/k)=Ω(n) queries are required. This concludes the proof.
→
−
→
−
Note that the above results only apply to the oracles O and Oπ , but not to O(1), since the in-degrees
make it easy to distinguish between the two graphs. However, it is straightforward to extend the graph
such that the sample complexity remains Ω(n) even if the in-degrees are known; thus even with access
→
−
to O(1), Ω(n) queries are required.
Observation 4.3. Let n be a multiple of k. Then DoubleComet(2n,2k) (Defined in Figure 5) has mixing
→
−
time tmix = O(1) and diameter 2k. Furthermore, any algorithm requires at least Ω(n) queries to O(1)
e
to distinguish between G=Comet(n,k) and G=DoubleComet(2n,2k)
on 2n nodes.
The proof is along the same lines as the proof of Theorem 4.2. Observe that the in-degrees of nodes
v1,...,vk give no extra information about the size of the graph.

4.1

Assuming a Bound on the Connectivity

In this section we introduce the parameter general conductance. We first recall some graph notation in
the directed setting. Given a non-empty proper subset of vertices S ⊂V , let deg+(S)=|{(u,v)∈E :u∈S}|
be the out-degree of S. The cut of S, ∂S, is the set of edges crossing between S and V \ S, that is,
∂S = {(u,v) ∈ E : u ∈ S,v ∈
/ S}. The general conductance of S, φ(S), is the ratio between the cut of S,
and the out-degree of S. That is, φ(S) = |∂S|/deg+(S). Given ε > 0, the graph ε-general conductance,
φε, is the minimum of φ(S) over every non-empty proper subset of V of size at most (1−ε)|V |, i.e.,

15

φε(G)=minS⊆V :1≤|S|≤(1−ε)|V |φ(S). Note that the parameter φε decreases monotonically as ε decreases.
In the undirected setting for ε=1/2 this is just what is commonly known as the conductance.6
In the following we describe the algorithm that estimates the graph size.
Upper bound in terms of the general conductance. We consider algorithm EdgeSampling for
estimating the number of nodes. The algorithm takes as input the parameter φ, a lower bound on
the general conductance φε. The query complexity is O(n/φε) and the output estimate n
b satisfies
(1−ε)n≤ n
b ≤n with arbitrary confidence controlled by an input parameter `. Observe that O(n/φε) can
be much smaller than the run time of breadth-first search Ω(m).
Algorithm overview. The algorithm works as follows. At each time step the algorithm maintains a counter
Y . If at some point the counter exceeds the threshold `, then the algorithm terminates. The algorithm
divides the queries into blocks of length at most 2/φ corresponding to the execution of the for loop.
In each block, at every step the algorithm samples one outgoing edge uniformly at random from those
available and not queried before. If at any step a new node is disclosed, then this finishes the block
(break of the for loop) and the counter Y is decreased by 1. If the the block finishes without finding a
new node, then the counter is increased by 1. Once the counter reaches `, which will happen eventually,
then the algorithm outputs the number of nodes it discovered. Even though our goal is to minimise the
query complexity, it is worth noticing that the time and space complexity can be kept low by choice
of suitable data structures. Although the oracle returns labels of nodes, we use nodes and their labels
interchangeably in the algorithm and the analysis of Theorem 4.4.
→
−
Theorem 4.4. Algorithm EdgeSampling( O,`,φ) on graph G has a query complexity of min{2(2n+`)/φ,m}
and outputs an estimate n
b ≤n. Furthermore, if G has general conductance φε(G) of at least φ, then the
algorithm satisfies n
b ≥(1−ε)n w.p. at least 1−2−`.
Proof. First observe, that per iteration of the for loop at most one new node is discovered. Let Yt be the
variables defined in the algorithm and define Xt =|St|−|St−1|. In particular Xt ∈{0,1}. Note that the
number
of times the counter Y decreases, i.e., Yt <Yt−1, during the first τ iterations of the for loop is
P
since the counter increases when a new node is discovered. Therefore, the number of queries
X
≤n,
i
i≤τ
is bounded by 2·(2n+`)/φ. Moreover, every edge is only queried at most once yielding the claimed
bound on the query complexity. We now prove that the output n
b :=|St| satisfies n
b ≥(1−ε)n under the
conditions in the statement.
In the remainder we assume φε(G)≥φ since otherwise the statement is trivially true. Let
(
)
t
X
T =min t≥0
Xi ≥n(1−ε) or Yt =` .
i=0

Note that every iteration j ≤T of the for loop satisfies that the probability of finding a new node
is at least |∂Sj |/deg+(Sj ) ≥ φε(G) ≥ φ. Hence, we have that P[Xj =0] ≤ (1−φ)2/φ < 1/3. Observe that
Xt =1 implies Yt =Yt−1 −1 and Xt =0 implies Yt =Yt−1 +1. Consider the Markov chain (Zt)t≥0 defined
in Proposition A.2 with s=n,b=n+` and p=1/3. We couple Yt and Zt for t≤T such that Yt +n≤Zt,
6

The definition of conductance in the directed setting is more involved and more importantly doesn’t seem be directly
relevant to the question of estimating the number of nodes. It suffers from similar problems as the skewed stationary
distributions. Graphs having poor connectivity to a large fraction of the nodes may still have very good conductance if
the total mass of the poorly connected nodes under the stationary distribution is very small.

16

→
−
Algorithm 4.1 EdgeSampling( O,`,φ)
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:

Y0 =0 (fail surplus counter)
→
−
v =(node) O.init (query oracle to get the initial node)
S0 ={v}
E0 ={(v,i) | i≤deg+(v)} (set of undisclosed edges)
t=1
while Yt ≤` do
for τ =1 to 2/φ do
choose (u,i) uniformly at random from Et,τ−1.
→
−
v =(node) O.(u,i,out)
if v ∈
6 St−1 then
St =St−1 ∪{v}
E(t−1)·2/φ+τ ←(E(t−1)·2/φ+τ−1 ∪{(v,i) | i≤deg+(v)})\{(u,i)}
break
else
Et·2/φ ←Et·2/φ−1 \{(u,i)}
if |St|=|St−1|+1 then
Yt ←Yt −1
else
Yt ←Yt +1
St ←St−1
t←t+1
Output |St|.

since P[Yt =Yt−1 +1]=P[Xt =0]≤1/3=p=P[Zt =Zt−1 +1]. Let
n
o
T 0 =min t≥0 Zt ∈{0,n+`} .
From Proposition A.2 we get that

P[ZT 0 =n+`]= 

2/3
1/3

n

−1
≤2−`.
n+`
2/3
−1
1/3

P
Due to our coupling we have Yt +n ≤ Zt and observe that Zt = 0 implies that ti Xi ≥ n and therefore
we have T ≤T 0. Hence, ZT 0 =0 implies ZT <n+` which in turn implies YT <`. Thus,
" T
#
X
P[|ST |≥n(1−ε)] = P
Xi ≥n(1−ε)
i=0

= P[YT <`]
≥ P[ZT <n+`]
≥ P[ZT 0 <n+`]
= 1−P[ZT 0 =n+`]
≥ 1−2−`,
17

which concludes the proof.
Observe that the error made by Algorithm EdgeSampling is one-sided — the estimate never exceeds
n. Allowing a two-sided error and given knowledge of ε, one can instead output an estimate, which has
a smaller additive error. This is summarised in the following observation.
→
−
Observation 4.5. Consider a modification of Algorithm EdgeSampling( O,`,φ) on graph G which takes
ε
the additional parameter ε and outputs n
b∗ :=|St|(1+ 2−ε
) instead of |St|. If G has general conductance
ε
∗
∗
φε(G) of at least φ, then n
b satisfies |n−b
n |≤ 2−ε n w.p. at least 1−2−`.
Proof. By Theorem 4.4 we have n≥|St|≥(1−ε)n, where t is the the index of the last execution of the
while loop. We have that


ε
|n−b
n∗| = n−|St| 1+
2−ε





ε
ε
, n−n(1−ε) 1+
≤ max n−n 1+
2−ε
2−ε
ε
=
n,
2−ε
which finishes the proof.
Lower bound in terms of the general conductance. In the following we show that the bound of
Observation 4.5 is almost tight. Recall that, given φε, the modified version of Algorithm EdgeSampling in
ε
Observation 4.5 returns an estimate with and additive error of at most 2−ε
n using O(n/φε) queries. In what
follows we show that any algorithm, given the values φε and ε, cannot output an estimate with an error
ε−δ
smaller than 2−ε−δ
n unless it makes Ω(n/φε) queries, for any δ <ε/2. We prove the following lemma for
undirected graphs using O, but it should be clear that the same the same result holds for directed graphs, by
→
−
→
−
→
−
making the graph directed, with symmetric edges, and using O(2) (and hence also for oracles O and O(1)).

Figure 6: The graphs of Theorem 4.6. G contains the black nodes and the black and red (dashed)
edges which form a d1/φe-regular expander on cliques of size d1/φe. G0 is obtained by removing the
red (dashed) edge and adding the blue (dotted) graph. At least one blue edge needs to be sampled,
which takes Ω(n/φ) time, in order to estimate n accurately.
Theorem 4.6. Let n ∈ N, φ ∈ [1/n,1] and ε ∈ (0,1/2]. There exists an undirected graph with general
conductance φε = Θ(φ) such that any algorithm with access to O requires Ω(n/φε) queries to output n
b
ε−δ
such that |n−b
n|≤ 2−ε−δ
n w.p. at least 2/3 for any δ <ε/2.
18

Proof. Let d=d1/φe. For simplicity we assume that d divides n. Let G1 =(V1,E1) be a d-regular expander
on n∗ = n(1−ε+δ/2)/d nodes. We construct G = (V,E) (see Figure 6 for an illustration) by replacing
every node r by a clique K of size d such that every node of the clique has exactly one of the edges
incident to r. Let n1 :=|V |=n(1−ε+δ/2). Let G2 be a 3-regular expander on n−n1 nodes. Choose an
edge (u,v) uniformly at random among all edges where both nodes u and v belong to the same clique. We
construct G0 by removing (u,v), and by adding the edge (u,w),(v,w), where w is an arbitrary node of G2.
The proof idea is to couple the oracle decisions such that w.p. 2/3 no algorithm can distinguish between
ε−δ
G and G0. Incidentally, our construction ensures that there is no estimate n
b satisfying |b
n −n1|≤ 2−ε−δ
n1
ε−δ
and |b
n − n| ≤ 2−ε−δ n simultaneously. Suppose for the sake of contradiction this was possible, then
ε−δ
ε−δ
n1 and n− n
n
b −n(1−ε+δ/2) ≤ 2−ε−δ
b ≤ 2−ε−δ
. Adding up both equations yields n−n(1−ε+δ/2) ≤
ε−δ
ε−δ
2−ε−δ (n1 +n). This implies ε−δ/2≤ 2−ε−δ (2−ε+δ/2), which can be shown to a contradiction for ε≤1/2.
ε−δ
Thus, any algorithm approximating n up to an error of 2−ε−δ
needs to distinguish between G and G0.
We assume that the oracles O(G) and O(G0) use a consecutive labelling function, i.e., whenever it
chooses a new node, it picks the smallest as yet unused natural number as the label. In response to
the init query, both oracles pick v1 ∈V1 \{u,v}, set `(v1)=1 and return (`(v1),degG(v1)). As long as the
algorithm doesn’t disclose the edge (u,w) or (v,w) in G0 and (u,v) in G, we can couple the nodes returned
by the oracle and thus the two graphs are indistinguishable. Hence, similarly as before, we couple with
constant probability for the first cn/φ samples returned by the oracle for constant c>0 small enough.
It remains to show that G0 has general conductance φε =Θ(φ).
Consider an arbitrary clique K in the construction. Clearly, φε ≤ φ(V (K)) = O(d/d2) = O(φ). To
derive a lower bound on φε consider any set S such that φ=φ(S). Suppose that S contains only entire
cliques, i.e., if u∈S, then also v ∈S for u,v belonging to the same clique. Then, the general conductance
of S is φ(S)=Θ(φG1 /d)=Θ(φ), where 1/φG1 =Θ(1) is the general conductance of the G1.
We claim that there exists a set of cliques, K, containing a constant fraction of the cliques and no node of
S is in any clique of K. If this were not the case, then S either violates |S|≤n(1−ε) or S violates φ=φ(S).
Now suppose that S does not contain only entire cliques. Observe that for any clique K which
is not entirely included in S, we can include the remaining nodes which only decreases the general
conductance. The new resulting set S 0 might be larger than n(1−ε). However, observe that φε ≥φε−ε0
for any sufficiently small δ >ε0 >0. Note that S 0 does not contain any nodes of cliques in K. Hence, the
resulting general conductance fulfils φ(S)≥φ(S 0)≥Ω(φG1 /d)=Ω(φ). This completes the proof.

References
[1] Michael A. Bender and Data Ron. Testing properties of directed graphs: Acyclicity and connectivity.
Random Structures and Algorithms, 20(2):184–205, 2002.
[2] Béla Bollobás. A probabilistic proof of an asymptotic formula for the number of labelled regular
graphs. European Journal of Combinatorics, 1(4):311 – 316, 1980.
[3] Colin Cooper and Alan Frieze. Crawling on web graphs. In Proceedings of the thiry-fourth annual
ACM symposium on Theory of computing, pages 419–427. ACM, 2002.
[4] Colin Cooper, Tomasz Radzik, and Yiannis Siantos. Estimating network parameters using random
walks. In Computational Aspects of Social Networks, 4th International Conference on, pages 33–40,
2012.

19

[5] Artur Czumaj, Pan Peng, and Christian Sohler. Relating two property testing models for bounded
degree directed graphs. In Proceedings of the ACM Symposium on the Theory of Computing
(STOC), 2016.
[6] Anirban Dasgupta, Ravi Kumar, and Tamás Sarlós. On estimating the average degree. In
Proceedings of the 23rd international conference on World Wide Web, pages 795–806. ACM, 2014.
[7] William Feller. An Introduction to Probability Theory and Its Applications, volume 1. Wiley, 1968.
[8] Mark Finkelstein, Howard G Tucker, and Jerry Alan Veeh. Confidence intervals for the number
of unseen types. Statistics & Probability Letters, 37(4):423–430, 1998.
[9] Oded Goldreich. Introduction to testing graph properties. Survey article available at
http://www.wisdom.weizmann.ac.il/˜oded/COL/tgp-intro.pdf, 2010.
[10] I. J. Good. The population frequencies of species and the estimation of population parameters.
Biometrika, 40(3/4):237–264, 1953.
[11] Liran Katzir and Stephen J. Hardiman. Estimating clustering coefficients and size of social networks
via random walk. ACM Transactions on the Web, 9(4):19:1–19:20, 2015.
[12] Liran Katzir, Edo Liberty, Oren Somekh, and Ioana A. Cosma. Estimating sizes of social networks
via biased sampling. Internet Mathematics, 10(3-4):335–359, 2014.
[13] Donald E. Knuth. Estimating the efficiency of backtrack programs. Mathematics of computation,
29(129):122–136, 1975.
[14] David Levin, Yuval Peres, and Elizabeth Wilmer. Markov chains and mixing times. American
Mathematical Society, 2006.
[15] Alberto Marchetti-Spaccamela. On the estimate of the size of a directed graph. In International
Workshop on Graph-Theoretic Concepts in Computer Science, pages 317–326. Springer, 1988.
[16] Milena Mihail, Amin Saberi, and Prasad Tetali. Random walks with lookahead on power law
random graphs. Internet Mathematics, 3(2):147–152, 2006.
[17] Cameron Musco, Hsin-Hao Su, and Nancy A. Lynch. Ant-inspired density estimation via random
walks: Extended abstract. In Proceedings of the 2016 ACM Symposium on Principles of Distributed
Computing, PODC 2016, Chicago, IL, USA, July 25-28, 2016, pages 469–478, 2016.
[18] Gregory Valiant and Paul Valiant. Estimating the unseen: an n/log(n)-sample estimator for entropy
and support size, shown optimal via new clts. In Proceedings of the forty-third annual ACM
symposium on Theory of computing, pages 685–694. ACM, 2011.
[19] Gregory Valiant and Paul Valiant. Estimating the unseen: improved estimators for entropy and
other properties. In Advances in Neural Information Processing Systems, pages 2157–2165, 2013.

20

A

Auxiliary Claims

Theorem A.1 ([14]). Consider two irreducible Markov chains (Xt)t≥0, (Yt)t≥0 with transition matrix
P , X0 =x, and Y0 =y. Let {(Xt,Yt)} be a coupling satisfying that if Xs =Ys, then Xt =Yt for t≥s. Let
T =min{t≥0 | Xt =Yt}. Then pt(x,·)−pt(y,·) TV ≤P[T >t].
Proposition A.2. [7, Chapter XIV.2]] Let p ∈ (0,1/2) and b,s ∈ N. Consider a discrete time Markov
chain (Zt)t≥0 with state space Ω=[0,b] where
• Z0 =s∈[0,b]
• P[Zt =i | Zt−1 =i−1]=p for i∈[1,b−1],t≥1
• P[Zt =i | Zt−1 =i+1]=1−p for i∈[1,b−1],t≥1
• P[Zt =i | Zt−1 =i]=1 for i∈{0,b},t≥1
Let T =min{t≥0 | Zt ∈{0,b}}. Then

P[ZT =b]= 

21

1−p
p
1−p
p

s
b

−1
.
−1

