Testing properties of trees in graphical models with covariance queries

Technical Summary: Testing Properties of Trees in Graphical Models with Covariance Queries

1. Problem Statement

The paper addresses the problem of testing global structural properties of high-dimensional graphical models where the underlying graph is a tree. In standard settings, learning the full graph structure from data requires computing the sample covariance matrix, which incurs a computational cost of $O(n^2)$ for $n$ variables. In ultra-high-dimensional regimes, this cost is prohibitive, and even storing the covariance matrix is infeasible.

To address this, the authors adopt the covariance query model introduced by Lugosi et al. [11]. In this model, a statistician can adaptively query specific entries of the population covariance matrix $\Sigma$. For Gaussian graphical models (and related models like binary Markov random fields and linear structural equation models), the inverse covariance matrix $\Sigma^{-1}$ encodes the graph structure: zero entries correspond to conditional independence.

The paper focuses specifically on tree-structured models. A key property of these models is that the correlation between any two nodes is the product of edge-level correlations along the unique path connecting them. By taking the negative logarithm of squared correlations, this multiplicative structure transforms into an additive tree metric $d(u,v)$. Consequently, the problem is abstracted: instead of working directly with distributions, the authors work with an unknown tree $T$ equipped with an unknown tree metric $d$, accessible only via an oracle that returns exact distances $d(u,v)$ for queried pairs.

The primary goal is not to reconstruct the entire tree (which may still be costly), but to test specific global structural properties (e.g., diameter, maximum degree, number of leaves, typical distance) with a sub-quadratic number of queries.

2. Methodology

The proposed testing procedures follow a unified paradigm based on random sampling:

1. Sampling: A small subset of vertices $X = \{X_1, \dots, X_N\}$ is sampled uniformly at random from the $n$ vertices of the tree.
2. Querying: The oracle is queried for distances between sampled vertices and all other vertices (or pairs within the sample), depending on the specific property.
3. Subtree Recovery: For properties involving local structure (degree, leaves), the authors utilize a procedure (Lemma 4.1) to recover the minimal subtree $T_X$ spanned by the sampled nodes $X$. This involves identifying vertices $w$ such that $d(x, x') = d(x, w) + d(w, x')$ for some $x, x' \in X$. This step is crucial because it preserves intermediate vertices and degree information, unlike standard phylogenetic reconstruction which often suppresses degree-2 nodes.
4. Statistical Estimation: Global properties are inferred from statistics computed on the sampled data or the recovered subtree $T_X$. The authors employ concentration inequalities (Bernstein's inequality, Hoeffding's inequality for U-statistics) to bound the error probabilities.

The paper distinguishes between two regimes for testing the typical distance:

• U-statistic approach: Computing exact graph distances between sampled pairs to estimate the average path length.
• Path-intersection approach: Estimating path lengths by counting how many sampled vertices lie on the path between two endpoints, avoiding the need to query all pairwise distances.

3. Key Contributions and Results

The paper provides randomized testing algorithms for four fundamental properties, establishing explicit query complexity bounds that depend on the target threshold and tolerance parameters ($\delta, \epsilon$).

A. Testing the Diameter ($H_{diam}: \text{diam}(T) \ge D$)

• Method: The test relies on the fact that long paths intersect many randomly sampled nodes. The statistic counts the maximum number of sampled nodes lying on a path between any two sampled nodes.
• Result: The procedure accepts if the normalized count exceeds a threshold.
• Complexity: $\Theta\left( \left(\frac{n}{D\delta^2} \log \frac{n^2}{\epsilon}\right)^2 \right)$.
• Implication: If $D$ scales linearly with $n$, the complexity is polylogarithmic in $n$, significantly sub-quadratic.

B. Testing the Maximum Degree ($H_{deg}: \text{maxdeg}(T) \ge \Delta$)

• Method: High-degree vertices are rare and hard to detect via uniform sampling alone. The method reconstructs the subtree $T_X$ spanned by the sample. The maximum degree in $T_X$ serves as a proxy for the global maximum degree.
• Result: The test accepts if the maximum degree in the reconstructed subtree, normalized by sample size, exceeds a threshold.
• Complexity: $\Theta\left( \frac{n^2}{\Delta \delta^2} \log \frac{n}{\epsilon} \right)$.
• Comparison: This outperforms reconstruction-based testing (which requires $O(n\Delta \log n)$ queries) when $\Delta \ge \sqrt{n}$. For all $\Delta$, the degree can be tested with $O(n^{3/2} \log n)$ queries.

C. Testing the Number of Leaves ($H_{leaf}: |L(T)| \ge \Lambda$)

• Method: Similar to the degree test, the algorithm reconstructs $T_X$. Leaves of $T_X$ are candidates for leaves of $T$. A refinement step verifies if a candidate leaf in $T_X$ is truly a leaf in $T$ by checking if any un-sampled node is closer to it than to any other node in $T_X$.
• Complexity: $\Theta\left( \frac{n^2}{\Lambda \delta^2} \log \frac{1}{\epsilon} \right)$.
• Implication: If the tree has a linear number of leaves ($\Lambda \propto n$), the query complexity becomes linear in $n$.

D. Testing the Typical Distance ($H_{typ}: \ell_{typ}(T) \ge \ell$)

• Method: Two complementary estimators are used. One uses exact distances (U-statistic), and the other uses path intersections. The choice depends on the threshold $\ell$ and the diameter.
• Complexity: The bound is complex, involving terms like $\left(\frac{n \cdot \text{diam}(T)}{\delta \ell}\right)^2$ and a term for estimating the diameter itself.
• Implication: Sub-quadratic complexity is achieved when $\text{diam}(T)/\ell = o(\sqrt{n})$ or $\text{diam}(T)/\ell^2 = o(1)$.

E. From Testing to Estimation
The paper demonstrates that these testing procedures can be converted into estimation algorithms (Corollaries 2.6–2.9) by iteratively testing nested hypotheses. This allows for the construction of confidence intervals for the diameter, maximum degree, number of leaves, and typical distance with the same query complexity order.

4. Significance and Claims

The paper claims that while exact reconstruction of a tree in high dimensions may be costly or impossible with limited queries, global structural properties can be tested efficiently.

• Efficiency: The primary contribution is the demonstration that sub-quadratic query complexity is sufficient for testing these properties, whereas full reconstruction often requires $O(n^2)$ or higher complexity depending on the tree's degree.
• Applicability: The results apply to Gaussian graphical models, binary Markov random fields, and linear structural equation models on trees, leveraging the path-based representation of dependencies.
• Theoretical Boundaries: The work clarifies which aspects of tree structure can be inferred from a small number of distance queries and which necessarily require full reconstruction. It establishes that questions like "Does the tree contain large hubs?" or "Does the tree contain a long path?" can be answered effectively with far fewer queries than required for a full model recovery.

The authors note that their results concern query complexity in an exact oracle setting (population level). They acknowledge that extending these results to finite-sample settings with noisy covariance queries would require additional assumptions on edge lengths and diameter, which is left for future work. The paper does not propose specific experimental applications but provides the theoretical framework for such testing in ultra-high-dimensional regimes.