- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper introduces GeoGAE, a graph-level autoencoder that represents each input graph as a cloud of Euclidean hyperballs. The ball centers and radii are optimized to reproduce the graph’s adjacency structure, then normalized and ordered into a sequence. A Transformer encoder compresses this sequence into a fixed-dimensional latent representation, and an autoregressive decoder reconstructs the balls and predicts when to stop. Edges are recovered using a geometric intersection rule. The paper also introduces node bundling and multi-layer teacher forcing, and evaluates reconstruction performance across seven datasets.
Critical strengths
- A coherent approach to graph-level reconstruction. The hyperball representation provides continuous reconstruction targets and a simple rule for recovering edges. Combined with the stopping mechanism, the framework can reconstruct variable-sized graphs from fixed-dimensional latent representations without an explicit graph-matching module.
- Meaningful empirical improvements across several datasets. The evaluation covers seven datasets and generally reports five-run results with standard deviations, while documenting exceptions. The improvements on datasets such as IMDB-BINARY and SYNTHETIC NEW are encouraging. The teacher-forcing and bundling ablations also provide useful insight into training stability and the trade-off between sequence length and reconstruction quality.
Critical weaknesses
- The incremental benefit and practical significance of the core representation are not yet sufficiently established. The main contribution appears to lie in combining a geometric graph representation, an ordering procedure, and a Transformer autoencoder. While the complete system performs well, the current ablations do not isolate the benefit of the hyperball representation from the backbone and training procedure. A comparison with a simpler representation or ordering under a comparable model and latent budget would be particularly informative. A fixed-radius variant could also help establish the value of variable radii. GraViti, which is discussed in the related work, is another relevant comparison that is currently missing. More broadly, graph editing and optimization motivate the approach, but the evidence primarily concerns reconstruction. A clearer demonstration of the practical benefit—through either a downstream application or a compelling accuracy–cost trade-off—would strengthen the significance of the contribution.
- The canonical-ordering claim is stronger than the current justification supports. Centering, SVD alignment, and sign normalization can address rigid-transform ambiguities for a nondegenerate ball layout. However, this does not establish that independently optimized layouts of the same graph are equivalent up to such transformations. Different valid layouts may therefore lead to different ordered sequences, even beyond highly symmetric graphs. I did not find a dedicated evaluation of node relabeling and initialization sensitivity through the full preprocessing pipeline. This matters because stable ordering is central to the proposed alternative to explicit node matching.
Questions for authors
- Could you help clarify how much of the improvement comes from the geometric representation itself? A controlled comparison using a similar autoencoder with a simpler ordering or a fixed-radius representation would be especially helpful. A comparison with GraViti, or an explanation of the differences that prevent a direct comparison, would also help position the contribution.
- How stable are the resulting representations and reconstruction results when the same input graph is randomly relabeled or the ball optimization is initialized differently? I am particularly interested in experiments that rerun the full geometric preprocessing after relabeling the original graph.
- Does the end-to-end runtime in Table 8 include per-graph hyperball optimization? A breakdown of preprocessing, encoding, and decoding costs, together with the graph sizes involved, would help assess the computational benefit of avoiding explicit matching.
We thank the reviewer for the thoughtful comments and for recognizing the strengths of the algorithm and evaluation methodology.
Q1 - Node ordering, fixed radius representation and GraViti
Node ordering. We replaced the geometry-based ordering with a fixed random ordering (sampled once per seed, all else unchanged). Test F1 [%], 5 seeds:
Reconstruction collapses on every dataset, confirming that a predictable ordering is what enables the model to learn a useful graph embedding.
Fixed radius. We compare embedding F1 [%] of variable-radius balls (var), fixed-radius balls (fix; edges reduce to a distance threshold on centers) and distance-preserving embeddings (MDE) across dimensions d:
Fixed radii suffice for small, low-degree molecules but fail on graphs with hubs: in low dimensions a fixed-radius hub cannot intersect many neighbors without those neighbors overlapping each other and creating false edges. Per-node radii let hubs grow while leaves stay small, giving near-lossless low-dimensional encodings.
GraViti. We discuss GraViti (Bresson et al., 2026) in Related Work. We did not use it as a baseline because at submission time it was neither peer-reviewed nor accompanied by official code.
Q2 - Robustness to embedding re-randomization
A model trained with embeddings from the global seed is evaluated on test sets whose embeddings are recomputed with other seeds (3 training seeds × 5 embedding seeds):
Although most graphs change ordering, the resulting F1 std is below the training-seed std on all datasets, and even the max − min swing is at most comparable to it.
Q3 - Preprocessing cost and complexity
Appendix Table 8 reports training time only; embeddings are precomputed once per dataset. Preprocessing cost:
† Extrapolated from a random 5% sample. All embeddings reach 100% sphere F1.
Complexity (N nodes, K optimization steps): embedding O(K·N²) (all pairwise distances per step); encoding O(N²); autoregressive decoding with KV cache O(N²). In practice K is reduced by early stopping.