A key
result in [1]}
links the sparsity of the KR
rearrangement \(S\)  to the sparsity of \(\mathcal {G}\) .
For a given \(\mathcal {G}\) , define the
sequence of marginal graphs \(\mathcal {G}^n,\ldots ,\mathcal {G}^1\)  using a simple
recursion: (1) \(\mathcal {G}^n\mathcal {G}\) , and (2) \(\mathcal {G}^{k-1}\)  is
obtained from \(\mathcal {G}^k\)  by removing node \(k\)  and by
turning its neighborhood \( {\rm Nb} (k,\mathcal {G}^k)\)  into
a fully connected subset,For any graph \(\mathcal {G}\) , we denote by \( {\rm Nb} (k,\mathcal {G})\)  the
neighborhood of a node \(k\)  in \(\mathcal {G}\) . i.e., a clique.
By [1]}, each component \(S^k\)  of the rearrangement
can only depend on variables in \( {\rm Nb} (k,\mathcal {G}^k)\) , for all
\(k=1,\ldots ,n\) .
See Figure REF  for an illustration (adapted from [1]}).
Hence, if we know that \(\pi \)  is Markov with respect
to a sparse graph, then we can translate this information into sparsity of the estimator
\(\widehat{S}\) ,
possibly increasing the sparsity pattern
in
(REF ).
