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

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},
}

Loading related content...

Figure