Learning Product Graphs from Multidomain Signals

Sai Kiran Kadambari, Sundeep Prabhakar Chepuri

TL;DR

This paper introduces an efficient way to learn the structure of large graphs by treating them as "product graphs"—the combination of two or more smaller factor graphs (e.g., one for space and one for time). By leveraging the mathematical properties of Cartesian products and a "water-filling" optimization approach, the authors provide a method that is computationally cheaper and more accurate than standard techniques for multidomain data.

What Problem Does This Paper Address?

In many real-world scenarios, data is "multidomain." For example, a network of air quality sensors produces data that is both spatial (where the sensor is) and temporal (when the reading was taken). To analyze this data using Graph Signal Processing (GSP), we need a graph that represents these relationships.

However, learning a graph for $N$ nodes is computationally expensive—operations often scale at $O(N^3)$. If you have 1,000 sensors monitored over 365 days, the resulting graph would have 365,000 nodes, making standard graph learning algorithms infeasible. Furthermore, existing methods often ignore the structure of one domain (like time) or assume it is perfectly regular. This paper seeks to learn the underlying "factor" graphs for each domain simultaneously and efficiently.

Methods

The authors assume the underlying graph is a Cartesian product of two smaller factor graphs. If the full graph Laplacian is $L_N$, it can be expressed as the Kronecker sum of two smaller Laplacians: $L_N = L_P \oplus L_Q$.

Key technical contributions include:

  • One-Step Estimation: Instead of the traditional two-step approach (learning a massive graph and then trying to factorize it), the authors propose a one-step convex optimization problem to estimate the factor Laplacians directly from the data.
  • Smoothness Prior: The model assumes the data is "smooth" on the graph, meaning connected nodes have similar values.
  • Water-Filling Solution: For noise-free data, the authors derive an explicit solution based on the water-filling algorithm. This is significantly faster than using generic quadratic programming solvers because it relies on simple iterative updates.
  • Joint Matrix Completion: For real-world datasets with missing values, they propose an alternating minimization algorithm that simultaneously fills in missing data and learns the graph structure.

Datasets

The framework was evaluated on two types of data:

  1. Synthetic Data: A graph with 150 nodes formed by the product of two community graphs (10 nodes and 15 nodes). This allowed the authors to compare their results against a known "ground truth."
  2. Real-World Air Quality Data: PM2.5 concentration levels collected from 40 monitoring stations across India throughout 2018. This dataset is naturally multidomain (spatial locations × months) and contains many missing entries.

Key Insights and Ideas

  • Factorization is Efficiency: By learning two small matrices instead of one giant one, the number of variables in the optimization problem drops dramatically. This makes graph learning possible for much larger datasets.
  • Additive Smoothness: 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. This allows the optimization problem to be decoupled effectively.
  • Beyond Geography: In the air quality experiment, the learned spatial graph showed that cities aren't just connected by physical proximity, but by the similarity of their pollution profiles. Similarly, the temporal graph clustered months based on seasonal patterns (e.g., monsoon vs. non-monsoon months).

Key Results

  • Accuracy: On synthetic data, the proposed method (Solver 1) achieved an F-measure of 0.9755 (where 1.0 is a perfect recovery of edges), significantly outperforming the two-step baseline (Solver 2), which scored 0.7612.
  • Visual Consistency: The Laplacian matrices recovered by the proposed method were visually almost identical to the ground truth, whereas the baseline method introduced significant noise and errors.
  • Qualitative Success: On the Indian air quality data, the algorithm successfully identified clusters of months with similar pollution levels (June, July, and August clustered together due to the monsoon) and identified relationships between distant cities with similar environmental characteristics.

Limitations and Future Work

  • Fixed Product Type: The paper focuses specifically on the Cartesian product. Other types of graph products (like Kronecker or Strong products) exist and might better represent certain types of data.
  • Known Dimensions: The authors assume the dimensions of the factor graphs ($P$ and $Q$) are known beforehand. In some unsupervised tasks, these might need to be estimated.
  • Scalability to Many Factors: While the paper demonstrates a product of two graphs, extending this to $K$ factors (e.g., space × time × frequency) is a logical next step mentioned in the conclusion.

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

Loading related content...

Figure