A dictionary learning framework for graphs via filters and optimal transport

# A Dictionary Learning Framework for Graphs via Filters and Optimal Transport
Source: [https://arxiv.org/html/2609.05919](https://arxiv.org/html/2609.05919)
###### Abstract

We propose a graph dictionary learning \(GDL\) framework where each graph is represented as a zero\-mean Gaussian distribution derived from its filtered Laplacian\. Each observed graph is approximated by a barycenter over learned atom graphs, computed under the filter graph distance \(fGOT\) – a graph comparison metric sensitive to global structural properties\. The reconstruction error between the observed graph and its barycenter is measured by the surrogate fGOT \(sfGOT\) distance, a tractable approximation of fGOT that handles graphs without known node correspondence, and is minimized end\-to\-end via backpropagation\. We further provide a novel interpretation of sfGOT through the lens of the Hilbert\-Schmidt Independence Criterion, showing that minimizing the sfGOT distance between two graphs is equivalent to maximizing statistical dependence between the spectral embedding of their nodes\. Experiments on benchmark datasets demonstrate competitive performance over existing GDL methods on graph clustering and classification tasks\.

###### Index Terms:

Dictionary Learning; Graph Optimal Transport\.

††address:Graduate School of Information Science and Technology, Hokkaido University
[jinchuan\.liao\.v1@elms\.hokudai\.ac\.jp](mailto:[email protected])[hai@ist\.hokudai\.ac\.jp](mailto:[email protected])## 1Introduction

Learning with graph\-structured data has attracted significant interests from the machine learning and signal processing communities, with applications in bioinformatics, cheminformatics, and social network analysis\[[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)\]\. Approaches to this problem typically rely on graph kernels, distances and latent space representations, applied in supervised, unsupervised or semi\-supervised settings\[[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)\]\.

In this work, we focus on dictionary learning \(DL\) for graphs, which is an unsupervised learning framework that learns a set of basis, called*atoms*, constituting*dictionary*\[[25](https://arxiv.org/html/2609.05919#bib.bib25),[10](https://arxiv.org/html/2609.05919#bib.bib12)\]\. Atoms are inferred by minimizing a reconstruction error when approximating each input as a weighted combination of atoms\. The resulting combination coefficients serve as latent representations for downstream tasks such as classification and clustering\. For graph\-structured data, graph dictionary learning \(GDL\) frameworks based on Gromov\-Wasserstein \(GW\) discrepancy\[[15](https://arxiv.org/html/2609.05919#bib.bib16)\]have been proposed to handle graphs of varying sizes and without node correspondence\[[28](https://arxiv.org/html/2609.05919#bib.bib28),[26](https://arxiv.org/html/2609.05919#bib.bib26)\]\. However, GW compares graphs via pairwise node distances \(e\.g\., shortest\-path distances\), which primarily reflect local neighborhood structure rather than global patterns, thus failing to capture the global structure of graphs\.

Graph Optimal Transport \(GOT\)\[[12](https://arxiv.org/html/2609.05919#bib.bib21)\]offers an alternative by representing each graph as a zero\-mean Gaussian distribution whose covariance is derived from the graph Laplacian pseudo\-inverse, enabling comparison via the Wasserstein distance\. This was extended to filter graph distances \(fGOT\)\[[13](https://arxiv.org/html/2609.05919#bib.bib14)\], which introduces a spectral filter providing flexible spectral control over which structural scales are emphasized\. To handle unknown node correspondence,\[[13](https://arxiv.org/html/2609.05919#bib.bib14)\]further introduced surrogate fGOT \(sfGOT\) as a tractable upper bound of fGOT\. Despite its practical utility, the structural meaning of sfGOT as a graph distance remains underexplored\.

Contributions\.\(1\) We provide a novel interpretation of sfGOT through the lens of Hilbert\-Schmidt Independence Criterion \(HSIC\)\[[7](https://arxiv.org/html/2609.05919#bib.bib9)\], showing that minimizing sfGOT between two graphs is equivalent to maximizing statistical dependence between the spectral embeddings of their nodes\. \(2\) We proposefGOT\-GDL, a GDL framework that uses fGOT as the barycenter comparison metric to capture global strucrural properties, and uses sfGOT as the tractable reconstruction loss for graphs without known node correspondence\. \(3\) Experiments on benchmark datasets demonstrate competitive performance over existing GDL methods on clustering and classification\.

## 2Background

Notation\.We represent a graphGGwithNNnodes by its adjacency matrix𝐀∈ℝ\+N×N\\mathbf\{A\}\\in\\mathbb\{R\}\_\{\+\}^\{N\\times N\}and unnormalized Laplacian𝐋=𝐃−𝐀∈ℝN×N\\mathbf\{L\}=\\mathbf\{D\}\-\\mathbf\{A\}\\in\\mathbb\{R\}^\{N\\times N\}, where𝐃=diag⁡\(𝐀𝟏N\)\\mathbf\{D\}=\\operatorname\{diag\}\(\\mathbf\{A\}\\mathbf\{1\}\_\{N\}\)is the degree matrix\. Since𝐀\\mathbf\{A\}and𝐋\\mathbf\{L\}are in one\-to\-one correspondence, we use them interchangeably\. We denote by𝐈N∈ℝN×N\\mathbf\{I\}\_\{N\}\\in\\mathbb\{R\}^\{N\\times N\}the identity matrix and𝟏N∈ℝN\\mathbf\{1\}\_\{N\}\\in\\mathbb\{R\}^\{N\}the all\-ones vector\. WhenGGhasdd\-dimensional node attributes, we writeG=\(𝐀,𝐗\)G=\(\\mathbf\{A\},\\mathbf\{X\}\)with𝐗∈ℝN×d\\mathbf\{X\}\\in\\mathbb\{R\}^\{N\\times d\}; otherwiseG=𝐀G=\\mathbf\{A\}\. Given a collection of observed graphs\{𝐀i∈ℝ\+Ni×Ni\}i=1I\\\{\\mathbf\{A\}\_\{i\}\\in\\mathbb\{R\}\_\{\+\}^\{N\_\{i\}\\times N\_\{i\}\}\\\}\_\{i=1\}^\{I\}, our goal is to learn a dictionary ofKKatom graphs𝐔1:K=\{𝐔k∈ℝ\+N0×N0\}k=1K\\mathbf\{U\}\_\{1:K\}=\\\{\\mathbf\{U\}\_\{k\}\\in\\mathbb\{R\}\_\{\+\}^\{N\_\{0\}\\times N\_\{0\}\}\\\}\_\{k=1\}^\{K\}, where all atoms share the same support sizeN0N\_\{0\}, and to represent each observed graph𝐀i\\mathbf\{A\}\_\{i\}by an embedding vector𝝀i∈ΔK−1=\{𝝀∈ℝK:λj≥0\(∀j\),∑j=1Kλj=1\}\\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\\\}\. Note that observed graphs may differ in size \(Ni≠NjN\_\{i\}\\neq N\_\{j\}fori≠ji\\neq j\) and are not assumed to be aligned\.

### 2\.1Graph Dictionary Learning \(GDL\)

Given the observed graphs\{𝐀i\}i=1I\\\{\\mathbf\{A\}\_\{i\}\\\}\_\{i=1\}^\{I\}, GDL jointly learns a dictionary𝐔1:K\\mathbf\{U\}\_\{1:K\}, and embeddings𝝀1:I=\{𝝀i\}i=1I\\bm\{\\lambda\}\_\{1:I\}=\\\{\\bm\{\\lambda\}\_\{i\}\\\}\_\{i=1\}^\{I\}, such that each𝐀i\\mathbf\{A\}\_\{i\}is well approximated by a reconstruction𝐀~i\\widetilde\{\\mathbf\{A\}\}\_\{i\}built from𝐔1:K\\mathbf\{U\}\_\{1:K\}andλi\\lambda\_\{i\}:

min\{𝐔1:K,𝝀1:I\}∈Ω∑i=1Idlossp\(𝐀~i,𝐀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\)whereΩ\\Omegais the feasible constraint set,dlossd\_\{\\mathrm\{loss\}\}is a distance measure between the \(possibly different\-sized\) reconstruction𝐀~i\\widetilde\{\\mathbf\{A\}\}\_\{i\}and observed graph𝐀i\\mathbf\{A\}\_\{i\}, andppis the order\. The reconstruction is defined as the barycenter of the atoms weighted by𝝀i\\bm\{\\lambda\}\_\{i\}:

𝐀~i=b\(𝐔1:K,𝝀i\)≜argmin𝐀∈Ω∑k=1Kλi,kdbq\(𝐀,𝐔k\),\\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\)wheredbd\_\{\\mathrm\{b\}\}is a distance between atom\-sized graphs andqqis its order\. When all graphs share the same size, settingdb​\(𝐀,𝐔k\)=‖𝐀−𝐔k‖Fd\_\{\\mathrm\{b\}\}\(\\mathbf\{A\},\\mathbf\{U\}\_\{k\}\)=\\\|\\mathbf\{A\}\-\\mathbf\{U\}\_\{k\}\\\|\_\{F\}\(where∥⋅∥F\\lVert\\cdot\\rVert\_\{F\}is the Frobenius norm\),q=2q=2reduces the barycenter to a linear combination𝐀~i=∑k=1K𝝀i,k​𝐔k\\widetilde\{\\mathbf\{A\}\}\_\{i\}=\\sum\_\{k=1\}^\{K\}\\bm\{\\lambda\}\_\{i,k\}\\mathbf\{U\}\_\{k\}, but this cannot handle graphs of varying sizes or unknown node correspondence\. This is addressed in\[[28](https://arxiv.org/html/2609.05919#bib.bib28),[26](https://arxiv.org/html/2609.05919#bib.bib26)\]by instantiatingdlossd\_\{\\mathrm\{loss\}\}anddbd\_\{\\mathrm\{b\}\}with the GW discrepancy\[[15](https://arxiv.org/html/2609.05919#bib.bib16)\], yielding the GW Factorization \(GWF\) model, which aligns nodes to handle size mismatch but, as discussed in Section 1, relies on pairwise distances, failing to reflect global structural properties of graphs\.

### 2\.2Graph optimal transport \(GOT\) and its variants

GOT\.GOT\[[12](https://arxiv.org/html/2609.05919#bib.bib21)\]represents a graph𝐀∈ℝN×N\\mathbf\{A\}\\in\\mathbb\{R\}^\{N\\times N\}with Laplacian𝐋\\mathbf\{L\}as a distribution over smooth graph signal𝐱∈ℝN\\mathbf\{x\}\\in\\mathbb\{R\}^\{N\}– signals that vary slowly across connected nodes\. Such smoothness is naturally encoded by a zero\-mean Gaussian with the Laplacian pseudo\-inverse as covariance,ν=𝒩⁡\(0,𝐋†\)\\nu=\\mathcal\{N\}\(0,\\mathbf\{L\}^\{\\dagger\}\), since low\-frequency \(smallest\-eigenvalue\) modes of𝐋†\\mathbf\{L\}^\{\\dagger\}dominate and encode global connectivity, while high\-frequency modes capture local variation\. For two graphs of the same size with distributionsν1=𝒩⁡\(0,𝐋1†\)\\nu\_\{1\}=\\mathcal\{N\}\(0,\\mathbf\{L\}\_\{1\}^\{\\dagger\}\)andν2=𝒩⁡\(0,𝐋2†\)\\nu\_\{2\}=\\mathcal\{N\}\(0,\\mathbf\{L\}\_\{2\}^\{\\dagger\}\), the GOT distance is computed by the Bures\-Wasserstein \(BW\) distance\[[2](https://arxiv.org/html/2609.05919#bib.bib5)\]:

𝒲22\(ν1,ν2\)=tr\(𝐋1†\)\+tr\(𝐋2†\)−2tr\[\(𝐋1†/2𝐋2†𝐋1†/2\)1/2\]\.\\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\.To control which spectral scales are emphasized, fGOT\[[13](https://arxiv.org/html/2609.05919#bib.bib14)\]generalizes GOT via a*graph filter*gg, defined spectrally asg⁡\(𝐋\)=𝐔​g^​\(Λ\)​𝐔⊤g\(\\mathbf\{L\}\)=\\mathbf\{U\}\\hat\{g\}\(\\Lambda\)\\mathbf\{U\}^\{\\top\}for𝐋=𝐔​Λ​𝐔⊤\\mathbf\{L\}=\\mathbf\{U\}\\Lambda\\mathbf\{U\}^\{\\top\}, whereg^:ℝ\>0→ℝ\>0\\hat\{g\}:\\mathbb\{R\}\_\{\>0\}\\to\\mathbb\{R\}\_\{\>0\}withg^​\(0\)=0\\hat\{g\}\(0\)=0is the*frequency response*applied elementwise to the eigenvalues\. Passing while noise𝐰∼𝒩⁡\(0,𝐈N\)\\mathbf\{w\}\\sim\\mathcal\{N\}\(0,\\mathbf\{I\}\_\{N\}\)through the filter yields𝐱f=g⁡\(𝐋\)​𝐰∼𝒩⁡\(0,g2​\(𝐋\)\)\\mathbf\{x\}\_\{f\}=g\(\\mathbf\{L\}\)\\mathbf\{w\}\\sim\\mathcal\{N\}\(0,g^\{2\}\(\\mathbf\{L\}\)\)\. The fGOT distance is then computed by the BW distance between two graphs’ filtered\-signal distributionsν1,g=𝒩⁡\(0,g2​\(𝐋1\)\)\\nu\_\{1,g\}=\\mathcal\{N\}\(0,g^\{2\}\(\\mathbf\{L\}\_\{1\}\)\)andν2,g=𝒩⁡\(0,g2​\(𝐋2\)\)\\nu\_\{2,g\}=\\mathcal\{N\}\(0,g^\{2\}\(\\mathbf\{L\}\_\{2\}\)\):

𝒲22​\(ν1,g,ν2,g\)=tr⁡\(g2​\(𝐋1\)\)\+tr⁡\(g2​\(𝐋2\)\)−2​tr⁡\[\(g⁡\(𝐋1\)​g2​\(𝐋2\)​g​\(𝐋1\)\)1/2\]\.\\displaystyle\\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\)
Common choices of filters includeg\(𝐋\)=𝐋†/2g\(\\mathbf\{L\}\)=\\mathbf\{L\}^\{\\dagger/2\},g⁡\(𝐋\)=𝐋2g\(\\mathbf\{L\}\)=\\mathbf\{L\}^\{2\}, andg⁡\(𝐋\)=exp⁡\(−0\.8​𝐋\)g\(\\mathbf\{L\}\)=\\exp\(\-0\.8\\mathbf\{L\}\), each prioritizing a different spectral scale\.

sfGOT\.Both distances in \([3](https://arxiv.org/html/2609.05919#S2.E3)\) and \([4](https://arxiv.org/html/2609.05919#S2.E4)\) assume known node correspondence\. Under unknown alignment, we optimize over permutations𝐏∈𝒞perm=\{𝐏∈\{0,1\}N×N:𝐏𝟏N=𝟏N,𝐏⊤𝟏N=𝟏N\}\\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\\\}, comparingν1,g\\nu\_\{1,g\}to the permuted distributionν2,g,𝐏=𝒩⁡\(0,g2​\(𝐏𝐋2​𝐏⊤\)\)\\nu\_\{2,g,\\mathbf\{P\}\}=\\mathcal\{N\}\(0,g^\{2\}\(\\mathbf\{P\}\\mathbf\{L\}\_\{2\}\\mathbf\{P\}^\{\\top\}\)\):

dfGOT,g2​\(𝐀1,𝐀2\)=min𝐏∈𝒞perm⁡𝒲22​\(ν1,g,ν2,g,𝐏\)=min𝐏∈𝒞perm\[tr\(g2\(𝐋1\)\)\+tr\(g2\(𝐋2\)\)−2tr\[\(g\(𝐋1\)g2\(𝐏𝐋2𝐏⊤\)g\(𝐋1\)\)1/2\]\]\.\\displaystyle\\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\)Since𝐏\\mathbf\{P\}appears under a matrix square root, solving \([5](https://arxiv.org/html/2609.05919#S2.E5)\) is computationally intractable\.\[[13](https://arxiv.org/html/2609.05919#bib.bib14)\]instead replaces𝒲22\\mathcal\{W\}\_\{2\}^\{2\}with a tractable surrogate𝒲~22\\widetilde\{\\mathcal\{W\}\}\_\{2\}^\{2\}, giving the surrogate fGOT \(sfGOT\) distance:

dsfGOT,g2​\(𝐀1,𝐀2\)=min𝐏∈𝒞perm⁡𝒲~22​\(ν1,g,ν2,g,𝐏\)=min𝐏∈𝒞perm\[tr\(g2\(𝐋1\)\)\+tr\(g2\(𝐋2\)\)−2⟨g\(𝐋1\)𝐏g\(𝐋2\),𝐏⟩\]\.\\displaystyle\\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\)Lemma[1](https://arxiv.org/html/2609.05919#Thmlemma1)shows that𝒲~22\\widetilde\{\\mathcal\{W\}\}\_\{2\}^\{2\}is an upper bound of𝒲22\\mathcal\{W\}\_\{2\}^\{2\}, implying thatdfGOT,g2d\_\{\\mathrm\{fGOT\},g\}^\{2\}\([5](https://arxiv.org/html/2609.05919#S2.E5)\) is upper bounded bydsfGOT,g2d\_\{\\mathrm\{sfGOT\},g\}^\{2\}\([6](https://arxiv.org/html/2609.05919#S2.E6)\)\.

###### Lemma 1\(\[[13](https://arxiv.org/html/2609.05919#bib.bib14)\]\)\.

For any graph filterg⁡\(⋅\)g\(\\cdot\)and𝐏∈𝒞perm\\mathbf\{P\}\\in\\mathcal\{C\}\_\{\\mathrm\{perm\}\},𝒲22​\(ν1,g,ν2,g,𝐏\)≤𝒲~22​\(ν1,g,ν2,g,𝐏\)\\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\}\}\); consequently,dfGOT,g2≤dsfGOT,g2d\_\{\\mathrm\{fGOT\},g\}^\{2\}\\leq d\_\{\\mathrm\{sfGOT\},g\}^\{2\}\.

## 3Proposed Method

We present two main contributions: a novel interpretation of the sfGOT distance \([6](https://arxiv.org/html/2609.05919#S2.E6)\) through the lens of the Hilbert\-Schmidt independence criterion \(HSIC\)\[[7](https://arxiv.org/html/2609.05919#bib.bib9)\], andfGOT\-GDL, a GDL model using fGOT and sfGOT as the graph comparison metrics\.

### 3\.1HSIC\-based interpretation of sfGOT

As shown in Lemma[1](https://arxiv.org/html/2609.05919#Thmlemma1), the sfGOT distance is a tractable upper bound of fGOT, circumventing the matrix square root in \([5](https://arxiv.org/html/2609.05919#S2.E5)\)\. However, its structural meaning as a graph distance remains underexplored\. We now provide a new interpretation of sfGOT via HSIC\.

###### Definition 1\(HSIC\[[7](https://arxiv.org/html/2609.05919#bib.bib9)\]\)\.

Let𝐱∼p\\mathbf\{x\}\\sim pand𝐳∼q\\mathbf\{z\}\\sim qbe random variables on domains𝒳\\mathcal\{X\}and𝒵\\mathcal\{Z\}, with RKHS kernelsk1:𝒳×𝒳→ℝk\_\{1\}:\\mathcal\{X\}\\times\\mathcal\{X\}\\to\\mathbb\{R\}andk2:𝒵×𝒵→ℝk\_\{2\}:\\mathcal\{Z\}\\times\\mathcal\{Z\}\\to\\mathbb\{R\}\. HSIC is defined as the squared Hilbert\-Schmidt norm of the cross\-covariance operator𝒞𝐱𝐳\\mathcal\{C\}\_\{\\mathbf\{x\}\\mathbf\{z\}\}:HSIC⁡\(p,q\)=‖𝒞𝐱𝐳‖HS2\\mathrm\{HSIC\}\(p,q\)=\\\|\\mathcal\{C\}\_\{\\mathbf\{x\}\\mathbf\{z\}\}\\\|\_\{\\mathrm\{HS\}\}^\{2\}\. GivenNNi\.i\.d\. samples\{\(𝐱i,𝐳i\)\}i=1N\\\{\(\\mathbf\{x\}\_\{i\},\\mathbf\{z\}\_\{i\}\)\\\}\_\{i=1\}^\{N\}, the empirical estimator is:

HSIC^​\(p,q\)=1\(N−1\)2​tr⁡\(𝐊1​𝐇𝐊2​𝐇\),\\widehat\{\\mathrm\{HSIC\}\}\(p,q\)=\\frac\{1\}\{\(N\-1\)^\{2\}\}\\operatorname\{tr\}\(\\mathbf\{K\}\_\{1\}\\mathbf\{H\}\\mathbf\{K\}\_\{2\}\\mathbf\{H\}\),where\(𝐊1\)a​b=k1​\(𝐱a,𝐱b\)\(\\mathbf\{K\}\_\{1\}\)\_\{ab\}=k\_\{1\}\(\\mathbf\{x\}\_\{a\},\\mathbf\{x\}\_\{b\}\),\(𝐊2\)c​d=k2​\(𝐳c,𝐳d\)\(\\mathbf\{K\}\_\{2\}\)\_\{cd\}=k\_\{2\}\(\\mathbf\{z\}\_\{c\},\\mathbf\{z\}\_\{d\}\)are the Gram matrices and𝐇=𝐈N−1N​𝟏N​𝟏N⊤\\mathbf\{H\}=\\mathbf\{I\}\_\{N\}\-\\frac\{1\}\{N\}\\mathbf\{1\}\_\{N\}\\mathbf\{1\}\_\{N\}^\{\\top\}is the centering matrix\.HSIC⁡\(p,q\)=0\\mathrm\{HSIC\}\(p,q\)=0iff𝐱\\mathbf\{x\}and𝐳\\mathbf\{z\}are independent \(for universal kernels\)\.

Rather than viewing a graph as a generator of smooth graph signals \(as in GOT/fGOT\), we treat each graph’sNNnodes, embedded via the filtered spectrum, as samples of a random vector, and interpretg⁡\(𝐋1\)g\(\\mathbf\{L\}\_\{1\}\),g⁡\(𝐋2\)g\(\\mathbf\{L\}\_\{2\}\)as kernel Gram matrices over the nodes of𝐀1\\mathbf\{A\}\_\{1\}and𝐀2\\mathbf\{A\}\_\{2\}, respectively\. Sinceg^​\(0\)=0\\hat\{g\}\(0\)=0, the filtered Laplacian is centered, i\.e\.,𝐇​g​\(𝐋\)​𝐇=g⁡\(𝐋\)\\mathbf\{H\}g\(\\mathbf\{L\}\)\\mathbf\{H\}=g\(\\mathbf\{L\}\), so no additional centering is required\. Using the identityg⁡\(𝐏𝐇2​𝐏⊤\)=𝐏​g​\(𝐋2\)​𝐏⊤g\(\\mathbf\{P\}\\mathbf\{H\}\_\{2\}\\mathbf\{P\}^\{\\top\}\)=\\mathbf\{P\}g\(\\mathbf\{L\}\_\{2\}\)\\mathbf\{P\}^\{\\top\}for𝐏∈𝒞perm\\mathbf\{P\}\\in\\mathcal\{C\}\_\{\\mathrm\{perm\}\}\[[13](https://arxiv.org/html/2609.05919#bib.bib14)\], the empirical HSIC between𝐀1\\mathbf\{A\}\_\{1\}and the permuted𝐏𝐀2​𝐏⊤\\mathbf\{P\}\\mathbf\{A\}\_\{2\}\\mathbf\{P\}^\{\\top\}defines a similarity:

s⁡\(𝐀1,𝐀2\)\\displaystyle s\(\\mathbf\{A\}\_\{1\},\\mathbf\{A\}\_\{2\}\)=max𝐏∈𝒞perm⁡\(N−1\)2​HSIC^​\(𝐀1,𝐏𝐀2​𝐏⊤\)\\displaystyle=\\max\_\{\\mathbf\{P\}\\in\\mathcal\{C\}\_\{\\mathrm\{perm\}\}\}\(N\-1\)^\{2\}\\widehat\{\\mathrm\{HSIC\}\}\\left\(\\mathbf\{A\}\_\{1\},\\mathbf\{P\}\\mathbf\{A\}\_\{2\}\\mathbf\{P\}^\{\\top\}\\right\)=max𝐏∈𝒞perm⁡tr⁡\(g⁡\(𝐋1\)​𝐏​g​\(𝐋2\)​𝐏⊤\),\\displaystyle=\\max\_\{\\mathbf\{P\}\\in\\mathcal\{C\}\_\{\\mathrm\{perm\}\}\}\\operatorname\{tr\}\\left\(g\(\\mathbf\{L\}\_\{1\}\)\\mathbf\{P\}g\(\\mathbf\{L\}\_\{2\}\)\\mathbf\{P\}^\{\\top\}\\right\),\(7\)i\.e\.,s⁡\(𝐀1,𝐀2\)s\(\\mathbf\{A\}\_\{1\},\\mathbf\{A\}\_\{2\}\)finds the node alignment that maximizes the statistical dependence between the spectral embeddings of𝐀1\\mathbf\{A\}\_\{1\}’s nodes and𝐀2\\mathbf\{A\}\_\{2\}’s nodes\. Comparing \([7](https://arxiv.org/html/2609.05919#S3.E7)\) to the sfGOT objective \([6](https://arxiv.org/html/2609.05919#S2.E6)\), we obtain:

dsfGOT,g2​\(𝐀1,𝐀2\)=s⁡\(𝐀1,𝐀1\)\+s⁡\(𝐀2,𝐀2\)−2​s​\(𝐀1,𝐀2\),\\displaystyle\\begin\{split\}d^\{2\}\_\{\\mathrm\{sfGOT\},g\}\(\\mathbf\{A\}\_\{1\},\\mathbf\{A\}\_\{2\}\)&=\\operatorname\{s\}\(\\mathbf\{A\}\_\{1\},\\mathbf\{A\}\_\{1\}\)\+\\operatorname\{s\}\(\\mathbf\{A\}\_\{2\},\\mathbf\{A\}\_\{2\}\)\-2s\(\\mathbf\{A\}\_\{1\},\\mathbf\{A\}\_\{2\}\),\\end\{split\}where we usedg⁡\(𝐏𝐋2​𝐏⊤\)=𝐏​g​\(𝐋2\)​𝐏⊤g\(\\mathbf\{P\}\\mathbf\{L\}\_\{2\}\\mathbf\{P\}^\{\\top\}\)=\\mathbf\{P\}g\(\\mathbf\{L\}\_\{2\}\)\\mathbf\{P\}^\{\\top\}from Lemma 1 of\[[13](https://arxiv.org/html/2609.05919#bib.bib14)\], and𝐏⊤​𝐏=𝐈N\\mathbf\{P\}^\{\\top\}\\mathbf\{P\}=\\mathbf\{I\}\_\{N\}\. So minimizing sfGOT between𝐀1\\mathbf\{A\}\_\{1\}and𝐀2\\mathbf\{A\}\_\{2\}is equivalent to maximizings⁡\(𝐀1,𝐀2\)s\(\\mathbf\{A\}\_\{1\},\\mathbf\{A\}\_\{2\}\)–the dependence between these two graphs’ filtered spectral embeddings\. Proposition[1](https://arxiv.org/html/2609.05919#Thmproposition1)gives an eigenmode decomposition ofs⁡\(𝐀1,𝐀2\)s\(\\mathbf\{A\}\_\{1\},\\mathbf\{A\}\_\{2\}\)\.

###### Proposition 1\.

Letg⁡\(𝐋1\)=𝐔​g^​\(Λ\)​𝐔⊤g\(\\mathbf\{L\}\_\{1\}\)=\\mathbf\{U\}\\hat\{g\}\(\\Lambda\)\\mathbf\{U\}^\{\\top\}andg⁡\(𝐋2\)=𝐕​g^​\(Ω\)​𝐕⊤g\(\\mathbf\{L\}\_\{2\}\)=\\mathbf\{V\}\\hat\{g\}\(\\Omega\)\\mathbf\{V\}^\{\\top\}be eigendecompositions with orthonormal𝐔=\[𝐮1,…,𝐮N\]\\mathbf\{U\}=\[\\mathbf\{u\}\_\{1\},\\dots,\\mathbf\{u\}\_\{N\}\],𝐕=\[𝐯1,…,𝐯N\]\\mathbf\{V\}=\[\\mathbf\{v\}\_\{1\},\\dots,\\mathbf\{v\}\_\{N\}\]and eigenvaluesΛ=diag⁡\(λ1,…,λN\)\\Lambda=\\operatorname\{diag\}\(\\lambda\_\{1\},\\dots,\\lambda\_\{N\}\),Ω=diag⁡\(ω1,…,ωN\)\\Omega=\\operatorname\{diag\}\(\\omega\_\{1\},\\dots,\\omega\_\{N\}\)\. Then

s⁡\(𝐀1,𝐀2\)=max⁡∑i,j=1N𝐏∈𝒞perm⁡g^​\(λi\)​g^​\(ωj\)​⟨𝐮i,𝐏𝐯j⟩2\.s\(\\mathbf\{A\}\_\{1\},\\mathbf\{A\}\_\{2\}\)=\\max\_\{\\mathbf\{P\}\\in\\mathcal\{C\}\_\{\\mathrm\{perm\}\}\}\\sum\_\{i,j=1\}^\{N\}\\hat\{g\}\(\\lambda\_\{i\}\)\\hat\{g\}\(\\omega\_\{j\}\)\\langle\\mathbf\{u\}\_\{i\},\\mathbf\{P\}\\mathbf\{v\}\_\{j\}\\rangle^\{2\}\.

###### Proof\.

By substituting the eigendecompositions and applying cyclicity of trace:

tr⁡\(g⁡\(𝐋1\)​𝐏​g​\(𝐋2\)​𝐏⊤\)\\displaystyle\\operatorname\{tr\}\\left\(g\(\\mathbf\{L\}\_\{1\}\)\\mathbf\{P\}g\(\\mathbf\{L\}\_\{2\}\)\\mathbf\{P\}^\{\\top\}\\right\)=tr⁡\(𝐔​g^​\(Λ\)​𝐔⊤​𝐏𝐕​g^​\(Ω\)​𝐕⊤​𝐏⊤\)\\displaystyle=\\operatorname\{tr\}\\left\(\\mathbf\{U\}\\hat\{g\}\(\\Lambda\)\\mathbf\{U\}^\{\\top\}\\mathbf\{P\}\\mathbf\{V\}\\hat\{g\}\(\\Omega\)\\mathbf\{V\}^\{\\top\}\\mathbf\{P\}^\{\\top\}\\right\)=tr⁡\(g^​\(Λ\)​𝐂​g^​\(Ω\)​𝐂⊤\),\\displaystyle=\\operatorname\{tr\}\\left\(\\hat\{g\}\(\\Lambda\)\\mathbf\{C\}\\hat\{g\}\(\\Omega\)\\mathbf\{C\}^\{\\top\}\\right\),where𝐂=𝐔⊤​𝐏𝐕\\mathbf\{C\}=\\mathbf\{U\}^\{\\top\}\\mathbf\{P\}\\mathbf\{V\}, with𝐂i​j=𝐮i⊤​𝐏𝐯j=⟨𝐮i,𝐏𝐯j⟩\\mathbf\{C\}\_\{ij\}=\\mathbf\{u\}\_\{i\}^\{\\top\}\\mathbf\{P\}\\mathbf\{v\}\_\{j\}=\\langle\\mathbf\{u\}\_\{i\},\\mathbf\{P\}\\mathbf\{v\}\_\{j\}\\rangle\. Expanding the trace over indices gives,

tr⁡\(g^​\(Λ\)​𝐂​g^​\(Ω\)​𝐂⊤\)=∑i,j=1Ng^​\(λi\)​g^​\(ωj\)​⟨𝐮i,𝐏𝐯j⟩2\.\\displaystyle\\operatorname\{tr\}\\left\(\\hat\{g\}\(\\Lambda\)\\mathbf\{C\}\\hat\{g\}\(\\Omega\)\\mathbf\{C\}^\{\\top\}\\right\)=\\sum\_\{i,j=1\}^\{N\}\\hat\{g\}\(\\lambda\_\{i\}\)\\hat\{g\}\(\\omega\_\{j\}\)\\langle\\mathbf\{u\}\_\{i\},\\mathbf\{P\}\\mathbf\{v\}\_\{j\}\\rangle^\{2\}\.∎

Proposition[1](https://arxiv.org/html/2609.05919#Thmproposition1)shows thats⁡\(𝐀1,𝐀2\)s\(\\mathbf\{A\}\_\{1\},\\mathbf\{A\}\_\{2\}\)measures how well theii\-th eigenmode𝐮i\\mathbf\{u\}\_\{i\}of𝐀1\\mathbf\{A\}\_\{1\}aligns with thejj\-th permuted eigenmode𝐏𝐯j\\mathbf\{P\}\\mathbf\{v\}\_\{j\}of𝐀2\\mathbf\{A\}\_\{2\}, weighed by their spectral energiesg^​\(λi\)​g^​\(ωj\)\\hat\{g\}\(\\lambda\_\{i\}\)\\hat\{g\}\(\\omega\_\{j\}\)\. Furthermore, the filterggcontrols which eigenmodes dominate this weighting: a low\-pass filter emphasizes global structure \(e\.g\., connectivity and community membership\), while a high\-pass filter emphasizes local variation \(e\.g\., node degrees\)\.

### 3\.2GDL with filters and optimal transport

We proposefGOT\-GDL, which setsdb=dfGOT,gd\_\{\\mathrm\{b\}\}=d\_\{\\mathrm\{fGOT\},g\},dloss=dsfGOT,gd\_\{\\mathrm\{loss\}\}=d\_\{\\mathrm\{sfGOT\},g\},p=2p=2,q=2q=2\. Training runs forTTepochs, each repeating three steps: \(1\) estimate each input graph’s barycenter via fGOT; \(2\) compute the reconstruction loss via sfGOT; \(3\) update parameters via backpropagation to minimize the total reconstruction loss\.

![Refer to caption](https://arxiv.org/html/2609.05919v1/figures/fig1_sbm_graph.png)\(a\)Synthetic SBM illustration
![Refer to caption](https://arxiv.org/html/2609.05919v1/figures/fig1_sbm_metric.png)\(b\)Recovery metrics

Figure 1:Comparison of GW\-based GDLs and fGOT\-GDL in recovering two\-class SBM community structure\.Barycenter via fGOT\.Settingdb=dfGOT,gd\_\{\\mathrm\{b\}\}=d\_\{\\mathrm\{fGOT\},g\}in \([2](https://arxiv.org/html/2609.05919#S2.E2)\) gives the Bures–Wasserstein Fréchet mean of\{νk,g=𝒩\(0,g2\(𝐋k\)\)\}k=1K\\\{\\nu\_\{k,g\}=\\mathcal\{N\}\(0,g^\{2\}\(\\mathbf\{L\}\_\{k\}\)\)\\\}\_\{k=1\}^\{K\}, where𝐋k\\mathbf\{L\}\_\{k\}is the Laplacian of atom𝐔k\\mathbf\{U\}\_\{k\}\. This is estimated by the fixed\-point iteration\[[8](https://arxiv.org/html/2609.05919#bib.bib10)\]\. For eachi=1,2,…,Ii=1,2,\\dots,I,

𝐒i,t\+1\\displaystyle\\mathbf\{S\}\_\{i,t\+1\}←𝐒i,t−1/2\(∑k=1Kλi,k\(𝐒i,t1/2𝚺k𝐒i,t1/2\)1/2\)2𝐒i,t−1/2,\\displaystyle\\leftarrow\\mathbf\{S\}\_\{i,t\}^\{\-1/2\}\\left\(\\sum\_\{k=1\}^\{K\}\\lambda\_\{i,k\}\\left\(\\mathbf\{S\}\_\{i,t\}^\{1/2\}\\bm\{\\Sigma\}\_\{k\}\\mathbf\{S\}\_\{i,t\}^\{1/2\}\\right\)^\{1/2\}\\right\)^\{2\}\\mathbf\{S\}\_\{i,t\}^\{\-1/2\},𝚺k\\displaystyle\\bm\{\\Sigma\}\_\{k\}=g2​\(𝐋k\+1N0​𝐈N0\)\.\\displaystyle=g^\{2\}\\left\(\\mathbf\{L\}\_\{k\}\+\\frac\{1\}\{N\_\{0\}\}\\mathbf\{I\}\_\{N\_\{0\}\}\\right\)\.\(8\)Afternbn\_\{b\}iterations, the barycenter Laplacian is𝐋~i=g−1​\(𝐒i,nb1/2\)−1N0​𝐈N0\\widetilde\{\\mathbf\{L\}\}\_\{i\}=g^\{\-1\}\(\\mathbf\{S\}\_\{i,n\_\{b\}\}^\{1/2\}\)\-\\frac\{1\}\{N\_\{0\}\}\\mathbf\{I\}\_\{N\_\{0\}\}, with adjacency𝐀~i=diag⁡\(𝐋~i\)−𝐋~i\\widetilde\{\\mathbf\{A\}\}\_\{i\}=\\operatorname\{diag\}\(\\widetilde\{\\mathbf\{L\}\}\_\{i\}\)\-\\widetilde\{\\mathbf\{L\}\}\_\{i\}\.

Table 1:K\-means clustering accuracy \(%\)\.Table 2:Graph classification accuracy \(%\)Reconstruction loss via sfGOT\.Settingdloss=dsfGOT,gd\_\{\\mathrm\{loss\}\}=d\_\{\\mathrm\{sfGOT\},g\}in \([1](https://arxiv.org/html/2609.05919#S2.E1)\), the main difficulty is that the constraint𝐏∈𝒞perm\\mathbf\{P\}\\in\\mathcal\{C\}\_\{\\mathrm\{perm\}\}makes \([6](https://arxiv.org/html/2609.05919#S2.E6)\) a discrete optimization with factorially many feasible solutions\. Following\[[12](https://arxiv.org/html/2609.05919#bib.bib21),[13](https://arxiv.org/html/2609.05919#bib.bib14)\], we relax𝒞perm\\mathcal\{C\}\_\{\\mathrm\{perm\}\}to the convex set of possible soft assignments for each pair of𝐀i\\mathbf\{A\}\_\{i\}and𝐀~i\\widetilde\{\\mathbf\{A\}\}\_\{i\}of possibly different sizesNiN\_\{i\}andN0N\_\{0\}:

𝒞fuzzy=\{𝐏∈\[0,1\]Ni×N0:𝐏𝟏N0=1Ni𝟏Ni,𝐏⊤𝟏Ni=1N0𝟏N0\}\.\\displaystyle\\mathcal\{C\}\_\{\\mathrm\{fuzzy\}\}=\\left\\\{\\mathbf\{P\}\\in\[0,1\]^\{N\_\{i\}\\times N\_\{0\}\}:\\mathbf\{P\}\\mathbf\{1\}\_\{N\_\{0\}\}=\\frac\{1\}\{N\_\{i\}\}\\mathbf\{1\}\_\{N\_\{i\}\},\\mathbf\{P\}^\{\\top\}\\mathbf\{1\}\_\{N\_\{i\}\}=\\frac\{1\}\{N\_\{0\}\}\\mathbf\{1\}\_\{N\_\{0\}\}\\right\\\}\.The sfGOT distance \([6](https://arxiv.org/html/2609.05919#S2.E6)\) is then approximated as:

dsfGOT,g2​\(𝐀i,𝐀~i\)≈\\displaystyle d^\{2\}\_\{\\mathrm\{sfGOT\},g\}\(\\mathbf\{A\}\_\{i\},\\widetilde\{\\mathbf\{A\}\}\_\{i\}\)\\approxtr⁡\(g2​\(𝐋i\)\)\+tr⁡\(g2​\(𝐋~i\)\)−2​max𝐏∈𝒞fuzzy​⟨g⁡\(𝐋i\)​𝐏​g​\(𝐋~i\),𝐏⟩\.\\displaystyle\\operatorname\{tr\}\(g^\{2\}\(\\mathbf\{L\}\_\{i\}\)\)\+\\operatorname\{tr\}\(g^\{2\}\(\\widetilde\{\\mathbf\{L\}\}\_\{i\}\)\)\-2\\max\_\{\\mathbf\{P\}\\in\\mathcal\{C\}\_\{\\mathrm\{fuzzy\}\}\}\\langle g\(\\mathbf\{L\}\_\{i\}\)\\mathbf\{P\}g\(\\widetilde\{\\mathbf\{L\}\}\_\{i\}\),\\mathbf\{P\}\\rangle\.
Since the first two terms are constant in𝐏\\mathbf\{P\}, this reduces to the quadratic optimization problem:max𝐏∈𝒞fuzzy⁡⟨g⁡\(𝐋i\)​𝐏​g​\(𝐋~i\),𝐏⟩\\max\_\{\\mathbf\{P\}\\in\\mathcal\{C\}\_\{\\mathrm\{fuzzy\}\}\}\\langle g\(\\mathbf\{L\}\_\{i\}\)\\mathbf\{P\}g\(\\widetilde\{\\mathbf\{L\}\}\_\{i\}\),\\mathbf\{P\}\\rangle, solved via the Sinkhorn\-Knopp algorithm\[[22](https://arxiv.org/html/2609.05919#bib.bib22),[9](https://arxiv.org/html/2609.05919#bib.bib11)\]overnoutn\_\{\\mathrm\{out\}\}outer iterations\. At outer iterationmm\(m≤noutm\\leq n\_\{\\mathrm\{out\}\}\), we fix one𝐏=𝐏\(m\)\\mathbf\{P\}=\\mathbf\{P\}^\{\(m\)\}, and solve the following entropy\-regularized problem byninn\_\{\\mathrm\{in\}\}inner Sinkhorn iterations\[[22](https://arxiv.org/html/2609.05919#bib.bib22),[4](https://arxiv.org/html/2609.05919#bib.bib3)\]:

max𝐏∈𝒞fuzzy⁡⟨g⁡\(𝐋i\)​𝐏\(m\)​g​\(𝐋~i\),𝐏⟩\+ε​ℋ​\(𝐏\)\.\\max\_\{\\mathbf\{P\}\\in\\mathcal\{C\}\_\{\\mathrm\{fuzzy\}\}\}\\langle g\(\\mathbf\{L\}\_\{i\}\)\\mathbf\{P\}^\{\(m\)\}g\(\\widetilde\{\\mathbf\{L\}\}\_\{i\}\),\\mathbf\{P\}\\rangle\+\\varepsilon\\mathcal\{H\}\(\\mathbf\{P\}\)\.\(9\)The final plan𝐏\(nout\)\\mathbf\{P\}^\{\(n\_\{\\mathrm\{out\}\}\)\}is then used to evaluatedsfGOT,gd\_\{\\mathrm\{sfGOT\},g\}\.

![Refer to caption](https://arxiv.org/html/2609.05919v1/figures/fig2_aids_heat.png)\(a\)AIDS
![Refer to caption](https://arxiv.org/html/2609.05919v1/figures/fig2_imdb_heat.png)\(b\)IMDB\-BINARY
![Refer to caption](https://arxiv.org/html/2609.05919v1/figures/fig2_protein_heat.png)\(c\)PROTEIN

Figure 2:Visualization of the adjacency matrices of atoms learned by fGOT\-GDL, using three datasets: AIDS, IMDB\-BINARY, PROTEIN\.Reparameterization\.Solving \([1](https://arxiv.org/html/2609.05919#S2.E1)\) is challenging due to the constraints on𝐔1:K\\mathbf\{U\}\_\{1:K\}and𝝀1:I\\bm\{\\lambda\}\_\{1:I\}\. To handle these constraints, we reformulate \([1](https://arxiv.org/html/2609.05919#S2.E1)\) as an unconstrained optimization problem via

𝐔k\\displaystyle\\mathbf\{U\}\_\{k\}=Φ⁡\(𝜽k\)=diag0⁡\(softplus⁡\(𝜽k\)\+softplus⁡\(𝜽k\)⊤2\),\\displaystyle=\\Phi\(\\bm\{\\theta\}\_\{k\}\)=\\operatorname\{diag\}\_\{0\}\\left\(\\frac\{\\operatorname\{softplus\}\(\\bm\{\\theta\}\_\{k\}\)\+\\operatorname\{softplus\}\(\\bm\{\\theta\}\_\{k\}\)^\{\\top\}\}\{2\}\\right\),𝝀i\\displaystyle\\bm\{\\lambda\}\_\{i\}=softmax⁡\(𝐳i\),\\displaystyle=\\operatorname\{softmax\}\(\\mathbf\{z\}\_\{i\}\),where𝜽k∈ℝN0×N0\\bm\{\\theta\}\_\{k\}\\in\\mathbb\{R\}^\{N\_\{0\}\\times N\_\{0\}\}and𝐳i∈ℝK\\mathbf\{z\}\_\{i\}\\in\\mathbb\{R\}^\{K\}are unconstrained parameters;diag0⁡\(⋅\)\\operatorname\{diag\}\_\{0\}\(\\cdot\)zeroes the diagonal elements;Φ⁡\(𝜽k\)\\Phi\(\\bm\{\\theta\}\_\{k\}\)ensures𝐔k\\mathbf\{U\}\_\{k\}is nonnegative, symmetric, zero\-diagonal;softmax⁡\(𝒛i\)\\operatorname\{softmax\}\(\\bm\{z\}\_\{i\}\)ensures𝝀i∈ΔK−1\\bm\{\\lambda\}\_\{i\}\\in\\Delta^\{K\-1\}\. This yields an unconstrained optimization problem,min𝜽1:K,𝒛1:I∑i=1IdsfGOT,g2\(𝐀~i,𝐀i\),\\min\_\{\\bm\{\\theta\}\_\{1:K\},\\bm\{z\}\_\{1:I\}\}\\sum\_\{i=1\}^\{I\}d^\{2\}\_\{\\mathrm\{sfGOT\},g\}\\left\(\\widetilde\{\\mathbf\{A\}\}\_\{i\},\\mathbf\{A\}\_\{i\}\\right\),where𝐀~i\\widetilde\{\\mathbf\{A\}\}\_\{i\}is estimated by minimizing∑k=1K𝝀i,k​dfGOT,g2​\(𝐀,Φ⁡\(𝜽k\)\)\\sum\_\{k=1\}^\{K\}\\bm\{\\lambda\}\_\{i,k\}d\_\{\\mathrm\{fGOT\},g\}^\{2\}\(\\mathbf\{A\},\\Phi\(\\bm\{\\theta\}\_\{k\}\)\), and𝝀i=softmax⁡\(𝐳i\)\\bm\{\\lambda\}\_\{i\}=\\operatorname\{softmax\}\(\\mathbf\{z\}\_\{i\}\)\. The parameters are updated end\-to\-end via backpropagation\.

## 4Experiments

### 4\.1Synthetic experiments

We evaluate whether the learned embedding can distinguish two community\-structure regimes using stochastic block model \(SBM\) graphs \(Fig\.[1](https://arxiv.org/html/2609.05919#S3.F1)\):Strong community\(pin=0\.45,pout=0\.01p\_\{\\mathrm\{in\}\}=0\.45,p\_\{\\mathrm\{out\}\}=0\.01, well\-separated\) andWeak community\(pin=0\.40,pout=0\.05p\_\{\\mathrm\{in\}\}=0\.40,p\_\{\\mathrm\{out\}\}=0\.05, subtler\)\. Each class has 25 graphs of 32 nodes \(50 total\), over 3 data\-generation and 2 training seeds \(6 runs\)\. Embeddings𝝀i\\bm\{\\lambda\}\_\{i\}are clustered via K\-means \(two clusters and 10 random initializations\) and scored by Adjusted Rand Index \(ARI\) and balanced accuracy\.

Baselines\.GWF\-PPA\[[28](https://arxiv.org/html/2609.05919#bib.bib28)\]learns atoms and𝝀i\\bm\{\\lambda\}\_\{i\}via GW discrepancy for both barycenter and reconstruction loss, solved with the Proximal Point Algorithm \(K=2K=2,N0=32N\_\{0\}=32,ε=0\.1\\varepsilon=0\.1, five PPA layers, one\-dimensional node embedding, Adam optimizer with learning rate of 0\.1, andT=16T=16training epochs\)\.BW\-GWuses fGOT for the barycenter \(as in fGOT\-GDL\) but GW discrepancy for reconstruction loss, isolating the effect of sfGOT vs\. GW as the loss\.

fGOT\-GDL setup\.We useK=2K=2,N0=32N\_\{0\}=32,T=16T=16training epochs,nb=10n\_\{b\}=10barycenter iterations, learning rate of 0\.05,nout=5n\_\{\\mathrm\{out\}\}=5,nin=20n\_\{\\mathrm\{in\}\}=20, andε=0\.1\\varepsilon=0\.1\. We evaluate two filter choices: a high\-pass filter \(g^​\(λ\)=λ2\\hat\{g\}\(\\lambda\)=\\lambda^\{2\}\), and a low\-pass heat kernel filter \(g^​\(λ\)=e−2​λ\\hat\{g\}\(\\lambda\)=e^\{\-2\\lambda\}\)\.

Results\.The low\-pass filter substantially outperforms the high\-pass filter \(ARI 0\.140 vs\. 0\.007\) and both baselines \(ARI – 0\.002 GWF\-PPA, 0\.013 BW\-GW; balanced accuracy 0\.690 vs\. 0\.543/0\.567\)\. Distinguishing community strength requires sensitivity to global topology, which GW’s local pairwise distances fail to capture, while fGOT\-GDL’s low\-frequency eigenmodes naturally detect it\.

### 4\.2Real\-world experiments

We evaluate on AIDS, PROTEIN, PROTEIN\-F, and IMDB\-BINARY \(statistics in Table[1](https://arxiv.org/html/2609.05919#S3.T1)\) using four fGOT\-GDL variants:Pure\(structural Laplacian, single heat kernel filter\),Attr\(attribute\-mixed Laplacian𝐋α=\(1−α\)​𝐋\+α​𝐋attr\\mathbf\{L\}\_\{\\alpha\}=\(1\-\\alpha\)\\mathbf\{L\}\+\\alpha\\mathbf\{L\}\_\{\\mathrm\{attr\}\}, where𝐋attr=diag⁡\(𝐒attr​𝟏N\)−𝐒attr\\mathbf\{L\}\_\{\\mathrm\{attr\}\}=\\operatorname\{diag\}\(\\mathbf\{S\}\_\{\\mathrm\{attr\}\}\\mathbf\{1\}\_\{N\}\)\-\\mathbf\{S\}\_\{\\mathrm\{attr\}\}with𝐒attr=𝐗¯​𝐗¯⊤\\mathbf\{S\}\_\{\\mathrm\{attr\}\}=\\bar\{\\mathbf\{X\}\}\\bar\{\\mathbf\{X\}\}^\{\\top\}and𝐗¯\\bar\{\\mathbf\{X\}\}the row\-wiseℓ2\\ell\_\{2\}\-normalized𝐗\\mathbf\{X\},α\\alphatuned via Bayesian optimization\),MF\(concatenated embeddings across 3 heat\-kernel bandwidths\), andMFMS\(MF across two random seeds\)\.

Setup\.We use the heat kernel filterg^​\(λ\)=exp⁡\(−h​λ\)\\hat\{g\}\(\\lambda\)=\\exp\(\-h\\lambda\)throughout\. For single\-filter experiments, the bandwidth ish=0\.18h=0\.18\(AIDS\),h=0\.30h=0\.30\(IMDB\-BINARY\), andh=0\.25h=0\.25\(PROTEIN, PROTEIN\-F\)\. For multi\-filter experiments, three bandwidths are used:h∈\{0\.12,0\.18,0\.25\}h\\in\\\{0\.12,0\.18,0\.25\\\}\(AIDS\),h∈\{0\.25,0\.30,0\.40\}h\\in\\\{0\.25,0\.30,0\.40\\\}\(IMDB\-BINARY\), andh∈\{0\.15,0\.22,0\.25\}h\\in\\\{0\.15,0\.22,0\.25\\\}\(PROTEIN, PROTEIN\-F\)\. The number of atoms isK=64K=64with support sizesN0=16N\_\{0\}=16\(AIDS\),N0=20N\_\{0\}=20\(IMDB\-BINARY\), andN0=40N\_\{0\}=40\(PROTEIN, PROTEIN\-F\)\. Dictionary learning uses learning rate of 0\.003,nb=5n\_\{b\}=5fGOT barycenter iterations,nout=30n\_\{\\mathrm\{out\}\}=30outer iterations, andnin=50n\_\{\\mathrm\{in\}\}=50inner iterations withε=0\.1\\varepsilon=0\.1for computing the sfGOT distance\. Atom graphs are initialized by randomly selectingKKobserved graphs, cropped toN0N\_\{0\}nodes by degree\-based ranking if larger, or zero\-padded otherwise\. Results are reported over 10 random seeds\.

Evaluation\.For clustering, K\-means with two clusters and 20 random initializations is applied to𝝀i\\bm\{\\lambda\}\_\{i\}; accuracy is reported after matching cluster labels to ground\-truth classes by the best label permutation\. We compare against FGWK\[[24](https://arxiv.org/html/2609.05919#bib.bib24)\], GWB\-KM\[[22](https://arxiv.org/html/2609.05919#bib.bib22)\], and GWF\-BADMM/GWF\-PPA\[[28](https://arxiv.org/html/2609.05919#bib.bib28)\]\. For classification, an RBF kernel matrix is constructed from𝝀i\\bm\{\\lambda\}\_\{i\}and a kernel SVM is trained under stratified 10\-fold cross\-validation\. We compare against SPK\[[3](https://arxiv.org/html/2609.05919#bib.bib4)\], HOPPERK\[[5](https://arxiv.org/html/2609.05919#bib.bib7)\], PROPAK\[[16](https://arxiv.org/html/2609.05919#bib.bib17)\], GCK\[[23](https://arxiv.org/html/2609.05919#bib.bib23)\], FGWK, GWF\-BADMM, and GWF\-PPA\[[28](https://arxiv.org/html/2609.05919#bib.bib28)\]\.

Results\.Purealready matches GW\-based baselines on AIDS \(98\.09%\) and IMDB\-BINARY \(63\.36%\);Attrimproves further when node attributes are informative\.MFconsistently outperformsPure, confirming multi\-bandwidth filters capture complementary spectral information;MFMSreduces initialization variance and achieves the best overall results: 99\.50% \(AIDS\), 71\.84%/71\.73% \(PROTEIN/\-F\), 64\.00% \(IMDB\-BINARY\) clustering accuracy \(Table[1](https://arxiv.org/html/2609.05919#S3.T1)\), and 74\.31%/64\.60% classification accuracy \(Table[2](https://arxiv.org/html/2609.05919#S3.T2)\) — outperforming GWF\-BADMM/PPA and competitive with the strongest baseline, FGWK \(75\.1%/64\.2%\)\. Fig\.[2](https://arxiv.org/html/2609.05919#S3.F2)visualizes learned atom graphs as adjacency heatmaps, offering qualitative insight into recovered structural prototypes\.

## 5Conclusions

We proposed fGOT\-GDL, a graph dictionary learning framework using fGOT as the barycenter metric and sfGOT as the reconstruction loss to capture global graph structure\. We further showed that minimizing sfGOT is equivalent to maximizing HSIC\-based statistical dependence between spectral embeddings, with experiments confirming competitive performance on clustering and classification\.

## Acknowledgment

This work was supported by MEXT KAKENHI Grant Number 26K21294\.

## References

- \[1\]A\. D\. Baxevanis, G\. D\. Bader, and D\. S\. Wishart\(2020\)Bioinformatics: a practical guide to the analysis of genes and proteins\.John Wiley & Sons\.Cited by:[§1](https://arxiv.org/html/2609.05919#S1.p1.1)\.
- \[2\]R\. Bhatia, T\. Jain, and Y\. Lim\(2019\)On the bures–wasserstein distance between positive definite matrices\.Expositiones mathematicae37\(2\),pp\. 165–191\.Cited by:[§2\.2](https://arxiv.org/html/2609.05919#S2.SS2.p1.1)\.
- \[3\]K\. M\. Borgwardt and H\. Kriegel\(2005\)Shortest\-path kernels on graphs\.InProc\. 5th IEEE Int\. Conf\. Data Min\. \(ICDM\),pp\. 8–15\.Cited by:[§4\.2](https://arxiv.org/html/2609.05919#S4.SS2.p3.1)\.
- \[4\]M\. Cuturi\(2013\)Sinkhorn distances: lightspeed computation of optimal transport\.Advances in neural information processing systems26\.Cited by:[§3\.2](https://arxiv.org/html/2609.05919#S3.SS2.p4.1)\.
- \[5\]A\. Feragen, N\. Kasenburg, J\. Petersen, M\. D\. Bruijne, and K\. Borgwardt\(2013\)Scalable kernels for graphs with continuous attributes\.InProc\. Adv\. Neural Inf\. Process\. Syst\. \(NeurIPS\),Vol\.26,pp\. 216–224\.Cited by:[§4\.2](https://arxiv.org/html/2609.05919#S4.SS2.p3.1)\.
- \[6\]J\. Gilmer, S\. S\. Schoenholz, P\. F\. Riley, O\. Vinyals, and G\. E\. Dahl\(2017\)Neural message passing for quantum chemistry\.InProc\. Int\. Conf\. Mach\. Learn\. \(ICML\),pp\. 1263–1272\.Cited by:[§1](https://arxiv.org/html/2609.05919#S1.p1.1)\.
- \[7\]A\. Gretton, O\. Bousquet, A\. Smola, and B\. Schölkopf\(2005\)Measuring statistical dependence with Hilbert\-Schmidt norms\.InProc\. Int\. Conf\. Algorithmic Learn\. Theory \(ALT\),pp\. 63–77\.Cited by:[§1](https://arxiv.org/html/2609.05919#S1.p4.1),[§3](https://arxiv.org/html/2609.05919#S3.p1.1),[Definition 1](https://arxiv.org/html/2609.05919#Thmdefinition1)\.
- \[8\]I\. Haasler and P\. Frossard\(2024\)Bures\-Wasserstein means of graphs\.InProc\. Int\. Conf\. Artif\. Intell\. Statist\. \(AISTATS\),pp\. 1873–1881\.Cited by:[§3\.2](https://arxiv.org/html/2609.05919#S3.SS2.p2.1)\.
- \[9\]P\. A\. Knight\(2008\)The Sinkhorn\-Knopp algorithm: convergence and applications\.SIAM J\. Matrix Anal\. Appl\.30\(1\),pp\. 261–275\.Cited by:[§3\.2](https://arxiv.org/html/2609.05919#S3.SS2.p4.1)\.
- \[10\]K\. Kreutz\-Delgado, J\. F\. Murray, B\. D\. Rao, K\. Engan, T\. Lee, and T\. J\. Sejnowski\(2003\)Dictionary learning algorithms for sparse representation\.Neural Comput\.15\(2\),pp\. 349–396\.Cited by:[§1](https://arxiv.org/html/2609.05919#S1.p2.1)\.
- \[11\]A\. R\. Leach and V\. J\. Gillet\(2007\)An introduction to chemoinformatics\.Springer\.Cited by:[§1](https://arxiv.org/html/2609.05919#S1.p1.1)\.
- \[12\]H\. P\. Maretic, M\. E\. Gheche, G\. Chierchia, and P\. Frossard\(2019\)GOT: an optimal transport framework for graph comparison\.InProc\. Adv\. Neural Inf\. Process\. Syst\. \(NeurIPS\),Vol\.32\.Cited by:[§1](https://arxiv.org/html/2609.05919#S1.p3.1),[§2\.2](https://arxiv.org/html/2609.05919#S2.SS2.p1.1),[§3\.2](https://arxiv.org/html/2609.05919#S3.SS2.p3.1)\.
- \[13\]H\. P\. Maretic, M\. E\. Gheche, G\. Chierchia, and P\. Frossard\(2022\)fGOT: graph distances based on filters and optimal transport\.InProc\. AAAI Conf\. Artif\. Intell\. \(AAAI\),Vol\.36,pp\. 7710–7718\.Cited by:[§1](https://arxiv.org/html/2609.05919#S1.p3.1),[§2\.2](https://arxiv.org/html/2609.05919#S2.SS2.p1.2),[§2\.2](https://arxiv.org/html/2609.05919#S2.SS2.p3.2),[§3\.1](https://arxiv.org/html/2609.05919#S3.SS1.p2.1),[§3\.1](https://arxiv.org/html/2609.05919#S3.SS1.p2.3),[§3\.2](https://arxiv.org/html/2609.05919#S3.SS2.p3.1),[Lemma 1](https://arxiv.org/html/2609.05919#Thmlemma1)\.
- \[14\]A\. Marin and B\. Wellman\(2011\)Social network analysis: an introduction\.InThe SAGE Handbook of Social Network Analysis,pp\. 11–25\.Cited by:[§1](https://arxiv.org/html/2609.05919#S1.p1.1)\.
- \[15\]F\. Mémoli\(2011\)Gromov\-Wasserstein distances and the metric approach to object matching\.Found\. Comput\. Math\.11\(4\),pp\. 417–487\.Cited by:[§1](https://arxiv.org/html/2609.05919#S1.p2.1),[§2\.1](https://arxiv.org/html/2609.05919#S2.SS1.p1.3)\.
- \[16\]M\. Neumann, R\. Garnett, C\. Bauckhage, and K\. Kersting\(2016\)Propagation kernels: efficient graph kernels from propagated information\.Mach\. Learn\.102\(2\),pp\. 209–245\.Cited by:[§4\.2](https://arxiv.org/html/2609.05919#S4.SS2.p3.1)\.
- \[17\]D\. H\. Nguyen, C\. H\. Nguyen, and H\. Mamitsuka\(2019\)ADAPTIVE: learning data\-dependent, concise molecular vectors for fast, accurate metabolite identification from tandem mass spectra\.Bioinformatics35\(14\),pp\. i164–i172\.Cited by:[§1](https://arxiv.org/html/2609.05919#S1.p1.1)\.
- \[18\]D\. H\. Nguyen, C\. H\. Nguyen, and H\. Mamitsuka\(2019\)Recent advances and prospects of computational methods for metabolite identification: a review with emphasis on machine learning approaches\.Briefings in bioinformatics20\(6\),pp\. 2028–2043\.Cited by:[§1](https://arxiv.org/html/2609.05919#S1.p1.1)\.
- \[19\]D\. H\. Nguyen, C\. H\. Nguyen, and H\. Mamitsuka\(2021\)Learning subtree pattern importance for Weisfeiler\-Lehman based graph kernels\.Mach\. Learn\.110\(7\),pp\. 1585–1607\.Cited by:[§1](https://arxiv.org/html/2609.05919#S1.p1.1)\.
- \[20\]D\. H\. Nguyen and K\. Tsuda\(2023\)On a linear fused Gromov\-Wasserstein distance for graph structured data\.Pattern Recognit\.138,pp\. 109351\.Cited by:[§1](https://arxiv.org/html/2609.05919#S1.p1.1)\.
- \[21\]H\. Nguyen, S\. Maeda, and K\. Oono\(2017\)Semi\-supervised learning of hierarchical representations of molecules using neural message passing\.arXiv preprint arXiv:1711\.10168\.Cited by:[§1](https://arxiv.org/html/2609.05919#S1.p1.1)\.
- \[22\]G\. Peyré, M\. Cuturi, and J\. Solomon\(2016\)Gromov\-Wasserstein averaging of kernel and distance matrices\.InProc\. Int\. Conf\. Mach\. Learn\. \(ICML\),pp\. 2664–2672\.Cited by:[§3\.2](https://arxiv.org/html/2609.05919#S3.SS2.p4.1),[§4\.2](https://arxiv.org/html/2609.05919#S4.SS2.p3.1)\.
- \[23\]N\. Shervashidze, S\. V\. N\. Vishwanathan, T\. Petri, K\. Mehlhorn, and K\. Borgwardt\(2009\)Efficient graphlet kernels for large graph comparison\.InProc\. Int\. Conf\. Artif\. Intell\. Statist\. \(AISTATS\),pp\. 488–495\.Cited by:[§4\.2](https://arxiv.org/html/2609.05919#S4.SS2.p3.1)\.
- \[24\]V\. Titouan, N\. Courty, R\. Tavenard, and R\. Flamary\(2019\)Optimal transport for structured data with application on graphs\.InProc\. Int\. Conf\. Mach\. Learn\. \(ICML\),pp\. 6275–6284\.Cited by:[§4\.2](https://arxiv.org/html/2609.05919#S4.SS2.p3.1)\.
- \[25\]I\. Tošić and P\. Frossard\(2011\)Dictionary learning\.IEEE Signal Process\. Mag\.28\(2\),pp\. 27–38\.Cited by:[§1](https://arxiv.org/html/2609.05919#S1.p2.1)\.
- \[26\]C\. Vincent\-Cuaz, T\. Vayer, R\. Flamary, M\. Corneli, and N\. Courty\(2021\)Online graph dictionary learning\.InProc\. Int\. Conf\. Mach\. Learn\. \(ICML\),pp\. 10564–10574\.Cited by:[§1](https://arxiv.org/html/2609.05919#S1.p2.1),[§2\.1](https://arxiv.org/html/2609.05919#S2.SS1.p1.3)\.
- \[27\]S\. V\. N\. Vishwanathan, N\. N\. Schraudolph, R\. Kondor, and K\. M\. Borgwardt\(2010\)Graph kernels\.J\. Mach\. Learn\. Res\.11,pp\. 1201–1242\.Cited by:[§1](https://arxiv.org/html/2609.05919#S1.p1.1)\.
- \[28\]H\. Xu\(2020\)Gromov\-Wasserstein factorization models for graph clustering\.InProc\. AAAI Conf\. Artif\. Intell\. \(AAAI\),Vol\.34,pp\. 6478–6485\.Cited by:[§1](https://arxiv.org/html/2609.05919#S1.p2.1),[§2\.1](https://arxiv.org/html/2609.05919#S2.SS1.p1.3),[Table 1](https://arxiv.org/html/2609.05919#S3.T1.5.1.6.1.1),[Table 2](https://arxiv.org/html/2609.05919#S3.T2.5.2.1.1),[§4\.1](https://arxiv.org/html/2609.05919#S4.SS1.p2.1),[§4\.2](https://arxiv.org/html/2609.05919#S4.SS2.p3.1)\.