  We develop a general framework for conducting inference on the mean of
dependent random variables given constraints on their dependency graph. We
establish the consistency of an oracle variance estimator of the mean when the
dependency graph is known, along with an associated central limit theorem. We
derive an integer linear program for finding an upper bound for the estimated
variance when the graph is unknown, but topological and degree-based
constraints are available. We develop alternative bounds, including a
closed-form bound, under an additional homoskedasticity assumption. We
establish a basis for Wald-type confidence intervals for the mean that are
guaranteed to have asymptotically conservative coverage. We apply the approach
to inference from a social network link-tracing study and provide statistical
software implementing the approach.
