Abstract
Gaussian Graphical Models (GGMs) are essential for representing conditional dependencies in complex systems. Traditional structure estimation relies on simple sparsity priors, such as the Graphical Lasso. This paper proposes a novel framework that incorporates arbitrary, data-driven structural priors learned via Graph Neural Networks (GNNs). By employing annealed Langevin dynamics to sample from the posterior distribution, the method achieves superior performance in recovering graph structures, especially in data-scarce regimes.
Introduction
Estimating the structure of GGMs—identifying the zero-pattern of the precision matrix—is a fundamental task in fields ranging from genomics to finance. While classical methods like Graphical Lasso use $L_1$ regularization to enforce sparsity, they often fail to capture complex structural motifs present in real-world networks. This work addresses the challenge of integrating rich, non-parametric structural priors directly on the adjacency matrix, allowing the model to learn from a distribution of related graphs.
Methodology
The proposed approach shifts from finding a Maximum A Posteriori (MAP) estimate to estimating the posterior mean through sampling. The pipeline consists of three main components:
- Annealed Langevin Dynamics: To handle the discrete nature of adjacency matrices, the authors use an annealed version of Langevin dynamics, adding Gaussian noise that is gradually reduced to sample from the target posterior.
- Score Matching with GNNs: The score function (gradient of the log-posterior) is decomposed into a likelihood score and a prior score. An Equivariant Diffusion Graph Neural Network (EDP-GNN) is trained on a dataset of graphs to estimate the prior score.
- Posterior Mean Estimator: Multiple samples are generated, projected to binary values, and averaged to produce the final estimate.
Experimental Evaluation
The method was evaluated on synthetic (Grid, Barabási–Albert, ERGM) and real-world (Deezer Ego-nets) datasets. The results demonstrate that the proposed method, "LPost," consistently outperforms baselines such as Weighted Graphical Lasso, TIGER, and GraphSAGE.
Key Insights
- Structural Priors over Matrix Penalties: Learning priors on the discrete adjacency matrix captures complex motifs (e.g., triangles, hubs) that simple matrix-based penalties miss.
- The Value of Priors in Data Scarcity: The structural prior is most impactful when the number of observations ($k$) is small. As $k$ increases, the likelihood dominates, and performance across methods tends to converge.
- Scalability with Prior Data: Performance improves as the size of the prior training dataset increases, typically saturating around 1,000 graphs.
Conclusion and Future Work
While the method offers significant accuracy gains, it is computationally intensive due to the $O(n^3)$ complexity of precision matrix inversion at each Langevin step. Future research will focus on optimizing these computations to scale the approach to larger graphs ($n > 1000$) and exploring more efficient sampling strategies.
Summary updated