The quest for the GRAph Level autoEncoder (GRALE)
Authors: Paul Krzakala
Gabriel Melo
Charlotte Laclau
Florence d'Alché-Buc
Rémi Flamary
Venue: NeurIPS 2025 poster ()
Keywords: Graph
Graphs
AutoEncoder
Encoder-Decoder
Deep Learning
Optimal Transport
Attention
Representation Learning
Graph Matching
Combinatorial
Primary area: deep_learning
TL;DR: We introduce a graph AutoEncoder that can encode (and decode) graphs of different sizes into the same embedding space. The model is trained using a new module that learns to solve a combinatorial problem (graph matching).

Abstract: Although graph-based learning has attracted a lot of attention, graph representation learning is still a challenging task whose resolution may impact key application fields such as chemistry or biology. To this end, we introduce GRALE, a novel graph autoencoder that encodes and decodes graphs of varying sizes into a shared embedding space. GRALE is trained using an Optimal Transport-inspired loss that compares the source and reconstructed graphs and leverages a differentiable matching module, which is trained jointly with the encoder and decoder. The proposed attention-based architecture relies on Evoformer, the core component of AlphaFold, which we extend to support both graph encoding and decoding. We show, in numerical experiments on simulated and molecular data, that GRALE enables a highly general form of pre-training, applicable to a wide range of downstream tasks, from classification and regression to more complex tasks such as graph interpolation, editing, matching, and prediction.

The quest for the GRAph Level autoEncoder (GRALE)
Paul Krzakala
LTCI & CMAP, Télécom Paris, IP Paris
Gabriel Melo
Charlotte Laclau
LTCI, Télécom Paris, IP Paris
LTCI, Télécom Paris, IP Paris
Florence d' Alche-BBuc LTCI, Télécom Paris, IP Paris
Rémi Flamary
CMAP, Ecole Polytechnique, IP Paris
Abstract
Although graph- learning has attracted of attention, graph representation learning is still challenging task whose resolution may impact key application fields such as chemistry or biology. To this end, we introduce GRALE, a novel graph autoencoder that encodes and decodes graphs of varying sizes into a shared embedding space. GRALE trained using an Optimal Transport-inspired loss that compares the original and reconstructed graphs and leverages a differentiable node matching module, which is trained jointly with the encoder and decoder. The proposed irentiin-baset architecture relies Evoformer, the component of AlphaFold, which we extend to support both graph encoding and decoding. We show, in numerical experiments enables a highly general form of pre- te-itraining, applicable to a wide range of down- stream tasks, from classification and regression to more complex tasks such graph interpolation, editing, matching, and prediction.
simulated and molecular data, that GRALE
Introduction
Graph representation learning. Graph-structured data are omnipresent in a wide variety of fields ranging from social sciences chemistry, which has always motivated an intense interest in graph learning. Machine learning tasks related to graphs are mostly divided into two categories: node-level tasks such node classificatin/reggrsssoon clustering, as graph classffication/regression or graph generation/prediition [7, 38, 69, 28, 84]. This paper is de- voted graph-level representation learning, that is, unsupervised learning of graph-level Euclidean representation that can be used directly or fine-tuned for later tasks [25]. From the large spectrum of existing representation learning methods, focus the AutoEncoder approach, as it natively fea- tures the possibility to decode graph back from the embedding space. In this work, we illustrate that this enables leveraging the learned representation variety of downstream tasks, ranging from classi- fication/regressionn to more involved tasks such as graph interpolation, editing, matching or prediction.
edge prediction, and graph-level tasks such
From node-level AutoEncodrrs... Scrutinizing the literature, we observe that most existing works on graph AutoEncoders provide node-level embeddings instead of one unique graph-level embedding (See Fig. 1, left). In the following, we refer to this class of models as Node-Level AutoEncoders. The most emblematic example is the celebrated VGAE model [36], where the encoder is graph
Code available at http:///gggtuub..ooo//taaaaaaaae
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Graph Matching NP (eunet) or (spprox))
Graph Reconstruction
Edge Reconstruction Loss 0,8")
Graph Reconstruction
O(N"
ON
g
g
f
Node-lavel
X
Graph Matching
Graph-level
Graph Matching
Graph-lovel tasks
No Graph Matching
NODE-LEVEL
GRAPH-LEVEL (NAIVE)
GRALE
Figure The different classes of graph AutoEneoders. (Left) Node-level AutoEncoders such as [36] provide node level embeddings. (Center) Naive graph-level AutoEncoders such [53] directly provide graph-level embeddings but rely on graph matching solver to compute the training loss. (Right) Matching free approaches, such as proposed in this work and in [68] use learnable module to provide the matching.
convolutional network (GCN) that returns node embeddings 2;, and the decoder reconstructs the adjacency matrix from a dot product A,,j o (22, 22)). Many extensions have been proposed for this model, such as adversarial regularization [48] or masking [56], and it has been shown to be efficient for many node-level tasks, such as node clustering [81, 82, 60] or node outlier detection [14]. Node- level models can also be used for graph generation, given that one knows the size (number of nodes) of the graph to generate; this includes GVAE [36] but also GraphGAN [61] and graph normalizing flows [44]. When graph-level representation is needed, one can apply some pooling operation on the node embeddings, for instance = Σ Zz. Yet, this strategy is not entirely satisfying, as inevitably leads to information loss, and it becomes difficult to decode graph back from this representation [59, 68].
...to graph-level AutoEncoders. In contrast, very few works attempt to build graph-level AutoEn- coders where the encoder embeds the full graph into single vector and the decoder reconstructs the whole graph (including the number of nodes). The Graph Deconvolutional AutoEncoder [41] and Graph U-net [21] are close to this goal, but in both cases, the decoder takes advantage of the ground-trun truth information, including the graph size, in the decoding phase. Ultimately, we identify only two works that share similar goal with this paper: GraphVAF. [53] (not to be confused with GVAE [36]) and PIGVAE [68]. Graph VAE is a pioneering work, but it is heavily based on an expensive graph matching algorithm. In that regard, the main contribution of PIGVAE is the addition of learnable module that predicts the matching instead. This was major step forward, yet we argue that PIGVAE is still missing some key components: for instance, the ground truth size of the graph needs to be provided to the decoder. We detail our positioning with respect to PIGVAE in Section 4.
Contributions. We introduce a GRAph Level autoEncoder (GRALE) that encodes and decodes graphs of varying sizes into a shared Euclidean space. GRALE is trained with an Optimal Transport- inspired loss, without relying on expensive solvers, as the matching is provided by learnable module trained end-to-end with the rest of the model. The proposed architecture leverages the Evoformer module [30] for encoding and introduces novel "Evoformer Decoder" for graph reconstruction. GRALE enables general pretraining, applicable to wide range of downstream tasks, including classification, regression, graph interpolation, editing, matching, and prediction. We demonstrate these capabilities through experiments on both synthetic benchmarks and large-scale molecular datasets.
2 Building Graph-Level AutoEncoder
2.1 Problem Statement
The goal of this paper is to learn graph-level AutoEncoder. Given unsupervised graph dataset D = {x: [ we aim at learning an encoder G + Z and decoder / - G where is an euclidean space and is the space of graphs. To this end, the classic AutoEncoder approach is to minimize a reconstruction loss [(f a g(v,), x.)) However, the Graph setting poses unique challenges compared to more classical AutoEncoders (e.g., images):
1. The encoder g must be permutation invariant.

---

2. The decoder f must be able to map vectors of fixed dimension to graphs of various sizes, 3. The loss C must be permutation invariant, differentiable and efficient compute.
Permutation invariant encoder. The first challenge is a well-studied topic for which a variety of architectures have been proposed, most of which rely on message passing [83, 84, 73] or attention- based [47, 50] mechanisms. In this work, we have chosen to use an attention-based architecture, the Evoformer module from AlphaFold [30]. As the numerical experiments show it, this architecture is particularly powerful, enabling the encoding and updating of pairwise relationships between graph nodes. To maintain symmetry with the encoder, the decoder also uses a novel Evoformer Decoder module. Details are provided in Appendix C.
Padded graphs for multiple output sizes. The second challenge can be mitigated by using classical padded representation [37, 52]. We represent a graph G E 9 as a triplet G (h, F, C) where h E [0, 1 is masking vector, F E R RN'x is node feature matrix, and C R NxNNn is an edge feature tensor. N is maximum graph size; all graphs are padded to this size. A node i exists if h4 and is a padding node if h; 0. Thus, original and reconstructed graphs of various sizes are represented with fixed-dimensional tensors that can be efficiently parametrized.
Permutation invariant loss. The third challenge is arguably the hardest to overcome, since any permutation innvariant loss Lr between graphs G and G can be written matching problem
(pr(G, G) min LALIGN(G, P(G)), PEEN
where N is the set of permutation matrices and P denote the application of permutation P to graph G i.e. P[G]= (Ph, PF, PCPT). This be seen as first, aligning the two graphs, and then computing a loss LALIGN between them. This is problematic because, for any nontrivial loss LALIGN such that LALION(2;; (z. y) 0 < x y. the optimization problem in (1) is NP complete [20]. We discuss how to avoid this pitfall in the next section.
2.2 Matching-free reconstruction loss
A common approach to mitigate the computational complexity of a loss like (1) is to relax the discrete optimization problem into more tractable one. For instance, Any2Graph [37] relaxes the graph matching problem into an Optimal Transport problem LAzG(G, G)- = milreey (G, G, T) opti- mized over TT (T E [0, 1]
NNN [IN- IN, T'1 Ix) ) the set of bi-stochastic matrices and
N
N
N
Cor(G, ((GG,,GT)= = Σ
En hn, Tu.
Σ 1
Σ h,hylo(Ci,ke Cr.)TT,TT.. (2) G..kd
6,5
where G= (h, (h, F, F,,, (h, F. C), and l, ep lo are ground losses responsible for the correct prediction of node masking, node features and edge features respectively. Despite the relaxation, this loss still satisfies key properties stated in Propositions 1 and 2 (proofs in Appendix F).
G
Proposition 1. If la is a Bregman divergence, then Cor(G, C,T) can be computed in O(N)). Proposition There exist T E uN such that (o G, T) = 0 if and only if there exist P E ON such that G = P[G] (i.e. G and G are isomorphic).
Unfortunately, the inner optimization problem w.r.t. T is still NP-complete, as it is quadratic but not convex. The authors suggest an approximate solution using conditional gradient descent, with a complexity of (k(NN) "), where k(N) is the number of iterations until convergence. However, there is no guarantee that the optimizer reaches global optimum.
Another approach, first proposed in PIGVAE [68], is to completely bypass the inner optimization problem by making the matching T prediction of the model, that is, the model does not only re- construct graph Ö f g(G), but it also provides the matching 7 between output and input graphs.
We propose to combine the loss (2) from Any2Graph with the matching prediction strategy from PIGVAE, Thus, the loss that minimize to train GRALE is
LORALE(G) Lor ((C)
Note that T(G) must be differentiable so that the model can learn T, and by backpropagation.
3

---

LEGEND
MATCHER
Truinable
Affinity (5)
Projection (6)
T
Trainable Modile
N.N.
(Pipeline Order)
Tranepass
Linnar
prading
AM
Evoformer Decoder
Evoformer
Encoder
a.
Nx de
Linezr
Transformer Decoder
Encoder
g: ENCODER
f: DECODER
NxNxna
Featurizer
(0)
(,,
Featurizer
G¹ = -MMPP"
O(G", G.
OIN))
N' Nong
Figure 2: GRALE illustrated for input of size and maximum output graph size N = 4.
3
GRALE architecture
3.1
Overview
The design of the GRALE architecture revolves around the parametrization of the matching matrix I' between the input graph G and the reconstructed graph G. Our approach follows classical idea: approximating the intractable Graph Matching problem (NP-hard) via linear assignment (cubic complexity) of some learnable node embeddings [? 63, 49, 42]. Concretely, extract node embeddings (Gande(G) X and f X, and compute T MATCHING(X, X), where MATCHING denotes a differentiable matching algorithm detailed below. A key feature of our design that Gnodes and fnedes are not treated independent modules; instead, we employ extensive weight sharing so that these components reuse the same hidden representations as the encoder and decoder.
We next provide the details of this implementation.
3.2
Graph pre-processing and featurizer
The first step is to build the input (resp. target) graph (resp. G*) from the datapoint x: E
p(x)= d" (z) G*
(4)
This module first extract from data? simple graph presentation with adjacency matrix and node labels then builds additional node and edge features, by including higher order interactions such the shortest path matrix. Note that we consider different schemes for the imput and target graphs (ø * Φ²) it has been shown that breaking the symmetry between inputs and targets be beneficial to AutoEncoders [74]. In particular, ó outputs slightly noisy node features while ø² is deterministic. This is crucial for breaking symmetries in the input graph, enabling the encoder produce distinct node embeddings, which in turn facilitates matching, We discuss this phenomenon in appendix B.3.
3.3 Encoder g
The input graph G (F,C) is passed through the encoder g that returns both graph level embedding Z E k and node level embeddings X Ng..
ggrahh (G) = Z, Inodes (G) =
(5)
For molecules, is typically SMILES string that can be converted into graph using RDKit [39].

---

Embedding, We represent the graph embedding set of K tokens, each of dimension D, with both and D fixed. For most downstream tasks, we simply flatten this representation into single vector of dimension d = K x D.. This token-based approach follows broader trend of modeling data as sets of abstract units (tokens) beyond NI.P [29, 55, 26]. In this context, K can be interpreted as the number of concepts used to represent the graph, though qualitative analysis is beyond the scope of this paper. We discuss the choice of and quantitatively in Section 5.
Architecture. The main component of the encoder is an Evoformer module that provides hidden representation for the node feature matrix F and edge feature tensor C. Then, we use transformer decoder as pooling function to produce the graph level representation Z and apply simple linear layer on F to get the node level representations X.
3.4 Decoder f
The decoder uses the graph-level embedding Z reconstruct graph & and its node embeddings X that will be used for matching as discussed in the next subsection.
fgraph Z) = G, fnodes (Z) X
(6)
The decoder architecture mirrors that of the encoder. First, a transformer encoder updates the graph representation Z, then a novel Evoformer decoder module reconstructs the output graph nodes and edges. This new module, detailed in Appendix C, is based on the original Evoformer module, augmented with cross-attention blocks to enable decoding. As before, X is obtained by applying a simple linear layer to the last layer hidden node representations.
3.5 Matcher m and loss
Finally, matcher module leverages the node embeddings X and X to predict the matching between input and output graphs:
T= m (X,X)
To enforce that T' nN, decompose the matcher in two steps: 1) We construct affinity matrix K and Kij Aff Xÿ) where Aff learnable affinity function We apply the Sinkhorn algorithm to project K on TN in a differentiable manner i.c. T = SINKHORN( [16, 19, 23].
GRALE loss. Omitting the preprocessing and denoting by o sb and the parameters of the encoder, decoder, and matcher respectively, the expression of the loss function writes as follows:
LG,ALE(G,O, 0) Lor (G.
Igraph (G),
11m(mmmmeee (Inxeees (G), Fmndees
I ggraph (G))
(8)
The detailed implementation of the modules mentioned in this section provided in Appendix C and the whole model is trained end-to-end with classic batch gradient descent as described in A.
4
Related Works
4.1 Permutation Invariant Graph Variationnal AutoEncoder (PIGVAE)
We devote this section to highlighting the differences with the work of Winter et al. [68] who first proposed a graph-level AutoEncoder with a matching free loss (PIGVAE).
Graph size. In PIGVAE, the decoder needs to be given the ground truth size of the output graph and the encoder is not trained to encode this critical information in the graph-level representation. In comparison, GRALE is trained to predict the size of the graph through the padding vector h. In the following, we assume that graphs are of fixed size (h- = 1) to make the methods comparable.
Loss. Denoting î(G = (TF, TCTT the reordering of a graph, PIGVAE loss rewrites as
LPIOVAE(G, G.T) EAL
(9)
5

---

where CALION = (FF, EE== Co(Crg.Cig), This reveals that LHGVAA and Lor can be seen as two different relaxations of the same underlying matching problem minpeaw CALIGN (G, P(G1). We detail this relationship in Proposition 3. However, Proposition 4 highlights an important limitation of the relaxation chosen in PIGVAE as the loss can be zero without perfect graph reconstruction. All proofs are provided in appendix F.
Proposition 3. For a permutation P E on, CPIOVAE and Lor are equivalent to matching loss,
LPIOVAE(G, P) Cor(G, LALIGN(G,
(10)
If we relax to T TN we only have an inequality instead LeiovAE G, S BaGG,,,TT) Proposition 4. It can be that CrIOVE G, G. = 0 while G and G are not isomorphic.
Architecture. PIGVAE architecture is composed of 3 main blocs: encoder, decoder and permuter. The role of the permuter is similar to that of our matcher but it only relies me-dimensional sorting of the input node embeddings X while we leverage the Sinkhorn algorithm to compute a d dimensional matching between X and X which makes our implementation more expressive. Besides, training the permuter requires schedule a temperature parameter. The scheduling scheme is not detailed in the PIGVAE paper which makes it hard to reproduce the reported performances.
4.2 Attention-based architectures for graphs
The success of attention in NLP [58] has motivated many researchers to apply attention-basee models to other types of data [32, 67J. For graphs, attention mainly exists in two flavors: node-level and edge- level. In the case of node-level attention, each node can pay attention to the other nodes of the graph, resulting in an N x N attention matrix that then biased or masked using structural information [79, 77, 50]. Similarly, edge-level attention results in a N x N2 attention matrix. To prevent these prohibitive costs, all edge-level attention models use a form of factorization, which typically results in ((N*) complexity instead [9, 68, 30J. Since the complexity of our loss and that of our matcher is also cubic', it seemed like a reasonable choice to use edge-level attention in our encoder and decoder. To this end, we select the Evoformer module [30], as it elegantly combines node and edge-level attention using intertwined updates of node and edge features. Our main contribution is the design of novel Evoformer Decoder that enables Evoformer to cross- aoose-atttntoon for graph reconstruction.
4.3 Graph Matching with Neural Networks
Our model relies on the prediction of the matching between input and output graphs. In that sense, we are part of larger effort towards approximating graph matching with deep learning models in data-driven fashion. However, is important to note that most existing works treat graph matching as regression problem, where the inputs are pairs of graphs (G1, G2) and the targets are either the ground truth matching [80, 63, 66, 78, 64] or the ground truth matching cost (edit distance) 165, 31, 3, 42, 46). or both [49]. In contrast, we train our matcher without any ground truth by simply minimizing the matching cost, which is an upper bound of the edit distance. Furthermore, our matcher not separate model; it is incorporated and trained end-to-end with the rest of the AutoEncoder.
Numerical experiments
Training datasets. We train GRALE on three datasets. First, COLORING is synthetic graph dataset introduced in [37] where each instance connected graph whose node labels are colors that satisfy the four color theorem. Specifically, we train on the COLORING 20 variant, which is composed of 300k graphs of size less than or equal to 20. Then, for molecular representation learning. we download and preprocess molecules from the PUBCHEM database [33]. We denote PUBCHEM 32 and PUBCHEM 16 as the subsets containing 84M and 14M molecules, respectively, with size up to 32 and 16 atoms. PUBCHEM 16 is used for training a lightweight version of GRALE in the ablation studies, while downstream molecular tasks use the model trained on PUBCHEM 32. We refer to appendix A. for more details on the datasets, and A.2 for the training parameters.

---

Table 1: Reconstruction performances of graph-level AutoEncoders. indicates that the decoder relies on the ground truth size of the graph. N.A. indicates that the model is too expensive to train.
COLORING
PUBCHEMM
PUBCHEM
MonnI
EDVT. Dist. (4)
AcC. (1)
EDIT. DisT. (L)
GI AcC. (11
Eon. DiSI. (b)
GI Acc. (1)
GRAPHVAE PIGVAE
2.13
35.90
3.72
07.8
N.A.
N.A.
0.09
85.30
1.69
41.0
2.53
24.91
GRALE
0.02
99.20
0.11
93.0
0.78
68.80
Table 2: Ablation Studies (PUBCHEM 16). We report (avg + std) reconstruction metrics runs.
MODEL COMPONENT
PROPOSED
REMPLACED BY
EDIT DIST.
G1 Acc.
LOss
Cor
LPIOVAE REGULARIZATION [68]
0.13 + 0.16
91.8 5.01
FEATURIZER ENCODER f DECODER MATCHER mn
SECOND ORDER
FIRST ORDER
0.24 1 0.17
90.3 6.46
EVOFORMER
GNN
1.32 + 0.16
53.2 2.69
EVOFORMER
TRANSFORMER DECODER [37J
0.71 + 0.09
66.6 2.78
SINKHORN
SOFTSORT [68]
1.47 1 0.36
49.7 9.15
DISAMBIGUATION NOISE
WITH
WITHOUT
1.16 1 0.03
GRALE (NO REMPLACEMENT)
0.11 0.04
93.0 + 0.18
5.1
Reconstruction performances and ablation studies
In this section, we evaluate the performance AutoEncoders based on the graph reconstruction quality using the graph edit distance (Edit Dist) [62] and Graph Isomorphism Accuracy (GI Acc), i.e. the percentage of graphs perfectly reconstructed (see Appendix A.3 for details on the metrics). All models trained PUBCHEM 16, with holdout of 10,000 graphs for evaluation.
Model performance and impact of components. First, we compare GRALE to the other graph- level Autoeneoders (PIGVAE [68], GraphVAF: [53]). Table shows that GRALE outperforms the other models by large margin. Next, we conduct ablation studies to assess the impact of the individual components of our model. For each component, we replace it with a baseline (detailed in E) and measure the effect performance. Results shown in Table 2. Overall, all new components contribute to performance improvements. We also report the variance the reconstruction metrics over training seeds, revealing that while the choice of loss function and featurizer has limited impact on average performance, it significantly improves training robustness.
Size of the embedding space. We now focus on the choice of embedding space and report reconstruction accuracy over a grid values for K and D (Figure 3). As expected, accuracy increases with the total embedding dimension d K D. For given fixed d, the perfor- mance is generally better when K > 1, with optimal results typically around K D. In- terestingly, this choice is also computationally favorable as the cost of transformer encoder scales with O max K, D)). These findings align with the broader hypothesis that many types of data benefit from being represented as tokens [29, 55, 26), direction already explored in recent theoretical works [17].
Accuracy
0:37
0.33
0.48
0.70
0.63
0.88
0.84
0.85
A
5.92
0.8
0.7
128
3.52
5.65
0.79
0.84
0.43
0.6
Dimenatonnt
206
0.5
1024
2.68
3.76
128
Figure 3: G.I. accuracy vs (K, D). Both axes are in log-scale so that the diagonals correspond to given total dimension d = K D.
5.2 Qualitative properties of GRALE
Complex graph operations in the latent space. We now showcase that GRALE enables complex graph operations with simple vector manipulations in the embedding space. For instance, graph interpolation [6, 18, 27], traditionnally defined as the Fréchet mean with respect to some graph distance L i.e. G2 arg mi t) L(Go, G) L(G,, G), which is challenging compute.
Sinkhorm is ((N2)) but test time the Hungarian algorithm, its discrete, ((N2) counterpart.
7

---

(Ig(C1)) (1 1)9(G())
G Bly(G))
Average
Figure 4: Interpolating graphs (from COLORING) using GRALE's latent space. On the left interpolate between two graphs while on the right we compute the barycenter of the whole dataset.
Embeddiigg Space
PRle))
2
VV((s))
X
Encode
Decode
Decode
Decode
Decode
6
=
9
10
Figure 5: Latent space edition of the size of a graph. Here, is a mee-hddee-llaer MLP trained to predict graph size, and set 0.01. Steps that did not produce any visible change omitted.
Instead, we propose to compute interpolations at lightspeed using GRALE's embedding space via =,= f((1 t) gG)) + gG))) This approach can also be used compute the barycenter of more than 2 graphs, including an entire dataset as illustrated in Figure 4.
graph editing. Given a property of interest p(G) E R, Z - R such that p(G) R (()( and compute a perturbation such that p(g(G) u) 2 (G)( For instance, one can set vV)(gG))) The edited graph is then decoded as G' - f() + u). In Figure 5, we illustrate this on COLORING by setting p(G) n(G), the size of the graph, and successfully increasing
We can also perform property-guide
train predictor
Denoising Properties. We explore GRALE's denoising capabilities by corrupting the COLORING test through random modifications of node colors, potentially creating invalid graphs where adja- cent nodes share the same color. We then plot, as function of noise level, the probability that a noisy graph is valid versus that its reconstruction is valid. As shown in Figure 6, reconstruction significantly increases the proportion of valid graphs, highlighting that GRALE's latent space effectively captures the underlying data structure.
Coloring Denoising
Noisy Input
Reconstruction
Noisy inputs Reconstruution
Validiy M%
60
40
Encode
Decode
20
Errors!
Valid
Noise Level (%6
Figure 6: Left: Percentage of valid coloring vs noise level. Right: example of corrupted input and
its reconstruction. The decoder consistently maps noisy input back toward valid COLORING graphs.
5.3 Quantitative performances of GRALE models downstream tasks
We use the graph representations obtained by GRALE as input for classification and regression tasks in the MoleculeNet benehmark [70]. We compare our method to several graph representation learning baselines, including graph AutoEncoders (PIGVAE [68], VGAE [36], GraphMAE [? 1) and contrastive learning methods (Infograph [54], Simgrace [71]). For fair comparison, all models are pre-trained on PUBCHEM 32, and the same predictive head is used for the downstream tasks. Detailed settings are provided Appendix Overall, GRALE outperforms the other graph AutoEncoders and performs similarly, if not better, than the other basclines.
Graph

---

Table 3: Downstream tasks performance of different graph representation learning methods pretrained on PUBCHEM 32. We report the mean + std over 5 train/test splits.
MLP REGRESSION (MAE L) (M40
SVR RECRESSION (MAB
SVC CLASSIE, ROCC-UCC f> ВВВР
MODEL
ESOL
LIPU
PREESOLV
BACE
SIMGRACE
0.110 :: 0.003
0.025 + 0.005
0.293 = 0.020
0.534 +: 0.023
0.374 - 0.008
0.745 4: 0.072
0.866 = 0.050
INFOGRAPH
0.001
0.001
0.255
0.297
0.729
GRAPHMAE
0.222
0.016
0.247
+ 0.036
0.291
= 0.012
0.527
0.029
0.378 - 0.028
0.773
0.036
0.857
039
GVAF
0.765 4 0.005
0.328
+ 0.005
0.306 = 0.027
0.668
0.014
0.344 0.002
0.705 + 0.060
0.771
= 00.049
PIGVAR
0.031
0.001
0.019
+ 0.001
0.279
0.020
0.023
0.019
0.283 = 0.013
0.673 + 0.079
0.816
0.049
GRALE
0.015 + 0.001
0.018 0.083 0.274
0.014
0.011 + 0.022
0.272
0.017 0.731 + 0.026 0.821 0.051
Table 4: Performances of different methods on graph prediction benchmarks from [37].
MODEL
COLORING
EDIT DIST. (L) COLDRING
QM9
GDB11
COLORING
GI Acc. (f) COLORING
GDRI
PGWBARY
6.73
N.A.
2.84
N.A.
01.00
N.A.
28. 19.95
N.A.
RELATIONFORMER
ANYIGRAPH
0.19
1.22
2.01
3.63
84.44
43:77
29.85
16.25
3.82
86
30.77
GRALE FINETUNING
0.22
0.45
2.13
2.28
90.04
$3.87
35:27
33.22
Table 5: We report (avg+sstd) edit distance and compute time over 1000 pairs of test graphs. All solvers use the default Pygmtools parameters except Greedy A which is A with beam width one.
EDIT
COMPUIE COLDRING
MODEL
COLORING
PUBCHEM
PUBCHEM
21.10
0.006 d:
0.073
RRWM
20.66
+ 10.90
42.24
+ 12.71
0.540 + 6.190
1.271
0.244
SM
20.90
10.91
43:20
12.86
0.002
0.901
0.078
0.022
GREEDY A
20.41
11:21
32.53
06.15
0.021 1 0.016
0,110
0.054
19.66
3.487 + 1.925
GRALE GRALE FINETUNING
07.64
08.92
1: 04.42
19.33 :: 07.85
32.77
11.67
0.003 + 0.001
0.008 0.002
Graph prediction. We now consider the challenging task of graph prediction, where the goal is to map an input æ E X' to target graph G*. Following the surrogate regression strategy of [75, 8, 6], we train surrogate predictor y X 2 minimize - ((")) I| At inference time, the predicted
embedding is decoded into a graph using the pretrained decoder = f y (ar). We also consider finetuning phase, where yp and f are jointly trained with the end-to-end loss L(f (xxx) G*). We evaluate this approach on the Fingerprin22raphh and Image2Graph tasks introduced in [37], using the same model for yp Results are reported in Table 4. Thanks to pre-training (on COLORING for Imagh2Graph and PUBCHEM for Fingerprin(GGraph), GRALE significantly outperforms prior methods most tasks.
Graph Matching, Finally, we propose to use GRALE to match arbitrary graphs G1 and G2. To this end, we compute the node embeddings of both G and G2 and plug them into the matcher
T(G1, G2) m Gnodes (G1), Gnodes
Guodes (G2)
(11)
where we enforce that T G2) E O by replacing the Sinkhorn algorithm with the Hungarian algorithm [15] inside the matcher. Then, we use this (potentially suboptimal) matching to compute an upper bound the edit distance. In Table 5, we compare this approach to more classical methods as implemented in Pygmtools [62]. Pygmtools is fully GPU compatible, which enables a fair comparison with the proposed approach in terms time complexity. The matcher operates out of distribution since it is trained to match input/output graphs that are expected to be similar G1 G2 convergence and here we sample random pairs graphs. To mitigate this, we fine-tune the matcher on random pairs of graphs from the training set. As shown in Table 5, the proposed approach yields better upper bounds of the edit distance than classical solvers while being orders of magnitude faster.
6 Conclusion, limitations and future works
We introduced ALE,, a novel graph AutoEncoder, and showed that its embeddings capture intrinsic properties of the input graphs, achieving SOTA performance and beyond, across numerous

---

tasks. Trained on large-scale molecule data, GRALE provides a strong foundation for solving graph-level problems through vectorial embeddings. Arguably, GRALE's main limitation is its computational complexity (mostly cubic), which led us to restrict graphs to N = 32. This could be mitigated in future work using approximate attention in the wyoformer-based modules [2. 11, 13] and accelerated Sinkhorn differentiation in the matcher [5, 16]. Beyond this, GRALE opens up several unexplored directions. For instance, GRALE could serve as the basis for a new graph variational autoencoder for generative tasks. Finally, given its strong performance in graph prediction, applying GRALE to the flagship task molecular elucidation [34, 43] appears to be a promising next step.
Acknowledgments and Disclosure of Funding
This project was provided with computing AI and storage resources by GENCI at IDRIS thanks to the grant 2025-AD01 1016098 on the supercomputer Jean Zay's H100 partition. It received funding from the European Union's '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 can be held responsible for them. This research was also supported in part by the French National Research Agency (ANR) through the PEPR IA FOUNDRY project (ANR-23 2030 program
the MATTER project (ANR-233 133EERCC-0006- It also received funding from the Hi! PARIS and Fondation de I'École polytechnique. Finally, the authors would like to thank the Isaac Newton Institute for Mathematical Sciences, Cambridge, for support and hospitality during the programme "Representing. calibrating & leveraging prediction uncertainty from statistics to machine learning" where work on this paper was undertaken. This work was supported by EPSRC grant no EP/Z000580/1.
and ANR/France
References
[1] Aflalo, Y., Bronstein, A., and Kimmel, R. (2015). On convex relaxation of graph isomorphism. Proceedings of the National Academy of Sciences, 12(10))2942-29)) 29472947.
[2] Ahdritz, G., Bouatta, N.. Floristean, C., Kadyan. S., Xia, Q., Gerecke. W., O'Donnell, T. J., Berenberg, D., Fisk, I., Zamichelli, N., et al. (2024). Openfold: Retraining alphafold2 yields new insights into its learning mechanisms and capacity for generalization. Nature Methods, 21 21(8):1514-1524
[3] Bai, Y., Ding, H., Bian, S., Chen, T., Sun, Y., and Wang. W. (2019). Simgnn: A neural network approach to fast graph similarity computation. In Proceedings of the twelfth ACM international conference on web search and data mining, pages 384-392.
[4] 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, 131(25):8732-733.
[5] Bolte, J. Pauwels, E.,, and Vaiter, S. (2023). One-step differentiation of iterative algorithms. Advances in Neural Information Processing Systems, 36.77089-77103
[6] Mrotet-Motte, L.,, Flamary, R., Brouard, C., Rousu, J., and d' Alché-Buc, (2022). Learning to predict graphs with fused Noomov-wasserstede barycenters. In International Conference on Machine Learning, pages 2321 22355. PMLR.
[7] Bronstein, M. M., Bruna, J., LeCun, Y., Szlam, A., and Vandergheynst, P. (2017). Geometric deep learning: going beyond euclidean data. IEEE Signal Processing Magazine, 34(4):18-42,
[8] Brouard, C., Shen, H., Dührkop, K., d' Alché-Bue, F., Böcker, S., and Rousu, J. (2016). Fast metabolite identification with input output kernel regression. Bioinformatics, 32(12):128-i36
[9] Buterez, D., Janet, J. P., Oglic, D., and Liò, P. (2025). An end-to-end attention-based approach for learning on graphs. Nature Communications, 16(1):5244.
[10] Chen, D., Zhu, Y., Zhang, J., Du, Y., Li, Z., Liu, Q. Wu, S., and Wang. I. (2023). Uncov- ering neural scaling laws in molecular representation learning. Advances Neural Information Processing Systems, 36: 16:1455-1475.
10

---

[11] Cheng, S., Zhao, X., Lu, G., Fang, J., Yu, Z., Zheng, T., Wu, R., Zhang, X., Peng. J., and You, Y. (2022). Fastfold: Reducing alphafold training time from 11 days 67 hours. arXiv preprint arXiv:2203.08854
[12] Cuturi, M. (2013). Sinkhorn distances: Lightspeed computation of optimal transport. Advances in neural information processing systems, 26.
[13] Dao, T., Fu, D., Ermon, S., Rudra, A., and Ré, C. (2022). Flashattention: Fast and memory- efficient exact attention with io-awareness. Advances in neural information processing systems, 35:16344-16359.
[14] Du, X., Yu, J., Chu, Z., Jin, L., and Chen, J. (2022). Graph autoencoder- based unsupervised outlier detection. Information Sciences, 608:532-2 -50.
[15] Edmonds, J. and Karp, R. M. (1972). Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM (JACM), 19(2)248-264.
[16] Eisenberger, M., Toker, A.,
L., Bernard, F., and Cremers, D. (2022). A unified framework for implicit sinkhorn differentiation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 509-518.
[17] Erba, V., Troiani, E., Biggio, L., Maillard, A., and Zdeborová, L. (2024). Bilinear sequence regression: A model for learning from long sequences of high-dimensional tokens. arXiv preprint arXiv:2410.1882.
[18] Ferrer, M., Valveny, E.,, Serratosa, F., Riesen, K., and Bunke, H. (2010). Generalized me- dian graph computation by means of graph embedding in vector spaces. Pattern Recognition, 4344):1642-1655
[19] Flamary, R., Cuturi, M., Courty, N., and Rakotomamonjy, A. (2018). Wasserstein discriminant analysis. Machine Learning, 107:1923-199
[20] Fortin, S. (1996). The graph isomorphism problem.
[21] Gao, H. and Ji, S. (2019). Graph u-nets. In international conference on machine learning, pages PMLR.
[22] Gao, X., Xiao, B., Tao, D., and Li, X. (2010). A survey of graph edit distance. Pattern Analysis and applications, 13:113-129.
[23] Genevay, A., Peyré, G., and Cuturi, M. (2018). Learning generative models with sinkhorn divergences. In International Conference Artificial Intelligence and Statistics, pages 1608- 1617. PMLR.
[24] Gold, S. and Rangarajan, A. (2002). A graduated assignment algorithm for graph matching. IEEE Transactions on pattern analysis and machine intelligence, 1774):377-388.
[25) Hamilton, W. I.. (2020). Graph representation learning. Morgan & Claypool Publishers.
[26] He, X., Hooi, B., Laurent, T., Perold, A., LeCun, Y., and Bresson, X. (2023). A generalization of vit/mlp-mixxt to graphs. In International conference on machine learning, pages 12724-12745. PMLR.
[27] Hlaoui, A. and Wang, S. (2006). Median graph computation for graph clustering. Soft Computing, 10:47-53.
[28] Hu, W., Fey, M., Zitnik, M., Dong, Y., Ren, H., Liu, B., Catasta, M., and Leskovec, (2020). Open graph benchmark: Datasets for machine learning graphs. Advances in neural information processing systems. 33:22118 18-22133.
[29] Jaegle, A., Gimeno, F. Brock, A., Vinyals, O.,, Zisserman, A., and Carreira, J. (2021). Perceiver: General perception with iterative attention. International conference on machine learning, pages 4651-4666 PMLR.

---

[30] Jumper, J., Evans, R., Pritzel, A., Green, T., Figurnov, M., Ronneberger, O., Tunyasuvunakool, K., Bates, R., Zidek, A., Potapenko, A., et al. (2021). Highly accurate protein structure prediction with alphafold. nature, 596(7873):883-58)
[31] Kaspar, R. (2017). Graph matching toolkit.
[32] Khan, S., Naseer, M., Hayat, M., Zamir, S. W. Khan, F. S., and Shah, M. (2022). Transformers in vision: A survey, ACM computing surveys (CSUR), 54(10s):1-41,
[33] Kim, S., Thiessen, P. A., Bolton, E. E., Chen, J., Fu, G., Gindulyte, A., Han, L., He, J., He, S., Shoemaker, B. A., et al. (2016). Pubchem substance and compound databases. Nucleic acids research, 44(D1):D1002-12215
[34] Kind, T. and Fiehn, O. (2010). Advances in structure elucidation of small molecules using mass spectrometry. Bioanalytical reviews, 2:23 20.
[35] Kingma, D. and Ba, J. (2014). Adam: A method for stochastic optimization. arXiv preprint arXiv: 1412.6980.
[36] Kipf. T. N. and Welling, M. (2016). Variational graph auto-encoders. arXiv preprint arXiv:1611.00
[37] Krzakala, P.. Yang, J., Flamary, R., d' d'Alché-Bue F., Laclau, C., and Labeau, M. (2024). Any2graph: Deep end-to-end supervised graph prediction with an optimal transport loss. Advances in Neural Information Processing Systems, 37:101552-101588.
[38] Laforgue, P., Clémençon, S., and d' Alché-Buc, F. (2019). Autoencoding any data through kernel autoencoders. In the 22nd International Conference on Artificial Intelligence and Statistics, pages 1061-1069. PMLR.
[39] Landrum, G. (2013). Rdkit documentation. Release, 1(1-79):4.
[40] Lee, J., Lee, Y., Kim, J., Kosiorek, A., Choi, S., and Teh, Y. W. (2019). Set transformer: framework for attention-based permutation-invariant neural networks. In International conference on machine learning, pages 3744-3753, PMLR.
[41] J., Yu, T., Juan, D.-C., Gopalan, A., Cheng. H., and Tomkins, A. (2020). Graph autoencoders with deconvolutional networks, arXiv preprint 188.8:2012..1888.
[42] Ling, X., Wu, L., Wang, S., Ma, T., Xu, F., Liu, A. X., Wu, C., and Ji, (2021). Multilevel graph matching networks for deep graph similarity learning. IEEE Transactions on Neural Networks and Learning Systems, 34(2):7998813.
[43] Litsa, F. E., Chenthamarakshan, V., Das, P., and Kavraki, L. E. (2023). An end-to-end deep learning framework for translating mass spectra to de-novo molecules. Communications Chemistry, 6(1):132.
[44] Liu, J., Kumar, A., Ba, J., Kiros, J., and Swersky, K. (2019). Graph normalizing flows. Advances Neural Information Processing Systems, 32.
[45] Lu, S., Gao, Z., He, D., Zhang, L., and Ke, G. (2024). Data-driven quantum chemical property prediction leveraging 3d conformations with uni-mol- Nature Communications, 15(1):7104.
[46] Moscatelli, A., Piquenot, J., Bérar, M., Héroux, P., and Adam, S. (2024). Graph node matching for edit distance. Pattern Recognition Letters, 184:14-200 20.
[47] Müller, L., Galkin, M.. Morris, C., and Rampášck, L. (2023), Attending to graph transformers. arXiv preprint arXiv:2302.04181.
[48] Pan, S., Hu, R., Long, G., Jiang, J., Yao, L., and Zhang, C. (2018). Adversarialyy regularized graph autoencoder for graph embedding. arXiv preprint arxiv: 1xXx:18802004407
[49] Piao, C., Xu, T., Sun, X., Rong, Y., Zhao, K., and Cheng, H. (2023). Computing graph edit distance via neural graph matching. Proceedings of the VLDB Endowment, 16(8)_1817-1829.
12

---

[50] Rampášek, L., Galkin, M. Dwivedi, V. P., Luu, A. T., Wolf, G., and Beaini, D. (2022). Recipe for general, powerful, scalable graph transformer. Advances in Neural Information Processing Systems, 35:14501-14571
[51] Sanfeliu, A. and Fu, K.-S. (1983). A distance measure between attributed relational graphs for pattern recognition. IEEE transactions on systems, man, and cybernetics, (3):353-362.
[52] Shit, S., Koner, R., Wittmann, B., Paetzold, J., Ezhow, I., Li, H., Pan, J., Sharifzadeh, S., Kaissis, G., Tresp, V., et al. (2022). Relationformer: unified framework for image-to-graphl generation. In European Conference on Computer Vision, pages 422 4399. Springer.
[53] Simonovsky, M. and Komodakis, N. (2018). Graphvae: Towards generation of small graphs using variational autoencoders. In Artificial Neural Networks and Machine Learning-ICANN 2018: 27th International Conference on Artificial Neural Networks, Rhodes, Greece, October 4-7, 2018, Proceedings, Part I 27, pages 412-422, Springer.
[54] Sun, F.-Y., Hoffmann, J., Verma, V., and Tang, J. (2019). Infograph: Unsupervised and semi-supervised graph-level representation learning via mutual information maximization. arXiv preprint arXiv: 190.000000
[55] Tolstikhin, I. O., Houlsby, N., Kolesnikov, A., Beyer, L., Zhai, X., Unterthiner, T., Yung, J., Steiner, A., Keysers, D., Uszkoreit, J., et al. (2021). Mlp-mixer: An all-mlp architecture for vision. Advances in neural information processing systems, 24:24261-24272
[56] Tu, W., Liao, Q., Zhou, S., Peng, X., Ma, C., Liu, Z., Liu, X., Cai, 7.,, and He, K. (2023). Rare: Robust masked graph autoencoder. IEEE Transactions on Knowledge and Data Engineering, (110)55340-335.
[57] Ucak, U. V.. Ashyrmamatov, I., and Lee, J. (2023). Reconstruction of lossless molecular representations from fingerprints. Journal of Cheminformatics, 15(1):1111
[58] 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.
[59] Vinyals. O., Bengio, S., and Kudlur, M. (2015). Order matters: Sequence to sequence for sets. arXiv preprint
[60] Wang, C., Pan, S., Long, G., Zhu, X., and Jiang, J. (2017). Mgae: Marginalized graph autoencoder for graph clustering. In Proceedings of the 2017 ACM on Conference Information and Knowledge Management, pages 889-898.
[61] Wang, H., Wang. J., Wang, J., Zhao, M., Zhang, W., Zhang, F., Xie, X., and Guo, M. (2018). Graphgan: Graph representation learning with generative adversarial nets. In Proceedings of the AAAI conference on artificial intelligence, volume 32.
[62] Wang, R., Guo, Z., Pan, W., Ma, J., Zhang, Y., Yang, N., Liu, Q., Wei, I.,, Zhang, H., Liu, C., et al. (2024). Pygmtools: A python graph matching toolkit. Journal of Machine Learning Research, 25(33):1-7.
[63] Wang, R., Yan, J., and Yang. X. (2019). Learning combinatorial embedding networks for deep graph matching. In Proceedings of the IEEE/CVF international conference on computer vision, pages 3056-3065.
[64] Wang. R., Yan, J., and Yang, X. (2020a). Combinatorial learning of robust deep graph matching: an embedding based approach. IEEE transactions on pattern analysis and machine intelligence, 45(6):984-7000.
[65] Wang, R., Zhang, T., Yu, T., Yan, J., and Yang, X. (2021). Combinatorial learning of graph edit distance via dynamic embedding. Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 5241-5250.
[66] Wang, T., Liu, H., Li, Y., Jin, Y., Hou, X., and Ling, H. (2020b). Learning combinatorial solver for graph matching. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 7568-7577.
13

---

[67] Wen, Q. Zhou, T., Zhang, C., Chen, W., Ma, Z., Yan, J., and Sun, L. (2022). Transformers in time series: A survey. arv preprint arXiv:2202.07125.
[68] Winter, R., Noé, F,, and Clevert, D. (2021), Permutation-invariant variational autoencoder for graph-level representation learning. Advances in Neural Information Processing Systems, 34:9559-955 9573.
[69] Wu, Z., Pan, S., Chen, F., Long, G., Zhang, C., and Yu, P. S. (2020). A comprehensive survey on graph neural networks. IEEE transactions neural networks and learning systems, 32(1):4 24.
[70] Wu, Z., Ramsundar, Feinberg, E. N., Gomes, J., Geniesse, C., Pappu, A. S., Leswing, K., and Pande, V. (2018). Moleculenct: a benchmark for molecular machine learning. Chemical science, 92):513-530.
[71] Xia, J., Wu, I.., Chen, J., Hu, B., and Li, S. (2022). Simgrace: A simple framework for graph contrastive learning without data augmentation. In Proceedings of the ACM web conference 2022, pages 1070-1079.
[72] 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.
[73] Xu, K., Hu, W., Leskovec, J., and Jegelka, S. (2018). How powerful are graph neural networks? arXiv preprint 18.iv:18100000
[74] Yan, S., Yang. Z., Li, H., Song, C., Guan, L., Kang, H., Hua, G., and Huang, Q. (2023). Implicit autoencoder for point-cloud self-supervised representation learning. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 14530-14542.
[75] Yang, J., Labeau, M., and d' Alché Buc, F. (2024a). Learning differentiable surrogate losses for structured prediction. arXiv preprint arXiv:2411, 1.122211111166 11622.
[76] Yang. J., Labeau, M., and d' A'Alhéé-Buc, F. (2024b). Exploiting edge features in graph-based learning with fused network gromov-wasserstein distance. Transactions on Machine Learning Research.
[77] Ying, C., Cai, T., Luo, S., Zheng, S., Ke, G., He, D., Shen, Y., and Liu, T.-Y. (2021). Do transformers really perform badly for graph representation? Advances in neural information processing systems, 34:28877-28888.
[78] Yu, T., Wang, R., Yan. J., and Li, B. (2019). Learning deep graph matching with channel- independent embedding and hungarian attention. In International conference on learning representations.
[79] Yun, S., Jeong, M., Kim, R., Kang, J., and Kim, H. (2019). Graph transformer networks. Advances in neural information processing systems, 32.
[80] Zanfir, A. and Sminchisescu, C. (2018). Deep learning of graph matching. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 2684-2693.
[81] Zhang, H., Li, P., Zhang, R., and Li, X. (2022). Embedding graph auto-encoder for graph clustering. IEEE Transactions on Neural Networks and Learning Systems, 34311)29322-936.
[82] Zhang, X., Liu, H., Li, Q., and Wu, X.-M. (2019). Attributed graph clustering via adaptive graph convolution. arXiv preprint Xix: 1906.01210..
[83] Zhou, J., Cui, G., Hu, S., Zhang. Z.. Yang, C., Liu, Z., Wang, L., Li, C., and Sun, M. (2020). Graph neural networks: A review methods and applications. open, 1:57-81.
[84] Zhu, Y., Du, Y., Wang, Y., Xu, Y., Zhang, J., Liu, Q., and Wu, S. (2022). A survey on deep graph generation: Methods and applications. In Learning on Graphs Conference, pages 47-1. PMLR.
14

---

A Experimental setting
A.1 Datasets
COLORING. COLORING is suite of synthetic datasets introduced in [37] for benchmarking graph prediction methods. Each sample consists of a pair (Image, Graph) as illustrated in Figure Importantly, all COLORING graphs satisfy the 4-color theorem, that is, no adjacent nodes share the same color (label). Since is a synthetic dataset, one can generate as many samples as needed to create the train/test set. We refer to the original paper for more details on the dataset generation. Note that, unless specified otherwise, we ignore the images and consider COLORING as pure graph dataset.
Figure 7: Image/Graph pairs from the COLORING dataset (courtesy of [37]).
Molecular Datasets. To go beyond synthetic data, also consider molecular datasets. They represent a very interesting application of GRALE as 1) the graphs tend to relatively small, 2) very large amount of unsupervised data is available for training, and the learned representation can be applied to many challenging downstream tasks. Most molecular datasets are stored as a list of SMILES strings. In all cases, string to graphs using Rdkit, and we discard the datapoint the conversion fails. Then we remove the hydrogen atoms and use the remaining atom numbers as node labels and bond type (none, single. double, triple, or aromatic) as edge labels. Finally, we remove all graphs with more than N = 32 atoms save computations.
the same preprocessing pipeline. First, convert the SMILES
Training Datasets. We train GRALE on different datasets. First of all, we train COLORING 20, variant of COLORING where we sample 300k graphs of size ranging from 5 20. This version of GRALE is applied to all downstream tasks related to COLORING. Then, we also train on PUBCHEM 32, a large molecular dataset that we obtained by downloading all molecules, with up to 32 heavy atoms from the PUBCHEM database [33]. This version is applied to all downstream tasks related to molecules. For the ablation studies, we reduce computation by training a smaller version of the model on PUBCHEM 16, truncated version of PUBCHEM 32 that retains only graphs with up to nodes. Table presents the main statistics for each dataset.
Table 6: Training Datasets.
DATASET
GRAPH SIZE: AvG STD
GRAPH SIZE: MAX
N SAMPLES
COLORING 20
12.50 + 4.33
20
300K
PUBCHEM 16
13.82 2.17
16
14M
PUBCHEM 32
22.62 + 5.79
32
84M
For classification and regression downstream tasks, we consider supervised molecular datasets from the MoleculeNet benchmark [70]. We choose datasets that cover wide range of fields from Quantum Mechanics (QM9, QM40 4), to Physical Chemistry (Esol, Lipo, Freesolv), to Biophysics (BACE), to Physiology (BBBP). all cases, we preprocess the molecules using the same pipeline as for PUBCHEM 32 to enable transfer learning. In
Downstream Datasets: Classifcation//eggres
*Out of the many available regression targets focus only internal energy.
15

---

particular, we discard all graphs with more than N = 32 atoms, resulting in a truncated version of the datasets. This motivates to sample new random train/test splits (90%/10%) For regression tasks, we also normalize the target with mean of () and a variance of 1. We provide the main statistics of those datasets in Table
Table Downstream datasets (Classfiicaton/Reerressooo We also report the number of samples in the original dataset, before the truncation due to the preprocessing pipeline.
DATASET
GRAPH SIZE: AVG STD
GRAPH SIZE:
MAX
N SAMPLES
N SAMPLES ORIGINAL
QM9
8.80 0.51
9
133885
133885
QM40
21.06 2 6,26
32
137381
162954
ESOL
13.06 6.40
32
1118
1118
LIPO
5.51
32
3187
4200
FREESOLV
8.72
642
BBBP
6.38
32
1686
2050
BACE
27.23 3.80 3.80
32
735
1513
Downstream Datasets: Graph Prediction. For graph prediction, we select two challenging tasks proposed in [37]. First of all. we consider the Image2Graph task where the goal is map the image representation of COLORING instance to its graph representation, meaning that the inputs are the first row of Figure 7 and the targets the second row. For this task, use COLORING 10 and COLORING 15, which are referred to as COLORING medium and COLORIN consider Fingerprint2Graph task. Here, the goal is to reconstruct molecule
big in the original
paper. Secondly, from its fingerprint representation [57], that is, a list of substructures. Once again, we consider the same molecular datasets proposed in the original article, namely QM9 and GDB13 [4]. Table presents the main statistics of those datasets.
Table 8: Downstream datasets (Graph prediction).
DATASET
GRAPH SIZE:
AVG STD
GRAPH SIZE:
MAX
N SAMPLES
COLORING 10 COLORING
7.52 + 1.71
10
100K
9.96 + 3.15
15
200K
QM9
8.79 + 0.51
120K
GDB13
12.76 + 0.55
13
1.3M
A.2 Model and training byperparameters
As detailed in the previous section, we train variants of our models, respectively. on COLORING 20, PUBCHEM 32 and PUBCHEM 16. We report the hyperparameters used in Table 9. Note that to reduce the number of hyperparameters, we set the number of layers in all modules (evoformer encoder, transformer decoder, transformer encoder, evoformer decoder) the same value L,, idem for the number of attention heads И and node/edge hidden dimensions. In all cases, we trained with ADAM [35], warm-up phase, and cosine annealing. We also report the number of GPUs and the total time required to train the models with these parameters.
A.3 Graph reconstruction metrics
To measure the eтror between predicted graph & and a target graph G we first consider the graph edit distance [22, 51], that the number of modification (editions) that should be applied to get to & from G (and vice-versa). The possible editions are node or edge addition, deletion, modification. where node/edge modification stands for changing the label of node/edge. In this paper, we set the cost of all editions 1. It is well known that computing the edit distance is equivalent solving graph matching problem [1]. For instance, in the case of two graphs of the same size G = (F,C)
and & (F, C), the graph edit distance is written
16

---

Table For every dataset used to train GRALE, we report: 1) The architecture parameters, 2) The training Parameters, 3) The computational resources required. Note that when the hidden dimension of ML.ss is set to "None", the MI.s are replaced by a linear layer plus a ReLU activation. This makes the model much more lightweight.
TRAINING DATASET
COLORING
PUBCHEM 16
PUBCHEM 32
MAXIMUM OUTPUT SIZE N
20
16
32
NUMBER OF TOKENS K
4
8
16
DIMENSION OF TOKENS D
32
32
32
TOTAL EMBEDDING DIM = K DD
128
256
512
NUMBER OF LAYERS
5
5
7
NUMBER OF ATTENTION HEADS
4
4
8
NODE DIMENSIONS
128
128
256
NODE HIDDEN DIMENSIONS (MLPS)
NONE
128
256
EDGE DIMENSIONS
64
64
128
EDGE HIDDEN DIMENSIONS (MLPS)
NONE
NONE
NONE
TOTAL PARAMETER COUNT
2.0M
2.5M
11.7M
NUMBER OF GRADIENT STEPS
300K
700K
1.5 M
BATCH SIZE
64
128
256
EPOCHS
64
5
5
NUMBER OF WARMUP STEPS
4K
8K
16K
BASE LEARNING RATE
0.0001
0.0001
0.0001
GRADIENT NORM CLIPPING
0.1
0.1
0.
NUMBER OF GPUs (L40S)
2
TRAINING TIME
8H
20H
100H
Edit(G,C) min PeaN
(A,
(12)
where P(ć] (PF, POPT) and
A CALIGN(G, (G 1(R A1+ Iis + C.pl
(13)
1.
Note that this rewrites as a Quadratic Assignment Problem (QAP) known as Lawler's QAP
Edit(G, = min vect(P)² Kvect(P)
(14)
PEaN
For the proper choice of K N² This formulation be extended cases where G and & have different sizes, up to the proper padding of K, which is equivalent to padding the graph directly do in this paper [24]. Since the average edit distance that observe with GRALE is typically lower than 1, we also report more challenging metric, the Graph Isomorphism Accuracy (GI Acc.), also known t-p-r- hitl, that measures the percentage of samples with edit distance O.
Acc(G, G) = 1 [[Edit(G, = 0)
(15)
B Additionnal experiments
B.1
Training Complexity
When it comes to molecules, unsupervised data is massively available. At the time this paper was written, the PubChem database [33] contained more than 120 million compounds, and this number increasing. In the context of this paper, this raises the question of how much of this data is necessary
17

---

to train the model. To answer this, we propose to train GRALE on truncated dataset and observe the performance. Once again, we train on PUBCHEM 16 using the medium-sized model described in Table 9 to reduce computational cost. Note that we keep the size of the model fixed. For more in-depth results on neural scaling laws in molecular representation learning, we refer [10].
We propose 2 different performance measures. On the one hand, we report the quality of reconstruction (on a test set) against the size of the data set (Figure 8, left). On the other hand, report the results achieved when the learned representation is applied to a downstream task. More precisely, we report the MAE observed when the learned representation is used for regression on the QM9 dataset (Figure 8, right).
0.8
Accuracy
MAE (QA9)
0.4
Gl
Reconstruction Accuracy (Test)
Reconstruction Accuracy (Train)
0.0
10
10a
10f
Pretraining Dataset Size
Pretraining Dotosat Siza
Figure 8: GRALE performances vs pretraining dataset size (in log scale). Left: Train/test recon-
struction accuracy. Right: Downstream performance on the QM9 regression task using the learned embeddings.
For the reconstruction accuracy, we observe overfitting for datasets smaller than one million molecules. More interestingly, observe that the performance the downstream task is also highly dependent on the size of the pretraining dataset, as the performances keep improving past one million samples. Overall, it appears that this version of GRALE is able leverage very large molecular dataset. To apply GRALE to different field, where pretraining datasets are smaller, it might require considering different set of parameters of perhaps more frugal architecture. For instance, the encoder and decoder could be replaced by the more lightweight baselines proposed in E.
B.2 Learning to AutoEncode as a pretraining task and the choice of the latent dimension
The original motivation for the AutoEncoder is dimensionality reduction: given an input x E Rdd=, the goal is find some equivalent representation = IR such that < d,, More generally, learning to encode/decode data in a small latent space is challenging unsupervised task, well-suited for of graphs, the original data
pretraining. However, in the estimate what is a "small" latent dimension d. To explore this question, we propose to train GRALE for various values of d and report the corresponding performances. As in the previous experiment, we report both the reconstruction accuracy and the downstream performance on QM9 (Figure 9).
vector, which makes it hard to
0.05
0.7
MAE QMB
x
acc. train
0.04
Gl Accuracy
0.6
MAE (049)
0.03
0.5
0.4
32
1024
2048
4096
1024
2048
2036
Embedding Dimension
Total Embedding Dimension
Figure 9: GRALE performances vs total embedding dimension d (in log scale). Left: Train/test reconstruction accuracy. Right: Downstream performance on the QM9 regression task using the leareed embeddings.
18

---

RANDOM
ADVERSARIAL
INPUT
RECONSTRUCTION
Figure 10: Inputs from the PUBCHEM 32 dataset along with their GRALE reconstruction. Node color represents the atomic number: Black for carbon, Blue for Oxygen, etc. The different types of bonds are not represented, but we represent the predicted probability for edge existence with its width. On left we provide random samples for reference. On the right we provide two "failure case" (sampled in adversarial fashion from PUBCHEM 32). In both adversarial molecule, the input graph exhibits many symmetries. For instance, the second sample, nodes are perfectly symmetric (in the sense of the Weisfeiler-Leman test).
First, we observe that reconstruction performance and downstream task performance are highly correlated, which is consistent with the observation made in the previous experiment and the results of this work in general. This confirms the intuition that learning to encode and decode a graph is suitable pretraining task. We also observe that small embedding dimensions act regularizer, preventing overfitting in terms of graph reconstruction accuracy. Despite this, we do not observe that the downstream performance deteriorates with higher embedding dimensions This suggests that learning to encode/decode entire graphs into an Euclidean space is always a challenging task, even when the latent space is of large dimensions.
B.3 Reconstruction failure case
We now highlight an interesting failure case of the AutoEncoder. To this end, we plot the pair of inputs and outputs with the maximum reconstruction error. We observe that the hardest cases to handle for the AutoEncoder are those where the input graph exhibits many symmetries. When this happens, it becomes difficult for the matcher to predict the optimal matching between input and output. The main reason for this is that similar nodes have similar embeddings, and since the matcher is based on these hidden node features, it might easily confuse nodes with apparently similar positions in the graph. As a result, GRALE has difficulty converging in this region of the graph space. To illustrate this phenomenon, random test samples and plot their reconstruction (Figure 10). For comparison, we also provide random samples that correctly reconstructed.
select the two graphs with the highest reconstruction error out of 1000
B.4 Latent space exploration
Finally, we conclude this section with qualitative exploration of the latent space learned by GRALE. In Figure 11, we first plot the two principal PCA components of the latent space learned for COL- ORING 20 and PUBCHEM 32. Remarkably, this reveals that the first PCA component explicitly encodes the size of the graph (number of nodes). This observation motivates interpretation of the second PCA direction. To this end, we sample 10,000 graphs from each dataset and select the four graphs whose embeddings maximize and minimize the projection along the second
investigate the
Within this "reasonable" range of values.
19

---

PCA component. We visualize these graphs in Figure 12. In both cases, we observe that the second component appears encode properties related to node labels, such as the number of carbon atoms for PUBCHEM 32. This aligns with the observations of Krzakala et al. [37], who report that graph prediction models tend to encode node lahels very strongly.
It is unclear whether this behavior is desirable in practice. For instance, in the case of molecular data, might be preferable for the latent space to structured according chemical properties instead. To further explore this aspect, we focus on the QM9 dataset. QM9 mostly contains molecules of size which allows us zoom in on subspace corresponding molecules of fixed size. Moreover, this dataset provides a wide range of ground-trumg chemical properties, We randomly sample 10,000 molecules with exactly 9 nodes from QM9, encode them using a version of GRALE pretrained on PUBCHEM 32, and apply t-SNE to reduce the embeddings to two dimensions. In Figure 13, we color the resulting 2D latent space according to various chemical properties. Overall, we observe that these properties exhibit some degree of structure in the latent space, although this structure is less pronounced than that associated with the structural properties discussed above.
PCA (PUBCHEM 32)
PCA (COLORING 20)
20
30
18
PCA Component
PCA Component 2
10
16
number of node
14
15
numbe
12
-5
10
-10
8
-20
-15
-10
10
-10
10
20
PCA Component
PCA Component
Figure 11: PCA in the latent space for PUBCHEM 32 (left) and COLORING (right). Each point corresponds to the embedding of one graph. Points are colored according to the number nodes in the graph. both cases, the first principal component appears encode the graph size.
PUBCHEM
COLORING
arg Max (Ri, M2)
arg min (2,, uz)
Figure 12: To reveal the role of the second principal component (uz), retrieve the graphs whose
embeddings maximize and minimize the projection along this direction. For PUBCHEM (resp. COL- ORING), this component appears roughly encode the number of carbon atoms (resp. yellow nodes).
20

---

where an hyperparameter set to = our experiments. Then the edge features are defined as u298 atom
alpha
2.0
1.5
1.5
1.5
1.0
0.5
0.5
0.5
0.0
-0.5
-0.5
-0.5
-1.0
-1.5
-1.
-1.5
-2.0
-2.0
zove
2.0
2.0
2.0
1.0
1.0
1.0
0.0
0.0
0.0
-1.0
-10
-10
-20
-20
-2.0
Figure 13: Awo-dimensional t-SNE of the QM9 embedding space, with perplexity set to 50. Each point corresponds to the embedding of one graph, colored according to different chemical properties.
C GRALE architecture details
C.1
Featurizer
There are many ways to parametrize the featurizers & and 6'. In this paper, we focus simple choices that have already demonstrated good empirical performances [45, 77. 68, 37]. From datapoint E D, the fcaturizer first constructs a node label matrix Fo(x) R Raxdo, an adjacency matrix A(x) E (0, 1 and shortest path matrix SP) E Naxx where n is the size of the graph. We then augment the node features with k-th order diffusion
F(x) =
(16)
(z) CONCAT(F,(t). (2),
(17)
where ONE-HOT denotes one-hot encoding and PE denotes sinusoidal positionnal encoding [58]. If edge labels are available, they are concatenated to as well. Finally, the featurizers are defined as
<(x) (F(x) Noise, C(x)), (x) PADDING (F(),
(18)
where Noise is random noise matrix, and PADDING pads all graphs to the same size N > as defined above. The noise component breaks the symmetries in the input graph, which enables the encoder to produce distinet embeddings for all the nodes. We demonstrate empirically that this is crucial for the performance of the matcher and provide a more qualitative explanation in B.3. We leave the exploration of more complex, and possibly more asymmetric, featurizers future work.
C.2 Encoder
The encoder g takes as input a graph G = (F, C) and returns both the node level embeddings Inodes (G) X and graph level embedding Igraph (G) = Z. The main component of is stack of L Evoformer Encoder layers [30] that produces the hidden representation (F', C².) of the input graph.
(Ft+1cCtt) cd+1)) EvoformerEEncoder C*)
(19)
21

---

where F' E Raxdy (resp. C E R=xuxd)) are initialized by applying node-wise (resp. edge-wise) linear layer on F (resp. C). The Evoformer Encoder layer used GRALE is represented in Figure 14. Compared to the original implementation, we make two notable changes that make this version much more lightweight. First, we replace the MLP of the Feed Forward Block (FFB) with a simple linear layer followed by an activation function. Then, of the 4 modules dedicated to the update of C, we keep only one that we call Triangular Self Attention Block (tSAB) to highlight the symmetry with Transformer Encoder. The definitions for all these blocks are provided in Appendix D.
OPB
ISAB
FFB
C
bSAB
FFB
Figure 14: Architecture of the Evoformer Encoder layer used for encoding the input graph (F,C).
Once the hidden representation (F4,C4) has been computed, the node level embeddings are simply derived from linear operation
X; Linear(P!)) if i n, X; otherwise.
(20)
where u is learnable padding vector.
Finally, the graph-level representation is obtained by pooling C with Transformer Decoder. More precisely, we first flatten C' to be a n² x de matrix, then we pass it to standard L layer Transformer Decoder output the graph level embedding 2 RXXD
Z
-TranssoorerrDDccder( C²
(21)
where zg is a learnable query matrix in R x This module is illustrated in Figure 15.
Zg
Z
Figure 15: Architecture the Transformer Decoder used for pooling C-L,
C.3 Decoder
The decoder takes input the graph embedding Z and should output both the reconstruction G (h, F., C') and the node embeddings X that are required match input and output graphs. To this end, the proposed architecture mimics that of a Transformer Encoder-Decodes except that we replace the usual Transformer Decoder with a novel Evoformer Decoder. More formally, the latent representation Z = Z is first updated by Transformer Encoder with L layers
z Transf (raennneeer
(22)
For completeness, we also recall the content of a transformer encoder layer in Figure 16.
z
SAB
FFB
Z
Figure 16: Architecture of the Transformer Encoder.
22

---

Then, similarly to Transformer Decoder, we define a learnable graph query Og) where F8 Rxxde and C RxNNNxde that we update using layers of the novel Evoformer Decoder
(FO 1) EvoformeeDeecode((f,, Co. z²)
(23)
The proposed Evoformer Decoder is the Evoformer Encoder, the the Transformer Decoder to the Transformer Encoder, i.e., it the same, plus up to a few Cross-Attention Blocks (CAB) that enable conditioning = See Figure 17 for the details of the proposed layer.
NEW
Co
OPB
FLATTEN
CAB
UNFLATTEN
Fl
F
Figure 17: Similarly Transformer Decoder, the proposed Evoformer Decoder layer augments the Evoformer Encoder with 2 Cross-Attention Blocks (CAB) so that the output can be conditioned on some source Z. All the inner blocks defined in D.
Finally, the reconstructed graphs are obtained with a few linear heads
à Sig (igmoid(Linear((FF))
= LinnearFFF)) (FG), Č= Liinear(CC)
(24)
where the linear layers are applied node and edge-wise. Similarly, the node-level embeddings of the output graphs are defined as
X Linear (F2)
(25)
C.4 Matcher
The matcher uses the node embeddings of the input graph X and target graph X to compute the matching 7 between the two graphs. The first step is build an affinity matrix K E R NxN between the nodes. We propose to parametrize K using two one hidden layer MLPs MLP and MLP HIPout
Ki = exp( - MLP (X,) MLP out (X₂)))
(26)
Note that K positive, but might not be a bistochastic matrix. To this end, we project on dN using Sinkhorn projections
1 = SINKHORN K)
(27)
We fix the number of Sinkhorn steps 100, and ensure stability, we perform the iterations in the log domain [12]. At train time, we backpropagate through Sinkhorn by unrolling through these iterations [16]. test time, we fully replace Sinkhorn by the Hungarian algorithm [15] to ensure that the matching I is discrete, permutation matrix.
C.5 Loss
Recall that we use the loss originally introduced Any2Graph [37]:
N Σ
Cor(G, G,T) = Σ (n TT. +
help(F, FT + Σ
hohglo(Cs, C,.T.
1.
A.
(28)
23

---

where the ground losses ln. f and & still need to be defined. We decompose the node reconstruction loss Ey between the part devoted node labels (discrete) f and node features (continuous) f- Similarly, we decompose fc into E and Eg Following Any2Graph [37], use cross-entropy loss for all discrete losses f,, FG, and L2 loss for all continuous losses Epp Cg This makes total of terms that we balance using 5 hyperparameters or;; at O',,, op, og and og. Once again, follow the guidelines derived in the original paper and set
0ç N
af N
aF 2N OC N
(29)
ac 2N
D Definitions of attention based models inner blocks
For completeness, devote this section the definition of all blocks that appear in the modules used in GRALE. For more details, we refer to specialized works such as Lee et al. [40] for Transformer and Jumper al. [30] for Evoformer.
From layers to blocks. We adopt the convention that block is always made of layer plus normalization and skip connection.
BLOCK(2) = NORM( + LAYER(1))
(30)
Note that, in some works, the layer normalization is placed at the start of the block instead [72].
Parallelization. To lighten the notations we denote f[X] whenever function f is applied to the last dimension of X. For instance, when X RND is feature matrix (N nodes with features of dimension D), we have f[X]; = f(X)). Similarly, when C E NxxxD an edge feature tensor, have f( f(C,)).
Subseripts convention. In the following, we use the subscripts j, is for the nodes/tokens indexing. b, e for features dimensions and for indexing the heads in multi-head attention.
D.1 Node level blocks
Feed-Forward Block (FFB). Given an input X E NxD, the FF layer simply consist in applying the same MLP to all lines/tokens/nodes of X parallel
FFB(X) NORM(X + MLP[X])
(31)
By construction, the FFB block is permutation equivariant w.r.t. X.
Dot Product Attention. Given query matrix Q NxD, key and value matrices K, V E MxD and biais matrix E IR NxM, the Dot Product Attention attention writes as:
DPA K, B) Softmax(QK BJV
(32)
More generally, for Xx Multi-Head Attention writes as
MHA(Q, KVV, CON ..., Op)
(33)
where
O, = DPA (q [ "v
(34)
and are linear layers and b/,5 B
24

---

Cross-Attention Block (CAB). Given X RND and Y E Rxx we defin::
CA(X, Y) (1AA
(35)
where q, U. RR + R are linear layers. The Cross-Attention Block is:
CAB(X, Y) NORM(X + CA(X,Y))
(36)
The Cross Attention layer permutation equivariant with respect X and invariant with respect the permutation of context Y.
Self-Attentinn Block (SAB). Given E RND the Self-Attention Block writes as
SAB X) CAB(XX
(37)
The Self Attention layer is permutation equivariant with respect to X.
D.2 Graph level blocks
Einstein Notations. In the following, we adopt the Einstein summation convention for tensor operations. For instance, given matrices A NxD and E DR the matrix multiplication C' AB, defined as Cj = >> BR.j. is denoted compactly as C D and the unused indices implicitly summed over.
Triangular Attention. Triangle Attention the equivalent of self-attention for the edges. To reduce the size of the attention matrix, edge (i.j) can only attend to its neighbouring edges (i, k). Thus for Q, K.K.V. NxNxD, the triangle attention layer writes as:
TA K, Vigaa = Aij,,
(38)
where the Arj. & is the attention between (i, and (i, k) defined as A. Soft (a Multi-head attention original Evoformer also includes similar layers where (i,j) can only attend to (k, i), (k, and (j, k). For the sake of simplicity, we remove those layers in implementation.
be defined in the same way for the self-attention layer. Note that the
triangular Self-Attention Block (tSAB). Denoting C E NNNxD we define:
tCA TA(g[C), (CI,
(39)
where y, u, RRD RD linear layers. The triangular Self-Attention Block is defined as:
TSAB C*) NORK(C + tSA(C))
(40)
The triangular self-attentio layer satisfies second-order permutation equivariance with respect to C.
Outer Product Block (OPB). Given node feature matrix X N and edge feature tensor C NxNxD the Outer Product layer enables information flow from the nodes to the edges.
OP(X) X W Wa.,Wabb.... a.b.
(41)
where W E DxDD is a learnable weight tensor. The Outer Product Block is defined as:
OPB(C, NORM(C + OP(X))
(42)
25

---

biased Self-Attention Block (bSAB). Conversely, the biased self attentttnnion layer enables information flow from the edges the nodes. Given a node feature matrix X Rx and edge feature tensor C' E RNNND we define:
BSA C) = MHA M AX], (X),,())
(43)
where q, k TR. RD and b: RDD b TRA are linear layers. Finally, the biased Block is:
DSAB C) NORM + DSA(X, C))
(44)
E Ablation studies details
In section 5.1, conduct extensive ablation study where validate the choice of our model components by replacing them with a baseline. We now provide more precise details on the baselines used for this experiment.
Loss. Recall the expression of the loss we propose for GRALE:
GG, G,
Σ Cn
Σ (e 8
E
hihalo io (45)
For the ablation study, we replace with the one proposed train PIGVAE [68]. Since the original PIGVAE loss cannot take into account the node padding vector h, we propose the following extension
N CPIGVEE+ (G, G,G Eenth, (he (Th).) Σ (.EE(FE,
N
+ Σ heh.f
(46)
We also add a regularization term as suggested in the original paper, and extend it to take into account the padding
OPIEVAE (f)= Σ
Li, log(T.))h,.
(47)
5.j
Finally, we replace our loss by LyιeNÆr (G, G, + Alprove (T)) and we report the results for X 10 (after a basic grid-search À E (0.1, 10)).
Featurizer. As detailed in C, the proposed featurizer & augments the graph representation with high-order properties such as the shortest path matrix. We check the importance of this preprocessing step by removing entirely. More precisely, we change the equation (16) that defines the node features into
F F(x)= Fu
(48)
and the equation (17) that defines the edge features into
(z)(x) CONCAT(F((2) (F), (x), ONE-HOT(AA,
(49)
26

---

Encoder. To assess the importance of the Evoformer Encoder module, we swap it with graph neural network (GNN), More precisely, we change equation (19) into
p GNN (* .A)
(50)
where A is the adjacency matrix. Since the GNN does not output hidden edge representations, Che- define them as J = CONCAT(E," P.... For this experiment, we use 4-layer GIN [73].
Decoder. Similarly, check the importance of the novel Evoformer Decoder by swapping it with a more classical Transformer Decoder. More precisely, we change equation (23) into
@e TransffrreerDecoder((f... z²,)
(51)
Since the Transformer Decoder does not reconstruct any edges, add an extra MLP (Ch) (LF(CONCAT((EE)) (F()))
Matcher. Since the role of our matcher is very similar to that of the permuter introduced for PIGVAE [68]. we propose to plug it inside our model instead. For completeness, we recall the definition of PIGVAE permuter:
m 08, SoftSort(XU")
(52)
where U E Rd is learnable scoring vector and the SoftSort: : RN + R operator is defined as the relaxation of the ArgSort operator
[ss (|3-- (orr(((s)))))
SoftSort(s)a, = soft tmax
(53)
where т fixed temperature parameter. Note that, compared the GRALE matcher, this implementation does not leverage the node features of the output graphs. Instead, it assumes that the permutation between input and output can be seen as sorting of some node scores 8,. Importantly, the original paper mentions that the Permuter benefits from decaying the parameter during training. However, detailed scheduling training is not provided in the original article; therefore, we report the best results from the grid search E {le 5, 1e 4, 1e 3, le 2}.
Disanbiguation noise. Finally, we propose to remove the disambiguation noise added to the input features. That is
<(x) (F(x),
(54)
Recall that the expected role this noise is to enable the model to produce distinct node embeddings for nodes that are otherwise undistinguishable (in the sense of the Weisfeiler-Lehman test).
F Proofs of the theoretical results
F.1 Loss properties
Proposition Computational cost. This proposition is trivial extension of Proposition from Any2Graph [37]. The only difference is that, proposed in [76], we consider edge feature tensor C instead an adjacency matrix A. The proof remains the same. Note that the assumption made the original paper is that there exist h1, l1,, fi, f2 such that lo b) fi()) + f2(b) - (h (a), (2(b)). Instead, we make the slightly stronger (but arguably simpler) assumption that & a Bregman divergence. By definition, any Bregman divergence E writes
((a.b) = F(b) F(a) (VF(a), a)
(55)
27

---

and thus, the original assumption is verified for fi(0) (VF(o), -(()) (()) (a) and h2 (6) b.
Proposition 2: Positivity. This is a direct extension to the case ne > 1 of Proposition 3 from [37].
F.2 Positioning with respect to PIGVAE
In the following, we assume that the ground losses by and & are Bregman divergences defined
above. G (F, C) and & = (f², C) are graphs of size and we omit the padding vectors, enabling fair comparison with PIGVAE. In this context, the proposed loss is rewritten
N
N Er(B, + Σ Ci
LG G,
(56)
k.
We also recall the expression of PIGVAE's loss
CPIOVAE (G, (GGG)
(57)
where LALIGN(G. (G, Ei (F(P; + Eij-1 (c(Ci, O4g) and β| -
E
Proposition Link between LPIgVa and Lor. Let nn be a bistochastic matrix. Since f is a Bregman divergence, it is convex with respect to the second variable and the Jensen inequality gives:
N EFF(B, 2 lo P.,
N
E = [FF
(58)
Note that Jensen's inequality applies because, by definition of bistochastic matrix, E, Tig = Applying the same reasoning twice we get that for any i, k
N
Co Th 2 to Ciis Eopiing Eo(Cin (TCT"))))
(59)
3.
which concludes that
Cor G, 2 LIIVAS G.
(60)
With equality if and only if all the Jensen inequalities equalities, that is, if and only if / is permutation matrix.
Proposition 4: Failure case of LPIGVAE- PIGVAE's loss can be zero even if and G are not isomorphic. This can be demonstrated with a very simple counterexample. Let N = 2, C = C and
00.5 0.5
!
F
(61)
While it obvious that the two graphs are not isomorphic (the sets of nodes are different), when we set the matching matrix to
f
0.5
0.5
(62)
0.5
0.5
28

---

we have that TF = F and that CrIOve G, = 0. Therefore, we conclude that LPIVAA does satisfy proposition 2.
29

---

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: More precisely, we provide "contribution" paragraph inside the introduction. All these contributions are justified through rigorous comparison with extensive experiments on simulated and real data.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: The main limitation of the model is the maximum graph size N which make clear in the model presentation. The cubic complexity with respect to N is also stressed in the conclusion of the paper.
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 on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of 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 fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
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
30

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification:
We provide dedicated appendix for this purpose.
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 in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We dedicate one appendix the details of the architecture and one appendix to the details of the experimental setting.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not 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 make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to model. In general. releasing code and data 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.
specific model and empirical evaluation, may
While NeurIPS 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 reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (c.g., a large language model), then there should either be way to 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 (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
31

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: We will provide GitHub page with all the code required to reproduce the main results upon publication of this paper. This includes data downloading and preprocessing.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS 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, "No" an acceptable answer. Papers cannot be rejected simply for 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 NeurlPS code and data submission guidelines (https: (oodeSummissionnoo
/ //niss. wwtpcccpppcc.aeeecc.ccccc.ccetle http:/ppww.ggcpp.///////eeeeea//
for more details.
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
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?
Question:
Answer:[Yen Yes]
Justification:
Yes, all the details are available in the dedicated appendix.
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, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Yes, whenever it is computationnaly possible report standard deviation (over several runs or several instances depending on the experiment).
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
32

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run 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).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
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 or figures symmetric error bars that would yield results that are out range (e.g. negative еπτог rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Yes, we provide the hardware and the total training time required to train our model in appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of 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 attps://neur/:
Answer: [Yes]
Justification: To the best of our knowledge, this work is conform to the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., - if there is 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 societal impacts of the work performed?
Answer: [NA]
Justification:
The scope of this paper is too fundamental to quantify any societal impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
33

---

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 not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that 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 out that 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
To the best of our knowledge there is no need for such safeguards in this paper.
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 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 the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
We provide proper credit for all assets mentioned in this paper.
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 dataset.
The authors should state which version of the asset used and, possible, include URI.
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.
34

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/dataseta has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information 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: This paper is dedicated to the description of the novel asset (model).
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent 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. Crowdsoureing 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 used neither crowdsourcing nor human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information 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 NeurIPS 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: Same as above.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending 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.
35

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere 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.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: We don't use LLMs for any important, original, non-standard component of the paper.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy (https: http://p//.//oooeeeee/////////// for what should or should not be described.
36


Reviews:
[{"review_id": "m3QmvfJfor", "reviewer": "Reviewer_LtMM", "summary": "The paper introduces GRALE, a novel graph-level autoencoder that encodes and decodes entire graphs—of variable sizes—into a shared Euclidean latent space. GRALE employs a loss inspired by Optimal Transport and features a differentiable node-matching module, trained end-to-end with the encoder and decoder. It builds upon the Evoformer architecture from AlphaFold, adapting it for both encoding and decoding graphs. Extensive experiments show that GRALE achieves state-of-the-art performance in tasks including graph reconstruction, classification, regression, interpolation, and editing, especially in molecular and synthetic datasets.", "questions": "- Can GRALE scale to significantly larger graphs (e.g., protein networks or social graphs with hundreds of nodes), and what would be required to do so?\n\n- Would incorporating graph-specific domain priors (e.g., valency in molecular graphs) improve GRALE’s reconstructions?\n\n- Can the Evoformer Decoder be applied independently for graph generation tasks?\n\n- Could fine-tuning the matcher module separately improve matching accuracy for unseen graph pairs?\n\n- Is there a way to adapt GRALE to support dynamic or evolving graphs (e.g., temporal sequences)?\n\n- How about comparing GRALE with GraphsGPT[1]? \n\n[1] A Graph is Worth K Words: Euclideanizing Graph using Pure Transformer", "limitations": "- Scalability: The O(N³) cost for attention and matching restricts practical use to small graphs (≤32 nodes).\n\n- Data-Hungry Training: Requires very large training sets to reach high accuracy—less suitable for low-resource domains.\n\n- No Ground Truth Matching Supervision: Matching is learned implicitly, which may limit interpretability and performance on exact alignment tasks.\n\n- Fixed Graph Size Ceiling: Padding strategy introduces a hard constraint on maximum graph size.\n\n- Generalization to Unstructured Inputs: Limited discussion or experiments on how well GRALE performs with real-world, noisy graph inputs outside curated datasets.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths：\n- Novel Architecture: Utilizes and adapts Evoformer for graph-level encoding and introduces a novel Evoformer Decoder.\n\n- End-to-End Differentiable Matching: Avoids NP-hard graph matching by integrating a learnable Sinkhorn-based matcher.\n\n- Versatile Applications: Enables not only basic tasks (e.g., classification, regression) but also complex operations like graph interpolation and editing in latent space.\n\n- SOTA Performance: Demonstrates strong results across multiple benchmarks (e.g., PUBCHEM, QM9) and outperforms baselines like PIGVAE and GraphVAE.\n\n- Thorough Evaluation: Includes detailed ablations and empirical analysis of architecture choices, matching methods, and representation space.\n\n- Scalability Evidence: Trained on massive molecular datasets (up to 84M samples), showing GRALE’s robustness and generalization.\n\nWeaknesses：\n- High Computational Complexity: The use of edge-level attention and Sinkhorn projections makes training and inference computationally intensive (O(N³)), limiting applicability to graphs with ≤32 nodes.\n\n- Limited Theoretical Justification: While empirical results are compelling, theoretical guarantees (e.g., generalization bounds, robustness under graph perturbation) are not deeply explored.\n\n- Heavy Reliance on Pretraining: The effectiveness of GRALE in downstream tasks depends strongly on massive pretraining on large datasets.", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review. In particular, many of your questions align with research directions that we are currently investigating for future works, which we found particularly encouraging. In the following, we address the points raised in your review.\n\n> Can GRALE scale to significantly larger graphs (e.g., protein networks or social graphs with hundreds of nodes), and what would be required to do so?\n\nAs you noted, the proposed model has an overall complexity of $\\mathcal{O}(N^3)$. A first step toward scalability would be reducing this to $\\mathcal{O}(N^2)$. While it's relatively easy to design an architecture with $\\mathcal{O}(N^2)$ complexity (see baselines in Appendix E), the real bottleneck is the loss, which remains $\\mathcal{O}(N^3)$ even with an oracle for the matching problem (Proposition 1). Therefore, the key would be to approximate the loss, for instance via low-rank approximations [1]. This might reduce reconstruction quality but could still yield a rich latent space.\n\nFor truly large graphs (e.g., social networks), an entirely new approach would be needed. Tasks for such graphs typically focus on node representation learning. In that context, we suggest training the autoencoder to encode and reconstruct a **node’s local neighborhood**, an idea well illustrated in Figure 1 of the seminal GraphSAGE paper [2].\n\n> Would incorporating graph-specific domain priors (e.g., valency in molecular graphs) improve GRALE’s reconstructions?\n\nYes, definitely. In this work, we deliberately avoid relying on expert knowledge to preserve generality, but incorporating such priors would certainly improve reconstruction quality. In particular, it could mitigate the artifacts discussed in Section B.3. This seems like a crucial direction for future work focused on a specific modality.\n\n> Can the Evoformer Decoder be applied independently for graph generation tasks?\n\nWe believe so! The proposed Evoformer layer is defined as $A' = f(A, Z)$, where $A$ is the adjacency matrix and $Z$ is a latent variable. This makes it a promising candidate for a conditional denoising model of the form:\n\n$$A_{\\text{denoised}} = f(A_\\text{noisy}, \\text{condition})$$\n\n> Could fine-tuning the matcher module separately improve matching accuracy for unseen graph pairs?\n\nExcellent question — it motivated us to conduct a new experiment. We fine-tuned the matcher using pairs of graphs from the training set, with 1000 gradient steps and a small learning rate. The new results (to be added to Table 5) are:\n\n**For COLORING:**\n\n| Method              | EDIT DIST | COMPUTE TIME (s) |\n|---------------------|-----------|------------------|\n| A*                  | 19.66     | 3.487            |\n| GRALE               | 08.92     | 0.005            |\n| GRALE + Finetuning  | 07.64     | 0.005            |\n\n**For PUBCHEM (note the large improvement!):**\n\n| Method              | EDIT DIST | COMPUTE TIME (s) |\n|---------------------|-----------|------------------|\n| Greedy A*           | 32.53     | 0.110            |\n| GRALE               | 32.77     | 0.008            |\n| GRALE + Finetuning  | 19.33     | 0.008            |\n\nThanks to fine-tuning, GRALE now outperforms the best baseline by a large margin on both datasets. Thank you for this suggestion, which strengthens the paper and highlights the value of the matcher.\n\n> Is there a way to adapt GRALE to support dynamic or evolving graphs (e.g., temporal sequences)?\n\nOur preliminary experiments on graph interpolation and editing suggest that continuous dynamics in the latent space could model discrete graph-level dynamics. While this still needs to be demonstrated on more complex dynamics, it is definitely a promising avenue for future work.\n\n> How about comparing GRALE with GraphsGPT[1]?\n\nThank you for pointing this out. GraphsGPT shares our goal of encoding graphs into Euclidean space, and we agree it merits discussion. We will update the introduction to cover methods that represent graphs as sequences (GraphsGPT and others [3,4,5]). A key limitation of these approaches is that sequencing breaks permutation invariance, which is central to many applications and to our method. Additionally, designing sequencing algorithms often requires domain-specific knowledge, reducing generality.\n\n> Scalability: The O(N³) cost for attention and matching restricts practical use to small graphs (≤32 nodes).\n\nWe agree that $\\mathcal{O}(N^3)$ scaling is a limitation, as stated in the conclusion. However, we would like to clarify that 32 nodes is not a strict limit. Below are time and memory costs for a single gradient step (batch size 1) on an RTX 3500 Ada (12GB VRAM):\n\n| N      | 8     | 16    | 32    | 64    | 128   | 256   |\n|--------|-------|-------|-------|-------|--------|--------|\n| Step Time (s) | 0.01  | 0.01  | 0.02  | 0.02  | 0.03   | 0.07   |\n| GPU Memory (GB) | 0.2   | 0.3   | 0.4   | 0.8   | 3.0    | 10.7   |\n\nNote that $N = 128$ fits in 3GB. This suggests that 8 A40 GPUs (48GB each) could support training with a batch size of 128 — a reasonable setting. The model used here is the same as for PUBCHEM.\n\n> Data-Hungry Training: Requires very large training sets to reach high accuracy—less suitable for low-resource domains.\n\nWe implemented our modules so the model **can** leverage large pretraining datasets. With a lighter implementation, the proposed pipeline (encoder-decoder-matcher-$\\mathcal{L}_{GRALE}$) could be used on smaller datasets.\n\nSince reviewer CWAG noted that \"it remains unclear whether the method generalizes well to non-chemical graphs,\" we addressed both concerns together by training GRALE on BN, a relatively small dataset of 200,000 8-node Bayesian networks [6]. Each network has a BIC score (on the Asia dataset) used as a regression target. Using a lighter GRALE version (GNN and transformer baselines from Appendix E), we managed to outperform the state-of-the-art reported in [6]. (See reply to CWAG for detailed results.)\n\n> Generalization to Unstructured Inputs: Limited discussion or experiments on how well GRALE performs with real-world, noisy graph inputs outside curated datasets.\n\nOur experiment on COLORING (lines 252–257) suggests that GRALE is fairly robust to noise. Still, we agree this is an interesting question for real-world data and an important direction for future work, though somewhat out of scope for this paper.\n\n### References\n\n[1] Scetbon, M., Peyré, G., & Cuturi, M. (2022). Linear-time Gromov-Wasserstein distances using low rank couplings and costs. *PMLR*.\n\n[2] Hamilton, W., Ying, Z., & Leskovec, J. (2017). Inductive representation learning on large graphs. *NeurIPS*.\n\n[3] Cofala, T., & Kramer, O. (2021). Transformers for Molecular Graph Generation. *ESANN*.\n\n[4] Xie, X. et al. (2022). From discrimination to generation: Knowledge graph completion with generative transformer. *WWW Companion*.\n\n[5] Belli, D., & Kipf, T. (2019). Image-conditioned graph generation for road network extraction. *arXiv:1910.14388*.\n\n[6] Zhang, M. et al. (2019). D-VAE: A variational autoencoder for directed acyclic graphs. *NeurIPS*."}, {"review_id": "AbwK7nN4fu", "reviewer": "Reviewer_CWAG", "summary": "This paper proposes GRALE, a graph-level autoencoder that learns to encode and decode entire graphs into a shared embedding space using an optimal transport inspired loss and a differentiable matching module. It leverages Evoformer-based architectures to support flexible graph reconstruction and shows strong results on reconstruction, classification, and prediction tasks.", "questions": "1. The paper claims that the graph size is predicted via the padding mask vector, yet the decoding process is not clearly explained. How does the model ensure the correct number of nodes is generated without explicit supervision on graph size?\n\n2. Lacks ablation against standard Transformer decoders. How critical is the Evoformer Decoder to performance, and what unique capabilities does it provide?", "limitations": "1.The method incurs relatively high computational overhead, primarily due to the use of Evoformer modules and Sinkhorn-based matching, which limits scalability to larger graphs.\n\n2. Although the OT-inspired loss is conceptually sound, the paper lacks theoretical analysis to guarantee that the learned embeddings faithfully preserve semantic or structural similarities between graphs.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1. GRALE embeds graphs into a tokenized vector space that supports a wide range of downstream tasks. The design supports vector arithmetic over graph embeddings, enabling novel use cases such as latent space editing and interpolation.\n\n2 . The method achieves superior performance over GraphVAE and PIGVAE in reconstruction accuracy and downstream tasks. Ablation studies are well-conducted and demonstrate the contribution of each module.\n\n 3.The incorporation of the Evoformer module from AlphaFold for both graph encoding and decoding is a noteworthy attempt, which might help effective modeling of interactions between node and edge features.\n\n\nWeaknesses:\n1. The paper omits some relevant graph-level models that could serve as strong baselines or comparisons. For instance, recent masked graph autoencoders (e.g., GraphMAE) and Transformer-based architectures for graphs (e.g., Graphormer, TokenGT) are not discussed or evaluated.\n\n2 . The proposed “Evoformer decoder” part lacks comparative analysis with standard Transformer decoders or other graph generation decoders.\n\n3. Most experiments are performed on molecules or COLORING datasets. It remains unclear whether the method generalizes well to non-chemical graphs", "was_revised": true, "final_justification": "1. They have expanded our evaluation with experiments on non-chemical datasets, demonstrating the method’s generalization beyond its original domain.\n2. They conducted an ablation study to validate the encoder’s effectiveness. \n3. Their response addresses my concern.", "rebuttal": "Thank you for your review. You raised important points that motivated us to conduct new experiments. We believe these new results strengthen the paper, and we hope you agree.\n\n> Most experiments are performed on molecules or COLORING datasets. It remains unclear whether the method generalizes well to non-chemical graphs.\n\nWe agree. GRALE was designed as a general graph representation learning approach, and it is indeed interesting to evaluate it on a wider range of data. After reviewing the literature, we identified a very different modality: the BN dataset [1], which consists of 200,000 8-node Bayesian networks. Each network is associated with a BIC score on the Asia dataset. The task is to predict this BIC score from the graph.\n\nWe pre-trained GRALE on BN in an unsupervised fashion and used the learned graph-level embeddings as input to an MLP for the downstream regression task. We were pleased to observe that this direct use of GRALE outperformed the state-of-the-art results reported in [1], including autoencoders specifically designed for this task.\n\nWe reproduce the result table from [1] below, now including GRALE:\n\n| **Method** | **RMSE ↓** | **Pearson’s *r* ↑** |\n|-----------|------------|---------------------|\n| GRALE     | 0.18       | 0.98                |\n| D-VAE     | 0.30       | 0.95                |\n| S-VAE     | 0.36       | 0.93                |\n| GraphRNN  | 0.77       | 0.64                |\n| GCN       | 0.55       | 0.83                |\n| DeepGMG   | 0.78       | 0.62                |\n\nDespite the modality being very different from molecules, GRALE achieves state-of-the-art results. Thank you for raising this point — it led us to reinforce the claims of our paper.\n\n> The paper omits some relevant graph-level models that could serve as strong baselines or comparisons. For instance, recent masked graph autoencoders (e.g., GraphMAE) and Transformer-based architectures for graphs (e.g., Graphormer, TokenGT) are not discussed or evaluated.\n\nWe agree that GraphMAE is a relevant and strong baseline. We performed new experiments using GraphMAE, following the same protocol as our existing baselines. While GraphMAE supports transfer learning (as we do with pre-training on PUBCHEM), it does not provide default parameters for this setting. We therefore adapted the parameters provided for MUTAG and performed a grid search over the number of training epochs (20, 30, 50) and hidden dimensions (32, 64, 128, 256) to better utilize the large pre-training dataset.\n\nThe regression results are summarized below:\n\n| **Model** | **QM9** | **QM40** | **ESOL** | **LIPO** | **FreeSolv** |\n|----------|---------|----------|----------|----------|--------------|\n| **GraphMAE** (MAE ↓) | 0.222 ± 0.016 | 0.247 ± 0.036 | 0.291 ± 0.012 |  0.527 ± 0.029  |  0.378 ± 0.028  |\n| **GRALE**  (MAE ↓)    | 0.015 ± 0.001 | 0.018 ± 0.003 | 0.274 ± 0.014 | 0.511 ± 0.022 | 0.272 ± 0.017 |\n\nAnd the classification benchmarks:\n\n| **Model** | **BBBP** | **BACE** |\n|----------|----------|----------|\n| **GraphMAE** (ROC AUC ↑) | 0.773 ± 0.036 | 0.857 ± 0.039 |\n| **GRALE** (ROC AUC ↑)    | 0.731 ± 0.025 | 0.821 ± 0.051 \n\nOverall, we find that while GraphMAE is a strong baseline, GRALE outperforms it on 5 out of 7 tasks.\n\nRegarding Transformer-based architectures, we agree they are valid encoder options. Our only claim is that attention-based architectures are more adapted to GRALE than classical GNNs — a hypothesis we test in the ablations. While many alternatives exist, benchmarking all of them is outside our scope. We will include this discussion in the final version and reference works that investigate this space more thoroughly.\n\n> The paper claims that the graph size is predicted via the padding mask vector, yet the decoding process is not clearly explained. How does the model ensure the correct number of nodes is generated without explicit supervision on graph size?\n\nWe concede that this may be unclear. We will clarify it in the paper. The key lies in the first term of the training loss (Equation 2):\n\n$$\n\\mathcal{L}\\_{OT}(h,\\hat{h},T) = \\sum\\_{i,j} \\ell_h(h_i,\\hat{h}_j)T\\_{i,j}\n$$\n\nFor the sake of simplicity let's assume that the matching is the identity $T = I_n$, in that case\n\n$$\n\\mathcal{L}\\_{OT}(h,\\hat{h},I_n) = \\sum_{i} \\ell_h(h_i,\\hat{h}_i)\n$$\n\nHere, $\\hat{h}$ is the predicted mask, and $h$ is the ground truth. This loss is zero only when $h = \\hat{h}$ (up to permutation $T$). \nSince the size of the graph is encoded in $h$ ($\\text{size} = \\sum_i h_i$) this means that we explicitly train the model to predict the correct size. Note that we use binary cross-entropy as $\\ell_h$, so $\\hat{h}_i$ prediction becomes a binary classification (is node $i$ active or not). Hence the decoding step is a simple treshold:\n\n$$\nh_i \\leftarrow 1[h_i > 0.5]\n$$\n\n> Lacks ablation against standard Transformer decoders. How critical is the Evoformer Decoder to performance, and what unique capabilities does it provide?\n\nWe did include an ablation with a standard Transformer decoder (Table 2, line 4), which increases the edit distance by a factor of 7. This highlights the importance of Evoformer in our model.\n\nNote that by construction the standard Transformer Decoder can only process a feature matrix $X \\in R^{N \\times d}$, therefore we had to add a MLP head to output an adjacency matrix $A_{i,j} = MLP(X_i + X_j)$. In constrast, the proposed Evoformer Decoder is (to the best of our knowledge) the first attention module that can directly reconstruct a graph (feature and adjacency matrix) from a latent space. \n\n> The method incurs relatively high computational overhead, primarily due to the use of Evoformer modules and Sinkhorn-based matching, which limits scalability to larger graphs.\n\nFirst of all we agree that the $\\mathcal{O}(N^3)$ scaling is a limitation. There are also two aspects that we would like to highlight:\n\n1. **Potential for Optimization**: We believe that a $\\mathcal{O}(N^2)$ version of GRALE is feasible. This is straightforward for the architecture (see Appendix E), but the main bottleneck is the loss itself. Even assuming an oracle matcher (Proposition 1), the loss remains $\\mathcal{O}(N^3)$. Therefore, we think that the key for reaching $\\mathcal{O}(N^2)$ would be to use approximation of the loss, for instance low-rank approximation [2]. This would decrease the reconstruction quality but might still results in a rich latent space. \n\n2. **Practical Scalability**: We want to clarify that $N=32$ is not a hard limit. Below, we provide the time/memory cost of running one gradient step (with a batch size of 1) using a RTX 3500 Ada (12GB of memory).  For $N = 128$, the memory use is 3GB. This means that 8×L40 GPUs (48GB each) could handle a batch size of 128 — a realistic setting. The model used here matches the one used for PUBCHEM.\n\n| **N**  | **8** | **16** | **32** | **64** | **128** | **256** |\n|--------|------|-------|-------|-------|--------|--------|\n| Step Time (s) | 0.01 | 0.01  | 0.02  | 0.02  | 0.03   | 0.07   |\n| GPU Memory (GB) | 0.2  | 0.3   | 0.4   | 0.8   | 3.0    | 10.7   |\n\nThis supports our claim that larger graphs are feasible — similar to how AlphaFold managed long protein sequences despite similar complexity.\n\n---\n\n**References**\n\n[1] Zhang, M., Jiang, S., Cui, Z., Garnett, R., & Chen, Y. (2019). D-VAE: A variational autoencoder for directed acyclic graphs. *NeurIPS*.\n\n[2] Scetbon, M., Peyré, G., & Cuturi, M. (2022). Linear-time Gromov Wasserstein distances using low rank couplings and costs. *ICML*."}, {"review_id": "AGMsncE38B", "reviewer": "Reviewer_fwJt", "summary": "The paper proposes a graph autoencoder that works at the graph level (ideally without directly using node embeddings, although in practice this is not entirely true). The main idea is to avoid the expensive matching step between the input graph (of the encoder) and the output graph (from the decoder) by using a loss inspired by Optimal Transport. Instead of computing a permutation matrix, the method computes a transport matrix. Since this operation can also be complex, the model includes a module that learns to predict the matrix. The whole system is trained end-to-end.", "questions": "- How much of the performance depends on the preprocessing stage? This aspect is not clearly discussed and might deserve more attention\n- It’s not clear to me how the maximum number of nodes is fixed.\n\nFor other questions, please see above.", "limitations": "-", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "*Strengths*\n- The paper is well structured and easy to follow; the transition between (almost all) sections is smooth and helps the reader follow the flow of ideas.\n- The choice of using different schemes to build the input and target graphs is interesting, as well as highlighting that breaking the symmetry between input and output can improve learning.\n- The entire system, including the prediction of the graph matching, is trained end-to-end, which makes the approach elegant and potentially efficient.\n\n*Weaknesses*\n\n- The paper claims to produce a graph-level embedding, but in reality, it also produces node embeddings.\n- The paper states that it produces a graph-level embedding Z, but in practice, it is a representation composed of K tokens. This is an important point, but it is only briefly discussed. What does it mean that these tokens represent abstract \"concepts\"?\n- Figure 2 could be very helpful, but in its current form, it is hard to read. In particular, it is unclear where X comes from, what the \"linear\" block actually does, and what the K \\times D input to the transformer decoder represents (or maybe I missed some parts). The best solution would be to expand the figure caption to clearly describe the architecture, including a proper explanation of notations such as n_F, n_C, etc.\n- The readability of Figure 3 could be improved, for instance, by adding the labels K and D.\n- Figure 4 does not provide much insight. It would be more informative to include a comparison with existing methods (e.g., PIGVAE) to better assess the qualitative performance of GRALE.\n- Unless I missed it, there seems to be no table reporting training time comparisons with other methods. \n- While the paper emphasizes the importance of the proposed matching-free loss, the ablation results in Table 2 suggest that its contribution to reconstruction quality is relatively limited compared to other architectural components such as the encoder, matcher, or featurizer. This raises a question: could this be considered a discrepancy? In other words, are the empirical differences between the proposed loss and previous alternatives negligible in practice? Apart from the observation that GRALE shows reduced standard deviation (suggesting more stable training), the actual impact of the loss function seems limited, and it is not entirely clear how the authors interpret this result.\n- Complex graph operations in the latent space are presented as an ambitious aspect of the paper, but they are only briefly introduced. Graph interpolation in latent space is not a novel idea; actually, it is well established in the graph generative modeling community. Its effectiveness depends on how well-structured the latent space is (ie embeddings must reflect meaningful semantics, where similar graphs correspond to nearby vectors), otherwise, interpolations may lead to invalid or meaningless graphs. In this work, the discussion remains theoretical, making this part of the contribution speculative.", "was_revised": true, "final_justification": "After considering the rebuttal, I maintain my positive assessment of the paper. The authors provided clear answers to most of my questions, such as clarifying the relationship between graph-level and node-level embeddings, explaining the K-token representation in more detail, and adding the missing training time comparison. My positive recommendation is supported by 1) an elegant end-to-end approach, 2) valuable clarifications in the rebuttal, and 3) competitive results, even though there is still room for improvement.", "rebuttal": "Thank you for your positive and in-depth review. In particular, we really appreciate the feedback on the figures; we will update them accordingly. We address your other questions below:\n\n> The paper claims to produce a graph-level embedding, but in reality, it also produces node embeddings.\n\nThat’s true, and it’s an aspect of the paper that deserves more discussion.\n\nUltimately, we obtain both a graph-level embedding that is permutation invariant, and a set of node-level embeddings that are permutation equivariant. However, it’s very important to emphasize that **all the information required to reconstruct the graph is stored in the graph-level embedding**. The node embeddings are only passed to the matcher, which outputs a permutation matrix used solely for loss computation. Thus, the model cannot “cheat” by encoding structure in the node embeddings — the graph-level embedding acts as a true bottleneck, as in a standard autoencoder.\n\nFrom a more abstract perspective, this means that our model naturally disentangles the permutation-invariant part of the input (stored in the graph-level embedding) from the arbitrary node ordering (stored in the node-level embeddings). We recently noticed a connection with similar strategies for disentangling other invariances, such as rotation symmetry [2]. We will add this discussion to the final version of the paper.\n\nOverall, we believe this is a strength rather than a weakness. In particular, the node-level embeddings prove useful for downstream tasks, as demonstrated in the graph matching experiment (see Table 5, that was further improved via fine-tuning thanks to Reviewer LtMM’s suggestion).\n\n> The paper states that it produces a graph-level embedding Z, but in practice, it is a representation composed of K tokens. This is an important point, but it is only briefly discussed. What does it mean that these tokens represent abstract \"concepts\"?\n\nThat's a fair point — the word “concepts” is too strong and implies a level of interpretability we do not yet justify. We will remove this term in the final version.\n\nWhat we can say without additional experiments is that (1) these tokens encode higher-order properties of the graph, as they result from cross-attention over all node-level embeddings, and (2) this token-based representation is empirically effective, as shown in Figure 3. As for why this works well, our hypothesis (mentioned in line 231) is that it aligns better with attention-based architectures — though more subtle mechanisms may be at play. A deeper analysis is out of scope for this paper.\n\n> Figure 4 does not provide much insight. It would be more informative to include a comparison with existing methods (e.g., PIGVAE) to better assess the qualitative performance of GRALE.\n\nFollowing your remark and a similar one from Reviewer XSRE, we realized that this figure is less informative than we initially thought. We are considering moving it to the appendix and adding a new plot (as you suggested) to enable a more meaningful qualitative comparison.\n\n> Unless I missed it, there seems to be no table reporting training time comparisons with other methods.\n\nYou're right — this table was missing. We provide it below and will include it in the final version. To ensure a fair comparison, all methods were implemented with the same architecture (e.g., using Evoformer as the encoder). This improves accuracy comparability, though some methods like GVAE could potentially be made more time efficient with a simpler architecture at the cost of reduced performance.\n\n| Model    | Training Time (COLORING) | Training Time (PUBCHEM 16) | Training Time (PUBCHEM 32) | Loss Complexity      |\n|----------|---------------------------|------------------------------|------------------------------|------------------------|\n| GVAE     | 8h                        | 18h                          | 90h                          | $\\mathcal{O}(N^2)$     |\n| GraphVAE | 40h                       | 80h                          | N.A.                         | $\\mathcal{O}(N^4)$     |\n| PIGVAE   | 8h                        | 18h                          | 95h                          | $\\mathcal{O}(N^3)$     |\n| GRALE    | 8h                        | 20h                          | 100h                         | $\\mathcal{O}(N^3)$     |\n\nGiven the same architecture and hardware (as reported in table 9), most methods have comparable training costs. The exception is GraphVAE, whose $\\mathcal{O}(N^4)$ loss introduces significant overhead.\n\n> While the paper emphasizes the importance of the proposed matching-free loss, the ablation results in Table 2 suggest that its contribution to reconstruction quality is relatively limited compared to other architectural components.\n\nThank you for pointing that out. In the current version (Appendix E), we compare our proposed loss to a strong baseline — the PIGVAE loss — which includes an additional regularization term, and for which we performed a grid search to optimize its weight. Despite this, our loss (without additional parameters) slightly outperforms it on average, which we consider a significant result.\n\nMoreover, as you noted, the lower standard deviation suggests greater training stability. Empirically, we observed that $\\mathcal{L}_\\text{PIGVAE}$ often gets stuck in local minima. This aligns with Proposition 4: the PIGVAE loss is highly sensitive to the balance between the reconstruction and regularization terms. Our proposed loss bypasses this issue entirely.\n\n> How much of the performance depends on the preprocessing stage? This aspect is not clearly discussed and might deserve more attention.\n\nWe use very simple preprocessing. In particular, for molecular data, we do not incorporate domain-specific knowledge — though doing so would likely improve performance. As detailed in Appendix C.1, our preprocessing simply involves adding higher-order interactions to the graph features and edges (via powers of the adjacency matrix and feature diffusion). \n\nThis strategy was tested in the ablation studies and showed a non-negligible impact (see the second line of Table 2). We concede that this is not clearly presented without consulting the appendix, and we will improve this in the final version.\n\n> It’s not clear to me how the maximum number of nodes is fixed.\n\nThanks for pointing this out — we forgot to include this simple detail. We set the model's maximum graph size to match the largest graph in the dataset. In principle, this could be set higher (i.e., overparameterized), but we chose not to explore that due to the associated computational costs.\n\n---\n\n### References\n\n[1] Zhang, M., Jiang, S., Cui, Z., Garnett, R., & Chen, Y. (2019). D-VAE: A variational autoencoder for directed acyclic graphs. *NeurIPS*.\n\n[2] Katzir, O., Lischinski, D., & Cohen-Or, D. (2022). Shape-pose disentanglement using SE(3)-equivariant vector neurons. *ECCV*."}, {"review_id": "tt2ieu0Uzg", "reviewer": "Reviewer_XSRE", "summary": "A fully differentiable graph autoencoder is introduced, including a suggestion of how to make node matching differentiable.", "questions": "Figure 4 seems cherry picked to me. All three properties scale with the graph size, as molecular weight and solubility are correlated, and also u0 as an extensive quantity is highly dependent on the graph size. It is not surprising that the embedding also scales with the graph size, as the decoder hast to reconstruct the mask, i.e. number of nodes from the latent embedding. How do these plots look like if you visualize intensive quantities, that are independent of the graph size (e.g. HOMO/LUMO energies or other intensive quantities in QM9). Showing plots of all QM9 properties in the appendix would be benefitial to support the claims in Section 5.2 or also to limit the applicability of those claims.\n\nThe same is true for Table 3 and Table 4(QM9): Which task was performed (there are many labels in QM9) for property prediction and graph prediction?\n\nWhat is the computational cost of training the model compared to previous models used in the benchmark? Please add that information to the paper. Please also discuss if the training scales cubic or even more than cubic with the typical graph size in the datasets (single forward/backward pass scales probably cubic, but if more data and/or more epochs are needed for training on larger graphs, one might expect above-cubic scaling).", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 3, "strengths_and_weaknesses": "The paper is very clearly and well written.\nIt presents one of the first solutions to a long-standing problem.\nThe results are very good and convincing.\nEven though there is related work (PIGVAE), the authors clearly discuss differences and show significant empirical advantages.\nThe approach is original and combines multiple known as well as new aspects in an interesting way.\nThe approach presented establishes a significant step forward in self-supervised graph representation learning.\nThe computational cost associated to the cubic scaling might become a bottleneck and should be discussed more openly in the paper.", "was_revised": true, "final_justification": "The paper is an important step in the direction of having graph autoencoders with graph neural networks also on the decoder side, rather than decoders that generate other graph representations in an indirect way. The method presented here is sufficiently different from other recent publications, and the approach is interesting, even though it has some disadvantages, such as the scaling in graph size. The questions were sufficiently addressed in the rebuttal.", "rebuttal": "Thank you very much for your review. In particular, the insights you provided about chemistry were really helpful. Below, we directly address the points you raised:\n\n> Figure 4 seems cherry-picked to me. All three properties scale with the graph size, as molecular weight and solubility are correlated, and also u0 as an extensive quantity is highly dependent on the graph size. It is not surprising that the embedding also scales with the graph size, as the decoder has to reconstruct the mask, i.e., number of nodes, from the latent embedding. How do these plots look like if you visualize intensive quantities that are independent of the graph size (e.g., HOMO/LUMO energies or other intensive quantities in QM9)? Showing plots of all QM9 properties in the appendix would be beneficial...\n\nWe agree that it is not surprising to observe graph size in the latent space, since one of the objectives of the model is to reconstruct graphs of varying sizes. This was more of a sanity check than a key result. That said, we still find it interesting that this appears so clearly — and linearly — in the first two PCA components.\n\nHowever, we were unaware that u0 and solubility were strongly correlated with the number of atoms. Thank you for pointing this out. For context, we selected u0 because it was commonly used as a regression benchmark on the QM9 dataset (out of the 17 targets, it was the only one tracked on the PapersWithCode leaderboard at that time). We selected solubility because it could be computed using RDKit and seemed like a chemically meaningful target for otherwise unsupervised PUBCHEM dataset.\n\nFollowing your suggestion, we applied the same visualization technique to intensive properties like HOMO/LUMO energies. These required additional tuning of the t-SNE parameters to obtain meaningful 2D visualizations.\n\nThanks to your comment, we now recognize that this figure is less informative than we originally thought. We are considering moving it to the appendix, along with the new HOMO/LUMO plots, and will include a more detailed discussion.\n\n> The same is true for Table 3 and Table 4 (QM9): Which task was performed (there are many labels in QM9) for property prediction and graph prediction?\n\nYou're absolutely right — this information was missing. We will add it to Table 7. Here is the missing column:\n\n| Dataset | Target |\n|---------|--------|\n| QM9     | internal energy (u0) |\n| QM40    | internal energy (u0) |\n| ESOL    | water solubility |\n| LIPO    | octanol/water distribution coefficient |\n| FREESOLV | hydration free energy of small molecules |\n| BBBP    | binary labels for blood-brain barrier permeability |\n| BACE    | IC50 (bioactivity classification) |\n\nNote that for all datasets we used the regression/classification targets defined in the MoleculeNet benchmark [1]. The only exception is QM9 and QM40, where we reported u0 for the reasons mentioned above.\n\nAs for Table 4, it corresponds to a different type of task: **supervised graph prediction**. Here, the goal is to predict an entire graph given some input $x$. In particular, we reproduced the benchmark from the Any2Graph paper, which includes, for instance, reconstructing molecular graphs from their Morgan radius-2 fingerprints ($x$ is the fingerprint). In this table, the \"QM9\" column refers to such tasks.\n\n> What is the computational cost of training the model compared to previous models used in the benchmark? Please add that information to the paper.\n\nThis was also noted by reviewer ‘fwJt’, this information is missing. We will add the following comparison. To ensure fairness, we implemented all models using the same architecture (e.g., Evoformer as encoder). This ensures fair accuracy comparison, though simpler architectures could make some models more time efficient (e.g., GVAE) at the cost of reduced performance.\n\n| Model    | Training Time (COLORING) | Training Time (PUBCHEM 16) | Training Time (PUBCHEM 32) | Loss Complexity      |\n|----------|---------------------------|------------------------------|------------------------------|------------------------|\n| GVAE     | 8h                        | 18h                          | 90h                          | $\\mathcal{O}(N^2)$     |\n| GraphVAE | 40h                       | 80h                          | N.A.                         | $\\mathcal{O}(N^4)$     |\n| PIGVAE   | 8h                        | 18h                          | 95h                          | $\\mathcal{O}(N^3)$     |\n| GRALE    | 8h                        | 20h                          | 100h                         | $\\mathcal{O}(N^3)$     |\n\nGiven the same architecture and hardware (as reported in table 9), most methods have comparable training costs. The exception is GraphVAE whose $\\mathcal{O}(N^4)$ loss introduces significant overhead.\n\n> Please also discuss if the training scales cubic or even more than cubic with the typical graph size in the datasets (a single forward/backward pass scales probably cubic, but if more data and/or more epochs are needed, one might expect above-cubic scaling).\n\nThis is a great point, and we will include this discussion. As discussed with Reviewer LtMM, while our current implementation is $\\mathcal{O}(N^3)$, it would be relatively easy to design an architecture with $\\mathcal{O}(N^2)$ complexity (see baselines in Appendix E). However, the true bottleneck is the loss, which remains $\\mathcal{O}(N^3)$ even assuming an oracle matcher (Proposition 1). To reduce this, approximating the loss (e.g., via low-rank approximations [2]) would be a promising direction. This could reduce reconstruction quality but might still result in a rich latent space.\n\nAs for **total training time**, you raise an interesting point. When moving from PUBCHEM 16 to PUBCHEM 32, we needed to double the number of gradient steps to reach convergence. It’s hard to determine whether this is due to the increased graph size or the larger dataset size (PUBCHEM 32 is six times larger, to be exact). Disentangling these effects would require careful and large-scale experiments, which are beyond the scope of this paper — but this is definitely worth exploring further, and we will add it to the discussion section.\n\n---\n\n### References\n\n[1] Wu, Z., Ramsundar, B., Feinberg, E. N., Gomes, J., Geniesse, C., Pappu, A. S., ... & Pande, V. (2018). MoleculeNet: A benchmark for molecular machine learning. *Chemical Science*, 9(2), 513–530.\n\n[2] Scetbon, M., Peyré, G., & Cuturi, M. (2022). Linear-time Gromov-Wasserstein distances using low-rank couplings and costs. *PMLR*."}, {"review_id": "1vFc86afJj", "reviewer": "Reviewer_s35a", "summary": "This work proposes GRALE, a graph auto-encoder (GAE) to generate representations for graph structure and node features. Graphs with varying sizes can be encoded/decoded by padding. The graph representation can be well conducted on various downstream tasks.", "questions": "This work proposes a graph autoencoder to generate both graph and node level embeddings for graphs with different sizes; using padding to align with the max size of  graphs. This work provides a detailed block design for the entire encoder/decoder framework and clear flow of evaluation. Generally I appreciate the technical contribution and completeness of the GRALE in this work. To save authors’ time, I may directly express my confusions and questions on GRALE:\n\n1. The introduction of GRALE is not easy to follow for readers not focusing on the GAE area. Many concepts are not well explained and it takes me some time to understand them by reviewing the appendix and papers referred.\n\n1.1 In the Introduction, authors claimed GAE like Graph U-Net take advantage of the ground-truth information, including the graph size, in the decoding phase. Could you give more explanation on it? Why is this not a good choice in practice? For example in Graph U-Net, the graph size/structure is utilized the information to conduct the pooling/global-pooling function, and finally we get the graph embedding for downstream tasks. It seems to me a similar approach as GRALE where “pooling” is utilized in GRALE’s decoder. Please further justify that Graph U-Net-like structures are not an appropriate one in your scenario.\n\n1.2 Regarding the padding, “N is a maximum graph size; all graphs are padded to this size.” May I ask if the padding strategy (for example where the zeros should be padded, evenly on  two sides of the graph, $[…]+n+[…]\\to N$, or simply just after the graph $n+[…]\\to N$.) Will the padding detail influence the model performance?\n\n1.3 In Sec. 3.4, the Matcher $m$ is introduced to calculate and projected into a differentiable manner for the GRALE loss later. I understand the intension of this module, but have no idea of the mechanism it uses. Might be clearer to explicitly show the expression (or quick illustration) for readers like me without knowledge of it. Also, In Sec. 4.3, authors mention that most GAE works treat matching as a regression problem, but in GRALE, the matcher is trained without groundtruth but minimizing the cost. To my understanding, is this also a regression problem? I mean the $\\hat{T}=SINKHORN(K)$ seems still a regression because $K$ comes from the affinity between $X$ and $\\hat{X}$, where $X$ is the processed “ground-truth”.\n\n2. The evaluation is comprehensively conducted, but some concerns from my current understanding.\n\n2.1 In Table 1, the GRALE outperforms other methods a lot, which is quite impressive. Besides the results, can you give some interpretation on why GRALE can have this good performance? \n\n2.2 Quickly following, also in the main body of this manuscript, it’s much better to include more analysis and justification on the design of modules. For example in each module introduction, could you talk about why you need these operations? Why your choice is or should be the optimal one? Simply stating these might not be convincing enough.\n\n2.3 In Sec.5.2, great qualitative evlauations! But could you provide more analysis and explanation on the results; those would be more instructive to followed researchers.\n\n3. The limitation of the GRALE is on the max graph size. I think this stems from the large model size, as well the training effort, of the proposed GRALE? Is there some intuitive or thinking-loudly strategy could mitigate this issue? \n\n**Minor comments:**\n\ni. “This module first extract from data” -> “extracts” \n\nii. “Remplaced” in Table 2 -> “Replaced”\n\niii. In Figure 11, the reconstruction failure on symmetric structure seems similar to the issue mentioned in [1]. It is interesting. If possible, could you share more opinion on this? I found your manuscript (using random noise) and this paper (using two branches to generate two different embedding) seem address the same issue in two ways. \n\niv. The proposed new decoder in GRALE seems a good contribution. Authors might consider moving it to the main body and provide more interpretation on it.\n\n[1] Duan, Shijin, et al. \"GraphCroc: Cross-Correlation Autoencoder for Graph Structural Reconstruction.\" Advances in Neural Information Processing Systems 37 (2024): 45409-45437.", "limitations": "Please see the questions.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\n1. Completeness: The work clearly defines the problem and outlines the modules in GRALE.\n\n2. Technical depth: The work provides a detailed design for the entire framework.\n\n**Weaknesses**\n\n1. Writing/Clarity: The paper does not adequately justify or clarify some content, making it difficult to follow.\n\n2. Novelty: While the framework design is comprehensive, its novelty should be further highlighted.", "was_revised": true, "final_justification": "This work proposes a graph autoencoder to generate both graph and node level embeddings for graphs with different sizes; using padding to align with the max size of  graphs. In the rebuttal, the authors clearly answered the questions that I raised, also with proper references. I have no further questions. I believe with the clarification, the revision will be more fluent for readers to understand their design philosophy and module detail. Thus I increase my rating to \"accept\", and hope it can have valuable contribution to the graph learning community.", "rebuttal": "Thank you for your feedback. You highlighted several aspects of the paper that need to be clarified. We provide the requested explanations below and will include these additional details in the final version of the paper, using the extra page available.\n\n> - Please further justify that Graph U-Net-like structures are not an appropriate one in your scenario\n\nFormally, Graph U-Net-like architectures are written as follows:\n\n$$\ng(G) = Z, I \\tag{U-Net Encoder}\n$$\n\nwhere $G$ is the input graph, $Z$ is the latent representation (permutation invariant), and $I$ contains additional information (not permutation invariant), such as the list of nodes removed at each layer. The associated decoder is:\n\n$$\nf(Z, I) = G' \\tag{U-Net Decoder}\n$$\n\nThat is, the decoder uses both the latent representation and the additional information to reconstruct the graph $G'$.\n\nThis structure implies that certain key properties of the graph, such as the number of nodes, are not encoded in the latent space but instead stored in $I$. As a result, the decoder cannot reconstruct a graph from an arbitrary point $Z$ in latent space without access to $I$. This limitation makes many of GRALE's intended applications infeasible (e.g., interpolation or sampling in latent space). We will make this point clearer in the final version of the paper.\n\n> - Will the padding order influence the model performance?\n\nNo, it won't. Thank you for the question—this is an important feature of GRALE. Because our loss is permutation invariant, any reordering of the input graph (including padded nodes) has no effect on the output. In particular, whether padded nodes appear at the beginning, the end, or in random positions has no impact on (a) the latent representation, or (b) the final loss.\n\n> - In Sec. 3.4, the Matcher $m$ is introduced to calculate and projected into a differentiable manner for the GRALE loss later. I understand the intension of this module, but have no idea of the mechanism it uses. Might be clearer to explicitly show the expression (or quick illustration) for readers like me without knowledge of it. Also, In Sec. 4.3, authors mention that most GAE works treat matching as a regression problem, but in GRALE, the matcher is trained without groundtruth but minimizing the cost. To my understanding, is this also a regression problem? I mean the $\\hat{T} = \\text{SINKHORN}(K)$ seems still a regression because comes from the affinity between $X$ and $\\hat{X}$, where is the processed “ground-truth”.\n\nThank you—this is an important comment. Indeed, several clarifications were missing.\n\nThe core intuition is as follows: **graph matching between $G$ and $\\hat{G}$ is hard, but we aim to learn node embeddings ($X$ and $\\hat{X}$) such that the optimal matching between the embeddings (which is easier to compute) approximates the matching between the original graphs.**\n\nWith this goal in mind, we use tools from Optimal Transport (see [1] for a detailed introduction).\n\nThe optimal matching between two sets of nodes (no edges) can be written as:\n\n$$\n\\hat{P} = \\arg\\min_{P \\in \\pi_N} \\sum_{i,j} P_{i,j} \\, d(X_i,\\hat{X}_j) \\tag{OT}\n$$\n\nwhere $d$ is a distance between node embeddings. However, this solution is non-differentiable with respect to $X$ and $\\hat{X}$, which prevents backpropagation.\n\nTo address this, we use the entropic regularization of the problem:\n\n$$\n\\hat{T} = \\arg\\min_{T \\in \\pi_N} \\sum_{i,j} T_{i,j} \\, d(X_i,\\hat{X}_j) + \\epsilon H(T) \\tag{Sinkhorn}\n$$\n\nwhere $H(T)$ is the negative entropy of $T$. This formulation is differentiable and thus suitable for end-to-end training [2].\n\nMoreover, the solution $\\hat{T}$ can be computed as:\n\n$$\n\\hat{T} = \\texttt{BREGMAN}(K)\n$$\n\nwhere $K_{i,j} = \\exp\\left(-\\frac{d(X_i,\\hat{X}_j)}{\\epsilon}\\right)$, and $\\texttt{BREGMAN}$ is the Bregman algorithm: it alternates row and column normalizations of $K$ until convergence. We use 100 iterations, making $\\texttt{BREGMAN}$ a differentiable module with respect to $X$ and $\\hat{X}$.\n\nRather than choosing a fixed distance $d$ and regularization coefficient $\\epsilon$, we let the model learn both via two MLPs:\n\n$$\n\\frac{d(X_i, X_j)}{\\epsilon}=\\left\\|  \\texttt{MLP}\\_\\text{in}(X_i) - \\texttt{MLP}\\_\\text{out}(X_j)\\right|\n$$\n\nFinally, let us clarify the claim that we train \"without ground truth\". Recall that the goal of the matcher is to approximate the optimal matching between $G$ and $G'$:\n\n\\begin{equation}\n    T^* = \\text{arg}\\,\\min\\limits_{T \\in \\pi_N} \\mathcal{L}_{OT}(G, G',T)\n\\end{equation}\n\nA supervised regression based approach would train following a supervised loss such as $||\\hat{T} - T^* ||_2$, but this approach requires to compute the target $T^*$ which is NP-hard. instead we propose to directly minimize \n\n\\begin{equation}\n     \\mathcal{L}_{OT}(G, G',\\hat{T})\n\\end{equation}\n\nThis makes sense because $\\mathcal{L}\\_{OT}(G, G',\\hat{T}) \\geq \\mathcal{L}\\_{OT}(G, G',T^*)$ and thus we indirectly minimize the otherwise untrackable loss.\n\nWe hope that this extra set of information clarify the proposed matcher. We fully agree that these informations should be provided in the main body of the paper and will use the additionnal page for this. Thank you again for raising this point.\n\n> - In Table 1, the GRALE outperforms other methods a lot, which is quite impressive. Besides the results, can you give some interpretation on why GRALE can have this good performance\n\nWe believe that the success of GRALE is ultimately a combination of factors. Our ablation studies show that each module contributes significantly to performance, making it difficult to isolate a single dominant factor. On a higher level, we think that the true explanation for this success is the strategy that we followed to design GRALE (see next answer). \n\n> - 2.2 Quickly following, also in the main body of this manuscript, it’s much better to include more analysis and justification on the design of modules. For example in each module introduction, could you talk about why you need these operations? Why your choice is or should be the optimal one? Simply stating these might not be convincing enough.\n\nWe fully agree with this. We think that the reader might benefit from more insights into GRALE's conception. We will add this discussion to the final version of the paper.\n\nBroadly, our design followed a two-step process: (1) we defined a “wish-list” of desired properties for each component (see Section 2.1), and (2) we surveyed the literature to find or adapt modules that meet these requirements. For example, Evoformer was a perfect fit for our encoder: it is graph-attention-based, scalable to large datasets, and permutation equivariant. A more complex case was that of the loss: the losses proposed in PIGVAE and Any2Graph were very close to our aim but were still missing a few components so we adapted them. No suitable decoder existed, so we proposed a new one inspired by both the Evoformer encoder and Transformer decoder—hence the name “Evoformer Decoder.”. \n\nBeyond the wordplay, this is why we called our work \"The Quest for the Graph AutoEncoder\". \n\n> - 2.2 Quickly following, also in the main body of this manuscript, it’s much better to include more analysis and justification on the design of modules. For example in each module introduction, could you talk about why you need these operations? Why your choice is or should be the optimal one? Simply stating these might not be convincing enough.\n\nWe fully agree. In the final version, we will include more discussion and justification for each module, as illustrated in the reply above.\n\n> - The proposed new decoder in GRALE seems a good contribution. Authors might consider moving it to the main body and provide more interpretation on it.\n\nThank you for this very positive feedback. This is our belief as well. We think that the clarifications that you suggested are also very important, but if we have some room left we will definitely move it to the main body of the paper. Note that as suggested by the other reviewers Figure 4 might go the appendices. With the additionnal page of the final version, we think we have the room for everything.  \n\n**References**\n\n[1] Peyré, G., & Cuturi, M. (2019). *Computational Optimal Transport: With Applications to Data Science*. Foundations and Trends® in Machine Learning, 11(5-6), 355–607.  \n[2] Genevay, A., Peyré, G., & Cuturi, M. (2018). *Learning generative models with Sinkhorn divergences*. In AISTATS, pp. 1608–1617."}]

Author rebuttal:

Meta-review: This paper proposes a novel graph-level autoencoder with an Evoformer-based encoder/decoder and differentiable matcher. Reviewers agree the method is technically solid, achieves strong results, and addresses concerns well in the rebuttal (including scalability, baselines, and clarity). The contributions are impactful and relevant to the community.
Decision: Accept (poster)