  We consider the problem of providing nonparametric confidence guarantees for
undirected graphs under weak assumptions. In particular, we do not assume
sparsity, incoherence or Normality. We allow the dimension $D$ to increase with
the sample size $n$. First, we prove lower bounds that show that if we want
accurate inferences with low assumptions then there are limitations on the
dimension as a function of sample size. When the dimension increases slowly
with sample size, we show that methods based on Normal approximations and on
the bootstrap lead to valid inferences and we provide Berry-Esseen bounds on
the accuracy of the Normal approximation. When the dimension is large relative
to sample size, accurate inferences for graphs under low assumptions are not
possible. Instead we propose to estimate something less demanding than the
entire partial correlation graph. In particular, we consider: cluster graphs,
restricted partial correlation graphs and correlation graphs.
