基于滤波器和最优传输的图字典学习框架

# 基于滤波器与最优传输的图字典学习框架
来源：https://arxiv.org/html/2609.05919
###### 摘要

我们提出一种图字典学习 \(GDL\) 框架，其中每个图被表示为一个由滤波拉普拉斯矩阵导出的零均值高斯分布。每个观测图通过学习到的原子图上的重心来近似，该重心在滤波图距离 \(fGOT\) 下计算——这是一种对全局结构性质敏感的图比较度量。观测图与其重心之间的重建误差通过替代 \(sfGOT\) 距离来衡量，这是 \(fGOT\) 的一种可处理近似，适用于没有已知节点对应关系的图，并通过反向传播进行端到端最小化。我们进一步从 Hilbert-Schmidt 独立性准则的角度对 \(sfGOT\) 提供了新颖的解释，表明最小化两个图之间的 \(sfGOT\) 距离等价于最大化它们节点谱嵌入之间的统计依赖性。在基准数据集上的实验表明，该方法在图聚类和分类任务上具有与现有 \(GDL\) 方法相竞争的性能。

###### 索引术语：

字典学习；图最优传输。

††地址：北海道大学研究生院信息科学与技术学院
[jinchuan\.liao\.v1@elms\.hokudai\.ac\.jp](mailto:[email protected])[hai@ist\.hokudai\.ac\.jp](mailto:[email protected])## 1引言

图结构数据学习在机器学习和信号处理领域引起了广泛关注，其在生物信息学、化学信息学和社会网络分析中有着广泛应用\[1 (https://arxiv.org/html/2609.05919#bib.bib1),11 (https://arxiv.org/html/2609.05919#bib.bib13),14 (https://arxiv.org/html/2609.05919#bib.bib15)\]。解决该问题的方法通常依赖于图核、距离和潜在空间表示，应用于监督、无监督或半监督设置中\[27 (https://arxiv.org/html/2609.05919#bib.bib27),21 (https://arxiv.org/html/2609.05919#bib.bib20),6 (https://arxiv.org/html/2609.05919#bib.bib8),19 (https://arxiv.org/html/2609.05919#bib.bib19),17 (https://arxiv.org/html/2609.05919#bib.bib6),18 (https://arxiv.org/html/2609.05919#bib.bib2),20 (https://arxiv.org/html/2609.05919#bib.bib18)\]。

在本工作中，我们专注于图的字典学习 \(DL\)，这是一种无监督学习框架，学习一组称为*原子*的基，构成*字典*\[25 (https://arxiv.org/html/2609.05919#bib.bib25),10 (https://arxiv.org/html/2609.05919#bib.bib12)\]。原子通过最小化将每个输入近似为原子加权组合时的重建误差来推断。所得的组合作为下游任务（如分类和聚类）的潜在表示。对于图结构数据，基于 Gromov-Wasserstein \(GW\) 差异的图字典学习 \(GDL\) 框架\[15 (https://arxiv.org/html/2609.05919#bib.bib16)\]已被提出以处理不同大小且没有节点对应的图\[28 (https://arxiv.org/html/2609.05919#bib.bib28),26 (https://arxiv.org/html/2609.05919#bib.bib26)\]。然而，\(GW\) 通过成对节点距离（例如最短路径距离）来比较图，这主要反映局部邻域结构而非全局模式，因此未能捕捉图的全局结构。

图最优传输 \(GOT\)\[12 (https://arxiv.org/html/2609.05919#bib.bib21)\]提供了一种替代方案，它将每个图表示为一个零均值高斯分布，其协方差由图拉普拉斯伪逆导出，从而能够通过 Wasserstein 距离进行比较。这被扩展到滤波图距离 \(fGOT\)\[13 (https://arxiv.org/html/2609.05919#bib.bib14)\]，它引入了一个谱滤波器，对强调哪些结构尺度提供了灵活的谱控制。为了处理未知节点对应关系，\[13 (https://arxiv.org/html/2609.05919#bib.bib14)\]进一步引入了替代 \(fGOT\) \(sfGOT\)，作为 \(fGOT\) 的一个可处理上界。尽管具有实际效用，但 \(sfGOT\) 作为图距离的结构意义仍未被充分探索。

贡献\.\(1\) 我们从 Hilbert-Schmidt 独立性准则 \(HSIC\)\[7 (https://arxiv.org/html/2609.05919#bib.bib9)\]的角度为 \(sfGOT\) 提供了一种新的解释，表明最小化两个图之间的 \(sfGOT\) 等价于最大化它们节点谱嵌入之间的统计依赖性。\(2\) 我们提出了 fGOT-GDL，一种使用 \(fGOT\) 作为重心比较度量以捕捉全局结构属性，并使用 \(sfGOT\) 作为处理没有已知节点对应关系图的可处理重建损失的 GDL 框架。\(3\) 在基准数据集上的实验表明，该方法在聚类和分类任务上相对于现有 \(GDL\) 方法具有竞争力。

## 2背景

符号\.我们用其邻接矩阵\(\mathbf{A}\in\mathbb{R}_{+}^{N\times N}\)和非归一化拉普拉斯矩阵\(\mathbf{L}=\mathbf{D}-\mathbf{A}\in\mathbb{R}^{N\times N}\)来表示一个具有\(N\)个节点的图\(G\)，其中\(\mathbf{D}=\operatorname{diag}(\mathbf{A}\mathbf{1}_{N})\)是度矩阵。由于\(\mathbf{A}\)和\(\mathbf{L}\)是一一对应的，我们可以互换使用它们。我们将\(\mathbf{I}_{N}\in\mathbb{R}^{N\times N}\)表示为单位矩阵，\(\mathbf{1}_{N}\in\mathbb{R}^{N}\)表示为全1向量。当\(G\)具有\(d\)维节点属性时，我们记\(G=(\mathbf{A},\mathbf{X})\)，其中\(\mathbf{X}\in\mathbb{R}^{N\times d}\)；否则\(G=\mathbf{A}\)。给定一组观测图\(\{\mathbf{A}_{i}\in\mathbb{R}_{+}^{N_{i}\times N_{i}}\}_{i=1}^{I}\)，我们的目标是学习一个由\(K\)个原子图组成的字典\(\mathbf{U}_{1:K}=\{\mathbf{U}_{k}\in\mathbb{R}_{+}^{N_{0}\times N_{0}}\}_{k=1}^{K}\)，其中所有原子共享相同的支持大小\(N_{0}\)，并为每个观测图\(\mathbf{A}_{i}\)寻找一个嵌入向量\(\bm{\lambda}_{i}\in\Delta^{K-1}=\{\bm{\lambda}\in\mathbb{R}^{K}:\lambda_{j}\geq 0(\forall j),\sum_{j=1}^{K}\mathbf{\lambda}_{j}=1\}\)。注意，观测图的大小可能不同（\(N_{i}\neq N_{j}\)，当\(i\neq j\)时），并且不要求对齐。

### 2.1图字典学习 \(GDL\)

给定观测图\(\{\mathbf{A}_{i}\}_{i=1}^{I}\)，\(GDL\) 联合学习一个字典\(\mathbf{U}_{1:K}\)和嵌入\(\bm{\lambda}_{1:I}=\{\bm{\lambda}_{i}\}_{i=1}^{I}\)，使得每个\(\mathbf{A}_{i}\)都能被由\(\mathbf{U}_{1:K}\)和\(\lambda_{i}\)构建的重建\(\widetilde{\mathbf{A}}_{i}\)很好地近似：

\[
\min_{\{\mathbf{U}_{1:K},\bm{\lambda}_{1:I}\}\in\Omega}\sum_{i=1}^{I}d_{\mathrm{loss}}^{p}\left(\widetilde{\mathbf{A}}_{i},\mathbf{A}_{i}\right),
\]
（1）

其中\(\Omega\)是可行约束集，\(d_{\mathrm{loss}}\)是（可能大小不同的）重建\(\widetilde{\mathbf{A}}_{i}\)与观测图\(\mathbf{A}_{i}\)之间的距离度量，\(p\)是阶数。重建被定义为由\(\bm{\lambda}_{i}\)加权的原子的重心：

\[
\widetilde{\mathbf{A}}_{i}=b(\mathbf{U}_{1:K},\bm{\lambda}_{i})\triangleq\arg\min_{\mathbf{A}\in\Omega}\sum_{k=1}^{K}\lambda_{i,k}d_{\mathrm{b}}^{q}(\mathbf{A},\mathbf{U}_{k}),
\]
（2）

其中\(d_{\mathrm{b}}\)是原子大小图之间的距离，\(q\)是其阶数。当所有图大小相同时，设置\(d_{\mathrm{b}}(\mathbf{A},\mathbf{U}_{k})=\|\mathbf{A}-\mathbf{U}_{k}\|_{F}\)（其中\(\lVert\cdot\rVert_{F}\)是Frobenius范数），\(q=2\)会将重心简化为线性组合\(\widetilde{\mathbf{A}}_{i}=\sum_{k=1}^{K}\bm{\lambda}_{i,k}\mathbf{U}_{k}\)，但这无法处理大小不同或节点对应未知的图。这在\[28 (https://arxiv.org/html/2609.05919#bib.bib28),26 (https://arxiv.org/html/2609.05919#bib.bib26)\]中通过使用\(GW\)差异\[15 (https://arxiv.org/html/2609.05919#bib.bib16)\]实例化\(d_{\mathrm{loss}}\)和\(d_{\mathrm{b}}\)来解决，从而得到\(GW\)分解 \(GWF\) 模型，该模型通过对齐节点来处理大小不匹配问题，但如第1节所述，它依赖于成对距离，未能反映图的全局结构属性。

### 2.2图最优传输 \(GOT\) 及其变体

GOT\.GOT\[12 (https://arxiv.org/html/2609.05919#bib.bib21)\]将具有拉普拉斯矩阵\(\mathbf{L}\)的图\(\mathbf{A}\in\mathbb{R}^{N\times N}\)表示为一个关于平滑图信号\(\mathbf{x}\in\mathbb{R}^{N}\)的分布——这些信号在连通节点上缓慢变化。这种平滑性自然地由一个以拉普拉斯伪逆为协方差的零均值高斯分布\(\nu=\mathcal{N}(0,\mathbf{L}^{\dagger})\)编码，因为\(\mathbf{L}^{\dagger}\)的低频（最小特征值）模式占主导地位并编码全局连通性，而高频模式捕捉局部变化。对于两个大小相同且具有分布\(\nu_{1}=\mathcal{N}(0,\mathbf{L}_{1}^{\dagger})\)和\(\nu_{2}=\mathcal{N}(0,\mathbf{L}_{2}^{\dagger})\)的图，\(GOT\)距离通过Bures-Wasserstein \(BW\)距离\[2 (https://arxiv.org/html/2609.05919#bib.bib5)\]计算：

\[
\mathcal{W}_{2}^{2}(\nu_{1},\nu_{2})=\operatorname{tr}(\mathbf{L}_{1}^{\dagger})+\operatorname{tr}(\mathbf{L}_{2}^{\dagger})-2\operatorname{tr}\left[\left(\mathbf{L}_{1}^{\dagger/2}\mathbf{L}_{2}^{\dagger}\mathbf{L}_{1}^{\dagger/2}\right)^{1/2}\right].
\]
（3）

fGOT\.为了控制强调哪些谱尺度，\(fGOT\)\[13 (https://arxiv.org/html/2609.05919#bib.bib14)\]通过一个*图滤波器*\(g\)将\(GOT\)推广，其谱定义为\(g(\mathbf{L})=\mathbf{U}\hat{g}(\Lambda)\mathbf{U}^{\top}\)，对于\(\mathbf{L}=\mathbf{U}\Lambda\mathbf{U}^{\top}\)，其中\(\hat{g}:\mathbb{R}_{>0}\to\mathbb{R}_{>0}\)且\(\hat{g}(0)=0\)是*频率响应*，逐元素应用于特征值。将噪声\(\mathbf{w}\sim\mathcal{N}(0,\mathbf{I}_{N})\)通过滤波器得到\(\mathbf{x}_{f}=g(\mathbf{L})\mathbf{w}\sim\mathcal{N}(0,g^{2}(\mathbf{L}))\)。然后\(fGOT\)距离通过两个图的滤波信号分布\(\nu_{1,g}=\mathcal{N}(0,g^{2}(\mathbf{L}_{1}))\)和\(\nu_{2,g}=\mathcal{N}(0,g^{2}(\mathbf{L}_{2}))\)的\(BW\)距离计算：

\[
\begin{split}\mathcal{W}_{2}^{2}(\nu_{1,g},\nu_{2,g})&=\operatorname{tr}(g^{2}(\mathbf{L}_{1}))+\operatorname{tr}(g^{2}(\mathbf{L}_{2}))\\ &-2\operatorname{tr}\left[\left(g(\mathbf{L}_{1})g^{2}(\mathbf{L}_{2})g(\mathbf{L}_{1})\right)^{1/2}\right].\end{split}
\]
（4）

常见的滤波器选择包括\(g(\mathbf{L})=\mathbf{L}^{\dagger/2}\)、\(g(\mathbf{L})=\mathbf{L}^{2}\)和\(g(\mathbf{L})=\exp(-0.8\mathbf{L})\)，每种都优先考虑不同的谱尺度。

sfGOT\.（3）和（4）中的两个距离都假设节点对应已知。在未知对齐的情况下，我们在置换矩阵\(\mathbf{P}\in\mathcal{C}_{\mathrm{perm}}=\left\{\mathbf{P}\in\{0,1\}^{N\times N}:\mathbf{P}\mathbf{1}_{N}=\mathbf{1}_{N},\,\mathbf{P}^{\top}\mathbf{1}_{N}=\mathbf{1}_{N}\right\}\)上进行优化，比较\(\nu_{1,g}\)与置换后的分布\(\nu_{2,g,\mathbf{P}}=\mathcal{N}(0,g^{2}(\mathbf{P}\mathbf{L}_{2}\mathbf{P}^{\top}))\)：

\[
\begin{split}&d_{\mathrm{fGOT},g}^{2}(\mathbf{A}_{1},\mathbf{A}_{2})=\min_{\mathbf{P}\in\mathcal{C}_{\mathrm{perm}}}\mathcal{W}_{2}^{2}(\nu_{1,g},\nu_{2,g,\mathbf{P}})\\ &=\min_{\mathbf{P}\in\mathcal{C}_{\mathrm{perm}}}\Big[\operatorname{tr}(g^{2}(\mathbf{L}_{1}))+\operatorname{tr}(g^{2}(\mathbf{L}_{2}))\\ &-2\operatorname{tr}\left[\left(g(\mathbf{L}_{1})g^{2}(\mathbf{P}\mathbf{L}_{2}\mathbf{P}^{\top})g(\mathbf{L}_{1})\right)^{1/2}\right]\Big].\end{split}
\]
（5）

由于\(\mathbf{P}\)出现在矩阵平方根下，求解（5）在计算上是难以处理的。\[13 (https://arxiv.org/html/2609.05919#bib.bib14)\]转而用一个可处理的替代\(\widetilde{\mathcal{W}}_{2}^{2}\)替代\(\mathcal{W}_{2}^{2}\)，得到替代\(fGOT\) \(sfGOT\)距离：

\[
\begin{split}&d_{\mathrm{sfGOT},g}^{2}(\mathbf{A}_{1},\mathbf{A}_{2})=\min_{\mathbf{P}\in\mathcal{C}_{\mathrm{perm}}}\widetilde{\mathcal{W}}_{2}^{2}(\nu_{1,g},\nu_{2,g,\mathbf{P}})\\ &=\min_{\mathbf{P}\in\mathcal{C}_{\mathrm{perm}}}\Big[\operatorname{tr}(g^{2}(\mathbf{L}_{1}))+\operatorname{tr}(g^{2}(\mathbf{L}_{2}))\\ &-2\langle g(\mathbf{L}_{1})\mathbf{P}g(\mathbf{L}_{2}),\mathbf{P}\rangle\Big].\end{split}
\]
（6）

引理1表明\(\widetilde{\mathcal{W}}_{2}^{2}\)是\(\mathcal{W}_{2}^{2}\)的上界，这意味着（5）中的\(d_{\mathrm{fGOT},g}^{2}\)以（6）中的\(d_{\mathrm{sfGOT},g}^{2}\)为上界。

###### 引理1（\[13 (https://arxiv.org/html/2609.05919#bib.bib14)\]）。

对于任何图滤波器\(g(\cdot)\)和\(\mathbf{P}\in\mathcal{C}_{\mathrm{perm}}\)，\(\mathcal{W}_{2}^{2}(\nu_{1,g},\nu_{2,g,\mathbf{P}})\leq\widetilde{\mathcal{W}}_{2}^{2}(\nu_{1,g},\nu_{2,g,\mathbf{P}})\)；因此，\(d_{\mathrm{fGOT},g}^{2}\leq d_{\mathrm{sfGOT},g}^{2}\)。

## 3提出的方法

我们提出两个主要贡献：从Hilbert-Schmidt独立性准则 \(HSIC\)\[7 (https://arxiv.org/html/2609.05919#bib.bib9)\]的角度对\(sfGOT\)距离（6）的新解释，以及fGOT-GDL，一种使用\(fGOT\)和\(sfGOT\)作为图比较