Estimating Structurally Similar Graphical Models

This paper considers the problem of estimating the structure of structurally similar graphical models in high dimensions. This problem is pertinent in multi-modal or multidomain datasets that consist of multiple information domains, each modeled by one probabilistic graphical model (PGM), e.g., in brain network modeling using different neuroimaging modalities. Induced by an underlying shared causal source, the domains, and subsequently their associated PGMs, can have structural similarities. This paper focuses on Gaussian and Ising models and characterizes the information-theoretic sample complexity of estimating the structures of a pair of PGMs in the degree-bounded and edge-bounded subclasses. The PGMs are assumed to have p nodes with distinct and unknown structures. Their similarity is accounted for by assuming that a pre-specified set of q nodes form identical subgraphs in both PGMs. Necessary and sufficient conditions on the sample complexity for a bounded probability of error are characterized. The necessary conditions are information-theoretic (algorithm-independent), delineating the statistical difficulty of the problem. The sufficient conditions are based on deploying maximum likelihood decoders. While the specifics of the results vary across different subclasses and parameter regimes, one key observation is that in specific subclasses and regimes, the sample complexity varies with p and q according to T(log(p - q)). For Ising models, a low complexity, online structure estimation (learning) algorithm based on multiplicative weights is also proposed. Numerical evaluations are also included to illustrate the interplay among different parameters on the sample complexity when the structurally similar graphs are recovered by a maximum likelihood-based graph decoder and the proposed online estimation algorithm.

Automated summary

This paper discusses the problem of estimating the structure of similar graphical models in high dimensions. The focus is on Gaussian and Ising models, and the sample complexity of estimating their structures is characterized. Necessary and sufficient conditions for a bounded probability of error are determined. Additionally, a low complexity, online structure estimation algorithm for Ising models is proposed.