Learning Product Graphs from Multidomain Signals

Sai Kiran Kadambari, Sundeep Prabhakar Chepuri

Abstract: In this paper, we focus on learning the underlying product graph structure from multidomain training data. We assume that the product graph is formed from a Cartesian graph product of two smaller factor graphs. We then pose the product graph learning problem as the factor graph Laplacian matrix estimation problem. To estimate the factor graph Laplacian matrices, we assume that the data is smooth with respect to the underlying product graph. When the training data is noise free or complete, learning factor graphs can be formulated as a convex optimization problem, which has an explicit solution based on the water-filling algorithm. The developed framework is illustrated using numerical experiments on synthetic data as well as real data related to air quality monitoring in India.

Introduction

In many real-world scenarios, data is inherently multidomain. A prominent example is a network of air quality sensors, where each data point is defined by both its spatial location and the time of observation. Analyzing such data using Graph Signal Processing (GSP) requires a graph that accurately represents these relationships. However, learning a graph for $N$ nodes is computationally expensive, with operations often scaling at $O(N^3)$. For a network of 1,000 sensors monitored over a year, the resulting graph would contain 365,000 nodes, making standard graph learning algorithms infeasible. This paper introduces an efficient framework to learn the structure of large graphs by treating them as "product graphs" composed of smaller factor graphs.

Methodology: The Cartesian Product Approach

The core assumption of this work is that the underlying graph structure can be modeled as a Cartesian product of two smaller factor graphs (e.g., one for space and one for time). Mathematically, if the full graph Laplacian is $L_N$, it can be expressed as the Kronecker sum of two smaller factor Laplacians: $L_N = L_P \oplus L_Q$.

One-Step Estimation and Smoothness

Unlike traditional two-step approaches that first learn a massive graph and then attempt to factorize it, the authors propose a one-step convex optimization problem to estimate the factor Laplacians directly from the data. The model assumes a smoothness prior, meaning that signals on the graph change gradually between connected nodes. A crucial mathematical insight is that the total smoothness of a signal on a product graph is simply the sum of its smoothness on each individual factor graph, allowing the optimization problem to be decoupled effectively.

The Water-Filling Solution

For noise-free or complete datasets, the authors derive an explicit solution based on a water-filling algorithm. This approach is significantly faster than generic quadratic programming solvers because it relies on simple, efficient iterative updates. For real-world datasets with missing values, an alternating minimization algorithm is proposed to simultaneously perform matrix completion and learn the graph structure.

Experimental Results

Synthetic Validation

The framework was evaluated on synthetic data consisting of 150 nodes formed by the product of two community graphs. The proposed method (Solver 1) achieved an F-measure of 0.9755, significantly outperforming the two-step baseline (Solver 2), which scored 0.7612. The recovered Laplacian matrices were visually almost identical to the ground truth, whereas the baseline introduced significant noise.

Real-World Case Study: Air Quality in India

The framework was applied to PM2.5 concentration levels collected from 40 monitoring stations across India throughout 2018. This dataset is naturally multidomain, spanning spatial locations and temporal months.

Spatial factor graph $\mathcal{G}_P$ learned from Indian air quality data. The graph reveals that cities are connected not just by physical proximity, but by the similarity of their pollution profiles.

As shown in Figure 4, the learned spatial graph $\mathcal{G}_P$ identifies clusters of cities with similar environmental characteristics. Interestingly, the connections extend beyond simple geography, linking distant cities that share similar pollution patterns.

Temporal factor graph $\mathcal{G}_Q$ representing seasonal relationships. Note the clustering of June, July, and August, which corresponds to the monsoon season in India.

Similarly, the temporal factor graph $\mathcal{G}_Q$ (Figure 1) successfully captures seasonal patterns. For instance, the months of June, July, and August are closely clustered, reflecting the unique pollution profiles during the Indian monsoon season.

Conclusion and Future Work

By learning two small matrices instead of one giant one, the proposed framework dramatically reduces the number of variables in the optimization problem, making graph learning possible for much larger datasets. While this paper focuses on the Cartesian product, extending this to other graph products (like Kronecker or Strong products) and scaling to more than two factors (e.g., space × time × frequency) are logical next steps for future research.

Summary updated

Abstract

In this paper, we focus on learning the underlying product graph structure from multidomain training data. We assume that the product graph is formed from a Cartesian graph product of two smaller factor graphs. We then pose the product graph learning problem as the factor graph Laplacian matrix estimation problem. To estimate the factor graph Laplacian matrices, we assume that the data is smooth with respect to the underlying product graph. When the training data is noise free or complete, learning factor graphs can be formulated as a convex optimization problem, which has an explicit solution based on the water-filling algorithm. The developed framework is illustrated using numerical experiments on synthetic data as well as real data related to air quality monitoring in India.
BibTeX
@inproceedings{kadambari2020learning,
  author = {Sai Kiran Kadambari and Sundeep Prabhakar Chepuri},
  title = {{Learning Product Graphs from Multidomain Signals}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2020},
  doi = {10.1109/icassp40776.2020.9054679},
}
Figure