Any2Graph: Deep End-To-End Supervised Graph Prediction With An Optimal Transport Loss

Thank you for reviewing our paper! All your questions are very interesting and answering them helped us to significantly improve the paper.

Weaknesses:

W1: The computational performance results could be more comprehensive. While the asymptotic time complexity is provided, it would be valuable to understand how training time scales with an increase in M. This information would help readers assess the practicality of using this approach for their specific use cases.

We report the training time for the different datasets in table 5 (appendix E.2) but we agree that the complexity analysis with respect to $M$ could be more detailed. Thank you for this important remark, we will fill this gap in the final version of the paper. In short: the cost of the transformer scales with $M^2$ and the cost of PMFGW scales with $kM^3$ where $k$ is the number of iteration required for the solver. We provide a novel plot for empirical estimation of $k$ in the pdf (figure 1).

W2: It would be interesting to understand the failure cases produced by Any2Graph.

This is very important as well, thank you. We think that they are two types of failure cases. One the one hand, it can happen that the training dynamic fail to converge. We discuss this in detail in appendix F.1 along with simple methods to prevent this bad behaviour. On the other hand there is the case where $M$ is too large which we already discussed above.

W3: Any2Graph produces continuous outputs; it would be interesting to know their distribution. How will the predicted graph affect the predicted graph if we use a different threshold, e.g., 0.1 or 0.9?

Once again this is an interesting point that is not discussed at all in the paper. We provide a few novel plots in the global response pdf. As you can see the model is very robust to the choice of the treshold (table 1 and 2)! This is because the model is quite confident in his prediction, as demonstrated in the histograms (figure 3 and 4).

Thank you for your detailed review and positive feedback.

I think to improve the readability of of the paper I suggest to extend the description of the graph matching (section 2, paragraph 'Comparing graphs of the same size')

We will follow your suggestion to provide a more detailled introduction to the graph matching problem in the final version of the paper.

(UOT as loss) At the end of section 2, the authors state that Unbalanced OT introduces several additional regularization parameters (I believe three) that are difficult to tune, especially in scenarios like SGP, where model predictions exhibit wide variability during training. While I agree, I was wondering if the authors have conducted any preliminary experiments using a UOT-based loss.

Thank you for this question! UOT is actually the first thing we tried and we are greatful for this opportunity to share the insight we gained from those initial attempts.

To illustrate the discussion we can try to keep the exact same framework except we use FUGW [1] instead of PMFGW, that is we swap equation (5) with

$

FUGW(\hat{y},y) = \min_{\mathbf{T}\geq 0} \quad &\alpha_f \sum_{i,j}T_{i,j}\ell_F(\hat{\mathbf{f}}_{i},\mathbf{f}_{j})+ \alpha_A \sum_{i,j,k,l} T_{i,j} T_{k,l}\ell_A(\hat{A}_{i,k},A_{j,l}) \newline &+ \rho \varphi(\mathbf{t}_{1}, \hat{h} ) + \rho \varphi(\mathbf{t}_{2}, h )

$

Where $\mathbf{t}\_{1}$ and $\mathbf{t}\_{2}$ are the marginals of $\mathbf{T}$ and $\varphi$ is the divergence that controls the soft marginal constraints, for instance L2. Following [2], the solver solves a sequences of linear UOT problems for which a majoration-minimization (mm) algorithm is provided in [3].

This UOT variant of PMFGW looks sound, but when we tried it we ran into the following issues:

1. The FUGW solver is extremely slow, about 10x slower than that of PMFGW. We tried to implement a GPU batched version but speedup was limited due to the shared convergence criterion.
2. Tuning the hyperparameters is very hard, the soft marginal constraint $\rho$ in particular is very unstable. We provide a simple illustration below for $\alpha_A = 0$ (that is we are only trying to learn the nodes).

Denoting

$\mathbf{T}^* = \text{argmin} \quad \alpha_f \sum\_{i,j}T\_{i,j}\ell\_F(\hat{\mathbf{f}}\_{i},\mathbf{f}\_{j})+ \rho \varphi(\mathbf{t}\_{1}, \hat{h} ) + \rho \varphi(\mathbf{t}\_{2}, h )$

we know from equation (7) of [3] that $T^*_{i,j} = 0$ whenever $\alpha\_f \ell\_F(\hat{\mathbf{f}}\_{i},\mathbf{f}\_{j}) > \rho (\hat{h}\_i + h\_j)$. In particular:

$\alpha\_f \ell\_F(\hat{\mathbf{f}}\_{i},\mathbf{f}\_{j}) \geq 2\rho \quad \implies \quad T^*\_{i,j} = 0$

This means that if $\rho$ is set too low it can happen that the optimal transport is $\mathbf{T}^* = 0$. But in that case the loss backpropagated to the network is

$\mathcal{L}(\hat{y},y) = \rho \varphi(\mathbf{0},\hat{h}) + \rho \varphi(\mathbf{0},h) = \rho \varphi(\mathbf{0},\hat{h}) + \text{cst}$

And the SGD will push the neural network toward a trivial prediction $\hat{h} = 0$.

Because of the wide variability you mention we were never able to overcome such instabilities despite searching over a grid of parameters.

[1] Thual, A., Tran, Q. H., Zemskova, T., Courty, N., Flamary, R., Dehaene, S., & Thirion, B. (2022). Aligning individual brains with fused unbalanced Gromov Wasserstein. Advances in neural information processing systems, 35, 21792-21804.

[2] Séjourné, T., Vialard, F. X., & Peyré, G. (2021). The unbalanced gromov wasserstein distance: Conic formulation and relaxation. Advances in Neural Information Processing Systems, 34, 8766-8779.

[3] Chapel, L., Flamary, R., Wu, H., Févotte, C., & Gasso, G. (2021). Unbalanced optimal transport through non-negative penalized linear regression. Advances in Neural Information Processing Systems, 34, 23270-23282.

Thank you for taking the time to review our paper. We adress your many interesting questions below:

1. Can an analysis of computational complexity be provided? Can a computationally feasible solution be proposed for graph generation problems with a large number of nodes (e.g., graphs with more than 100 nodes, which are commonly encountered in various data sets)?

We fully agree that the original version of the paper was missing a detailed computational complexity analysis that we have now added. Thank you for this important remark. In short: the cost of the transformer scales with $M^2$ and the cost of PMFGW scales with $kM^3$ where $k$ is the number of iteration required for the solver. We provide a novel plot for empirical estimation of $k$ in the pdf. Thus, this version of Any2Graph, like Relationformer, cannot scale to graphs with hundreds of nodes. Our opinion is that the supervised prediction of small graphs (few tens of nodes) is already a very challenging topics with many real world application. The goal of this first work is not to scale beyond this order of magnitude but to introduce a novel framework. Yet, we agree that this is a natural question and this motivated us to augment the conclusion with a detailed plan to scale Any2Graph in future works (using approximate attention [1], heuristics [2] and entropic regularization [3]).

2. Have you considered performing ablation studies or comparisons against popular baselines?

This is a natural question but we don't think that is possible to remove any part of Any2Graph without fully breaking the pipeline. For instance if we remove the $l_h$ terms in PMFGW, the model will simply not learn to predict which nodes are activated and the accuracy will drop to 0. Yet, we would like to point out that the comparison with Relationformer can be seen as a form of ablation study, since we use the exact same architecture except for the loss. We also provide the results with and without feature diffusion which we see as a form of ablation study even if we don't formulate it that way due to space constraints.

3. Can you discuss potential limitations or failure cases of your method? How might these impact real-world applications?

This is very important as well, thank you. We think that there are two types of failure cases. On the one hand, it can happen that the training dynamic fails to converge. We discuss this in detail in appendix F.1 along with simple methods to prevent this bad behaviour. On the other hand there is the case where $M$ is too large which we already discussed above.

4. Are there scenarios where traditional methods may outperform Any2Graph?

Split from the previous question for readability. To the best of our knowledge, the surrogate regression methods are the 'tradionnal approach' for tackling SGP in a general fashion. Yet they operate on a different data regime than Any2Graph as they are able to deal with scarse data but come with a high decoding cost. For instance, Any2Graph is ill-suited to deal with the metabolite prediction task [4] that benefits from a known candidate graph set.

[1] Fournier, Q., Caron, G. M., & Aloise, D. (2023). A practical survey on faster and lighter transformers. ACM Computing Surveys, 55(14s), 1-40.

[2] D. B. Blumenthal et al. “Comparing heuristics for graph edit distance computation”. The VLDB journal

[3] Altschuler, J., Niles-Weed, J., & Rigollet, P. (2017). Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration. Advances in neural information processing systems, 30.

[4] Brogat-Motte & all. (2022). Vector-valued least-squares regression under output regularity assumptions. Journal of Machine Learning Research

We are greatful for the in-depth review of our paper. We also thank you for having pointed out typos. They will be corrected in the final version of the paper. We answer your questions below:

The author uses PMFGW as the evaluation metric at the graph level, which is also the training objective of the model. The comparison may be not fair in that case since the loss functions $l_h, l_F, l_A$ and weights can be arbitrarily chosen. Please correct me if I am wrong.

You are absolutetly correct. This is why we never use PMFGW as an objective metric in the experiments. That being said, we were very careful to report meaningful values in table 1 by fixing $l_h, l_F, l_A$ and weights for each tasks, the values used are that reported in appendix E.2. We will make this clear in the final version of the paper.

In Section 4, the author mentions that threshold 1/2 is chosen. I wonder whether and how the threshold influences the model's capability. Please show me some experimental results on one or more datasets.

This is an interesting point. We provide a few plots with different thresholds in the global response pdf. As you can see the model is very robust to the choice of the threshold as it is quite confident in its prediction.

The datasets may be relatively simple since $M=16$ is sufficient to tackle the problem. Can you give some results on more complecated datasets (i.e., with higher orders of magnitude of nodes)?

Our opinion is that the supervised prediction of small graphs (few tens of nodes) is already a very challenging problem with many realy world applications. The goal of this first work is not to scale beyond this order of magnitude. That being said, your question motivated us to train Any2Graph on a dataset with graphs of size up to size $50$ (figure 2). Still, we understand that scaling to larger graph is a natural question. Thus we have enriched the conclusion of the paper with more ideas for scaling Any2Graph in a future work (using approximate attention [1], heuristics [2] and entropic regularization [3]).

[1] Fournier, Q., Caron, G. M., & Aloise, D. (2023). A practical survey on faster and lighter transformers. ACM Computing Surveys, 55(14s), 1-40.

[2] D. B. Blumenthal et al. “Comparing heuristics for graph edit distance computation”. The VLDB journal

[3] Altschuler, J., Niles-Weed, J., & Rigollet, P. (2017). Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration. Advances in neural information processing systems, 30.

Thank you for reviewing our paper! Note that we moved the following discussion in the global response as it might interest the other reviewers:

One may argue that a clearly successful paper could have more novelty, than proposing a loss with an additional term, the significance of which I am not sure about. The positive side is that the simple design has good empirical performance, and perhaps could inspire other researchers to simply add such a term to solve graph tasks with different sizes.

We would like to further explain our point of view here. We agree that PMFGW is a relatively straightforward extension of an existing OT problem but using it for SGP is novel and we hope that the important gain in performance of such a natural framework will help to spark more interest into SGP. This is also the reason why we provide tools for benchmarking future methods (synthetic datasets and set of metrics). Finally, note that we explored significantly more complex approaches with weaker results (see the UOT discussion with reviewer bW5k).

Could you please reveal more why the reported results about Relationformer in Table 1 are largely different from their original ones? I suppose the reason may be as written around line 278 'use the same architecture for both approaches...', but I still want to make sure the difference is well understood. Is there any other issue here, like data split

This is an important point indeed. You are correct, the main difference comes from the architecture as we use a simple Resnet18 while relationformer leverage a Resnet50 and a complex MultiLevel Attention scheme. This is very specific to images inputs and we did not use it as we wanted to show the generality of our approach to different data modalities. The data splits however are exactly the same (those of the original Toulouse and USCities papers). Finally, the definition of some metrics differ between the two papers. The graph level metrics reported in relationformer rely on the TOPO and SMD score which are heavily specific to Sat2Graph tasks. We believe that the Node level and Edge level metrics are similar to ours but no exact definition are given in the transformer paper. Anyway, the final table we provide is a fair comparison relying on the same backbone and a set of well defined task-agnostic metrics.