  In high-dimensional graph learning problems, some topological properties of
the graph, such as bounded node degree or tree structure, are typically assumed
to hold so that the sample complexity of recovering the graph structure can be
reduced. With bounded degree or separability assumptions, quantified by a
measure $k$, a $p$-dimensional Gaussian graphical model (GGM) can be learnt
with sample complexity $\Omega (k \: \text{log} \: p)$. Our work in this paper
aims to do away with these assumptions by introducing an algorithm that can
identify whether a GGM indeed has these topological properties without any
initial topological assumptions. We show that we can check whether a GGM has
node degree bounded by $k$ with sample complexity $\Omega (k \: \text{log} \:
p)$. More generally, we introduce the notion of a strongly K-separable GGM, and
show that our algorithm can decide whether a GGM is strongly $k$-separable or
not, with sample complexity $\Omega (k \: \text{log} \: p)$. We introduce the
notion of a generalized feedback vertex set (FVS), an extension of the typical
FVS, and show that we can use this identification technique to learn GGMs with
generalized FVSs.
