Any2Graph: Deep End-To-End Supervised Graph Prediction With An Optimal Transport Loss
Authors: Paul KRZAKALA
Junjie Yang
Rémi Flamary
Florence d'Alché-Buc
Charlotte Laclau
Matthieu Labeau
Venue: NeurIPS 2024 spotlight (2024)
Keywords: Optimal Transport
Graph Prediction
Structured Prediction
Graph
Deep Learning
Primary area: other
TL;DR: We introduce Any2Graph a framework for deep end-to-end supervised graph prediction. The key components of the framework is PMFGW, an Optimal Transport Loss.

Abstract: We propose Any2graph, a generic framework for end-to-end Supervised Graph Prediction (SGP) i.e. a deep learning model that predicts an entire graph for any kind of input. The framework is built on a novel Optimal Transport loss, the Partially-Masked Fused Gromov-Wasserstein, that exhibits all necessary properties (permutation invariance, differentiability and scalability) and is designed to handle any-sized graphs. Numerical experiments showcase the versatility of the approach that outperform existing competitors on a novel challenging synthetic dataset and a variety of real-world tasks such as map construction from satellite image (Sat2Graph) or molecule prediction from fingerprint (Fingerprint2Graph).

Any2Graph: Deep End-To-End Supervised Graph Prediction With An Optimal Transport Loss
Paul Krzakala
Junjie Yang
LTCI & CMAP, Télécom paris, IP Paris
LTCI, Télécom paris, IP Paris
Rémi Flamary
Florence d' D'Alché-But Buc LTCI, Télécom paris, IP Paris
CMAP, Ecole polytechnique, IP Paris
Charlotte Laclau
Matthieu Labeau
LTCI, Télécom paris, IP Paris
LTCI, Télécom paris, IP Paris
Abstract
We propose Any2Graph, a generic framework for end-to-end Supervised Graph Prediction (SGP) i.e. a deep learning model that predicts entire graph for any kind of input. The framework is built on a novel Optimal Transport loss, the Burtially-Masker Fused Gromov- Wasserstein, that exhibits all necessary proper- ties (permutation invariance, differentiability) and is designed to handle any-sized graphs. Numerical experiments showcase the versatility of the approach that out- performs existing competitors on novel challenging synthetic dataset and variety of real-worke tasks such as map construction from satellite image (Sat2Graph) or molecule prediction from fingerprint (Fingerprin(2Graph),
Introduction
This work focuses on the problem of Supervised Graph Prediction (SGP), at the crossroads of Graph-based Learning and Structured Prediction. In contrast node and graph classification or link prediction widely covered in recent literature by graph neural networks, the target variable in SGP graph and particular assumption is made about the input variable. Emblematic applications of SGP include knowledge graph extraction (28) or dependency parsing [17] in natural
language processing, conditional graph scene generation computer vision [53]. [12], molecule
identification in chemistry [10]55) 49]. to name but few. Moreover, close to SGP is the unsupervised
task of graph generation notably motivated by de novo drug design g 1
SGP raises some specific issues related to the complexity of the output space and the absence of widely accepted loss functions. First, the au-Euucideen nature of the output be predicted makes both inference and learning challenging while the size of the output space extremely large. Second, the arbitrary size of the output variable predict requires model with flexible expressive power in the output space. Third, graphs are characterized by the absence of natural or ground-truth ordering of their nodes, making comparison and prediction difficult. This particular issue calls for node permutation invariant distance to predict graphs. Scrutinizing the literature through the lens of these issues, we that existing methodologies circumvent the difficulty of handling output graphs in various ways. A first body of work avoids end end-to-end learning by relying on some relaxations. For instance, energy- based models (see for instance (38 convert the problem the learning of an
All code is available at /tt.tppe/ggghhbo.cco///raaaaaaap
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

energy function of input and output while surrogate regression methods [10] implicitly embed output graphs into a given Hilbert space where the learning task boils down to veluur- regression. Note that these two families of approaches generally involve rather expensive decoding step at inference time. In what follows, we focus on methods that directly output graphs or close relaxations, enabling end-to-end learning.
One strategy overcome the need for a permutation invariant loss is exploit the nature of the input data to determine a node ordering, with the consequence that application to new types of data requires similar engineering. For instance, in de novo drug generation SMILES representations [8] are generally used to determine atom ordering. In semantic parsing, the target graph is tree that can be serialized [3] while in wwwwooooeeeeeeeeeeeeeeee graph. the task re-framed into a seqquence-t--sqqeeee problem, often addressed with large autoregressive models. Finally, for road map extraction from satellite images, one can leverage the spatial positions of the nodes to define a unique ordering (5).
Another line of research proposes to address this problem more directly by seeking to solve a graph-matching problem, i.e., finding the one-to-one correspondence between nodes of the graphs. Among approaches in this category, we note methods dedicated to molecule generation (25) where the invariant loss is based on characterization of graphs, ad-hoc the molecule application. While being fully differentiable their loss does not generalize to other applications. In the similar topic of graph generation, Simonovsky and Komodakis 337 propose more generic definition of the similarity between graphs by considering both feature and structural matching. However, they solve the problem using a two-step approach by using first smooth matching approximation followed by rounding step using the Hungarian algorithm to obtain proper one-to-one matching, which comes with high computational cost and introduces a non-differentiable step. For graph scene generation, Relationformer (36] is based on bipartite object matching approach solved using a Hungarian matcher [Р.. The main shortcoming of this approach is that fails to consider structural information in the matching process. The same problem is encountered by Melnyk et al. (28) We discuss Relationformer in more detail later in the article.
Finally, another way to approach aad-to-end learning is to leverage the notion of graph barycenter to define the predicted graph. Relying on the Implicit Loss Embedding (ILE) property of surrogate regression, Brogat- Motte et al. [9] have exemplified this idea by exploiting an Optimal Transport loss, the Fused Gromov-Wasserstee Wasserstein (FGW) distance 45 for which barycenters can be computed
They proposed two variants, a non- parametri kernel-based one and neural network-based one, referred to as FGW- Bary and FGW FGW-BaryNN, respectively. However, to calculate the barycenter, the size must be known upstream, leaving the challenge of arbitrary size unresolved. In addition, prediction accuracy is highly dependent on the expressiveness of the barycenter, i.e. the nature and number of graph templates, resulting in high training and inference costs.
efficiently 32 44
In contrast to existing works, our goal is to address the problem of supervised graph prediction in an end-to-end fashion, for different types of input modalities and for output graphs whose size and node ordering can be arbitrary.
Main contributions This paper presents Any2Graph, versatile framework for end-to-end SGP, Any2Graph leverages a novel, fully differentiable, OT-based loss that satisfies all the previously mentioned properties, i.e., size agnostic and invariant to node permutation. In addition, the encoder part of Any2Graph allows us to leverage inputs of various types, such as images or sets of tokens. We complete our framework with a novel challenging synthetic dataset which we demonstrate to be suited for benchmarking SGP models.
The rest of the paper is organized as follows. After a reminder and discussion about the relation between graph matching and optimal transport (Section ( we introduce in Section 3 size-agnostic graph representation and associated differentiable and node permutation invariant loss. This loss, denoted as Partially Masked Fused Gromov Wasserstein (PMFGW) is a novel and necessary adaptation of the FGW distance 45 This loss is then integrated into Any2Graph, an end-to-end learning framework depicted in Figure and presented in Section 4 We express the whole framework objective an ERM problem and highlight the adaptations necessary for extending existing deep leamning architectures (36] to more general input modalities.
presents thorough empirical study of Any2Graph on various datasets. We evaluate our approach on four real-world problems with different input modalities as well as Coloring, a novel synthetic dataset. As none of the existing approaches could cover the range of input modalities, nor
Section 5
2

---

scale to very large-sized datasets, we adapted them for the purpose of fair comparison. The numerical results showcase the state-of-the-an thr performances of the proposed method in terms of prediction accuracy and ability to retrieve the right size of target graphs as well computational efficiency.
2 Background on graph matching and optimal transport
An attributed graph with m nodes can be represented by fm]" Rmxd encodes node features with f, IR labeling each node indexed by i, A E R=xm is symmetric pairwise distance matrix that describes the graph relationships between the nodes such the adjacency matrix or the shortest path matrix. Further, we denote 9m the set of attributed graphs of m nodes and g = Um= Im. the set of attributed graphs of size up to M, where the size refers to the number of nodes in graph and the largest size M an important hyperparameter.
Graph representation and notations
tuple (F.A) where F = =
the following, 1m E R is the all one vector and we denote P1. m, P 1m 1m] the set of permutation matrices.
Om = (P E {0, 1] () mm
(F2, A2) E Gm are said to be isomorphic whenever there exists P E om such that (F 1: A1) = (PF2, PA,P2), in which case we denote 91 92. In this work, we consider all graphs to be unordered, meaning that all operations should be invariant by Graph Isomorphism (GI).
Graph Isomorphism Two graphs = A1). ;
Comparing graphs of the same size Designing discrepancy to compare graphs is challenging, for instance, even for two graphs of the same size 9 (F, A). 9 (F, A), one cannot simply compute a point-wise comparison as it would not satisfy GI invariance. A solution is to solve a Graph Matching (GM) problem, i.c., to find the optimal matching between the graphs and compute the pairwise errors between matched nodes and edges. This problem can be written as the following
m Σ Pr.PPrreaAAn C.R.A
GM g) min Peam
Σ (,1=1
(f)
(1)
In particular, with the proper choice of ground metrics E and lA, this is equivalent to the popular Graph Edit Distance (GED) 33 The minimization problem however Quadratic Assignment Problem (QAP) which is known to be one of the most difficult problems in the NP-Hard class 27 To mitigate this computational complexity. Aflalo et al. (2] suggested to replace the space of permutation matrices with a convex relaxation. The Birkhoff polytope (doubly stochastic matrices)
Tm = -TT- E [0, 1]mexm Tl m m T 11 m 1 m is the tightest of those relaxations as exactly the convex hull of om which makes it suitable choice (2I). Interestingly, the resulting metric is known in OT [46) field as a special case of the (Fused) -assov-assersttiin (FGW) distance
proposed by 29
FGW = min Σ (f, TETm 1
Σ Tes A.J.
(2)
However, these two points of view differ in their interpretation of the FGW metric. From the GM perspective, FGW is cast as an approximation of the original problem, and the optimal transport plan typically projected back to the space of permutation via Hungarian Matching (47) From the OT perspective, FGW is used as a metric between distributions with interesting topological properties 44.. This raises the question of the tightness of the relaxation between GM and FGW. In the linear case, i.e., when f 0, the relaxation is tight and this phenomenon is known in the OT literature as the equivalence between Monge and Kantorovitch formulation (31]. The quadratic case, however, much more complex, and sufficient conditions under which the tightness holds have been studied in both fields 35].
As seen above, both OT and GM perspectives offer ways to characterize the same objects. In the remainder of this paper, we adopt the OT terminology, e.g., we use the term transport plan place of doubly stochastic matrix. We provide quantitative analysis of the effect of the relaxation in F.2
Numerical solver Computing the FGW distance requires solving the optimization problem pre- sented in Equation whose objective rewrites (T, U) + (T, & T) where U is fixed matrix, L
3

---

fixed tensor and & the tensor matrix product. A standard way of solving this problem 47 is to use conditional gradient (CG) algorithm which iteratively solves a linearization of the problem. Each step of the algorithm requires solving a linear OT/Matching problem of cost (T, C(k) where the linear cost C(k) U L (()) is updated at each iteration. The linear problem can be solved with Hungarian solver with cost ((M)) while the overall complexity of computing the tensor product L @ T(A is theoretically ((M*). Fortunately, this bottleneck can be avoided thanks to a (M)) factorization proposed originally by Peyré et al. (32)
Comparing graphs of arbitrary size The metrics defined above cannot directly be used to compare graphs of different sizes. To overcome this problem, Vayer al. 45] proposed a more general formulation that fully leverages OT to model weights on graph nodes and can be used to compare graphs of different sizes long as they have the same total mass. However, this approach raises specific issues. In scenarios where masses are uniform, nodes in larger graphs receive lower mass which might not be suitable for practical applications. Conversely, employing non-uniform masses complicates interpretation, as decoding discrete object from a weighted one becomes less straightforward. Those issues can be mitigated by leveraging Unbalanced Optimal Transport (UOT) [4)]. which relaxes marginal constraints, allowing for different total masses in the graphs. Unfortunately, UOT introduces several additional regularization parameters that are difficult to tune, especially in scenarios like SGP, where model predictions exhibit wide variability during training.
Another close line of work is Partial Matching (PM) [33. which consists in matching small graph g to a subgraph of the larger graph 9. In practice, this can be done by adding dummy nodes to through some padding operator after which one can directly compute PM g) GM(g. P(g)) 22.. However, PM is not suited to train model as the learned model would only be able to predict graph that includes the target graph. Partial Matching and its relationship with our proposed loss is discussed in more detail in Appendix B.3
3 Optimal Transport loss for Supervised Graph Prediction
size-agnostic representation for graphs Our first step toward building an end-to-end SGP framework to introduce a space y to represent any graph of size up to M.
= F,, h E (0, 11ld F E Mxd E [0, M|MxM).
(3)
We refer to the elements of y' as continuous graphs, in opposition with discrete graphs of G. Here h; (resp. As.j) should be interpreted as the probability of the existence of node (resp. edge [i.j] ). Any
graph of G can be embedded into D with padding operator P defined as
P(g) ((1.mm)
1m
(
Fm (OM-m)
Am
Om
)) for = (Fm, Am) E Gm. (4)
O%
Oy-m. -
We denote )' = P(g) C ) the space of padded graphs For any padded graph in V, the padding operator can be inverted to recover discrete graph p-1 y G. Besides, any continuous graph I E y can be projected back to padded graphs y by a threshold operator T J + y. Note that y convex and of fixed dimension which makes it ideal for parametrization with a neural network. Hence, the core idea of our work is use neural network to make a prediction ý y and to compare it to a target g E 9 through some loss E(), P(g)). This calls for the design of an asymmetric loss é: y x y + I.
An Asymmetric loss for SGP The Partially Masked Fused Gromov Wasserstein (PMFGW) is loss between a padded target graph P(g) = (h, A) E y with real size m = ||hl] S M and a continuous prediction 9
E V. We define PMFGW (g. P(g)) as:
Oth
Σ (h. 4J
OFF Σ (L,
GA m
Σ T..Th.lalAii And)hshi (5) k.j.k.l
min TETM
M
Let us decompose this loss function to understand the extend to which it simultaneously takes into account each property of the graph. The first term ensures that the padding of a node well predicted. In particular, this requires the model to predict correctly the number of nodes in the target graph. The

---

second term ensures that the features of all non non-padding nodes (h; 1) are well predicted. Similarly. the last term ensures that the pairwise relationships between non-padded nodes (h; h2 1) are well predicted. The normalizations in front of the sums ensure that each term is weighted average of its internal losses as Ti, = M, Tigh = m and TT, Th..hhhh
m Finally a [h, Or, 0A] A3 is triplet of hyperparameters on the simplex balancing the relative scale of the different terms. For la and é, we use the cross-entropy between the predicted value after a sigmoid and the actual binary value in the target. This is equivalent to a logistic regression loss after the OT plan has matched the nodes. For Ey we use the squared &g or the cross-entropy loss when the node features continuous discrete, respectively.
key feature of this loss is its flexibility. Not only other ground losses can be considered but is also straightforward to introduce richer spectral representations of the graph [1 For instance, in Section 5 we explore the benefits of leveraging a diffused version of the nodes features.
Finally, PMFGW translates all the good properties of FGW to the new size-agnostic representation. Proposition 1 (Complexity). The objective of the inner optimization can be evaluated in ((M)). Proposition (GI Invariance). If g' and g g' then PMFGW(Ú, P(g) PMFGW(y PPgg)). Proposition 3 (Positivity). PMFGW(j) (9. P(g)) 0 with equality if and only if P(g).
See Appendix A for toy example illustrating the behavior of the loss and Appendix B.1 and B.2 for formal statements and proofs of Proposition 2 3
Relation to existing metrics PMFGW is an asymmetric extension of FGW 44 suited for compar- ing continuous predicted graph with a padded target. The extension is achieved by adding (1) novel term to quantify the prediction of node padding, and (2) the partial masking of the components of the second and third terms reflect padding. should be noted that in contrast what is usually done in OT, the node masking vectors (h and h) are not used a marginal distribution but directly integrated into the loss. In that sense, the additional node masking term is very similar to the one of OTL, 39] that proposed to use uniform marginal weight and move the part that measures the similarity between the distribution weights in an additional linear term. However, OTLp is restricted to linear OT problems and does not use the marginal distributions as masking for other terms as in PMFGW.
PMFGW also relates to Partial GM/GW Chapel al. 113 both metries compare graphs by padding the smallest one with zero-cost dummy nodes. The critical difference lies in the new vector h which predicts which sub- uub-graphs are activated, i.e., should be matched to the target. The exact relationship between Partial Fused Gromov Wasserstein (PFGW) and PMFGW is summarized below
Proposition 4. If is set to a constant value, PMFGW is equal to PFGW (up constant).
Remark 1. In that case, the vector h disappears from the loss and cannot be trained. In particular, this would prevent the model from learning to predict the size of the target graph.
The formal definition of PFGW and the proof of Proposition 4 are provided in Appendix B.3
4
Any2Graph: framework for end-to-end SGP
4.1
Any2Graph problem formulation
The goal of Supervised Graph Prediction (SGP) is to learn function f X + 9 using the training samples {(1, } E (X' x g) In Any2Graph, we relax the output space and Iearn a function f: X f:X + y that predicts a continuous graph := fx) as defined in the previous section. Assuming f is parametric model (in this work, a deep neural network) completely determined by parameter 0, the Any2Graph objective writes as the following empirical risk minimization problem:
1 m
min
Σ n
(fo
(6)
At inference time, we recover a discrete prediction by a straightforward decoding f(x) P-1
where T is the thresholding operator with threshold 1/2 on the edges and nodes and P 1 is the inverse
5

---

ENCODER
TRANSFORMER
GRAPH DECODER
PM-FGW Loss
Input data
TRANSFORMEST
TRANSFORNER RECODER
MLP
Embeddings
Pradiction
Padded Target
Figure 1: Illustration of the architecture for target graph of size 3 and M 4.
padding defined in the previous section. In other words, the full decoding pipeline P T removes the nodes (resp. edges (i,j)) whose predicted probability smaller than 1/2 i.e. h; < (resp. Aig V2)).. Unlike surrogate regression methods, this decoding step is very efficient.
4.2 Neural network architecture
The model fe X' + y (left part of Figure is composed of three modules. namely the encoder that extracts features from the input, the transformer that convert these features into M nodes embeddings, that are expected to capture both feature and structure information, and the graph decoder that predicts the properties of output graph, i.e., (h, F, Á). As will discuss later, the proposed architecture draws heavily on that of Relationformer (36] since the latter has been shown to yield to state-of-the-an results the Image2Graph task.
Encoder The encoder extracts & feature vectors in RRd from the input. Note that is not fixed priori and can depend the input (for instance sequence length in case of text input). This is critical for encoding structures as complex as graphs and the subsequent transformer particularly apt treating this kind of representation. By properly designing the encoder, different types of input data. In Appendix[C] we describe how to handle images, text, graphs, and vectors and provide general guidelines to address other input modalities.
accommodate
Transformer This module takes as input a set of feature vectors and outputs a fixed number of M node embeddings. This resembles the approach taken in machine translation, and used an architecture based on a stack transformer encoder-dccoders, akin to Shit al. (36].
This module decodes a graph from the set of node embeddings Z = [Z1, 2M using the following equation:
Graph decoder
h = o (MLP, (z.)),
A = MLP,
Å. = o OMLP' + MLP
(7)
where is the sigmoid function and MLPm. m. MLP,. MLP are multi-layer perceptrons heads corresponding to each component of the graph (mask, features, structure). The adjacency matrix expected to be symmetric which motivate us to parameterize it as suggested by Zaheer et al. [66]
Positioning with Relationformer As discussed above, the architecture is similar to the one pro- posed in Relationformer [36], with two modifications: (1) we use symmetric operation with sum compute the adjacency matrix while Relationformer uses concatenation that is not symmetric; (2) we investigate more general encoders to enable graph prediction from data other than images. However, as stated in the previous section, the main originality of our framework lies in the design of the PMFGW loss. Interestingly Relationformer uses a loss that presents similarities with FGW where the matching is done on the node features only, before computing quadratic-linea loss similar to PMFGW. In other words, they solve bi-level optimization problem, where the plan is computed on only part of the information, leading potentially suboptimal results on heterophilic graphs as demonstrated in the next section.

---

5 Numerical experiments
This section is organized as follows. First, we describe the experimental setting (5.1) including baselines. Next, we showcase the state-of-the performances of Any2Graph for a wide range of metrics and datasets 5.2). Finally, we provide an empirical analysis of the key hyperparameters of Any2Graph 5.3
The code for Any2Graph and all the experiments will be released on GitHub.
5.1 Experimental setting
Datasets We consider 5 datasets thus covering a wide spectrum of different input modalities, graph types, and sizes. The first one. Coloring, is a new synthetic dataset that we proposed, inspired by the four-color theorem. The input is noisy image partitioned into regions of colors and the goal is to predict the graph representing the regions nodes (4 color classes) and their connectivity in the image. An example is provided in Figure 5 and more details are in Appendix D Then, we consider four real-world benchmarks. Toulouse [5] Sat2Graph datasets where the goal
extract the road network from binarized satellite images of a city. USCities is also a Sat2Graph dataset but features larger and more convoluted graphs. Note that we leave aside the more complex RGB version of USCities as it was shown to require complex multi-level attention architecture (36. which is beyond the scope of this paper. Finally, following Ucak al. (42), we address the Fingerprin(2Graph task where the goal is to reconstruct& a molecule from its fingerprint representation (list of tokens). We consider two widely different datasets for this tasks: QM9 (50), a scarce dataset of tiny molecules (up to 9 nodes) and GBDI3Blum and Reymond (7] a large dataset
2 featuring molecules with up to 13 heavy atoms. Additional details concerning the datasets (e.g. dataset size, number of edges, number of nodes) are provided in Appendix E.
Compared methods We compare Any2Graph, to our direct end-to-end competitor Relationformer (36) that has shown to be the state-of-the-art method for Image2Graph. For fair comparison, use the same architecture (presented in Figure T for both approaches so that the only difference the loss. We conjecture that Any2Graph and Relationformer might benefit from feature diffusion, that replacing the node feature vector by the concatenation [F, AF) before training. We denote by "+FD" the addition of feature diffusion before training. Moreover, also compare with a surrogate regression approach (FGW-Bary based on FGW barycenters [9]. We test both the end-to-end parametric variant, FGWBary-NN where weight functions agg as well as K 10 templates,
learned by a neural network and the non- non-parametric variant, FGWBary Bary- -I.E, where the templates training samples and ag learned by sketched kernel ridge regression
[54] [8] with gaussian
kernel. Both have been implemented using the codes provided by Brogat- et al. (9), modified to
incorporate sketching. Hyperparameters regarding architectures and optimization are provided in Appendix E.2
The heterogeneity of our datasets, calls for task-agnostic metrics focusing on different fine-grained levels of the graph. At the graph level, we report the PMFGW loss between continuous prediction ÿ and padded target P(g) and the graph edit distance Gao al. 19 between predicted graph P P- and target g. We also report the Graph Isomorphism Accuracy (GI AcC), a metric that computes the proportion of perfectly predicted graphs. At the edge level, we treat binary prediction problem and report the Precision and Recall.
Performance metries
the adjacency matrix prediction Finally, at the node level, we report NODE, the fraction of well-predicted node features, and SIZE a metric reporting the accuracy of the predicted number of nodes. See Appendix E.3 for more details.
5.2 Comparison with existing SGP methods on diverse modalities
Prediction Performances Table shows the performances of the different methods on the five datasets. First, we observe that Ary2Craph achieves state-of-the-art performances for all datasets and graph level metrics. On the Sat2Graph tasks (Toulouse and USCities) we note that Relationformer performs very close to AraPGr In fact, the features (2D positions) are enough to uniquely identify the nodes, making Relationformer's 's Hungarian matching sufficient. Moreover, both methods highly benefit from feature diffusion on Fingerprint2Graphh tasks which we discuss further in Appendix H Note that both barycenter methods struggle on Toulouse, possibly due to a lack of expressivity. On
2 For computational purposes use the ABCDDEGHH' subset (more than 1.3 millions molecules).
7

---

Table 1: Graph level, edge level, and node level metrics reported on test for the different models and datasets. denotes methods that use the actual size of the graph at inference time, hence the performance reported is non-realistic upper bound. We where not able train FGWBary all dataset due to the prohibitive cost of barycenter computations. N.A. stands for not applicable.
GRAPH LEVEL
EDGE LEVEL
NODE LEVEL ACC.
DATASET
MODEL
EDIT DIST. 4
Gl Acc. 1
PMFGW
PREC. f
REC. f
NODE
SI2E 1
FGWBARY-NN
6.73
0.91
75.19
77.58
N.A.
COLORING
FGWBARY-ILE
7.60
0.90
0.93
72.17
83.81
79.15
N.A.
RELATIONFORMER
5.47
18.14
0.32
80.39
86.34
92.68
99.32
ANYZGRAPH
0.20
85.20
0.03
99.15
99.37
99.95
99.50
FGWBARY-NN'
8.11
0.00
1.15
84.09
79.68
10.10
N.A.
TOULOUSE
FGWBARY-ILE"
9.00
0,00
1.21
72.52
56,30
1.62
N.A.
RELATIONFURMER
0.13
93.28
0,02
99.25
99.24
99.25
98. 30
ANY2GRAPH
0.13
93.62
0.02
99.34
99.26
99.39
98.81
USCITIES
RELATIONFORMER
2.09
55.00
0.13
92.96
98
95.18
79.80
ANY2GRAPH
1.86
58.10
0.12
92.91
90.85
95.70
78.95
FGWBARY-NN'
5.55
1,00
0.96
87.81
70.78
78.62
N.A.
FGWBARY-ILE ILE'
3.54
7.10
0.59
80.40
75.14
91.47
N.A.
FGWBARY ILE" +FD
2.84
28.95
0.28
62.96
79.76
92.99
N.A.
QM9
REL ATOONFORRRE
9.15
0.05
0.48
21.42
4.77
99.28
91.80
RELATIONFORMER
3.80
9.95
0.22
86.07
73.31
99.34
96.0
ANY2GRAPH
3.44
7.50
0.21
86.21
77.27
99.26
93.65
ANY2GRAPH
29.85
0.14
88.08
95.45
11.40
0.00
0.43
81.96
31.49
97.77
97.45
GDB13
RELATIONFORMER +
8.83
0.01
0.29
84.14
55.89
97.57
98.65
7.45
60.41
96.15
ANY2GRAPH FD
3.63
16.25
0.11
90.88
84.86
99.80
98. 15
QM9 on the other hand, FGW- PGW-Bary-ILB performs close to Any2Graph but still outperformed, even more if add feature diffusion. It should be stressed that FGW-BaaryIil is placed here under the most favorable conditions possible, in particular with the use of a SOTA kernel and being given the ground truth number of nodes. Finally, GDBI3, the most challenging dataset, Any2Graph strongly outperforms all competitors. To summarize this part, we observe that Any2Graph and its variant Any2Graph+FD
consistently better large margin three out of five benchmarks and tied for first place with RelationFormer on the remaining ones.
Computational Performances Table shows the cost of training and inference of all methods, ex- pressed as the number of graphs processed per second. All values are computed on NVIDIA V100/Intel Xeon E5-2660. The heavy cost of barycenters computation in FGWBary makes it eral orders of magnitude slower than Any2Graph. We note that Relationformer is faster at learning time because it avoids the need to solve a QAP. Overall, proposed approach offers the best of both worlds, achieving SOTA prediction perfor- mance at all levels of the graph, a very low com- putational inference cost.
Table 2: Computational speed for the differ- ent methods in terms graphs per second on QM9. Training performance is not provided for FGWBary-ILF as the closed-form expression is computed
CPU.
METHOD
TRAIN.
PRED.
FGWBARY-ILE (K=25)
N.A.
FGWBARY-NN (K=10)
10
10
RELATIONFORMER
2K
10K
ANY2GRAPH
1K
10K
Qualitative Performances We display a sample of the graph predictions performed by the models in Figure Figure[5](eet) (left) along with larger collection in appendix G We observe that not only Any2Graph can adapt to different input modalities, but also to the variety of target graphs at hand. For instance, Coloring graphs tend to be denser, while Sat2Graph maps contain multiple connected components and Fingerprint2Graph molecules exhibit unique substructures such as loops.
5.3 Empirical study of Any2Graph properties
Sensitivity to dataset size In figure we provide the test edit distance for different numbers of training samples in the explored datasets. Interestingly, we observe that a performance plateau reached for all datasets. We also observe that Coloring/Toulouse simpler than USCities/QM9 (in

---

Any2Graph
Coloring CaloringBig
Toulouse USCities
QM9
GDB13
Coloriin
Test Edit Distance
5
USCRiee
3
22
GDB13
10*
105
10
Dataset size (log scale)
Figure 5: (Left): sample of predictions made by Any2Graph and Relationformer for given input and ground truth target. Many more are provided in G (Right): we truncate the train datasets to provide overview of Any2Graph training curves (test performances against train set size).
terms of best edit distance) and illustrate the flexibility of Coloring by bridging this complexity gap with the more challenging variation described in D
Scalability to larger graphs As stated in property [1 each iteration of the PMFGW solver scales with ((M3). Denoting k(M) the average number of it- erations required for convergence, this means that the actual cost of computing the loss scales with O (M) We provide an empirical estimation of k(M) in figure 2 which we obtain by comput- ing (F())))(())
Without FD
for pairs of graphs 91, O2 sampled from the Coloring dataset. We observe that k(M) seems linear but can be made sub-linear using feature diffusion (FD). Still, the cubic cost prevents Any2Graph from scaling beyond few tens of nodes.
10
20
30
40
50
Figure 2: Average number of solver itera-
tions required for computing PMFGW loss.
Choice of maximal graph size M The default value of M the size of the largest graph in the train set. We explore whether not overparametrizing the model with higher values bring substantial benefits. To this end, we train our model on Coloring for M between 10 (default value) and 25 and report the (test) edit distance. To quantify the effective number of nodes used by the model, we also record the number of active nodes, i.e., that are masked less than 99% of the time (see Figure 3. Interestingly. we observe that performances are robust w.r.t. the choice of M which can be explained by the number of useful nodes reaching a plateau. This suggests model automatically learns the number of nodes it needs to achieve the required expressiveness.
Active Nodes
0.4
Edit Distance
13
0.3
12
0.1
10
0.0
10 12 14 16 18 20 25
Figure 3: Effect of M test edit distance and number active nodes for Coloring.
Sensitivity to the weights a We investigate the sensitivity of the proposed loss the triplet weight hyperparameters a. To this end, we train our model on Coloring for different values a on the simplex and report the (test) edit distance on Figure 4 We observe that the performance is optimal for uniform and robust to other choices as long as there is not too much weight on the structure loss term (corner aΛ = 1). Indeed, the quadratic term of the loss being the hardest, putting too much emphasis on might slow down the training. This explains the efficiency of feature diffusion, as it moves parts of the structure prediction to the linear term. Further evidence backing this intuitive explanation is provided in F.
=1
Figure 4: Effect of a on the test edit distance.

---

Conclusion and limitations
We present Any2Graph, novel deep learning approach to Supervised Graph Prediction (SGP) lever- aging an original asymmetric Partially- -asaeed Fused Gromov-Wasserttr Wasserstein loss. To the best of our knowledge, Any2Graph stands as the first end-to-end and versatile framework to consistently achieve otate-of-the-art performances across wide range of graph prediction tasks and input modalities. Notably, we obtain excellent results in both accuracy and computational efficiency. Finally, we illustrate the adaptability of the proposed loss (using diffused features), and the robustness of the method to sensitive parameters such as maximum graph size and weights of the different terms in PMFGW.
The main limitation of Any2Graph is its scalability to graphs of larger size. Considering the tasks at hand, in this paper, we limit ourselves to relatively small graphs of up to 20 nodes.
For the future, we envision two working directions to address this issue. First, given the promising results with feature diffusion, in Any2Graph, e.g., using diffusion on the adjacency matrix to capture higher-order interactions that may occur in large graphs. More generally, this extension could be useful even for smaller graphs. Secondly, we expect that the solver computing the optimal transport plan can be accelerated using approximation. In particular, the entropic regularization (32) might unlock the possibility of fully parallelizing the optimization on a GPU while low-rank OT solvers Scetbon et al. (34] could allow Any2Graph scale to large output graphs
plan to introduce more tools from spectral graph theory [14] 20,
Acknowledgements
The authors thanks Alexis Thual and Quang Huy Tran for providing their insights and code about the Fused Unbalanced Gromov Wasserstein metric. This work received funding from the European Union's ' Horizon Europe research and innovation programme under grant agreement 101 120237 (ELIAS). Views and opinions expressed are however those of the authors only and do not necessarily reflect those of the European Union or European Commission. Neither the European Union nor the granting authority French National Research Agency (ANR) through the PEPR IA FOUNDRY project (ANR-23-PEIA- 0003) and the MATTER project (ANR-23-ERCC 23-EERCC-0006-01) The first and second authors respectively received PhD scholarships from Institut Polytechnique de Paris and Hi.Paris.
be held responsible for them. This research
also supported in part by the
References
[1] Aflalo, Y., Bronstein, A., and Kimmel, R. (2014). Graph matching: relax not? arXiv preprint urXiv:/401.770
[2] Aflalo, Y., Bronstein, A., and Kimmel, R. (2015). On convex relaxation of graph isomorphism. Proceedings of the National Academy of Sciences, 112(10):942-2947,
[3] Babu, A., Shrivastava, A., Aghajanyan, A., Aly, A., Fan, A., and Ghazvininejad, M. (2021). Non-autoreeressive semantic parsing for compositional task-oriented dialog. arXiv preprint arXiv:2104.04923.
[4] Barbe, A., Sebban, M., Gonçalves, P., Borgnat, P., and Gribouval, R. (2020). Graph diffusion wasserstein distances. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 577-592. Springer.
[5] Belli, D. and Kipf, T. (2019). arXiv preprint ArXiv:1910. 14388.
graph generation for road network extraction.
[6] Birkhoff, G. (1946). Three observations on linear algebra. Univ. Nac. Tacuman, Rev. Ser. A, 5:147-151.
[7] Blum, L. C. and Reymond, J.L. (2009). 970 million druglike small molecules for virtual screening in the chemical universe database gdb- 13. Journal of the American Chemical Society, 1333-83
10

---

[8] Bresson, X. and Laurent, Т. (2019). A two-step graph convolutional decoder for molecule generation. arXiv preprint arXiv:1906.034/
[9] Brogat-Motte, L.,, Flamary, R., Brouard, C., Rousu, J., and d' Alché Buc, F. (2022). Learning to predict graphs with fused mromov-wasserstee barycenters. In International Conference on Machine Learning, pages 2321 2335.. PMLR.
[10] Brouard, C., Shen, H., Dührkop. K., d' Alché-Buc, F., Böcker, S., and Rousu, J. (2016). Fast metabolite identification with input output kernel regression. Bioinformatics, 32(12):128-136
[1I] Carion, N., Massa, F,, Synnaeve, G., Usunier, N., Kirillov, A., and Zagoruyko, S. (2020). End-to-end object detection with transformers. In European conference on computer vision, pages 213-229. Springer.
[12] Chang, X., Ren, P., Xu, P., Li, Z., Chen, X., and Hauptmann, A. (2021). A comprehensive survey of scene graphs: Generation and application. IEEE Transactions Pattern Analysis and Machine Intelligence, 45(1):1-26.
[13] Chapel, L., Alaya, M. Z., and Gasso, G. (2020). Partial optimal tranport with applications on positive-unlabeled learning. Advances in Neural Information Processing Systems, 33:2903-222 2913.
[14] Chung, F. R. (1997). Spectral graph theory, volume 92. American Mathematical Soc.
[15] De Cao, N. and Kipf, T. (2018), Molgan: An implicit generative model for small molecular graphs. arXiv preprint 1
[16] De Plaen, H.. De Plaen, P.-F., Suykens, J. A., Proesmans. M., Tuytelaars, T., and Van Gool, (2023). Unbalanced optimal transport: A unified framework for object detection. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 3198-33 -998-
[17] Dozat, T. and Manning, C. D. (2017). Deep biaffine attention for neural dependency parsing. In International Conference on Learning Representations, ICLR. OpenReview.net.
[18] EI Ahmad, T., Laforgue, P., and d' Alché-Buc, F. (2023). Fast Kernel Methods for Generic Lipschitz Losses via ipl-Sparsified Sketches. Transactions on Machine Learning Research.
[19] Gao, X., Xiao, B., Tao, D., and Li, X. (2010). A survey of graph edit distance. Pattern Analysis and applications, 13:113-129.
[20] Gasteiger, J., Weißenberger. S., and Günnemann, S. (2019). Diffusion improves graph learning. Advances in neural information processing systems, 32.
[21] Gold, S. and Rangarajan, A. (1996). A graduated assignment algorithm for graph matching. IEEE Transactions on pattern analysis and machine intelligence, 18(4)33773388
[22] He, K., Zhang, X., Ren, S., and Sun, J. (2016). Deep residual learning image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778.
[23] Karp, R. M. (2010). Reducibility among combinatorial problems. Springer.
[24] Kingma, D. P. and Ba, J. (2014). Adam: A method for stochastic optimization. arXiv preprint 4rX.v:1412.6980.
[25] Kwon, Y. et al. (2019). Efficient learning of non autorrgreesssvve graph variational autoencoders for molecular graph generation. J Cheminform 11.
[26] Landrum, G. et al. (2013). Rdkit: A software suite for cheminformatics, computational chemistry, and predictive modeling. Greg Landrum, 8(31.10):5281.
[27] Loiola, E. M., De Abreu, N. M. M.. Boaventura-Netto, P. O., Hahn, P., and Querido, T. (2007). A survey for the quadratic assignment problem. European journal of operational research, 176(2):657-690.
[28] Melnyk, I., Dognin, P., and Das, P. (2022). Knowledge graph generation from text. In Goldberg. Y., Kozareva, 7., and Zhang, Y., editors, Findings of the Association for Computational Linguisties: EMNLP 2022, pages 1610-1622.

---

[29] Mémoli, F. (2011). Foundations of Computational Mathematics, 11(4):41--47.
distances and the metric approach to object matching.
[30] Okabe, A., Boots, B., Sugihara, K., and Chiu, S. N. (2009). Spatial tessellations: concepts and applications of voronoi diagrams.
[31] Peyré, G., Cuturi, M., et al. (2019). Computational optimal transport: With applications to data science. Foundations and Trends@ in Machine Learning, 11(5-6):355-607.
[32] Peyré, G., Cuturi, M., and Solomon, J. (2016). Grosev-wasserstiin averaging of kemel and distance matrices. In International conference on machine learning, pages 2664-2672. PMLR.
[33] Sanfeliu, A. and Fu, K.-S. (1983). A distance measure between attributed relational graphs for pattern recognition. IEEE Transactions on Systems, Man, and Cybernetics, pages 353-362.
[34] Scetbon, M., Peyré, G., and Cuturi, M. (2022). Linear-time gromov wasserstein distances using low rank couplings and costs. In International Conference on Machine Learning, pages 19347-19365. PMLR.
[35] Séjourné, T., Vialard, F.-X., and Peyré, G. (2021). The unbalanced gromov wasserstein distance: Conic formulation and relaxation. Advances in Neural Information Processing Systems, 34:8766- 8779.
[36] Shit, S., Koner, R., Wittmann, B., Paetzold, J., Ezhov, I., Li, H., Pan, J., Sharifzadeh, S., Kaissis, G., Tresp, V., et al. (2022). Relationformer: A unified framework for mmage-to-grayp generation. European Conference on Computer Vision, pages 422-439. Springer.
[37] Simonovsky, M. and Komodakis, N. (2018). Graphvae: Towards generation of small graphs using variational autoencoders. In Artificial Neural Networks and Machine Bearning-CCAN) pages 412-422. Springer.
[38] Suhail, M., Mittal, A., Siddiquie, B., Broaddus, C., Eledath, J., Medioni, G., and Sigal, L. (2021). based learning for scene graph generation. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 13936-13945.
[39] Thorpe, M., Park, S., Kolouri, S., Rohde, G. K., and Slepčev, D. (2017). transportation In p p distance for signal analysis. Journal of mathematical imaging and vision, 59:187-210.
[40] Thual, A., Tran, H., Zemskova, T., Courty, N., Flamary, R., Dehaene, S., and Thirion, B. (2022). Aligning individual brains with fused unbalanced gromov-wassersten. Neural Information Processing Systems (NeurIPS).
[41] Tong, X., Liu, X., Tan, X., Li, X., Jiang, J., Xiong, Z., Xu, T., Jiang, H., Qiao, N., and Zheng, M. (2021). Generative models for de novo drug design. Journal of Medicinal Chemistry, 64(19):14011- 1011--14027.
[42] Ucak, U. V., Ashyrmamatov, I., and Lee, J. (2023). Reconstruction of lossless molecular representations from fingerprints. Journal of Cheminformatics, 15(1):1-11.
[43] Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L.., Gomez, A. N., Kaiser, E.., and Polosukhin, I. (2017). Attention is all you need. Advances in neural information processing systems, 30.
[44] Vayer, T., Chapel, L.,, Flamary, R., Tavenard, R., and Courty, N. (2019). Optimal transport for structured data with application graphs. In International Conference Machine Learning (ICML).
[45] Vayer, T., Chapel, L., Flamary, R., Tavenard, R., and Courty, N. (2020). Fused gromov- wasserstein distance for structured objects. Algorithms, 13 (9):212.
[46] Villani, C. (2009). Optimal transport: old and new. Springer, Berlin.
[47] Vogelstein, J. T., Conroy, J. M., Lyzinski, V., Podrazik, L. J., Kratzer, S. G., Harley, E. T., Fishkind, D. E., Vogelstein, R. J., and Priebe, C. E. (201 Fast approximate quadratic program- ming for large (brain) graph matching, arXiv preprint arXiv:1112.5507.
12

---

[48] Wang, R., Guo, Z., Pan, W., Ma. J., Zhang, Y. Yang, N., Liu, Q., Wei, L.,, Zhang, H., Liu, C., Jiang, Z., Yang, X., and Yan, J. (2024). Pygmtools: A python graph matching toolkit. Journal of Machine Learning Research, 25(33):1-7.
[49] Wishart, D. S. (2011). Advances in metabolite identification. Bioanalysis, 1(1)))17697771)888
[50] Wu, Z.., Ramsundar, B., Feinberg, E. N., Gomes, J., Geniesse, C., Pappu, A. S., Leswing, K., and Pande, V. (2018). Moleculenet: a benchmark for molecular machine learning. Chemical science, 92):513-530.
[51] Xiong, R., Yang, Y., He, D., Zheng, K., Zheng, S., Xing, C., Zhang, H., Lan, Y., Wang, L.,, and Liu, T. (2020), On layer normalization in the transformer architecture. In International Conference on Machine Learning, pages 10524-10533, PMLR.
[52] Xu, K., Hu, W., Leskovec, J., and Jegelka, S. (2018). How powerful are graph neural networks? arXiv preprint arXiv: /8100008000000020.
[53] Yang. J., Ang, Y. Z.,, Guo, Z., Zhou, K., Zhang, W., and Liu, Z. (2022). Panoptic scene graph generation. In European Conference on Computer Vision, pages 178-196. Springer.
[54] Yang, Y., Pilanci, M., and Wainwright, M. (2017). Randomized sketches for kernels: Fast and optimal nonparametric regression. The Annals Statistics, 45(3):91--
[55] Young, A., Wang, and Röst, H. (2021). Massformer: Tandem mass spectrum prediction with graph transformers. arXiv preprint arXiv:2111.04822
[56) Zaheer, M., Kottur, S., Ravanbakhsh, S., Poczos, B., Salakhutdinov, R. R., and Smola, A. J. (2017). Deep sets. Advances neural information processing systems, 30.
13

---

A Illustration of PMFGW On A Toy Example
On the one hand, we consider target graph of size g (F A2) where
fi
00
!)
F2 =
A
1
for some node features fi and fg. For M the padded target is P(g) (h, F, A) where
f
0 1
h F
f2
A
1 0
On the other hand, we consider a predicted graph Yo,h
(h, F, A) that has the form
1
a
h
h F 1
A
0
a
0
for some a, h [0, 1]. The loss between the prediction and the (padded) target is
Larain h) PMFGW (ya,h. Pg(g))
We are interested in the landscape of this loss. First of all, it appears that ý1,1 and Vo.o and P(g) are isomorphic, thus get two global minima Cuain [1, 1) Liiin (0, 0) = 0. Going into greater detail, it can be shown that for (a, b) La(a, b) (a b) we have the following expression
Luaan (a, h) min (1-a) a)² + (1 h)?:a² 2
and the optimal transport plan is the permutation 2,) when (1 - a)² 31 - h)2 < + 312 and (1,3, 2) otherwise. this toy example, the optimal transport plan always a permutation.
At inference time, we could similarly be interested in the edit distance between the (discrete) prediction and the target
Leval (a, h)
Once again, the expression can be computed explicitly
Leval (a, h) [a 0.5 and h 0.5] 1[a > 0.5 and 0.5]
We provide in Figure an illustration of the edit distance and the proposed loss that is clearly continuous and smoothed version of the edit distance which allows for learning the NN parameters.
B Formal Statements And Proofs
In this section, we write
PMFGW(). P(g)) min
EIetenhhnhit En En ET.TTelAAAA Agd)hsu
TERM
k...J.
meaning that we absorb the normalization factors in the ground losses to lighten the notation. Alternatively, also consider the matrix formulation:
PMFGW P(g)) = min (T.C) T
TERM
14

---

1.0
1.0
1.0
0.6
0.8
0.4
0.6
0.5
0.5
0,4
0.2
0.2
0.0
0.0
0.0
0.0
0.5
1.0
0.0
0.5
1.0
Figure 6: Heatmap of Liain (left) and Leval (right). The red line represents the transition between the regime where the optimal transport plan is the permutation (1, 2, 3) and that where it is (1, 2). In both cases, the optimal transport plan is a permutation.
where C.2 = Co (hi,,hg) + ly fy),,, Ligaa = (a(As,, A and @ is the tensor/matrix product.
B.1 PMFGW fast computation
The following results generalize the Proposition of Peyré et al. 32 that it can be applied the computation of PMFGW.
Proposition 5. Assuming that the ground loss than can decomposed as ((a = (a) + f2()) h1 (b)) for any transport plan T Raxm and matrices A, W R and A W E m then the tensor product of the form
(L Thi = Ao
38
can be computed
L 2 - + WTU, - ViTV?.
where U₁ = f(A) W. U2 f2(A)) W V1 (A) W, V2 = h2(A w and
[]] is the
point-wise multiplication.
Proof. Thanks the decomposition assumption the tensor product can be decomposed into terms:
(L 2 This Σ TTs
Σ
-E hy (22,)
3
35'
35'
Eh(As)) Σ Ti +
of Wis Enn(A.)), Σ Sy
Introducing U1, U2 V1 and U2 defined above, write:
(L 2 Th (U1)ss)) Σ Thy -(Us)eess ETs E(Vi)ss ETs
((W)) de + [UUr)e ( (Tir)ssT
which concludes that T UT + WTU. - V.TV..
Remark (Computational cost). U. U2, VI, V2 can be pre-computed for a cost of O(n m²) after which L & T can be computed (for any T) at cost of Omm?² + nm²).
15

---

Remark Kkullback-eiblee divergence decomposition). The Kullback-Leiben divergence ground loss in experiments satis- fies the required decomposition given fi()) = - log(p)) f2(9) = q glog(1) + (1 - q) log(1 - q).
[T(p 9) q log y + (1 q) log (1-p)² which
(1-4)
h1 (p) = log( 2) and, h2(g) =
Remark 4. The tensor product that appears in PMFGW is special case of this theorem that corresponds to n = m M, Wij and W = hghy. Thus, proposition iis direct corollary.
B.2 PMFGW divergence properties
First, we provide below more detailed version of Proposition
Proposition 6 (GI Invariance). For any m S M, U, 8' and g.g E Im. we have that PMFGW( ((g)) PMFGW( P(g')).
~ j~v.g~
Proof. We denote 9 (h, A, and P(g) (h, F. A). Since and g' are isomorphic, there exist a permutation P aw such that j'=(Ph PF, PAP"). Moreover, the fact that g and g' are isomorphic implies that P(g) and P(g)) are isomorphic as well, thus there exist a permutation Q E OM such that P(g') (Qh, QF, QAQ?). Plugging into the PMFGW objective we get
PMFGW(J P(g'))
min
E (PP)) (Qh),) Σ (PP)) (QF)
TETM
Te,Tu,l
)ikks (UAA))))((PPPP")
TPT h2) + Σ (PT T hj)h
min TETM
(PTTQ) (P"TQ) (PTTQ) Az1)hyh
Denoting T = PTTQ we have that
PMFGW(J/ P(g'))
TERM Ennglahhahi) ETsees(R f2)hg
min
iddil PMFFG P(g)).
We now provide a more detailed version of Proposition 3
Definition 1. We say that f: X x X + R is positive when for any x, E & x X, A(x, v) 2 0 with equality if and only if y. Proposition 7 (Positivity). Let assume that l, [0,1] (0, 1) + R, Rd x Rd R and
l [0, 1] x (0, + IR. are positive. Then we have that for any ğ V.9 EG:
i) PMFGW(0. P(g)) 2
ii) There is equality if and only if g- P(g)
(ii) In that case P-1T(p10 ()) g
Proof. The direct implication of ii) is the only statement that not trivial. First, let us show that PMFGW(). ((g)) O, the optimal transport T is permutation. Recall that any transport plan is
16

---

convex combination of permutations 66 i.. there exist Ai. dx EJO, 1] and Pi..... Px OM
such that Σ k= d and T
-E P
Thus
0 = CT T
(8)
K
K Σ
Σ Aa Pk C) Σ
PA
(9)
Aight
This is sum of positive terms, thus all terms null and in particular, for any
0 P C) + (PA.
(10)
Thus all the Pa are optimal transport plans. In the following, chose of them and denote it P. Moving back to the developed formulation of PMFGW we get that
PMFGW (0. P(g))
E (aa idikd
Once again this is a sum of positive terms thus for all i, k. and
Pestn(hs, hy) Pe.l PLyPR.LA Agtdhghh
and thus
0 hb)) =PP(")) Fj)h, (A((P" AP) A3.)hyhi
And from the positivity of en. Ey and la we get that: h = h, PT m] = Fi: m| and Pd AP|: m, m] = A(: m, m]. Since the nodes i >> m are not activated, by abuse of notation we simply write P F and p AP A. This concludes that P(g).
B.3 PMFGW and Partial Fused Gromov Wasserstein
Following Chapel et al. 13 we define an OT relaxation the Partial Matching problem.
For large graph 9 = (f, Å) E GM and smaller graph g = (F, A) Gm, the set of transport plan transporting subgraph of ğ to g be defined as
M. (T E [0,
1] Mxm
T1m S Las T 1M = 1m TTm =)
and the associated partial Fused Gromov Wasserstein distance is
M
M T (f, +
partialFGW((gg) = min TEEM.
Aga)-
1==1
In the following, show that partialFGW g) is equivalent to the padded Fused Gromov Wasser- stein distance defined as
M ΣΣ T Tefle(f.
M
paddedFGW($.g))
min TETM i=1
Σ
Σ T...AAA
i,k=
Lemma's Any transport plan E TM has the form (T, Te) where T, is partial transport
plan i.c. Tр E MM
17

---

Proof. Let us check that Tp is in TM.
MM = T M Tp1,, m + Mr 2 Tp m
T 1M And thus Ty LMs 1m T2 LM
LM T 1M
From the previous we immediately get that 1 Ty m
Lemma 6. For any partial transport plan Tp E TMM there exist T2 E R MM((M-m) such that
T= (Tp T2) E TM-
Proof. Let define p == 1M Tplm. This is the mass of the larger graph that is not matched by Tp. Note that since Tp E TM.m have that p 2 0. Thus the remaining mass uniformly across the padding nodes, Let us check that (Tp T2) E aM is indeed valid transport plan.
set T2 M-m pl T M-m i.e. spread
Ti Tp + Tola-m -Tp1m +p 1m
T 1 M
1
TT1
=
T
p
M M-m
1
(M-IN)
1m
1m (m-
M-m (1]
1
T
f 1 1M)
1M
Proposition 8. paddedFGW and PartialFGW are equal and any optimal plan T of PaddedFGW has the form T (Tp T2) where TØ is optimal for partialFGW.
Proof. Follows directly from the two previous lemmas.
Remark 7. Since PaddedFGW is equivalent to the proposed PMFGW loss and only if l, set to constant, proposition is direct corollary of Proposition 8
Remark The algorithm proposed to compute PMFGW can applied to PaddedFGW and thus to PartialFGW. Hence, we have indirectly introduced an alternative to the algorithm of Chapel et al. [33. Further comparisons are left for future work.
C Encoding Any Input To Graph
Philosophy of the Any2Graph encoder Any2Graph is compatible with different types of inputs, given that one selects the appropriate encoder. The role of the encoder is to extract a set of feature vectors from the inputs v i.e. each input is mapped to list of & feature vectors of dimension d, where is not necessarily fixed. This critically different from extracting a unique feature vector (k 1). If A is set to 1, the rest of the architecture must reconstruct and the architecture akin to that of an auto-encoder. In Any2Graph, we avoid this undesirable bottleneck by opting for richer (k > 1) and more flexible (k is not fixed) representation of the input. The feature vectors are then fed to a transformer which is well suited to process sets of different sizes. Since the transformer module is cormmutation-nvariian any meaningful ordering is lost in the process. To alleviate this issue, we add positional encoding to the feature vectors whenever the ordering carries information. Finally, note that the encoder might highly benefit from pre-training whenever applicable; but this goes beyond the scope of this paper.
entire graph from single vector,
We now provide general description of the encoders that can be used for each input modality.
18

---

Graph Nmural
Comvolational [CNN
Sel-Aftentio
Ieput
Set Features
(grop()
Set Features
Input (Image)
Features
Graph Noural
Convolationaal
SelfAAltendon
[GNN]
Inpae (Image)
Isput (Tect)
Inpurt (graph)
Figure 7: Illustration encoders extracting k features vectors different input modalities. For text/fingerprint, k is the number of input tokens. For graphs, k is the size of the input graph. For images, & depends on the resolution of the image and the CNN kernel size.
Images For Image2Graph task we use Convolutional Neural Networks (CNN) as suggested in [36]. From an input image of shape h X w c the CNN outputs a tensor of shape H W x C which is seen as H x W feature vectors of dimension C. The raw output of the CNN is reshaped and passed through a linear layer produce the final output of shape H W x de- Since the ordering of the H x W features carries spatial information we add positional encoding accordingly.
For tasks where the input is list of tokens (e.g. Text2Graph or Fingerprint2Graph) we use the classical NL.P pipeline: each token transformed into a vector by an embedding layer and the list of vectors is then processed by transformer encoder module. In text2graph the tokens ordering carries semantic meaning and positionnal encoding should be added. On the contrary, in Fingerprint2Graph, the fingerprint ordering carries information and the permutation invariance of the transformer module a welcomed property.
Fingerprint/text
Graph For graph2graph task (not featured in this paper) would suggest using Graph Neural Network (GNN) [52]. A GNN naturally extracts feature vectors from an input graph, where is the number of nodes in the input graph. No positional encoding is required.
Vector We explore Vect2Graph task in Appendix D The naive encoder we composed parallel MLPs devoted to the extraction of the k feature vectors. This approach is arguably simplistic and more suited encoders should be considered depending on the type of data.
D COLORING: new synthetic dataset for benchmarking Supervised Graph Prediction
We introduce Coloring, new synthetic dataset well suited for benchmarking SGP methods. The main advantages of Coloring are:
The output graph is uniquely defined from the input image.
The complexity of the task can be finely controlled by picking the distribution of the graph sizes, the number of node labels (colors) and the resolution of the input image.
One can generate as many pairs (inputs, output) as needed to explore different regimes, from abundant to scarce data.
To generate new instance of Coloring, apply the following steps:
0) Sample the number of nodes (graph size) m. In this paper, we sample uniformly on some interval [Mminn Mmax].
19

---

Figure 8: Illustration of the five steps follow to generate new instance of Coloring.
1) Sample m centroids on [0, 1] x [0, 1]. In this paper, we sample the centroids as uniform i.i.d. variables.
2) Partition 1] x [0, 1] (the image) in a Voronoi diagram fashion 30 In this paper, we use the L, distance. and an image of resolution
H.
Create the associated graph i.c. each node a region of the image and nodes are linked by an edge whenever the two associated regions are adjacent.
4) Color the graph with K colors. In this paper. we use K 4. A coloring is said to be valid whenever adjacent nodes have the same color. Note that graph coloring is known to be NP-complete [23].
5) Color the original image accordingly.
As highlighted above, Coloring a flexible dataset. Beyond the default dataset simply referred as Coloring we also explore 2 variations in our experiments. ColoringBig is a more challenging dataset that features larger graphs. Coloring Vect is variation of Coloring where the input image flattened and treated as vector allowing us explore synthetic Vect2Graph task. The properties of these datasets, along with the performances of Any2Graph are reported table We hope that Coloring will be used to benchmark future SGP methods.
Table 3: Summary the properties of the variations of Coloring considered in this paper. We also report the test edit distance achieved by the different models. For FGWBary report the best performing variant that is ILE for ColoringVed Vect and NN for Coloring. None scales to ColoringBig.
DATASET
Man
Max
NUMBER OF SAMPLES
ANY2GRAPH
RELATIONFORMER
FGWBARY-NN
VoloringVect
4
6
16
100K
0.46
1.40
2.09
Coloring
10
100K
0.20
5.47
6.73
ColoringBig
10
15.
64
200K
1.01
8.91
20

---

E Additional Details On The Experimental setting
E.1
Datasets
In this paper, consider five datasets for which provide variety of statistics in Table Coloring a new synthetic dataset which we describe in detail in Appendix [ Toulouse (resp. USCities) is
Sat2Graph dataset [5] where the inputs images of size 64 64 (resp. 128 128). QM9 [50] and GDB13 7 are datasets of small molecules which we use to address the Fingerprint2Graph task. Here, we compute a fingerprint representation of the molecule and attempt to reconstruct the original molecule from this loss representation. Following Ucak et al. 42 we use the Morgan Radius-2 fingerprint [26] which represents molecule by bit vector of size 2048, where each bit represents the presence/absence of a given substructure. Finally, we feed our model with the list of non-zeros bits, i.c. the list of substructures (tokens) present in the molecule. The list of substructures has min/average/max length of 2/21/27 for QM9 and /229/36 for GDB13.
Table 4: Table summarizing the properties of the datasets considered.
DATASET
SiZE (TRAII/TEST/VALII)
NODES
EDGES (MIN/MAAN/MA))
INPUT MODALITY
NODE FEATURES
(MIN/MEAN/MAX)
Coloring
100k/10k/10k
4/7.0/10
3/10.9/22
RGB IMAGES
CLASSES (COLORS)
Toulouse
80k/10k/10K
3/6.1/9
2/5,0/14
GREY IMAGES
2D POSITIONS
USCinies
130K/10k/10K
2/7.5/17
1/5.8/20
GREY IMAGES
2D POSITIONS
120k/10k/10k
0/9.4/13
TOKENS
(ATOMS)
GDB13
1300k/70</70k
5/12.7/13
5/15.15/18
LIST TOKENS
CLASSES (ATUMS)
E.2 Training And Architecture Hyperparameters
Encoder We follow the guidelines established in for the choice of the encoder. In particular, all encoders for Coloring, Toulouse and USCities are CNNs. The encoder for Coloring is a variation of Resnet18 [22). where remove the first max-pooling layer and the last blocks accommodate for the low resolution of our input image. We proceed similarly for Toulouse except that we only remove the last block. For USCities we keep the full Resnet18. For the FingerprintGrrahh datasets, we use transformer encoder. In practice, this transformer encoder and that of the encoder-decoder module are merged avoid redundancy. All encoders end with a linear layer projecting the feature vectors to the hidden dimension de.
Transformer We use the Pre-LN variant Xiong et al. 51 of the transformer encoder-decoder model described in 43). To reduce the number of hyperparameters, encoder and decoder modules both consist of stacks of N, layers, with N₁, heads and the hidden dimensions of all MLP set to 4 x de.
Decoder All MLPs in the decoder module have one hidden layer.
Optimizer We train all neural networks with the Adam optimizer Kingma and Ba (24) learning rate 17, 8000 warm-up steps and all other hyperparameters default values. We also use gradient clipping with a max norm set to 0.1.
All hyperparameters given in Table
Table 5: Hyperparameters used to train our models. We also report the total training time on NVIDIA V100.
PMFGW aP
ARCHITECTURE
OPTIMIZATION BATCHSIZE
DATASET
Qu
de
N
N
M
STEPS
TIME
Coloring
1
256
3
8
12
3E-4
128
75k
411
Toulouse
5
256
4
8
12
1E-4
128
100k
811
USCittes
0.5
256
4
8
20
1E-4
128
1.50k
1411
OM9
128
3
3E-4
128
150K
GDB13
1
512
5
8
15
3E-4
256
150K
24H
21

---

E.3 Metrics
In the following, we provide detailed description of the metries reported table
Graph Level First report the PMFGW loss between continuous prediction ý and padded target P(g). For this computation, we set a to the values displayed in table
Then we report the graph edit distance Gao et al. 19
between predicted graph P- and target All edit costs (nodes and edges) are set 1. Note that for Toulouse and USCities, node labels are 2D positions and we consider two nodes features to be equal (edit cost of 0) whenever the L2 distance is smaller than 5% than the image width.
which we compute using Pygmtools Wang et al. 48
EDIT(P TT.9)
Finally, we report the Graph Isomorphism Accuracy GI ACC that
GI Acc(Ú.g) = L[EDDI(PP (T0.)) =0]
Node level Recall that for prediction (h, F, A) the size of the predicted graph is m || 0.5|/1. Denoting m the size of the target graph we report the size accuracy:
SIZE Acc(Ú, 9) 1[m m].
The remaining node and edge-level metrics need the graphs to have the same number of nodes. To this end, select the nodes with the highest probability h, resulting in graph 9 (F) A) with ground truth size. This is equivalent to assuming that the size of the graph is well predicted. Then we Pygmtools to compute one-to-one matching a between the nodes of and g that be used to align graphs (we use the matching that minimizes the edit distance). In the following, we assume that g and 9 have been aligned. We can now define the node accuracy NODE ACC
NODE Acc g) - m
Σ [[ FJ
m
which is the average number node features that are well predicted.
Edge level Since the target adjacency matrices are typically sparse, the edge prediction accuracy is a poorly informative metric. To mitigate this issue we report both Edge Precision and Edge Recall
Σij=1 1[A = 1, A = 1]
EDGE PREC.(İ.))
En 1[Ai, 1]
Eij=1 11 1[Ai,s = Ai. = 1]
m
EDGE PREC.(ÿ.g)
Σmj=1 1|Ars =
All those metrics are then averaged other the test set.
E.4 Compute resources
We estimate the total computational cost of this work to be approximately 1000 hours of GPU (mostly Nvidia V100). We estimate that up to 70% of this computation time was used in preliminary work and experiments that did not make it to the paper.
22

---

Additional Experiments and figures
Learning dynamic
The PMFGW loss is composed of three terms, two of them linear and account for the prediction of the nodes and their features, one quadratic and accounts for the prediction of edges. The last term is arguably the harder minimize for the model, performs best when the two first terms are minimized first which then guides the minimization of the structure term. In other words, the model must first learn predict the nodes before addressing their relationship. Fortunately, this behavior naturally arises in Any2Graph as long as aA, the hyperparameter controlling the importance of the quadratic term, is not too large. This is illustrated in figure g
consequence,
observe that the training
loss features
loss features
Losses (test set)
loss mask
Losses (test set)
loss mask
1.0
loss structure
1.0
loss structure
0.5
0.5
0.0
0.0
Epochs
Epochs
Figure 9: First epochs of training for Coloring. The test values of the 3 components of the loss are reported. On the left (resp. right) a is [1, 1, (resp. [1,1,00). In the first scenario, the first two terms of the loss are learned very fast and the structure is optimized next. In the second scenario, setting aA 10 prevents this desirable learning dynamic.
For the datasets where many nodes in the graphs share the same features (QM9 and GDB13) the good prediction of the nodes and their features is not enough to guide the prediction of the edges and this desirable dynamic does not occur. This motivates us to perform Feature Diffusion (FD) before training. The diffused node features carry a portion of the structural information. This makes the node feature term slightly harder to minimize much easier and we recover the previous dynamic. This is illustrated in figure 10
turn, the subsequent prediction of the structure
0.5
0.5
loss features
loss features
Loss (test set)
0.4
loss mask
Loss (test set)
0.4
loss mask
lass structure
loss structure
0.2
0.2
0.1
0.1
0.0
10
12
Epochs
Epochs
Figure 10: First epochs of training for GDB13, The test values of the 3 components of the loss are reported. On the left, we perform FD before training, on the right, we leave node features unchanged. We observe that the feature loss decreases slightly slower with FD (the features are more complex) but the minimization of the structure term is largely accelerated.
F.2 Effect of the OT relaxation on the performances
As stated in 2 that we do not project the OT plan back the set of permutations with a Hungarian matcher before plugging in the loss in Simonovsky and Komodakis (3]. Testing the effect of adding this extra
we adopted the OT point of view when designing Any2Graph. In practice, this means
23

---

step we observed a 5% to 10% increase of the edit distance across datasets (table 6 along with more unstable training curve (figure IT). This confirms that continuous transport plan provides slightly more stable gradient than discrete permutation, which aligns with the findings of De Plaen al. 16 on the similar topic of object detection.
Dataset
Coloring
Toulouse
USCities
QM9
GDBI3
ED without Hungarian
0.20
0.13
1.86
2.13
3.63
ED with Hungarian
0.23
0.15
2.03
2.08
3.86
Table 6: Effect of adding Hungarian Matching on the performances evaluated with the test edit distance. We observe, that Hungarian Matching slightly decreases the performances on all datasets but QM9.
With Hungarian Matching
Without Hungarian Matching
Loss (test set)
0.25
0.20
0.15
5
10
15
20
25
30
Epochs
Figure 11: First epochs of training for GDBI3 with and without projection of the optimal transport plan to the set permutations with Hungarian matching. Hungarian matching slightly decreases the performances and induces more oscillations of the loss, which could be explained by less stable gradient.
F.3 Repeatability
We checked the robustness of Any2Graph to the seed used for training. For each dataset, we ran times the whole training pipeline with 5 random seeds. The results are displayed in table Notably, we observe that all tate-of-thee-rr performances observed in table hold even we had reported the worst seed (we reported the first seed).
Dataset
Coloring
Toulouse
USCities
QM9
GDB13
Edit. (Max)
0.23
0.16
2.08
2.19
3.63
Edit. (Mean)
0.21
0.14
1.89
2.10
3.49
Edit. (Min)
0.2
0.13
1.7
2.03
3.43
Edit. (Std) 0.01
0.08
0.14
0.05
0.07
Table 7: For each dataset, we report the maximum, average, minimum and the standard deviation of the Any2Graph test edit distance over random seeds.
24

---

G
Additional Qualitative Results
G.1
Qualitative results on COLORING
Input
Target
Any2Graph
Relationformer
FGWBary-ILE
FGWBary-NN
Figure 12: Graph prediction on the Coloring dataset.
25

---

G.2
Qualitative results on QM9
Input
Target
Any2Graph
Relationformer
FGWBary-ILE
FGWBary-NN
26380 LAE
10130 OF
Figure 13: Graph prediction on the QM9 dataset.
26

---

G.3
Qualitative results on GDB13
Input
Target
Any2Graph
Relationformer
228
111 925
2024
1332 1466 1eas
1922 2039
207 222
613
1233 1204
2724 1880
68 3633030
522 425
3241240
3751 1012 1803
2005 70
1818 1836
2012
201366 96
137 337
1872 2040
23 283453222
2403008
2050 2300
2557
2006 2039
201514
DO0 628
025 2423
1223
1382 1058
Figure 14: Graph prediction on the GDB13 dataset.
27

---

G.4
Qualitative results on TOULOUSE
Input
Target
Any2Graph
Relationformer
FGWBary-NN
FGWBary-ILE
Figure 15: Graph prediction on the Toulouse dataset.
28

---

G.5
Qualitative results on USCities
Input
Target
Any2Graph
Relationformer
Figure 16: Graph prediction on the USCities dataset.
29

---

G.6 Out of distribution performances
We tested if, once trained on Toulouse dataset, the predictive model able cope with out-of- distribution data. Figure [7 shows that this is the case on these toy images, that are not related to satellite images road maps. We leave for future work the investigation of this property.
I
L
Figure 17: Any2Graph trained on Toulouse performing on out-of-distribution inputs. Input images displayed on top row and prediction in the bottom row.
30

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The claims about the performances of Any2Graph are demonstrated numer-
ically in section 5 Those about the properties of PMFGW are stated in 3 and proofs
provided in
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
The current limitations of the work are stated explicitly the dedicated last section.
Justification:
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
31

---

Answer: [Yes].
Justification: To the best our knowledge, all proofs provided are correct. Note that the propositions stated in the core of the paper are informal. All formal propositions and proofs are provided in
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof's provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Question:
Answer: [Yes]
We make a special effort to provide all hyperparameters and experimental settings in section and appendix E We also provide the code of the paper and will release a GitHub repository upon publication of the paper.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should be possible for other researchers to have some path to reproducing verifying the results.
32

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: We provide the code of the paper in supplementary materials and plan to release GitHub repository upon publication of the paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cc.
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https for more details.
7 //nips. //nips.cc/pub/l/ wwtpc//pppp.guueeeeeooeppppp httpa///guuddes/odeeuubbiiisses prbooeSubmissionool11..
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All those details are provided in appendix D Note that for the data splits we used the existing splits when available (OM9, Toulouse and USCities) and created our own random split for the other datasets.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
would be computationally too expensive to report the eиror bar for all experiments. However, make an extra computational effort to run 5 times (with random seeds) what we consider to be the main experiments to check that our conclusions are statistically significant (appendix F3
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
33

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: We include a discussion regarding the computational cost of the different models in the main paper. Besides, we report the exact computing resources used to train Any2Graph and an estimate of the total computing cost of the research project appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics huttps://neurip::: httsss/rrss///pprrrs...////////p
Answer: [Yes]
Justification: To the best of knowledge, this work is not harmful in any of the ways detailed in the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g.. there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
34

---

Answer: [NA]
Justification:
This paper is a fundamental research paper about supervised learning.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Answer: [NA]
Justification:
No need for responsible release of code or data.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All datasets are properly referenced and cited.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
35

---

The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperssi thoode com comddatasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: All new assets (model, loss, synthetic dataset) are described in the core paper and supplementary, and the associated code is provided.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
We did not use any crowdsourcing nor human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: We did not any crowdsourcing nor human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
36

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
37


Reviews:
[{"review_id": "fbzU3Bmikg", "reviewer": "Reviewer_CHfS", "summary": "This work aims to design an end-to-end pipeline for structured graph prediction (SGP). The proposed loss, PMFGW, is a extension of Fused Gromov Wasserstein to generate graphs with bounded arbitrary sizes, along with a standard pipeline carefully modified from Relationformer. It is empirically verified on public tasks and a novel synthetic dataset, Coloring, with outstanding performance.", "questions": "1. 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?", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The solution is straightforward with good empirical performance: the extension is clear as penalizing loss for misalignment of padding dependent of graph sizes, and the empirical performance is outstanding against the related work, Relationformer.\n2. The presentation is well written: for each contribution and novel design, the details are closely accompanied with reasons of design and necessary discussion about related works, which makes it easy to position this work in the literature.", "weaknesses": "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. \n\nHence, I would like to provide a score of weak accept for now, and see how the other reviewers think about this potential argument.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing our paper! Note that we moved the following discussion in the global response as it might interest the other reviewers:\n\n> 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.\n\nWe 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**).\n\n> 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\n\nThis 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "UXmm19POSb", "reviewer": "Reviewer_YNCo", "summary": "This work proposes Any2Graph, an end-to-end deep learning framework for Supervised Graph Prediction (SGP) leveraging a novel OT loss called PMFGW. The model consistently achieves state-of-the-art performances across multiple graph prediction tasks and input modalities.", "questions": "- 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 $\\alpha$ can be arbitrarily chosen. Please correct me if I am wrong.\n- 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.\n- The datasets may be relatively simple since $M=16$ is sufficient to tackle the problem. Can you give some results on more complecated datasets (\\emph{i.e.}, with higher orders of magnitude of nodes)?", "limitations": "- As mentioned in the paper, the main limitation is its scalability to graphs of larger size.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The author combines Partial Matching and OT methods, using permutation and padding operator to consistently predict and compare graphs of arbitrary sizes.\n- The author uses a variety of datasets to illustrate that Any2Graph has consistent and strong performance on different modal inputs, including noisy images, real world satellite images and texts (molecular fingerprints).", "weaknesses": "- There are some inconsistent notations in the paper. For example, the loss function for node features is denoted as $l_F$ in Eq. (1), while the author uses $l_f$ in the next sentence.\n- The author emphasizes the importance of the maximum node size $M$ that strongly influences efficiency and expressiveness of the model. However, the analysis in Section 5.3 shows $M=16$ is sufficient to tackle the problem, indicating that the datasets may be relatively simple and cannot fully reflect the prediction ability on more complex graphs with higher orders of magnitude of nodes.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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:\n\n> 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.\n\nYou 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. \n\n> 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.\n\nThis 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.\n\n> 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)?\n\nOur 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]).\n\n[1] Fournier, Q., Caron, G. M., & Aloise, D. (2023). A practical survey on faster and lighter transformers. ACM Computing Surveys, 55(14s), 1-40.\n\n[2] D. B. Blumenthal et al. “Comparing heuristics for graph edit distance computation”. The VLDB journal\n\n[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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "aMovOf7awL", "reviewer": "Reviewer_9w7t", "summary": "This paper presents Any2Graph, a generic framework for end-to-end supervised graph prediction (SGP) with an optimal transport loss. The framework handles various input modalities and output graphs of arbitrary size and node ordering. The novel Partially-Masked Fused Gromov-Wasserstein loss is differentiable and permutation invariant, making it suitable for SGP. Numerical experiments showcase the versatility and superior performance of Any2Graph on a synthetic dataset and several real-world tasks such as map construction and molecule prediction. The paper addresses a practical challenge in deep learning models and offers a promising solution.", "questions": "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)?\n2. Have you considered performing ablation studies or comparisons against popular baselines? \n3. Can you discuss potential limitations or failure cases of your method? How might these impact real-world applications? Are there scenarios where traditional methods may outperform Any2Graph?", "limitations": "As Discussed In Sec. Weakness & Sec. Limitations", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Innovative Methodology: The paper introduces a novel approach to supervised graph prediction (SGP) that is end-to-end, versatile, and achieves state-of-the-art results. The proposed framework, Any2Graph, leverages a new asymmetric Partially-Masked Fused Gromov-Wasserstein loss that is differentiable and node permutation invariant.\nPractical Impact: The method is demonstrated on a wide range of real-world tasks including map construction from satellite images and molecule prediction from fingerprints. The results showcase the effectiveness of the proposed approach, offering a promising solution to practical challenges in deep learning models.", "weaknesses": "1. This paper addresses the SGP problem, characterized by size agnostic, node order insensitivity, and a vast search space. As the number of nodes increases, the computational load may significantly increase. However, the discussion of this issue in the paper is relatively limited.\n2. Evaluation and Ablation Studies: The evaluation results are impressive but lack sufficient ablation studies. Additional analysis on the impact of different components (e.g., loss function) would enhance our understanding of the proposed method’s strengths and weaknesses.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our paper. We adress your many interesting questions below:\n\n> 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)?\n\nWe 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]).\n\n\n> 2. Have you considered performing ablation studies or comparisons against popular baselines?\n\nThis 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. \n\n> 3. Can you discuss potential limitations or failure cases of your method? How might these impact real-world applications? \n\nThis 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. \n\n> 4. Are there scenarios where traditional methods may outperform Any2Graph? \n\nSplit 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.\n\n[1] Fournier, Q., Caron, G. M., & Aloise, D. (2023). A practical survey on faster and lighter transformers. ACM Computing Surveys, 55(14s), 1-40.\n\n[2] D. B. Blumenthal et al. “Comparing heuristics for graph edit distance computation”. The VLDB journal\n\n[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.\n\n[4] Brogat-Motte & all. (2022). Vector-valued least-squares regression under output regularity assumptions. Journal of Machine Learning Research", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "r3PZapMQJ4", "reviewer": "Reviewer_bW5k", "summary": "The authors propose a flexible framework for end-to-end Supervised Graph Prediction (SGP), called Any2Graph, capable of handling various types of input data. This framework leverages a novel, fully differentiable, and node permutation-invariant optimal transport-based loss called the Partially Masked Fused Gromov-Wasserstein (PMFGW) loss. Unlike the Fused Gromov-Wasserstein loss (FGW), which cannot compare graphs of different sizes, the PMFGW is size-agnostic. To satisfy this property, the discrete output space is relaxed to a continuous space. A discrete graph is mapped to a continuous graph using a padding operator. The PMFGW measures the discrepancy between the predicted continuous graph and the target padded graph. Essentially, PMFGW extends FGW by adding an additional term that ensures the padding of a node is well predicted, and the partial mapping of the second and third terms. The authors introduce three propositions demonstrating that PMFGW translates all properties of FGW to the new size-agnostic graph representation. The architecture of the end-to-end SGP framework is a modification of the Relationformer, ensuring versatility in terms of input data (not only images) and modifying the operation for computing the adjacency matrix. The authors showed that Any2Graph achieved state-of-the-art prediction performance at a very low computational inference cost on four real-world datasets characterized by different types of input data.", "questions": "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.", "limitations": "The authors have adequately addressed the limitations of the Any2Graph framework. Their work does not appear to have any potential negative societal impact.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper is well-written, and both the description of the PMFGW loss and the architecture of the Any2Graph framework are clearly presented\n\nThe flexibility regarding the input data type and the size-agnostic graph representation properties provided by Any2Graph have the potential to significantly impact  the supervised graph prediction task, which play an important role in several applications from graphics to neuroscience.\n\nThe sound theoretical analysis proves that the novel PMFGW loss translates all the properties of FGW to the new size-agnostic representation based on the idea of mapping each graph to the corresponding continuous padded graph.\n\nThe numerical experiments are well-conducted with respect to:\n- The comparison of state-of-the-art (SOTA) methods in terms of both accuracy and computational efficiency.\n- The study of the robustness of Any2Graph concerning maximum graph size and the weight of the three terms of the PMFGW loss.", "weaknesses": "I think to improve the readability of of the paper I suggest to include a extend the description of the graph matching (section 2, paragraph 'Comparing graphs of the same size' by including a formal definition of the graph matching problem.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review and positive feedback.\n\n> 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') \n\nWe will follow your suggestion to provide a more detailled introduction to the graph matching problem in the final version of the paper.\n\n> **(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.\n\nThank 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. \n\nTo 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 \n\n\\begin{align}\n  \\texttt{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 )\n\\end{align}\n\nWhere $\\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].\n\nThis UOT variant of PMFGW looks sound, but when we tried it we ran into the following issues:\n\n1. 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. \n2. 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).\n\n Denoting \n\n$$\\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 )   $$\n\nwe 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:\n\n$$\\alpha\\_f \\ell\\_F(\\hat{\\mathbf{f}}\\_{i},\\mathbf{f}\\_{j}) \\geq 2\\rho \\quad \\implies \\quad T^*\\_{i,j} = 0$$\n\nThis 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\n\n$$\\mathcal{L}(\\hat{y},y) = \\rho \\varphi(\\mathbf{0},\\hat{h}) + \\rho \\varphi(\\mathbf{0},h) = \\rho \\varphi(\\mathbf{0},\\hat{h}) + \\text{cst}$$\n\nAnd the SGD will push the neural network toward a trivial prediction $\\hat{h} = 0$.\n\nBecause of the wide variability you mention we were never able to overcome such instabilities despite searching over a grid of parameters. \n\n[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.\n\n[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.\n\n[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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "089aq0V2LU", "reviewer": "Reviewer_ct8H", "summary": "This paper presents a generic framework for end-to-end supervised graph prediction. The proposed framework can take different types of data as input and learn to output graphs. The core of the framework is a novel loss function (PMFGW) that enables generalizability in different scenarios. In the end, the paper demonstrates the capability and superior performance of Any2Graph over existing solutions on synthetic datasets as well as real-world datasets.", "questions": "Please check the weaknesses section.", "limitations": "The paper's contributions are unlikely to have any negative societal impacts.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "S1: The paper tackles an interesting and important problem: supervised graph predictions, which can potentially benefit many applications.\n\nS2: The paper is very well-written and easy to follow. It effectively motivates the key challenge of the problem and clearly articulates the proposed idea step by step.\n\nS3: The paper's primary contribution, PMFGW, is well-formulated. It also shows good performance across various metrics compared to prior solutions.\n\nS4: The experiments in this paper are comprehensive and solid. They not only showcase PMFGW's high performance but also provide insights into its properties.", "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.\n\nW2: It would be interesting to understand the failure cases produced by Any2Graph.\n\nW3: 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?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing our paper! All your questions are very interesting and answering them helped us to significantly improve the paper.\n\n**Weaknesses:**\n\n> 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.\n\nWe 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).\n\n> W2: It would be interesting to understand the failure cases produced by Any2Graph.\n\nThis 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.\n \n> 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?\n\nOnce 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).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
First we would like to thank the reviewers for their mostly positive reviews with constructive questions.

The majority of the comments are positive with many reveiwers finding the paper well written (**CHfS**,**bW5k**,**ct8H**), well positioned in the literature (**CHfS**) and with a nice potential impact in SGP and applications (**ct8H**,**bW5k**). Reviewers also noted that the numerical experiments are solid (**ct8H**, **bW5k**) and demonstrate very good empirical performance for a wide range of modalities (**CHfS**,**YNCo**,**9w7t**,**YNCo**), all this with very low computational inference cost (**bW5k**). The novel proposed loss PMFGW remain simple (**CHfS**) but also relies a sound theoretical analysis (**bW5k**).

On a slightly more reserved note, **CHfS** was wondering about the limited novelty of the PMFGW loss but we believe that those small changes are the ones that made the large gain in performance possible which provides an important contribution to the community. Reviewers also asked questions about the scalability of the method (**YNCo**, **9w7t**, **ct8H**). We acknowledged that the computationnal complexity analysis was not detailed enough and thus provided new experiments to fill this gap. Any2Graph is suited to the supervised prediction of graphs with few tens of nodes (we provide a novel exemple with 50 nodes) and reviewers agree that this is enough for many practical applications (**ct8H**, **bW5k**). Yet we understand that scaling to larger graph is a natural question. For that reason, we enriched the conclusion of the paper by drawing additional ideas for scaling Any2Graph in a future work.

Meta-review: This paper presents Any2Graph, a versatile end-to-end deep learning framework designed for Supervised Graph Prediction (SGP). The core innovation of this framework is the introduction of a novel loss function, Partially-Masked Fused Gromov-Wasserstein (PMFGW), which extends the Fused Gromov-Wasserstein loss to accommodate graph prediction with arbitrary sizes and node orderings.  Along with a standard pipeline carefully modified from Relationformer, the framework demonstrates consistent and state-of-the-art performance across a diverse range of datasets, including real-world tasks like map construction from satellite images and molecule prediction from fingerprints. 

The reviewers praise the paper regarding its novelty, theorectical soundness, strong empirical performance, and clearity. The PMFGW loss is highlighted as a significant contribution, providing a differentiable, permutation-invariant, and size-agnostic approach to graph prediction, which is a meaningful extension of existing methods. Some minor issues were raised regarding the presentation, experimental evaluations, and complexity analyses. However, all reviewers were satisfied with the authors' explanations and provided positive support for the paper. The paper is recommended for acceptance.
Decision: Accept (spotlight)