Joint graph learning from Gaussian observations in the presence of hidden nodes

Samuel Rey, Madeline Navarro, Andrei Buciulea, Santiago Segarra, Antonio G. Marques

Introduction

Graph learning—the process of uncovering underlying connections in a network based on data observed at its nodes—is a cornerstone of modern data science. However, researchers face two major hurdles in real-world scenarios: the presence of hidden nodes and limited data availability. Learning a single graph with hidden nodes is often an ill-posed problem. This paper introduces Joint-Hid, a framework that learns the structure of multiple related networks simultaneously, even when some nodes are completely unobserved.

Methodology

Joint-Hid operates under the assumption that nodal signals follow a Gaussian Markov Random Field (GMRF), where the precision matrix directly encodes the graph's edges. To handle hidden nodes, the authors utilize the Schur complement to express observed data as a combination of direct connections between observed nodes and a low-rank matrix ($P$) capturing the influence of hidden nodes.

The core innovation is a convex optimization framework that balances data fidelity, sparsity (via $\ell_1$ norm), and low-rank structure (via nuclear norm). By penalizing differences between the observed portions of the graphs and the $P$ matrices, the method harnesses similarity even for unobserved parts of the network.

Experimental Evaluation

The researchers evaluated Joint-Hid using both synthetic and real-world data:

  • Synthetic Graphs: Erdős-Rényi and Small-World networks were used to test scalability.
  • University of Ljubljana Student Network: A real-world dataset of 32 students with multiple interaction types (e.g., friendship, social support) provided a benchmark for complex multi-layer structures.

Results and Discussion

Joint-Hid consistently outperforms standard baselines like Graphical Lasso (GL) and Latent Variable Graphical Lasso (LVGL).

Performance comparison of Joint-Hid against baselines across varying number of graphs (a), samples (b), and observed nodes (c).

Key Insights

  • Similarity in the Shadows: If two networks are similar, the influence of their hidden nodes on observed ones should also be similar. Enforcing similarity on the $P$ matrices allows the algorithm to "see" through missing data noise.
  • Scalability and Efficiency: As shown in plot (a), error drops significantly as the number of related graphs increases. Plot (b) shows that Joint-Hid reaches low error rates with far fewer samples than competitors.
  • Robustness: On the student dataset (plot c), Joint-Hid provides the most accurate topology estimates regardless of how many nodes are hidden. Interestingly, even with no hidden nodes, the model performs as well as standard joint learning methods.

Conclusion

Joint-Hid transforms an ill-posed problem into a solvable convex optimization task, significantly improving network topology inference. Future work includes extending this to non-Gaussian data and dynamic, time-varying networks.

Summary updated

Abstract

Graph learning problems are typically approached by focusing on learning the topology of a single graph when signals from all nodes are available. However, many contemporary setups involve multiple related networks and, moreover, it is often the case that only a subset of nodes is observed while the rest remain hidden. Motivated by this, we propose a joint graph learning method that takes into account the presence of hidden (latent) variables. Intuitively, the presence of the hidden nodes renders the inference task ill-posed and challenging to solve, so we overcome this detrimental influence by harnessing the similarity of the estimated graphs. To that end, we assume that the observed signals are drawn from a Gaussian Markov random field with latent variables and we carefully model the graph similarity among hidden (latent) nodes. Then, we exploit the structure resulting from the previous considerations to propose a convex optimization problem that solves the joint graph learning task by providing a regularized maximum likelihood estimator. Finally, we compare the proposed algorithm with different baselines and evaluate its performance over synthetic and real-world graphs.
BibTeX
@inproceedings{rey2022joint,
  author = {Samuel Rey and Madeline Navarro and Andrei Buciulea and Santiago Segarra and Antonio G. Marques},
  title = {{Joint graph learning from Gaussian observations in the presence of hidden nodes}},
  booktitle = {IEEECONF},
  year = {2022},
  doi = {10.1109/ieeeconf56349.2022.10051977},
}
Figure