Pith. sign in

REVIEW 3 major objections 5 minor 33 references

Diffusion enabled Optimal Transport distances for graph matching

T0 review · 3 major / 5 minor · reviewed 2026-07-11 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Diffusing node features before semi-relaxed fused Gromov-Wasserstein transport turns noisy graph matching from worse-than-random into usable cluster recovery.

desk verdict Clean incremental OT method with real synthetic gains over srFGW, but the 92% claim is an oracle upper bound and the evaluation is too narrow for the abstract's language. read the letter →

arxiv 2607.06646 v1 pith:E336LDES submitted 2026-07-07 cs.LG cs.AI

Iman Seyedi , Francesco Archetti This is my paper
classification cs.LGcs.AI
keywords optimaltransportGromov-Wassersteingraphdiffusionsemi-relaxedFGWmatchingheatkernelnode-attributedgraphs
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper claims that raw node features and static edge structure are not enough when graphs are sparse or noisy: information must first be allowed to spread along the graph before two graphs are compared. By running a heat-kernel diffusion on the node attributes and then solving a semi-relaxed fused Gromov-Wasserstein problem, the resulting distance (DsrFGW) recovers the correct cluster alignment far more reliably than the same transport plan without diffusion. On 36 synthetic pairs that range from clean two-block graphs to heavily mixed ones, the method lifts accuracy by up to 20 points and converts negative Adjusted Rand Index scores (worse than chance) into positive ones, especially in the medium-noise regime. The practical message is that a single, tunable diffusion scale can make optimal-transport graph matching usable under the structural uncertainty that real networks routinely exhibit.

What carries the argument

Diffusion Semi-Relaxed Fused Gromov-Wasserstein (DsrFGW): the heat-kernel operator exp(-τL) is applied to node feature matrices before they enter the feature-cost term of the semi-relaxed FGW objective, so that local neighborhood structure is baked into the features that the transport plan sees.

What would settle it

On a held-out set of the same stochastic-block pairs, fix τ by any unsupervised criterion (or by cross-validation on a separate training split) and check whether DsrFGW still beats τ=0 srFGW by the same accuracy and ARI margins reported in Tables 1-3.

Watch

Extended reading notes

Core claim

Replacing raw node attributes by their heat-kernel-diffused versions inside the semi-relaxed fused Gromov-Wasserstein objective systematically improves both accuracy and Adjusted Rand Index of the recovered node matching on synthetic stochastic-block graphs, turning negative ARI (worse than random) into positive ARI in the medium-difficulty regime and improving clustering quality in 92 percent of the 36 tested configurations.

Load-bearing premise

The diffusion scale that works best can be chosen by looking at ground-truth labels on the same synthetic pairs that are later used to claim superiority; without that oracle the reported gains may not transfer.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper proposes Diffusion Semi-Relaxed Fused Gromov-Wasserstein (DsrFGW), which replaces raw node attributes in the semi-relaxed fused Gromov-Wasserstein objective with heat-kernel diffused features (Eqs. 6–8). The resulting discrepancy is evaluated on 36 synthetic pairwise matching tasks generated from two-block stochastic block models at three difficulty levels (easy/medium/hard) and three sizes (n=50,100,200). Against the sole baseline of srFGW (τ=0), the authors report accuracy gains of 0–20 points and large ARI improvements that convert many negative (worse-than-random) ARI values into positive ones, claiming superiority in 92% of configurations when the best diffusion scale τ* is selected per cell.

Significance. If the empirical claims transfer, DsrFGW would supply a simple, principled way to inject multi-hop structural context into fused OT matching and would be immediately useful for noisy or sparsely observed attributed graphs in neuroscience and traffic analysis—the domains the introduction invokes. The construction itself (diffused features plugged into an existing srFGW solver) is modular and easy to re-implement. The systematic grid over τ and α, together with the multi-metric reporting (accuracy, ARI, distance, sparsity) and the Pareto/sparsity analyses in §5.4–5.5, constitutes a careful synthetic stress test that is stronger than many OT-graph papers. The main limitation is that the headline 92% figure and the dramatic medium-regime ARI rescues rest on oracle selection of τ, so the practical significance remains conditional on a transferable parameter-selection procedure.

major comments (3)
  1. §5.1 and Tables 1–3: for every (size, α) cell the authors report the single best τ* chosen from the grid by maximizing Accuracy/ARI on the same pairs used for evaluation. Because ground-truth cluster labels are required both to pick τ* and to compute the metrics, the 92% superiority claim (Abstract, §5.3, Conclusions) is an oracle upper bound. No fixed-τ, cross-validated, or unsupervised selection experiment is provided; without it the central robustness claim under structural uncertainty is not yet established.
  2. §5.1–5.2: the only baseline is srFGW (τ=0). The introduction and related-work sections motivate the method by Graph Diffusion Distance, FGW, and other diffusion-OT constructions, yet none of these (nor classical graph matchers) appear in the tables. Consequently it is impossible to judge whether the observed gains are specific to the diffusion-plus-srFGW combination or would be matched by simpler diffusion or non-relaxed FGW baselines.
  3. §5.1 and Abstract: all 36 tasks are two-block SBMs with controlled p_in/p_out and Gaussian feature noise. No real attributed graphs (brain networks, traffic, social) are evaluated despite the application claims. The representativeness of this synthetic suite for the “structural uncertainty” the paper claims to address therefore remains untested.
minor comments (5)
  1. Abstract and §5.2: “Adjusted Rank Index” should be “Adjusted Rand Index”; the same typo appears in the abstract’s parenthetical.
  2. Eq. (6) and surrounding text: the heat-kernel operator is written exp(−τ L) but the Laplacian convention (combinatorial vs. normalized) and the numerical approximation method (truncated spectral / Chebyshev) are only mentioned later; a short clarifying sentence would help reproducibility.
  3. Tables 1–3: the Δ Acc / Δ ARI columns are helpful, yet the absolute distance and sparsity values that appear in the later figures are never tabulated, making quantitative comparison across metrics harder.
  4. §2: several arXiv preprints are cited with future access dates (2025/2026); these should be updated or replaced by published versions where available.
  5. Fig. 1 caption and text: the diffusion scales shown (τ=0.05, 0.15, 0.5) are illustrative; it would be useful to note whether the same scales appear in the experimental grid.

Circularity Check

1 steps flagged · score 3.0 of 10

Mild oracle circularity: reported 92% superiority and ARI gains rest on best-τ* selected by maximizing Acc/ARI on the same evaluation pairs (not a fixed a-priori rule).

  1. fitted input called prediction [Abstract; §5.1 grid search; Tables 1–3 (τ* columns); §5.2–5.3; Conclusions]
    "for each graph pair, we perform a grid search over the diffusion parameter τ ∈ {0.0,0.01,0.05,0.1,0.2,0.5} … with baseline srFGW corresponding to τ = 0. … Even under severe noise, DsrFGW improves clustering quality in 92% of the synthetic tasks with optimal diffusion scales adapting to problem difficulty"

    τ* is chosen by maximizing the same Acc/ARI metrics that are later reported as evidence of superiority. The 0–20 pp accuracy gains, the medium-regime ARI flips from negative to positive, and the 92% figure are therefore conditioned on oracle knowledge of ground-truth labels for hyper-parameter selection; they are not the performance of a fixed, label-free rule. Removing the oracle selection can shrink or reverse the claimed gains.

full rationale

This is an empirical methods paper, not a first-principles derivation. DsrFGW is defined independently (Eq. 8) by substituting heat-kernel diffused features (Eq. 6) into the existing srFGW objective; the math does not force the numerical outcomes by construction. Ground-truth cluster labels are external to the method. The only circularity is the standard-but-load-bearing reporting practice of selecting, for every (n, α) cell, the single best τ from the evaluation grid and then claiming superiority of “DsrFGW” (Abstract; Tables 1–3 τ* columns; §5.2–5.3; 92% figure). Because Acc/ARI both choose τ* and score the method, the headline gains are an oracle upper bound. No self-definitional loop, no uniqueness theorem imported from the authors, and no renaming of a known result. Score 3 reflects this partial fitted-input issue without elevating it to definitional collapse.

Assumptions & free parameters 2 free parameters · 5 assumptions · 1 invented entities

The claim rests on standard OT/GW machinery plus two modeling choices (heat-kernel feature diffusion is the right multi-scale embedding; SBM pairs with shortest-path costs are a fair testbed) and two free parameters (τ, α) that are grid-searched per task. No new physical entities; the invented object is the composite distance itself.

free parameters (2)
  • diffusion scale τ (and pair τ_s, τ_t) = task-dependent; often 0.5 (easy/medium small n), 0.01–0.2 (hard or large n)
    Chosen from {0, 0.01, 0.05, 0.1, 0.2, 0.5} by best accuracy/ARI on each evaluation configuration; load-bearing for the reported gains.
  • structure–feature weight α = grid values; no single global α
    Swept over {0.1, 0.3, 0.5, 0.7}; balances feature vs structure terms in Eq. (8); results reported per α.
assumptions (5)
  • domain assumption Heat-kernel diffusion of node features encodes multi-hop structure and improves robustness to edge noise for OT matching.
    Stated as motivation from Graph Diffusion Distance (§1, §3.5); not proved for the matching objective, only motivated.
  • domain assumption Semi-relaxed fused Gromov–Wasserstein with one free marginal is a valid and preferable objective for attributed graph matching of unequal relevance.
    Inherited from Vincent-Cuaz et al. [1]; used as the base objective in Eq. (5)–(8).
  • ad hoc to paper Stochastic block models with controlled p_in, p_out, and feature noise σ form a representative test of ‘structural uncertainty’ for real attributed graphs.
    Entire evaluation (§5.1) rests on this; no real-network validation is provided.
  • domain assumption Shortest-path distances via Floyd–Warshall are an adequate structural cost matrix C for the GW term.
    Stated in §5.1; alternatives (resistance, diffusion distances) are mentioned in §3.5 but not used in experiments.
  • standard math Standard discrete OT / GW optimization theory (existence of plans, conditional-gradient style solvers) applies to the diffused-feature objective.
    Invoked in §3–4 via Peyré & Cuturi [7] and related GW literature.
invented entities (1)
  • DsrFGW (Diffusion Semi-Relaxed Fused Gromov–Wasserstein) discrepancy
    purpose: Name and formalize the composite distance that plugs heat-kernel-diffused features into srFGW (Eq. 8).
    Composite of existing pieces; independent_evidence is only the synthetic tables in this paper, not an external falsifiable prediction.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Diffusion enabled Optimal Transport distances for graph matching." pith.science (2026). https://pith.science/paper/E336LDES

@misc{pith2026260706646,
  author       = {Pith},
  title        = {Pith review of: Diffusion enabled Optimal Transport distances for graph matching},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/E336LDES}},
  note         = {Machine review of arXiv:2607.06646}
}
read the original abstract

This paper introduces Diffusion Semi-Relaxed Fused Gromov-Wasserstein (DsrFGW), a novel method for graph comparison that unifies node features and structural connectivity through optimal transport. While traditional Gromov-Wasserstein and semi-relaxed variants (srGW, srFGW) capture graph structure, they often struggle with sparse, noisy, or partially observed graphs. Inspired by Graph Diffusion Distance, which posits graphs are similar if they enable similar information transmission patterns, DsrFGW incorporates diffusion processes allowing information propagation across nodes, capturing local and global structural patterns while reducing sensitivity to noise or missing edges. An extensive evaluation on 36 synthetic pairwise graph matching tasks (easy, medium, hard) demonstrates consistent superiority over srFGW, achieving accuracy improvements of 0-20 percentage points and dramatic Adjusted Rand Index (ARI) gains: in medium-difficulty scenarios, srFGW often achieves negative ARI (worse than random) while DsrFGW offers better performance in terms of both internal and external clustering quality measures (i.e., Adjusted Rank Index and Accuracy with respect to the true underlying clusters, respectively). Even under severe noise, DsrFGW improves clustering quality in 92% of the synthetic tasks with optimal diffusion scales adapting to problem difficulty, establishing DsrFGW as a robust framework for graph comparison under structural uncertainty.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

33 extracted references · 33 canonical work pages

  1. [1]

    In: Colloque GRETSI 2022 – XXVIIIème Colloque Francophone de Traitement du Signal et des Images (2022)

    Vincent-Cuaz, C., Flamary, R., Corneli, M., Vayer, T., Courty, N.: Semi -relaxed Gromov- Wasserstein divergence for graphs classification. In: Colloque GRETSI 2022 – XXVIIIème Colloque Francophone de Traitement du Signal et des Images (2022). Available online, last accessed 2025/09/25

    work page 2022

  2. [2]

    Takeda, K., Sasaki, M., Abe, K., Oizumi, M.: Unsupervised alignment in neuroscience: In- troducing a toolbox for Gromov–Wasserstein optimal transport. J. Neurosci. Methods 419, 110443 (2025)

    work page 2025

  3. [3]

    In: Hutter, F., Kersting, K., Lijffijt, J., Valera, I

    Barbe, A., Sebban, M., Gonçalves, P., Borgnat, P., Gribonval, R.: Graph diffusion Wasser- stein distances. In: Hutter, F., Kersting, K., Lijffijt, J., Valera, I. (eds.) Machine Learning and Knowledge Discovery in Databases, LNCS, vol. 12458, pp. 577 –592. Springer, Cham (2021)

    work page 2021

  4. [4]

    In: 2013 IEEE Global Conference on Signal and Information Processing, pp

    Hammond, D.K., Gur, Y., Johnson, C.R.: Graph diffusion distance: A difference measure for weighted graphs based on the graph Laplacian exponential kernel. In: 2013 IEEE Global Conference on Signal and Information Processing, pp. 419 –422. IEEE (2013). Avail able online, last accessed 2026/01/15

    work page 2013

  5. [5]

    Optimal and Diffusion Transports in Machine Learning

    Peyré, G.: Optimal and diffusion transports in machine learning. arXiv:2512.06797 (2025)

    work page Pith review arXiv 2025

  6. [6]

    Wasserstein Diffusion on Multidimensional Spaces

    Sturm, K.-T.: Wasserstein diffusion on multidimensional spaces. arXiv:2401.12721 (2024)

    work page Pith review arXiv 2024

  7. [7]

    Peyré, G., Cuturi, M.: Computational optimal transport: With applications to data science. Found. Trends Mach. Learn. 11(5–6), 355–607 (2019)

    work page 2019

  8. [8]

    Optimal Transport-Based Clustering of Attributed Graphs with an Application to Road Traffic Data

    Gavra, I., Guichard-Sustowski, K., Le Marrec, L.L.: Optimal transport -based clustering of attributed graphs with an application to road traffic data. arXiv:2512.15570 (2025)

    work page Pith review arXiv 2025

Show all 33 references
  1. [9]

    In: Advances in Neural Information Processing Systems, vol

    Canas, G., Rosasco, L.: Learning probability measures with respect to optimal transport metrics. In: Advances in Neural Information Processing Systems, vol. 25 (2012). Available online, last accessed 2026/01/15

    2012

  2. [10]

    Chowdhury, S., Needham, T., Semrad, E., Wang, B., Zhou, Y.: Hypergraph co -optimal transport: Metric and categorical properties. J. Appl. Comput. Topol. 8(5), 1171 –1230 (2024). Diffusion-enabled Optimal Transport distances for graph matching 15

    2024

  3. [11]

    Available online, last accessed 2026/01/15

    Brécheteau, C., Verdebout, T.: Learning on mm spaces based on Gromov’s reconstruction theorem (2025). Available online, last accessed 2026/01/15

    2025

  4. [12]

    In: International Conference on Machine Learning, pp

    Chen, Y., Yao, R., Yang, Y., Chen, J.: A Gromov-Wasserstein geometric view of spectrum- preserving graph coarsening. In: International Conference on Machine Learning, pp. 5257–

  5. [13]

    arXiv:2511.08733 (2025)

    Taveras, C.A., Segarra, S., Uribe, C.A.: Gromov -Wasserstein graph coarsening. arXiv:2511.08733 (2025)

    2025

  6. [14]

    Algorithms 13(9), 212 (2019)

    Vayer, T., Chapel, L., Flamary, R., Tavenard, R., Courty, N.: Fused Gromov -Wasserstein distance for structured objects. Algorithms 13(9), 212 (2019)

    2019

  7. [15]

    -K., Sturm, K

    von Renesse, M. -K., Sturm, K. -T.: Entropic measure and Wasserstein diffusion. Ann. Probab. 37(3), 1114–1191 (2009). Available online, last accessed 2026/01/20

    2009

  8. [16]

    Electron

    Marx, V.: A new approach for the construction of a Wasserstein diffusion. Electron. J. Probab. 23 (2018). Available online, last accessed 2026/01/20

    2018

  9. [17]

    -Y., Wittmann, S.: Diffusion processes on 𝑝-Wasserstein space over Ba- nach space

    Ren, P., Wang, F. -Y., Wittmann, S.: Diffusion processes on 𝑝-Wasserstein space over Ba- nach space. arXiv:2402.15130 (2025)

    2025 arXiv

  10. [18]

    arXiv:2401.17958 (2025)

    Gao, X., Zhu, L.: Convergence analysis for general probability flow ODEs of diffusion mod- els in Wasserstein distances. arXiv:2401.17958 (2025)

    2025 arXiv

  11. [19]

    arXiv:2402.02239 (2025)

    Assel, H.V., Vincent-Cuaz, C., Courty, N., Flamary, R., Frossard, P., Vayer, T.: Distribu- tional reduction: Unifying dimensionality reduction and clustering with Gromov -Wasser- stein. arXiv:2402.02239 (2025)

    2025 arXiv

  12. [20]

    Impri- merie Royale, Paris (1784)

    Monge, G.: Mémoire sur le calcul intégral des équations aux différences partielles. Impri- merie Royale, Paris (1784)

  13. [21]

    Kantorovich, L.: On the transfer of masses. Dokl. Akad. Nauk 37, 227–229 (1942)

    1942

  14. [22]

    In: International Con- ference on Machine Learning, pp

    Cuturi, M., Doucet, A.: Fast computation of Wasserstein barycenters. In: International Con- ference on Machine Learning, pp. 685–693. PMLR (2014)

    2014

  15. [23]

    Candelieri, A., Ponti, A., Giordani, I., Archetti, F.: On the use of Wasserstein distance in the distributional analysis of human decision making under uncertainty. Ann. Math. Artif. Intell. 91(2–3), 217–238 (2023)

    2023

  16. [24]

    Grundlehren der mathematischen Wissenschaften, vol

    Villani, C.: Optimal Transport. Grundlehren der mathematischen Wissenschaften, vol. 338. Springer, Berlin, Heidelberg (2009)

    2009

  17. [25]

    Mathematics 13(13) (2025)

    Seyedi, I., Candelieri, A., Messina, E., Archetti, F.: Wasserstein distributionally robust op- timization for chance constrained facility location under uncertain demand. Mathematics 13(13) (2025)

    2025

  18. [26]

    Seyedi, I., Candelieri, A., Archetti, F.: Distributionally robust Bayesian optimization via Sinkhorn-based Wasserstein barycenter. Mach. Learn. Knowl. Extr. 7(3) (2025)

    2025

  19. [27]

    Journal of Transportation Research, 19(71), 183-206 (2022)

    Seyedi, I., Hamedi, M., & Tavakkoli-Moghaddam, R.: Optimization for a truck scheduling problem in multi-door cross dokcing with learning effect and deteriorating jobs. Journal of Transportation Research, 19(71), 183-206 (2022)

    2022

  20. [28]

    Mathematics, 14(11), 1972 (2026)

    Seyedi, I., Candelieri, A., Messina, E., & Archetti, F.: Gromov–Wasserstein Meets Combi- natorial Optimization: A Scalable Solver for the Capacitated Quadratic Assignment Prob- lem. Mathematics, 14(11), 1972 (2026)

    1972

  21. [29]

    Caspian Journal of Applied Sciences Research, 2(4) (2013)

    Seyedi, I., & Maleki -Daronkolaei, A.: Solving a two -stage assembly flowshop scheduling problem to minimize the mean tardiness and earliness penalties by three meta -heuristics. Caspian Journal of Applied Sciences Research, 2(4) (2013)

    2013

  22. [30]

    Coifman, R.R., Lafon, S.: Diffusion maps. Appl. Comput. Harmon. Anal. 21(1), 5 –30 (2006)

    2006

  23. [31]

    Seyedi, I., Maleki-Daronkolaei, A., & Kalashi, F. (2012). Tabu search and simulated anneal- ing for new three-stage assembly flow shop scheduling with blocking. Interdisciplinary Jour- nal of Contemporary Research in Business, 4(8), 394-402. 16 I. Seyedi and F. Archetti

    2012

  24. [32]

    Hubert, L., Arabie, P.: Comparing partitions. J. Classification 2, 193–218 (1985)

    1985

  25. [33]

    Mathemat- ics, 14(3), 417 (2026)

    Seyedi, I., Candelieri, A., Archetti, F.: Fused Unbalanced Gromov–Wasserstein-Based Net- work Distributional Resilience Analysis for Critical Infrastructure Assessment. Mathemat- ics, 14(3), 417 (2026). https://doi.org/10.3390/math14030417

    2026 doi

Pith tools

Reviewed July 11, 2026 · model on record in the stance chip above.