- Rating
- 1
- Confidence
- 4
- Informativeness
- 1
- Presentation
- 1
- Soundness
- 1
Read review
Paper summary
The paper proposes a graph-level autoencoder using explicit supervision of spectral coordinates. The authors claim that their method improves graph reconstruction compared to previous methods such as GRALE, since previous methods do not explicitly supervise node matching and graph reconstruction.
Critical strengths
Did not find any.
Critical weaknesses
The paper proposes a graph-level autoencoder using explicit supervision of spectral coordinates. The authors claim that their method improves graph reconstruction compared to previous methods such as GRALE, since previous methods do not explicitly supervise node matching and graph reconstruction. However, I have serious concerns regarding the claims, methodology, and experiments.
-
The paper claims that GRALE's hidden representations are not directly supervised toward mathematically predefined node-level structural descriptors. However, GRALE already incorporates structural information into its node representations and jointly trains the encoder, decoder, and matcher through graph reconstruction loss. Therefore, the lack of explicit structural supervision does not necessarily mean that GRALE fails to learn meaningful structural information. To justify this claimed limitation and demonstrate the benefit of explicit structural descriptors, the authors should provide extensive ablation studies and controlled experiments showing that explicit supervision offers a clear advantage over the existing implicit structural learning approach.
-
Sign ambiguity in Laplacian eigenvectors can lead to incorrect node matching, even when two nodes have the same structural information. Equation (5) directly compares the coordinates without checking whether a sign flip makes them equivalent. Equation (7) introduces SignAlign, but it is applied to the reconstruction loss, not the matching cost.
-
Limited methodological novelty. The approach combines existing techniques and claims to design a new loss function. Also, this paper does not provide experimental ablation studies showing how the use of existing techniques improves performance or solves previous limitations. It remains unclear which component accounts for the reported improvements over GRALE. A slightly different loss function does not meet the standard of novelty.
-
- Using Hungarian matching to measure reconstruction accuracy is problematic (Appendix A.3). The main limitation of Hungarian matching is that it finds the best one-to-one assignment based on the given matching cost, not necessarily the best structural alignment between two graphs. Therefore, when the authors use this method in Equations (9) and (10), even if two graphs are isomorphic, an incorrect assignment can produce a nonzero graph edit distance.
-
The predicted spectral coordinates are not guaranteed to produce a valid graph Laplacian, since the method does not enforce Laplacian properties such as zero row sums and non-positive off-diagonal entries.
-
The evaluation focuses on three molecular reconstruction benchmarks with small graphs. There is insufficient evidence of robustness to graph symmetries, eigenvalue multiplicity, and node permutations.
-
The paper claims a quadratic encoder complexity advantage over the cubic-complexity GRALE when spectral truncation is used. However, the experimental configurations in Table 5 use , matching the respective maximum graph sizes. Therefore, the author uses the full spectrum, for which standard dense eigendecomposition has cubic computational complexity. Thus, the claimed advantage does not hold for these configurations.
Questions for authors
N/A.
4 comments
b) Sign ambiguity in Laplacian eigenvectors can lead to incorrect node matching, even when two nodes have the same structural information. Equation (5) directly compares the coordinates without checking whether a sign flip makes them equivalent. Equation (7) introduces SignAlign, but it is applied to the reconstruction loss, not the matching cost.
The reviewer is correct in observing that while GNNs guarantee permutation invariant, the eigendecomposition is not, i.e., node permutations can induce sign flips and random eigenbasis rotation in the computed eigenvectors. Our intention, however, was to allow the encoder to learn a stable representation wrt potential sign flips and bases rotations, while defining a matching strategy stable enough to not be impacted by a limited amount of sign flips and bases rotations. The robustness of the matcher stems from the observation that in general sign flips result in non-coherent signals for the matcher, while the coordinates with correct sign provide a coherent signal towards the correct match. For example, under the assumption of a 50% sign flip, half of the coordinates will effectively be noise, while the other will provide a useful signal towards finding the correct match. The signal is further reinforced by node feature information as well as information on the neighbourhood structure given by the probes (see Eq. 6 in the paper and Table 3 (overall response), which highlights the importance of the probe cost term).
Empirically, we observe that this robustness assumption holds true for PubChem16/32, as shown in Table 4 (overall response), where the performance on PubChem16/32 is not significantly impacted by random permutations of the test graphs (4th row), nor by random sign flips (2nd row) or a combination of this and random rotations (3rd row). Indeed, regardless of the perturbation the model still outperforms all the other approaches.
However, while performing these additional experiments, we have noticed that the same does not hold for QM9. We posit that this is due to the fact that in the training graphs of QM9 there is a consistent node ordering which provides a signal that our model is overfitting. We verify this hypothesis by re-training our model under different augmentation strategies and a new set of optimized hyper-parameters, i.e., (1) random node permutations, (2) random eigenvectors sign flips, and (3) random eigenvector sign flips + random orthogonal rotations of the eigenbasis in degenerate spaces. Table 5 (overall response) shows the results of this new experiment, highlighting that this simple training strategy allows our model to be robust wrt these perturbations.
In Table 8 (overall response) we perform an additional experiment where we measure the effect of introducing the sign correction in the matcher as well. This is achieved by alternating (a) the estimation of the permutation matrix P and (b) the estimation of the sign of the eigenvectors. The results show that this strategy has minimal impact on the reconstruction performance.
c) Limited methodological novelty. The approach combines existing techniques and claims to design a new loss function. Also, this paper does not provide experimental ablation studies showing how the use of existing techniques improves performance or solves previous limitations. It remains unclear which component accounts for the reported improvements over GRALE. A slightly different loss function does not meet the standard of novelty.
We would like to stress that the similarity with GRALE is largely confined to the use of a per-node representation which allows us to do unilateral node alignment (bipartite matching) instead of the bilateral alignment required by traditional graph matching. Our model is novel in several ways, not just the definition of a new loss term. As explained in response to previous comments, our architecture explicitly separates node, edge, and structural latent spaces by design. It also enables us in principle to use truncated spectral information, which in turn can potentially reduce the computational complexity at inference time. Also, the explicitly supervised spectral coordinates are part of the decoding path and provide a clearly defined structural target. The main distinction is that we reconstruct these coordinates from a structural latent and use them to guide both graph decoding and node matching, rather than relying solely on implicitly learned matching representations.
The new, extensive ablation experiments we have performed and reported in the “Overall response” shows the importance of the different architectural components of our model, particularly the spectral/structural supervision signal. We are indeed thankful to the reviewers for their comments, as a result of which we have performed a wide range of new experiments that we believe significantly strengthen the message of our paper.
d) Using Hungarian matching to measure reconstruction accuracy is problematic (Appendix A.3). The main limitation of Hungarian matching is that it finds the best one-to-one assignment based on the given matching cost, not necessarily the best structural alignment between two graphs. Therefore, when the authors use this method in Equations (9) and (10), even if two graphs are isomorphic, an incorrect assignment can produce a nonzero graph edit distance.
Note that we followed the same standard protocol used by GRALE. In general, computing the exact GED and GI Acc would be unfeasible for large graphs, which is why this approximation is used in practice. Specifically, we used the code provided by GRALE’s authors, i.e., class GraphAutoencoderMetric in https://github.com/KrzakalaPaul/GRALE/blob/main/GRALE/loss/objective.py. Note that using any sub-optimal match will only result in a reduction of the estimated GI Acc and an increase of the estimated GED, respectively. In other words, the matcher can be seen as providing a lower/upper bound for the GI Acc/GED results.
However, given the limited size of the graphs in QM9, we were able to compute the exact GED and GI Acc for these graphs, without relying on the model’s matcher and its predicted matching matrix. We used the VF2 algorithm to identify isomorphics graphs (GED=0) and NetworkX’s graph_edit_distance to measure the exact GED for the remaining graphs. Table 1 (overall response) shows that our method, when evaluated using the exact GED and GI Acc, still outperforms GRALE by a similar margin.
e) The predicted spectral coordinates are not guaranteed to produce a valid graph Laplacian, since the method does not enforce Laplacian properties such as zero row sums and non-positive off-diagonal entries.
The L_gram loss term (Eq. 7 in the paper) was indeed added to ensure that SS^T is the graph Laplacian (i.e., close to it in L1 sense). We observe that this loss term steadily decreases during training, while the ablation analysis of Table 2 (overall response) shows that this term does not appear to play an important role in the model’s performance. The latter can be explained by the fact that enforcing the reconstruction of the input eigenvectors is already a strong prior for the reconstruction of the input graph Laplacian.
f) The evaluation focuses on three molecular reconstruction benchmarks with small graphs. There is insufficient evidence of robustness to graph symmetries, eigenvalue multiplicity, and node permutations.
Note that we evaluated the reconstruction performance on the same datasets as GRALE, with the exception of COLORING, a synthetic dataset, which we swapped for the real-world dataset QM9, as in the former dataset the node features are largely unrelated to the graph structure. Note also that while GRALE performs a larger set of downstream task experiments, in all these experiments the autoencoder was still trained on PubChem32.
Table 6 (overall response) evaluates the robustness of our model wrt symmetries and eigenvalue multiplicity and compares it with that of GRALE. The results show that our model is indeed largely robust, particularly on the larger graphs of PubChem16 and PubChem32, where GRALE’s performance (especially on PubChem32) is negatively affected by the large number of symmetries and degenerate eigenspaces. We would also like to take this opportunity to stress that while we tried to replicate GRALE’s results (Table 1 of their paper) on PubChem16 and PubChem32 using their code and the recommended hyper-parameters configuration of both (a) their codebase and (b) their paper, the results we obtained were significantly lower (e.g., GED 0.277 and GI Acc 85.70% on PubChem16). In fairness to the authors of GRALE, we therefore reported their results (from Table 1 of GRALE’s paper) in our Table 1 (main paper). This in turn explains the discrepancy between the results of Table 1 (main paper) and the new ablation presented in Table 6 (overall response).
g) The paper claims a quadratic encoder complexity advantage over the cubic-complexity GRALE when spectral truncation is used. However, the experimental configurations in Table 5 use (K=9,16,32), matching the respective maximum graph sizes. Therefore, the author uses the full spectrum, for which standard dense eigendecomposition has cubic computational complexity. Thus, the claimed advantage does not hold for these configurations.
We would like to stress that the quadratic complexity of our model (with truncated spectrum) is not a main contribution of our work, as highlighted by the fact that this is only discussed briefly in the appendix. Also, note that the model configurations of Table 5 (appendix) refer to the models of Table 1 (main paper), which were trained using the full spectrum. We never claimed otherwise. However, we do have results using the truncated spectrum, i.e., Figure 3 (main paper), which shows the reconstruction performance on PubChem16 with truncated spectrum, and Tables 6 and 7 (appendix), which evaluate the performance of the encoder with truncated spectrum on downstream tasks.
a) The paper claims that GRALE's hidden representations are not directly supervised toward mathematically predefined node-level structural descriptors. However, GRALE already incorporates structural information into its node representations and jointly trains the encoder, decoder, and matcher through graph reconstruction loss. Therefore, the lack of explicit structural supervision does not necessarily mean that GRALE fails to learn meaningful structural information. To justify this claimed limitation and demonstrate the benefit of explicit structural descriptors, the authors should provide extensive ablation studies and controlled experiments showing that explicit supervision offers a clear advantage over the existing implicit structural learning approach.
We agree that GRALE incorporates structural information into its node representations, as also already highlighted in the paper and indeed we do not claim that GRALE fails to learn meaningful structural information. However, in our case we explicitly structure the model to learn three separate latent spaces capturing node, edge, and structural information, each with a corresponding loss term. This in turn allows us to use only node/edge feature or structure information for downstream tasks (see Table 2 of the original paper) and to interpolate only on some latent spaces (see Table 3 and Figure 5 of the original paper). The unseparated latent space design of GRALE does not allow for this. This is indeed one of the novel contributions of our approach. We will revise the manuscript to clarify this point better.
To be specific, on page 2 we state that GRALE’s matching representations are “not directly supervised to encode fine-grained node-level descriptors with explicit structural meaning.” Again, this does not imply that GRALE cannot learn meaningful structural information through reconstruction. Our main difference is that we explicitly supervise mathematically defined spectral coordinates and use the predicted coordinates jointly for graph decoding and node matching.
Indeed, the paper was missing an ablation analysis to show the importance of this structural supervision signal, as well as the other loss terms. As shown in the Tables included in the “Overall Response”, we have now performed an extensive set of ablation studies to verify this as well as other aspects of our model. Table 2 (overall response) shows the result of the loss terms ablation. This indicates the importance of the spectral/structural signals: removing the spectral losses causes the GED to increase from 0.0444 to 0.4060 and the GI Acc to drop from 97.44 to 65.63 on PubChem16. All these new results will be included in the appendix of the revised manuscript.