Learning Product Graphs from Two-dimensional Stationary Signals

技术摘要：从二维平稳信号中学习产品图

问题陈述
传统的图学习框架通常从节点上观测到的标量信号推断网络结构，将多个实现（例如时间样本、实验重复或群体数据）视为单一维度。这种方法往往忽视了这些额外维度之间存在的结构化依赖关系。在许多应用中，如时空过程或推荐系统，数据自然地表示为二维信号，其索引同时包含节点（实体）和实现维度（时间、用户或实验）。将这些视为单一向量化维度会导致可扩展性问题，因为未知数的数量呈二次增长（对于 $P \times Q$ 个节点为 $P^2Q^2$），且难以从有限样本中准确估计高维协方差矩阵。尽管近期方法尝试使用产品图（例如 Kronecker 积或笛卡尔积）对这些依赖关系进行建模，但现有方法通常依赖非凸优化，或者仍然需要估计大型的全维协方差矩阵。

方法论
作者提出了一个图信号处理（GSP）框架，将二维信号建模为作用于白高斯噪声的联合滤波过程的输出。核心假设是观测到的矩阵信号 $Y \in \mathbb{R}^{P \times Q}$ 由以下公式生成：
$$Y = H_P(S_P) W H_Q(S_Q)$$
其中 $S_P$ 和 $S_Q$ 是两个维度的图移位算子（GSO），$H_P$ 和 $H_Q$ 是多项式图滤波器，$W$ 是元素独立同分布的噪声矩阵。

基于该模型，本文推导了三种不同的图学习问题表述：

1. 通用向量化模型：将 $P \times Q$ 信号视为单个向量并学习非结构化 GSO。由于复杂度为 $O((PQ)^2)$，这在计算上是不可行的。
2. 结构化产品图模型：假设底层图是两个图的乘积（Kronecker 积、笛卡尔积或强积）。这将变量减少到 $P^2 + Q^2$，但引入了涉及 Kronecker 积的非凸约束，通常需要交替优化且无法保证恢复。
3. 逐维协方差表述（所提出的方法）：利用特定的信号生成模型，作者表明边际协方差矩阵 $C_P = E[YY^\top]$ 和 $C_Q = E[Y^\top Y]$ 分别是 $S_P$ 和 $S_Q$ 的多项式。这使得学习问题可以解耦为两个独立的凸优化问题：
   $$\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$$
   该表述避免了估计完整的 $PQ \times PQ$ 协方差矩阵，显著降低了计算成本和样本复杂度，同时保持了产品图结构。

主要贡献

• 平稳性的扩展：该工作将图平稳性的概念扩展到二维信号，将其建模为沿独立维度联合滤波的结果。
• 可处理的优化：通过利用逐维协方差的结构，作者将拓扑识别任务重构为两个可分离的低维凸问题。这规避了以往产品图学习方法所关联的非凸性和高维性。
• 理论保证：所提出的表述允许在所述信号模型下，对最优的底层 Kronecker 积、笛卡尔积或强积图进行可证明的恢复。

实验结果
作者使用合成数据评估了他们的方法（具体为“独立 Kronecker-ST"或 SepK-ST 变体），并与谱模板（ST）、Kronecker-ST（K-ST）、DNNLasso 和 TERRALasso 进行了对比。

• 精度与复杂度：SepK-ST 实现了与 K-ST 相当的恢复精度，但运行时间显著更短。与无法捕捉底层结构且扩展性差的非结构化 ST 方法不同，SepK-ST 有效地利用了二维结构。
• 样本效率：在信号实现数量（$R$）有限的情况下，SepK-ST 的表现优于 ST 和 K-ST。因为它操作的是较小的 $P \times P$ 和 $Q \times Q$ 协方差矩阵，而不是完整的 $PQ \times PQ$ 矩阵，所以它需要更少的样本来实现可靠的估计和更好的平稳性（交换性）。
• 对信号模型的鲁棒性：当针对由不同模型（马尔可夫随机场与多项式滤波器）生成的信号进行测试时，SepK-ST 始终能够恢复图结构。相比之下，当信号生成模型偏离其特定假设时，DNNLasso 和 TERRALasso 表现出性能下降。

意义
该论文声称其主要贡献是提供了一个框架，用于平衡从二维平稳信号中学习图时的估计精度和计算效率。通过将学习问题解耦为特定于维度的凸优化，该方法为那些受困于维数灾难或非凸约束的现有方法提供了一种可扩展的替代方案。结果表明，在存在跨多种模态依赖关系的情景中，显式地对跨维度的乘积结构和滤波过程进行建模对于准确推断至关重要。