# Learning Kronecker-Structured Graphs from Smooth Signals

arXiv: https://arxiv.org/abs/2505.09822 · HTML: https://mlsanity.com/paper/2505.09822/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 23 of its 56 references that are in the map.
- First posted on arXiv 14 May 2025.

## Builds on (most cited first, 23 of 23)

- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Graph Signal Processing: Overview, Challenges and Applications](https://mlsanity.com/paper/1712.00468/) (2017)
- [How to learn a graph from smooth signals](https://mlsanity.com/paper/1601.02513/) (2016)
- [Connecting the Dots: Identifying Network Structure via Graph Signal Processing](https://mlsanity.com/paper/1810.13066/) (2018)
- [Network Topology Inference from Spectral Templates](https://mlsanity.com/paper/1608.03008/) (2016)
- [A Unified Framework for Structured Graph Learning via Spectral Constraints](https://mlsanity.com/paper/1904.09792/) (2019)
- [Learning heat diffusion graphs](https://mlsanity.com/paper/1611.01456/) (2016)
- [Learning Sparse Graphs Under Smoothness Prior](https://mlsanity.com/paper/1609.03448/) (2016)
- [Learning Graphs from Smooth and Graph-Stationary Signals with Hidden Variables](https://mlsanity.com/paper/2111.05588/) (2021)
- [Tensor Graphical Lasso (TeraLasso)](https://mlsanity.com/paper/1705.03983/) (2017)
- [Maximum likelihood estimation in Gaussian models under total positivity](https://mlsanity.com/paper/1702.04031/) (2017)
- [Identifying the Topology of Undirected Networks from Diffused Non-stationary Graph Signals](https://mlsanity.com/paper/1801.03862/) (2018)
- [Multi-way Graph Signal Processing on Tensors: Integrative analysis of irregular geometries](https://mlsanity.com/paper/2007.00041/) (2020)
- [The Sylvester Graphical Lasso (SyGlasso)](https://mlsanity.com/paper/2002.00288/) (2020)
- [Product Graph Learning from Multi-domain Data with Sparsity and Rank Constraints](https://mlsanity.com/paper/2012.08090/) (2020)
- [Learning Product Graphs Underlying Smooth Graph Signals](https://mlsanity.com/paper/2002.11277/) (2020)
- [Learning product graphs from multidomain signals](https://mlsanity.com/paper/1911.07411/) (2019)
- [Learning Product Graphs from Spectral Templates](https://mlsanity.com/paper/2211.02893/) (2022)
- [Estimation of Laplacian spectra of direct and strong product graphs](https://mlsanity.com/paper/1507.03030/) (2015)
- [Another estimation of Laplacian spectrum of the Kronecker product of graphs](https://mlsanity.com/paper/2102.02924/) (2021)
- [EiGLasso for Scalable Sparse Kronecker-Sum Inverse Covariance Estimation](https://mlsanity.com/paper/2105.09872/) (2021)
- [Graph Laplacian Learning with Exponential Family Noise](https://mlsanity.com/paper/2306.08201/) (2023)
- [Learning Cartesian Product Graphs with Laplacian Constraints](https://mlsanity.com/paper/2402.08105/) (2024)

## Abstract (arXiv)

Graph learning, or network inference, is a prominent problem in graph signal processing (GSP). GSP generalizes the Fourier transform to non-Euclidean domains, and graph learning is pivotal to applying GSP when these domains are unknown. With the recent prevalence of multi-way data, there has been growing interest in product graphs that naturally factorize dependencies across different ways. However, the types of graph products that can be learned are still limited for modeling diverse dependency structures. In this paper, we study the problem of learning a Kronecker-structured product graph from smooth signals. Unlike the more commonly used Cartesian product, the Kronecker product models dependencies in a more intricate, non-separable way, but posits harder constraints on the graph learning problem. To tackle this non-convex problem, we propose an alternating scheme to optimize each factor graph and provide theoretical guarantees for its asymptotic convergence. The proposed algorithm is also modified to learn factor graphs of the strong product. We conduct experiments on synthetic and real-world graphs and demonstrate our approach's efficacy and superior performance compared to existing methods.