Learning Shared Subgraphs in Ising Model Pairs

Burak Varici, Saurabh Sihag, Ali TajerAISTATS 2021 · OpenReview

Abstract

Probabilistic graphical models (PGMs) are effective for capturing the statistical dependencies in stochastic databases. In many domains (e.g., working with multimodal data), one faces multiple information layers that can be modeled by structurally similar PGMs. While learning the structures of PGMs in isolation is well-investigated, the algorithmic design and performance limits of learning from multiple coupled PGMs are investigated far less. This paper considers learning the structural similarities shared by a pair of Ising PGMs. The objective is learning the shared structure with no regard for the structures exclusive to either of the graphs, and significantly different from the existing approaches that focus on entire structure of the graphs. We propose an algorithm for the shared structure learning objective, evaluate its performance empirically, and compare with existing approaches on structure learning of single graphs.

Introduction

Probabilistic Graphical Models (PGMs), particularly Ising models, are foundational tools in statistical physics and machine learning for representing dependencies between stochastic variables. In many modern applications, researchers encounter multimodal data—different observational layers of the same underlying system. For instance, in neuroscience, DTI and fMRI scans provide distinct structural and functional views of the brain. While these views differ, they often share a common structural "core" or backbone.

Traditional approaches to identifying this shared structure are typically "naive": they reconstruct the full structure of each graph independently and then compute their intersection. This process is computationally and statistically inefficient. If the objective is to identify only the shared 10% of a network, learning the unique 90% of each graph represents a significant waste of data resources. This paper addresses the challenge of directly learning the shared subgraph between a pair of Ising models, significantly reducing the sample complexity required.

Conceptual illustration of two graphs $G_1$ and $G_2$ sharing a common subgraph $G_s$ (highlighted in green).

Methodology

The authors propose a two-step adaptive framework that integrates statistical pruning with online learning to isolate shared edges efficiently.

1. Similarity-based Pruning

The algorithm begins by considering all vertices as potential members of the shared subgraph. It computes empirical pairwise correlations between vertices across both datasets. Utilizing a thresholding rule derived from Hoeffding’s inequality, the algorithm progressively "prunes" vertices that demonstrate a low probability of belonging to the shared structure. This adaptive pruning focuses subsequent computational efforts on the most relevant portions of the graphs.

2. Prediction-guided Joint Learning

For the remaining candidate vertices, the algorithm employs an online structure learning process based on a multiplicative weight update method (akin to the "Hedge" algorithm). Unlike standard methods that update weights for each graph in isolation, this approach performs a joint update. By transferring loss information between the two models simultaneously, the algorithm filters out noise from unshared edges, allowing the "signal" of the shared structure to emerge more rapidly than independent learning.

Experimental Setup

The performance of the proposed algorithm was evaluated using three synthetic graph ensembles designed to represent diverse network topologies:

  • Ensemble 1 (Sparse Erdős-Rényi): Random graphs where edges are formed with a fixed probability.
  • Ensemble 2 (Trees): Acyclic graphs common in hierarchical data representations.
  • Ensemble 3 (Cyclic Blocks): Graphs composed of small cyclic components with a restricted maximum degree.

Additionally, the authors applied the method to U.S. Senate voting records to demonstrate its efficacy on real-world behavioral datasets where shared ideological structures are expected.

Key Results

The empirical results demonstrate a clear advantage for the joint learning approach over independent reconstruction. In all tested ensembles, the joint method achieved a zero probability of error with significantly fewer samples (lower "horizon") than the independent baseline.

Probability of error vs. sample horizon for three graph ensembles, comparing joint learning to independent learning.

As shown in the performance plots, the joint learning approach (blue) consistently converges to zero error faster than the independent approach (red). The method also outperformed standard baselines such as Correlation Thresholding (CT) and $\ell_1$-constrained logistic regression (sparse mirror descent). In random graph scenarios, the proposed algorithm reached low error rates using approximately half the samples required by sparse logistic regression. Theoretically, the authors prove that for isolated subgraphs, the sample complexity scales logarithmically with the number of vertices ($p$) and exponentially with the maximum degree ($d$), matching information-theoretic lower bounds.

Conclusion

By intentionally ignoring the unique structures of individual graphs, this research demonstrates that learning shared subgraphs can be achieved with much higher efficiency than full graph reconstruction. While current theoretical guarantees assume the shared subgraph is somewhat "isolated," the empirical success across various topologies suggests broader applicability. Future work will focus on relaxing these assumptions and extending the "shared-only" learning philosophy to other PGM classes, such as Gaussian Graphical Models.

Summary updated

Abstract

Probabilistic graphical models (PGMs) are effective for capturing the statistical dependencies in stochastic databases. In many domains (e.g., working with multimodal data), one faces multiple information layers that can be modeled by structurally similar PGMs. While learning the structures of PGMs in isolation is well-investigated, the algorithmic design and performance limits of learning from multiple coupled PGMs are investigated far less. This paper considers learning the structural similarities shared by a pair of Ising PGMs. The objective is learning the shared structure with no regard for the structures exclusive to either of the graphs, and significantly different from the existing approaches that focus on entire structure of the graphs. We propose an algorithm for the shared structure learning objective, evaluate its performance empirically, and compare with existing approaches on structure learning of single graphs.
BibTeX
@inproceedings{varici2021learning,
  author = {Burak Varici and Saurabh Sihag and Ali Tajer},
  title = {{Learning Shared Subgraphs in Ising Model Pairs}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2021},
  url = {https://openreview.net/forum?id=k2eJLgLGx3i},
}
Figure