⚡ electrical engineering

Learning Product Graphs from Two-dimensional Stationary Signals

This paper proposes a graph signal processing framework that learns underlying product graph structures from two-dimensional stationary signals by modeling them as jointly filtered matrix signals, offering a provably optimal and computationally efficient solution that outperforms existing methods in accuracy and cost.

Original authors: Andrei Buciulea, Bishwadeep Das, Elvin Isufi, Antonio G. Marques

Published 2026-05-08

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Andrei Buciulea, Bishwadeep Das, Elvin Isufi, Antonio G. Marques

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Mapping the Unknown

Imagine you are trying to draw a map of a city, but you don't know the streets exist. All you have are thousands of photos of traffic patterns taken at different times. Your goal is to figure out how the streets connect just by looking at how the cars move.

In the world of data science, this is called Graph Learning. Usually, scientists look at data from just one angle (like just the "time" the cars moved). But in the real world, data often has two dimensions at once. For example:

Time (when the event happened) AND Location (where it happened).
Users (who clicked) AND Movies (what they clicked on).

This paper proposes a new, smarter way to draw that map when the data has two dimensions.

The Problem: The "Flat" Map vs. The "3D" Reality

The Old Way (The Flat Map):
Traditional methods treat every single combination of "Time + Location" as a unique, isolated point. If you have 100 locations and 100 time steps, the old method tries to figure out the connections between 10,000 points (100 × 100).

The Analogy: Imagine trying to learn the layout of a massive library by treating every single book on every single shelf as a completely different room. You'd have to draw a map connecting 10,000 rooms. It's slow, confusing, and requires a huge amount of memory.

The New Way (The Product Map):
The authors realized that the "Time" dimension and the "Location" dimension usually follow their own separate rules, and they work together like a grid.

The Analogy: Instead of mapping 10,000 rooms, imagine the library is a grid. You only need to map the "Row" rules (how shelves connect horizontally) and the "Column" rules (how shelves connect vertically). Then, you just combine those two simple maps to get the whole picture. This is what they call a Product Graph.

The Core Idea: The "Filter" and the "Noise"

The paper uses a concept from signal processing called Stationarity.

The Metaphor: Imagine you are listening to a song played through a specific speaker system (the graph). The music (the signal) is just random static (noise) that has been smoothed out by the speaker.
The Claim: If the music sounds "smooth" and consistent (stationary) across the speaker system, you can work backward to figure out what the speaker system looks like just by listening to the music.

The authors say: "If we assume our two-dimensional data (like Time and Location) is created by two separate 'filters' working together—one for time and one for location—we can solve the puzzle much easier."

The Solution: Splitting the Puzzle

The authors developed a mathematical recipe (an optimization problem) that does three main things:

Separates the Dimensions: Instead of trying to solve for the big 10,000-point map all at once, they split it into two small problems: one for the "Time" map and one for the "Location" map.
Uses "Commutativity": This is a fancy math word that basically means "order doesn't matter." If you shuffle the data by time first, then by location, it looks the same as shuffling by location first, then time. The paper uses this rule to prove that the two small maps are correct.
Saves Time and Money: Because they split the problem, they don't need as much data to get a good answer, and their computer doesn't have to work as hard.

The Results: What Did They Find?

The team tested their method using fake data (simulations) and compared it to other top methods.

Accuracy: Their method (called SepK-ST) was just as good at finding the correct map as the most complex methods, but much better than the simple "flat" methods.
Speed: It was significantly faster. While other methods got bogged down as the data got bigger, their method stayed fast.
Data Efficiency: They needed fewer samples (fewer "photos" of the traffic) to get a reliable map compared to other methods.

Summary

Think of this paper as a new instruction manual for organizing a messy room.

Old Method: Try to figure out where every single sock and shirt goes by looking at the pile as one giant mess.
This Paper's Method: Realize that socks go in the drawer (Dimension A) and shirts go on the rack (Dimension B). Figure out the rules for the drawer and the rules for the rack separately, then combine them.

The result is a faster, more accurate way to understand how complex, two-sided data is connected, without needing a supercomputer to do the math.

Technical Summary: Learning Product Graphs from Two-Dimensional Stationary Signals

Problem Statement
Traditional graph learning frameworks typically infer network structures from scalar signals observed at nodes, treating multiple realizations (e.g., time samples, experimental repetitions, or population data) as a single dimension. This approach often disregards the structured dependencies existing across these additional dimensions. In many applications, such as spatio-temporal processes or recommender systems, data is naturally represented as two-dimensional signals indexed by both the node (entities) and a realization dimension (time, users, or experiments). Treating these as a single vectorized dimension leads to scalability issues due to the quadratic growth in unknowns ( $P^2Q^2$ for $P \times Q$ nodes) and the difficulty of accurately estimating high-dimensional covariance matrices from limited samples. While recent methods attempt to model these dependencies using product graphs (e.g., Kronecker or Cartesian products), existing approaches often rely on non-convex optimization or still require estimating large, full-dimensional covariance matrices.

Methodology
The authors propose a Graph Signal Processing (GSP) framework that models two-dimensional signals as outputs of a joint filtering process acting on white Gaussian noise. The core assumption is that the observed matrix signal $Y \in \mathbb{R}^{P \times Q}$ is generated by:
$Y = H_P(S_P) W H_Q(S_Q)$
where $S_P$ and $S_Q$ are the Graph Shift Operators (GSOs) for the two dimensions, $H_P$ and $H_Q$ are polynomial graph filters, and $W$ is a noise matrix with i.i.d. entries.

Based on this model, the paper derives three distinct problem formulations for graph learning:

General Vectorized Model: Treats the $P \times Q$ signal as a single vector and learns an unstructured GSO. This is computationally prohibitive due to the $O((PQ)^2)$ complexity.
Structured Product-Graph Model: Assumes the underlying graph is a product (Kronecker, Cartesian, or strong) of two graphs. This reduces variables to $P^2 + Q^2$ but introduces a non-convex constraint involving the Kronecker product, typically requiring alternating optimization without guaranteed recovery.
Dimension-wise Covariance Formulation (Proposed): Leveraging the specific signal generation model, the authors show that the marginal covariance matrices $C_P = E[YY^\top]$ and $C_Q = E[Y^\top Y]$ are polynomials in $S_P$ and $S_Q$ , respectively. This allows the learning problem to be decoupled into two separate, convex optimization problems:
$\min_{S_P, S_Q} \|S_P\|_1 + \beta\|S_Q\|_1 \quad \text{s.t.} \quad C_P S_P = S_P C_P, \quad C_Q S_Q = S_Q C_Q$
This formulation avoids estimating the full $PQ \times PQ$ covariance matrix, significantly reducing computational cost and sample complexity while maintaining the product graph structure.

Key Contributions

Extension of Stationarity: The work extends the concept of graph stationarity to two-dimensional signals, modeling them as the result of joint filtering along independent dimensions.
Tractable Optimization: By exploiting the structure of the dimension-wise covariances, the authors reformulate the topology identification task into two separable, low-dimensional convex problems. This bypasses the non-convexity and high dimensionality associated with previous product graph learning methods.
Theoretical Guarantees: The proposed formulation allows for provable recovery of the optimal underlying Kronecker, Cartesian, or strong product graphs under the stated signal model.

Experimental Results
The authors evaluate their method (specifically the "Separate Kronecker-ST" or SepK-ST variant) against spectral templates (ST), Kronecker-ST (K-ST), DNNLasso, and TERRALasso using synthetic data.

Accuracy vs. Complexity: SepK-ST achieves recovery accuracy comparable to K-ST but with significantly lower runtime. Unlike the unstructured ST method, which fails to capture the underlying structure and scales poorly, SepK-ST effectively leverages the 2D structure.
Sample Efficiency: In regimes with a limited number of signal realizations ( $R$ ), SepK-ST outperforms both ST and K-ST. Because it operates on smaller $P \times P$ and $Q \times Q$ covariance matrices rather than the full $PQ \times PQ$ matrix, it requires fewer samples to achieve reliable estimates and better stationarity (commutativity).
Robustness to Signal Models: When tested against signals generated from different models (Markov Random Fields vs. Polynomial filters), SepK-ST consistently recovers the graph structure. In contrast, DNNLasso and TERRALasso show performance degradation when the signal generation model deviates from their specific assumptions.

Significance
The paper claims that its primary contribution is providing a framework that balances estimation accuracy and computational efficiency for learning graphs from two-dimensional stationary signals. By decoupling the learning problem into dimension-specific convex optimizations, the approach offers a scalable alternative to existing methods that struggle with the curse of dimensionality or non-convex constraints. The results suggest that explicitly modeling the product structure and the filtering process across dimensions is essential for accurate inference in scenarios where dependencies exist across multiple modalities.