Abstract
We propose a novel algorithm for the support estimation of partially known Gaussian graphical models that incorporates prior information about the underlying graph. In contrast to classical approaches that provide a point estimate based on a maximum likelihood or maximum a posteriori approach using (simple) priors on the precision matrix, we consider a prior on the graph and rely on annealed Langevin diffusion to generate samples from the posterior distribution. Since the Langevin sampler requires access to the score function of the underlying graph prior, we use graph neural networks to effectively estimate the score from a graph dataset (either available beforehand or generated from a known distribution). Numerical experiments in different setups demonstrate the benefits of our approach.
Introduction
Gaussian Graphical Models (GGMs) are a cornerstone of statistical machine learning used to uncover conditional dependencies between variables—for example, identifying gene interactions or mapping brain region communication. The structure of these models is represented by a graph where an edge exists between two nodes only if they are conditionally dependent.
Traditionally, researchers estimate these graphs using Maximum Likelihood or Maximum A Posteriori (MAP) methods. However, these methods usually rely on simple sparsity priors, such as the $L_1$ penalty used in Graphical Lasso. In reality, many real-world networks (like social networks or grids) exhibit specific structural motifs that go beyond simple sparsity. Furthermore, we often have access to datasets of similar graphs or partial knowledge of the network structure. Existing methods struggle to incorporate this rich, non-linear structural information effectively.
The LPost Framework
We propose a framework called LPost (Langevin Posterior) that shifts the focus from priors on the values of the precision matrix ($\Theta$) to priors directly on the adjacency matrix ($\mathbf{A}$), which represents the actual graph structure.
The LPost framework combines three sophisticated components:
- Score-Based Generative Modeling: Rather than defining an explicit probability density for a graph, we learn the "score function"—the gradient of the log-probability. This allows the model to capture highly complex distributions that lack closed-form expressions.
- GNN-Learned Priors: We train a specialized Graph Neural Network (EDP-GNN) on a dataset of graphs to estimate this score function. This GNN learns domain-specific connectivity patterns (e.g., what a "typical" social network looks like).
- Annealed Langevin Diffusion: To find the best graph, the algorithm samples from the posterior distribution. Starting from a noisy initialization, it uses the learned score (the prior) and the likelihood of the observed data to iteratively "nudge" the graph toward the posterior. "Annealing" helps the algorithm avoid getting stuck in local minima.
Crucially, the estimator is theoretically consistent, meaning that as more data is collected, the estimate is guaranteed to converge to the true underlying graph.
Experimental Evaluation
We evaluated LPost against standard benchmarks like Weighted Graphical Lasso (WGL), TIGER, and GraphSAGE on synthetic grid graphs, Barabási–Albert networks, and real-world Deezer social ego-nets.
Key results include:
- Superior Accuracy: LPost consistently achieved higher F1 scores across all datasets compared to traditional methods.
- Performance in Data-Starved Regimes: The advantage of LPost was most pronounced when the number of observations ($k$) was small. In these cases, the learned structural prior does the "heavy lifting" where the data likelihood is weak.
- Structural Awareness: On grid graphs, LPost significantly outperformed competitors because it "understood" the geometric grid structure, whereas Lasso-based methods only recognized sparsity.
Discussion and Future Work
While LPost demonstrates significant improvements in accuracy, it faces computational challenges. The Langevin sampling process involves multiple iterations with a complexity of $O(n^3)$, which may limit scalability for networks with thousands of nodes. Additionally, the method's performance is dependent on the quality and representativeness of the training graph dataset. Future work will explore scaling the method to larger networks and refining discrete score-based modeling to bridge the gap between continuous diffusion and discrete adjacency matrices.
Summary updated