# Low-Rank Gromov-Wasserstein Cross-Attention

- ID: 3125
- Canonical URL: https://synthcore.org/idea/3125/low-rank-gromov-wasserstein-cross-attention
- API JSON: https://synthcore.org/api/idea/3125.json
- API Markdown: https://synthcore.org/api/idea/3125.md
- Verification status: unverified
- Source: [arXiv:2609.03094](https://arxiv.org/abs/2609.03094)
- Category: architecture
- Solves: accuracy, scalability, stability
- ML areas: graph-nn, attention, retrieval, optimizer
- Math tags: optimal-transport, linear-algebra, convex-analysis, graph-theory
- Ratings: usefulness 6/10; difficulty 6/10; novelty 6/10

## Idea description

Replace ordinary feature-only cross-attention between two graph sets with a transport coupling optimized using pairwise structural costs. Use the paper's positive-semidefinite graph-kernel factorization to compute the quadratic GW interaction without materializing an O(N_0^2 N_1^2) tensor, and use the inexact-gradient convergence bound to control truncated or approximate updates. The resulting coupling can be used directly as attention weights or as a soft graph-matching matrix.

## Mathematical statement

For metric-measure spaces $(\mathcal X_0,d_0,\mu_0)$ and $(\mathcal X_1,d_1,\mu_1)$, the paper defines $\mathsf{GW}_{p,q}(\mu_0,\mu_1)=\inf_{\pi\in\Pi(\mu_0,\mu_1)}(\int|d_0^q(x,x')-d_1^q(y,y')|^p\,d\pi\otimes\pi)^{1/p}$, where $\Pi(\mu_0,\mu_1)$ is the set of couplings with prescribed marginals. For finite supports, let $P\in\mathbb R^{N_1\times N_0}$ be the coupling, $P_{lm}=\pi(x_0^{(m)},x_1^{(l)})$, and let $x=\operatorname{vec}(P)$. The marginal constraints are $Ax=b$, where $b$ contains the node masses and $A$ contains the row- and column-sum operators. For the graph-collection construction in the paper and squared costs, the GW quadratic cost matrix is $M=-4K_0\otimes K_1$, with $K_0,K_1\succeq0$ the pairwise graph kernels. The displayed construction proves positive semidefiniteness by writing a kernel as a sum of outer products: $K=VV^\top+WW^\top$, where rows of $V$ are $\sqrt{2}(A_G\mathbf 1)^\top$ and rows of $W$ are $\operatorname{vec}(A_G)^\top/\sqrt{2}$. Thus $K=FF^\top$ for $F=[V\;W]$, and multiplication by $K_0\otimes K_1$ can be implemented through low-rank factors rather than a dense Kronecker matrix. The paper's inexact-oracle guarantee states that if $\|\widetilde{\nabla}\ell(u)-\nabla\ell(u)\|\le\eta'$ on $\mathbb B_{R_0}$ and $L'=\lambda_{\max}(B_0^\top B_0)/(\lambda_{\min}(B_1^\top B_1)+\varepsilon)$ is a Lipschitz constant for $\nabla(\ell(u)-\frac12\|u\|^2)$, then $\min_{0\le j<J}\|L'(u_{j+1}-u_j)\|^2\le 2L'(\ell(u_0)-\inf\ell)/J+8L'R_0\eta'$. Here $u$ is the optimization variable, $u_j$ are iterates, $B_0,B_1$ are the paper's cost-factor matrices, $R_0$ bounds the iterates, and $\varepsilon>0$ stabilizes the denominator. In the neural adaptation, $u=\operatorname{vec}(P)$ and the estimated gradient error $\eta'$ is monitored from the residual of a truncated low-rank kernel product.

## Key formulas

- $$\mathsf{GW}_{p,q}(\mu_{0},\mu_{1})=\inf_{\pi\in\Pi(\mu_{0},\mu_{1})}\left(\int\left|\mathsf d_{0}^{q}(x,x')-\mathsf d_{1}^{q}(y,y')\right|^{p}\,d\pi\otimes\pi(x,y,x',y')\right)^{1/p}.$$
- $$M=-4K_{0}\otimes K_{1},\qquad K_0=F_0F_0^{\top},\quad K_1=F_1F_1^{\top},\quad F=[V\;W].$$
- $$K=VV^{\top}+WW^{\top},\qquad V_G=\sqrt{2}(A_G\mathbf 1)^{\top},\qquad W_G=\frac{1}{\sqrt{2}}\operatorname{vec}(A_G)^{\top}.$$
- $$\min_{0\le j<J}\|L'(u_{j+1}-u_j)\|^{2}\leq\frac{2L'(\ell(u_0)-\inf_{\mathbb R^{r_0}}\ell)}{J}+8L'R_0\eta'.$$

## Implementation notes

(1) Integration point: insert the module between two graph encoders or graph-retrieval towers. Given graph embeddings and adjacency matrices for two graph sets, compute a structural cost matrix between source and target graph elements, then produce a coupling $P$ that is fed to cross-attention as $H_1^{\mathrm{aligned}}=P H_1$ or used to bias logits by $\log(P+10^{-8})$. Use uniform masses initially, so $P\mathbf1_{N_0}=\mathbf1_{N_1}/N_1$ and $P^\top\mathbf1_{N_1}=\mathbf1_{N_0}/N_0$. (2) Pseudocode: compute $F_0$ and $F_1$ by concatenating $\sqrt2$ times each graph's degree vector with $\operatorname{vec}(A_G)/\sqrt2$; optionally retain only the top-$r$ singular directions of each $F$. Set $P$ to the outer product of the marginals. For iteration $j=1,\ldots,J$, compute the structural gradient using the factorized interaction $M\operatorname{vec}(P)=-4(F_0\otimes F_1)(F_0\otimes F_1)^\top\operatorname{vec}(P)$, never forming $M$; reshape it to $G_P\in\mathbb R^{N_1\times N_0}$; add the feature term $\alpha C_{\mathrm{feat}}$; take $P\leftarrow\operatorname{Sinkhorn}(P-\tau G_P,\mu_1,\mu_0)$ or use a log-domain entropic proximal step. Stop after a fixed small number of iterations and normalize $P$ before attention. (3) Quantities from the paper are the GW coupling constraints, the factorized PSD/Kronecker interaction, and the inexact-gradient criterion. Estimate the truncation rank $r$ with randomized SVD, estimate $L'$ by a few power iterations on the factorized operator, and estimate $\eta'$ by comparing rank-$r$ and rank-$2r$ gradients on a held-out minibatch. Clip iterates to a bounded transport simplex to enforce the $R_0$ assumption. (4) First experiment: use a small Graph Matching Network or graph-classification model on MUTAG or AIDS, comparing ordinary cross-attention, dense entropic GW attention, and factorized GW attention at equal wall-clock time. Sweep $r\in\{8,16,32\}$ and $J\in\{3,5,10\}$. Success means improved graph matching accuracy or retrieval Recall@K at equal FLOPs, with the factorized method scaling substantially better as the number of graphs grows; the stability signal is monotone decrease of the transport objective and smaller variance across random seeds than unconstrained learned attention.

## Disclaimer

AI-generated research hypothesis, automatically tested. Not peer-reviewed.