Low-Rank Gromov-Wasserstein Cross-Attention

(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.