Outlier-Robust Gromov-Wasserstein for Graph Data

Summary

This paper proposes a Robust Gromov-Wasserstein (RGW) distance to tackle the high sensitivity to outliers of common GW distances. The key idea is to relax both the marginal distribution and the transport plan based on the KL divergence. An algorithm based on BPALM is further proposed with guaranteed convergence. Theoretical analysis demonstrates the robustness to Huber-$\epsilon$ contamination, and empirical results demonstrate the effectiveness in partial correspondence with the presence of outliers.

Strengths

- The paper is well-written and easy to follow, with theoretically and empirically sounded analysis. - The paper tackles the crucial robustness problem in GW distances, which could potentially benefit many OT-related research. - Experiment results demonstrate the effectiveness of RGW on the partial correspondence task, a task that is hard to addressed by most OT methods.

Weaknesses

- A section on related works is **strongly encouraged**. It would be beneficial to discuss the relation/superiority of the proposed RGW compared with other relaxed GW methods, e.g., UGW and srGW. - Some modifications in the experiment part are encouraged for better presentation. See details in the “Questions” section.

Questions

- RGW imposes an extra relaxation on the marginal distribution, i.e., $KL(\alpha|\mu)<\rho$. Comparing with UGW (UGW is equivalent to $GW_{0,0}$), can you illustrate the benefit/intuition of imposing this extra relaxation? - For Theorem 2.3, it is possible to have a similar result when both marginals $\mu, \nu$ are contaminated? - Line 161-162: the statement “By appropriately selecting … closely approximates the true GW distance (without outliers).” is inaccurate. Setting the second term in Theorem 2.3 only indicates achieving a tighter upper bound but does not necessarily indicates a better approximation. - For eq. (4-6), why the proximal operator is $KL(\pi|\pi^k)$ in Eq.(4) but $KL(\alpha^k|\alpha)$ in Eq.(5)? Since KL divergence is not symmetric, the authors should justify their choices here. - Experiments: - It is encouraged to show an empirical evaluation on the convergence of the proposed BPALM. - A key property of RGW is being robust to outlier. In the subgraph alignment part, will RGW achieve more significant improvements when the query graph is not an exact subgraph, but rather a subgraph with noises (e.g., pseudo nodes/edges) added or deleted? - For table 1, why different metrics are used for different datasets? - For figure 5, It would be good to show the results with $\rho=0$. i.e., no relaxation on the marginal, to justify the effect of marginal relaxation. - Typo: the abbreviation for fused Gromov-Wassertein should be FGW instead of FW.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

The authors properly addressed the limitations in the paper.

Summary

The authors propose a robust version of the Gromov Wasserstein (RGW) distance and theoretically bound their RGW distance applied to noisy distances in terms of the GW distance between the clean distributions and an error term depending on the choice of parameters in RGW and the distance between the clean distribution and the outlier distribution. The authors develop an algorithm for computing the RGW distance using Sinkhorn’s algorithm and Newton’s method.

Strengths

The theory provides guidance on how to choose parameters in order to get a good approximation (at least an upper bound) of the RGW distance in terms of the GW between clean distributions.

Weaknesses

To get the upper bound (mentioned above) one needs to know the GW distance between the clean distributions.

Questions

(1) How can one estimate the GW distance between clean distribution? (2) Can Theorem 2.3 be extended to where \nu also has an outlier distribution? (3) An obvious question, but can one hope to have a lower bound on the RGW distance? Numerically, I would have thought this would be fairly simple to investigate (for example in the context of the examples in Section 4.1) by computing GW of the clean distributions and then varying \rho in the RGW to see how close the upper bound in Theorem 2.3 comes to RGW.

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

The authors close the paper by discussing the heavy computational cost of the method.

Summary

The authors propose a new formulation of unbalanced Gromov-Wasserstein (GW), called Robust Gromov-Wasserstein (RGW). Instead of controlling the deviations of the OT marginals from the prior marginal distributions $\mu$ and $\nu$ directly via quadratic phi-divergences like UGW, RGW proposes to use linear phi-divergences (KL) operating on the intermediate learned marginals $\alpha$ and $\beta$ which are constrained to be relatively close to $\mu$ and $\nu$ w.r.t the KL. It is shown that this new formulation is theoretically better at handling outliers than the UGW under the assumption of Huber's contamination model. They then suggest using a Bregman proximal alternating linearisation minimisation (BPALM) algorithm to solve this problem, which is shown to converge asymptotically to a critical point. Finally, the authors show empirically on a synthetic dataset that their method is more robust to outliers, and that it leads to better performance than many competitors on subgraph alignments and partial shape correspondences.

Strengths

- Overall I find the paper well-written and I didn’t find any mistake in the proofs. - RGW is novel in the Gromov-Wasserstein literature, even if inspired from prior work on unbalanced linear OT as mentioned by authors. The theoretical results on robustness are compeling. The solver proposed by authors seem clearly competitive compared to the one for UGW, while its use is also theoretically supported. - RGW shows better results than competitors on partial shape matching of both synthetic and real-world data. - RGW also shows better results than competitors on subgraph alignment problems on many real-world graph datasets. Authors empirical study considers subgraphs of various proportions sampled from given input (full) graphs. RGW shows consistent improvements compared to competitors along these various proportions. Moreover authors show that RGW performances are rather consistent within considered sets of validated hyperparameters.

Weaknesses

- 1. Positioning w.r.t the unbalanced OT literature: - a) *[addressed by authors]* The extension to GW of the work on Wasserstein in [Balaji & al, 2020] should be more explicit. As the latter does not consider regularizing their loss function, you should justify why you do so in your GW setting. - b) *[addressed by authors]* The recent paper of [A] provides in a sense a primal point of view of robust GW, It would be good to discuss it and to benchmark it in your subgraph alignment benchmark. - 2. Robustness guarantees : - a) *[addressed by authors]* Missing proof: Could you provide the proof for UGW in Remark 2.4 ? - b) *[addressed by authors]* Tightness: Could you empirically analyze the tightness of both bounds for instance while e.g validating algorithm initializations to get better estimates of various GW terms ? - c) *[addressed by authors]* Positioning with recent analysis: Theorem 1 in [Tran & al, 2023] also provides an affine relation of the form: noisy UCOOT <= a * clean UCOOT + b. I believe that this theorem can be easily extended to UGW so could you discuss the relation of this theorem to your bounds ? - 3. Benchmark: - a) *[addressed by authors]* RGW depends on a lot of hyperparameters. Authors show that their performances were rather consistent for the hyperparameters tau and rho which are involved in the RGW program however it seems that the sensitivity analysis always includes an intensive validation of the BPALM step sizes hyperparameters. i) Could you clarify if shown results in Section 4.2 always includes this validation of BPALM hyperparameters ? ii) Could you provide a sensitivity analysis to these hyperparameters ? - b) *[partially addressed by authors using normalized degrees]* Sensitivity to input graph distribution: In the context of graph representation learning, an open question relates to a good choice of input graph distribution for tasks like graph partitioning [Xu & al, 2019a ; Chowdhury & al, 2021; Vincent-Cuaz & al , 2022]. Uniform distribution is the common simple choice which seems to be a good enough choice, but power-law distributions based on normalized degrees clearly allow better partitioning performances. Could you integrate these kind of considerations in your benchmark for subgraph alignment ? That would also provide insights on the robustness of RGW to these hyperparameters inherent to all transport problems. [A] Liu, Weijie, et al. "Robust Graph Dictionary Learning." The Eleventh International Conference on Learning Representations. 2022. NB: the citation model seems to be the wrong one for Neurips, currently names and dates instead of simple numbers. *Update after rebuttal : The authors have addressed most of my concerns through their rebuttals and discussions. Considering that the authors have undertaken to amend the paper and supplementary material accordingly, I increase my grade from 5 (borderline accept) to 7 (accept).*

Questions

I refer the authors to the weaknesses' list above for suggestions and questions that I encourage them to discuss. A last suggestion: - I believe both discussions and proofs for the Newton algorithm could be simplified simply observing that $p$ is strictly convex on the positive orthant.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.

Soundness

2 fair

Presentation

3 good

Contribution

3 good

Limitations

I think discussing the weaknesses I've mentioned and answering my questions detailed above would help identify and work around the other limitations of their current work. If the authors manage to address these, I will gladly increase my rating. This work has no negative societal impact.

Summary

The authors propose a new variant for unbalanced Gromov-Wasserstein with Kullback-Leibler (KL) divergence for marginal relaxation (Sejourne et al., 2021) by leveraging the outlier-robust approach (Mukherjee et al., 2021). The authors propose an algorithm approach by using Bregman proximal alternating linearization. The authors illustrate the advantages of the proposed method on several experiments.

Strengths

+ The authors propose a new variant for Unbalanced GW with KL divergence for marginal relaxation (Sejourne et al., 2021) by extending the outlier-robust approach (Mukherjee et al., 2021). + The authors propose to use the Bregman Proximal Alternating Linearized Method to optimize the proposed outlier-robust GW. + The authors empirically demonstrate the advantages of the proposed approach.

Weaknesses

+ The authors leverage the outlier-robust approach (Mukherjee et al., 2021) for unbalanced GW. The proposed method is essentially a new variant of unbalanced GW, but somewhat expected results. + Some claims and experimental results are needed to elaborate with more details (see the Questions part)

Questions

The ideas of the proposed method are clear. It is easy to follow the presentation. However, some parts are needed to elaborate with more details to clarify the claims and the contributions. + The authors should discuss the relation between the proposed outlier-robust GW with the approach in (Sejourne et al., 2021) for unbalanced GW and (Mukherjee et al., 2021) for outlier-robust approach. + As in Definition 2.2, the authors propose to use KL-divergence instead of quadratic KL-divergence (as in Sejourne et al., 2022) due to non-convexity. However, the problem (1) is non-convex. It is not clear the advantages of using KL-divergence over quadratic KL-divergence. Could the authors elaborate more details on this point? Additionally, as results in Theorem 3.3, could the authors comment the gain of such choice? + The quadratic KL-divergence helps to maintain the homogeneity of GW while KL-divergence will result in non-homogeneous unbalanced GW (especially when input measures have small or large total mass). Could the authors comment on the choice of KL-divergence over the quadratic KL-divergence? + For Theorem 2.3, is the bound tight? Additionally, Theorem 2.3 only address one of the input measures is corrupted, but not two input measures may be corrupted as in problem (1). Is there any limitation for this result? It is better if the authors extend this result for the case as considered in problem (1). + As in line 161-162, Theorem 2.3 gives the upper bound only, it is not clear why “robust GW value that closely approximates the true GW distance (without outliers)”. + It seems that the Proposition 3.2 is a standard optimization result about the unique solution for the root of a monotonic function? + For results in Figures 2 and 3, how to choose the hyperparameters? Do the hyperparameters affect the results? + Could the authors clarify the stopping condition of algorithms for the reported time? (since the problem is non-convex, are any algorithms sensitive to the initialization?) + As in line 285-288, could the authors elaborate how to choose the best result for those hyperparameters? + For results in Figure 5, it is surprising that the hyperparameters have negligible effects on accuracy when one maintains some fixed ratio? However, it is not clear how one can choose a suitable ratio? I suggest that it seems better to extend the range of $\rho$ and $\tau$ for results in Figure 5. Could the authors explain results in Figure 5 with more details? Minor point: + It is better to add the standard deviation for results in Table 1, Figure 4? --- Thank you for the rebuttal.

Rating

4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

2 fair

Presentation

3 good

Contribution

2 fair

Limitations

The authors have discussed limitations of their work. However, there is no discussion about the potential negative societal impact of their work.

Reply to authors

Thank you for your answers, overall I found authors' rebuttal convincing and will increase my grade. Some remarks and questions: - All complementary results provided in the rebuttal pdf and other answers are good and of interest thus should be mentioned in the paper and reported in the supplementary material with adequate experimental details (RGWD should be included in the main paper). Could you please detail the experiments you did for Figure 1 in the pdf ? it would be of interest to observe mean and std for different noise samples. - **Q5**: from my understanding, as $UGW \leq GW$, once that one established that noisy UGW $\leq$ clean UGW (up to affine transform following [Tran & al 2023]), it follows that noisy UGW $\leq$ clean GW (up to affine transform). This way we can envision that UGW also gives an estimation of clean GW but Remark 2.4 provides a kind of impossibility result in practice. So indeed it would be good to emphasize this relation with the Theorem from [Tran & al 2023] (plus potentially Theorem 2 in UGW's paper on the tightness of bi-convex relaxation).

Follow-up

We would like to follow up to see if our response addresses your concerns or if you have further questions. We are happy to address any remaining points during the discussion phase.