acceptodds
Under review as a conference paper at ICLR 2027

Scalable Graph-Level Autoencoding via Hyperball Cloud Representations

Abstract

Embedding structured objects into Euclidean spaces has enabled a wide range of successful machine learning applications. Such objects include words, documents, image patches, time series, and graph nodes. In contrast, embedding entire graphs remains a challenging problem. Existing methods either sustain the original order of the graph nodes or match the output nodes to the input ones, both of which cre- ate scalability issues. In this work, we propose a graph representation as a cloud of hyperballs, which allows us to define a specific—typically unique—node order- ing. Based on this representation, we propose GeoGAE, an autoencoder, in which the Transformer encoder translates a hyperball cloud into a graph-level embed- ding, and the Transformer decoder translates the graph-level embedding back into the graph. This formulation enables the model to capture both the global graph structure and local relational patterns. We evaluate our method on multiple graph datasets, spanning various domains. The results demonstrate effectiveness of our method in encoding and reconstructing graphs from their embeddings.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
graph neural networks, autoencoders, graph embeddings, generative models, graph generation, transformers

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 2 reviews, above 27% of the others.
Reviewer_zAUqOpenReview ↗
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
  1. 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.
  2. 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
  1. 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.
  2. 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
  1. 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.
  2. 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.
  3. 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.
1 comment

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:

DatasetFixed randomGeoGAE
MUTAG11.3 ± 1.661.3 ± 5.4
IMDB-BINARY64.9 ± 3.194.0 ± 1.0
SYNTHETIC NEW0.0 ± 0.050.1 ± 0.4
AIDS18.7 ± 13.684.1 ± 1.7

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 dd:

DataMethodd=2d=3d=4d=6d=8d=12d=16
AIDSVar.6158.98751111—
Fix.8583.99641111—
MDE.9085.9624.9741.9817.9843.9939—
COLLABVar.8728.9839.9950.9992.99981—
Fix.8708.9412.9771.9939.9963.9975—
MDE.8246.9079.9530.9839.9916.9951—
REDDIT-BVar———.9998.9999.9999.9999
Fix———.4638.7080.7504.7715
MDE———.1252.1530.2432.3637

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):

DatasetF1 std [pp]F1 max − min [pp]Changed ordering
MUTAG0.71 ± 0.342.04 ± 1.0598.3%
IMDB-BINARY0.44 ± 0.471.07 ± 1.12100.0%
AIDS0.31 ± 0.110.83 ± 0.2683.7%
SYNTHETIC NEW0.18 ± 0.020.49 ± 0.0799.6%

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:

DatasetAvg. |V|BTime/graph [ms]Peak VRAM [MB]Total
MUTAG17.9641,24067≈ 4 min
AIDS15.764788103≈ 26 min
IMDB-BIN19.864848143≈ 14 min
SYNTHETIC NEW100.0321,82285≈ 9 min
QM9†18.0102467123≈ 2.4 h
COLLAB†74.5164,097194≈ 5.7 h
REDDIT-BIN†429.616181,86212,290≈ 101 h

† 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.

Reviewer_4wqtOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies the problem of reversible graph-level representation that compresses an entire graph into a fixed-dimensional vector z while enabling exact reconstruction. The core idea is to represent a graph as a "hyperball cloud" in Euclidean space: each node is mapped to a hyperball, and an edge exists iff two balls intersect. Proposition 1 provides a theoretical guarantee (an n-node graph can be losslessly represented in n² dimensions using equidistant hyperballs, with adjacency ⇔ intersection). To reduce dimensionality, variable radii are adopted, and SVD combined with skewness signs is used to eliminate rigid-transformation and reflection ambiguities, yielding (for most topologies) a unique canonical node ordering. GeoGAE uses a Transformer encoder to compress the ordered hyperball cloud into z∈ℝᵐ (via multiple [CLS] tokens); a decoder reconstructs the cloud, and a static ball-intersection rule recovers the discrete edges. Experiments compare against PIGVAE, ReGAE, and GRALE on 7 datasets (MUTAG/AIDS/IMDB-BIN/QM9/SYNTHETIC NEW/COLLAB/REDDIT-BIN), reporting edge-reconstruction F1, topology+attribute reconstruction, and graph-size error, claiming superiority and scalability over baselines on large graphs.

Critical strengths

Directly targets the three main bottlenecks of existing graph-level representations — node-order coupling, fixed n_max upper bound, and input-output node matching. The scalability design is pragmatic: "bundle" packing reduces the quadratic attention complexity, graph size is predicted dynamically, and no preset node upper bound is required. The experimental scale is acceptable: 7 datasets spanning chemistry/social/synthetic domains, 5 random seeds with ±std, including attribute (node/edge) reconstruction and ablations.

Critical weaknesses

Only PIGVAE/ReGAE/GRALE are compared; GraphVAE and MGVAE are mentioned in Related Work but not compared; GRALE directly runs OOM on COLLAB and degenerates to all-0/1 predictions on most datasets, weakening the "SOTA" comparison. At least one recent graph-autoencoder/graph-generation baseline should be added (e.g., the GraphRNN family or 2024–25 diffusion graph models as reconstruction baselines).

Questions for authors

(1) Can you provide evidence of z's downstream utility? E.g., a linear probe on z for a graph-classification benchmark, or qualitative examples of latent-space interpolation/generation. (2) Why not compare against recent methods such as the GraphVAE/MGVAE/DyGFormer families? Does GRALE's OOM on COLLAB imply that your "scalable" conclusion only holds relative to these three weak baselines? (3) What is the essential difference between the hyperball-cloud method and MinDistortionEmbedding / Nowak 2024? (4) Do the 0.75 decoding margin and T=0.4 have any sensitivity analysis or theoretical justification?

1 comment

We thank the reviewer for the thorough review and questions.

Downstream utility of embeddings

After GeoGAE training (with node and edge features, if present), we trained an MLP graph classifier on the frozen encoder's latent vectors (same train/validation sets) and evaluated it on the same test set. Results over 5 seeds:

DatasetF1 macroAUROC
MUTAG0.77±0.130.89±0.09
IMDB-BINARY0.72±0.050.81±0.05
AIDS0.99±0.001.00±0.00
REDDIT-BINARY0.79±0.030.88±0.02

zz retains class-relevant information (added to Appendix F).

GraphVAE/MGVAE/DyGFormer

  • GraphVAE (Simonovsky & Komodakis, 2018) decodes a padded adjacency of fixed size nmaxn_{max}, matched to the input in O(n4)O(n^4); it was evaluated only on graphs with ≤38 nodes. PIGVAE and GRALE (our baselines) build on it with more scalable matching, yet GRALE is OOM on COLLAB and REDDIT-BINARY, and PIGVAE on REDDIT-BINARY (Table 3). O(n4)O(n^4) matching makes GraphVAE impractical there (up to 492 and 3,782 nodes).
  • MGVAE (Hy & Kondor, 2021) is a hierarchical generative model for sampling new graphs and link prediction, not exact reconstruction of specific unseen graphs from one fixed-size vector (our task).
  • DyGFormer (Yu et al., 2023) does link prediction on continuous-time dynamic graphs; it yields neither graph-level embeddings nor reconstructions, so it is not comparable.

Scope of the scalability claim

To our knowledge, PIGVAE, ReGAE and GRALE are the only published methods for our task: encoding variable-size graphs into a fixed-size z∈Rmz\in\mathbb{R}^m generalizing to unseen graphs. GRALE (NeurIPS 2025, state of the art) is OOM on COLLAB and REDDIT-BINARY due to its architecture: pairwise node representations with Evoformer-style updates (O(n2)O(n^2) memory, O(n3)O(n^3) compute per layer) - not, we believe, a tuning artifact. PIGVAE uses an n×nn \times n soft permutation. Our method avoids node matching; its cost is dominated by self-attention over n/bn/b tokens.

We agree that ReGAE handles large graphs, so scalability alone is not unique to us. Among permutation-robust methods tested, only GeoGAE trains stably on COLLAB and REDDIT-BINARY, and it reconstructs more accurately than ReGAE. We revised Contributions and Conclusions and removed "unprecedented scalability".

Hyperballs vs. MDE (Agrawal et al., 2021; Nowak et al., 2024)

We first used MDE-style distance-preserving embeddings. They approximate graph distances, so adjacency is recovered only approximately via a global threshold. On COLLAB and REDDIT-BINARY this needed much higher dimensions, making the autoencoder harder to train. Hence hyperballs: adjacency is encoded exactly as ball intersections, a learned per-node radius acting as a node-specific threshold, allowing lossless encoding in low dimension.

Results of F1 [%] for variable-radius balls (var), fixed-radius balls (fix), and distance-preserving embeddings (MDE) across dimensions dd:

DataMethodd=2d=3d=4d=6d=8d=12d=16
AIDSVar.6158.98751111—
Fix.8583.99641111—
MDE.9085.9624.9741.9817.9843.9939—
COLLABVar.8728.9839.9950.9992.99981—
Fix.8708.9412.9771.9939.9963.9975—
MDE.8246.9079.9530.9839.9916.9951—
REDDIT-BVar———.9998.9999.9999.9999
Fix———.4638.7080.7504.7715
MDE———.1252.1530.2432.3637

Variable radius detects links significantly better than fixed radius or MDE.

Temperature and margin

Temperature (T=0.4T=0.4) appears only in training objectives (hyperball optimization, Eq. 2; decoder loss LgeoL_{geo}, Eq. 6), not in decoding. The margin mi,jm_{i,j} decides edge existence; as I[mi,j>0]I[m_{i,j}>0] is non-differentiable, we relax it to pi,j=σ(mi,j/T)p_{i,j}=\sigma(m_{i,j}/T) for the Focal Loss. For any T>0T>0, pi,j>0.5  ⟺  mi,j>0p_{i,j}>0.5 \iff m_{i,j}>0, so TT only scales gradients: as T→0T\to0 the sigmoid becomes a hard step and gradients vanish outside a narrow band around mi,j=0m_{i,j}=0 (severe Adam instability); as T→∞T\to\infty probabilities collapse to 0.5, destroying the decision boundary. Grid search over T∈{0.2,0.4,0.6,0.8}T\in\{0.2,0.4,0.6,0.8\} gives comparable F1 for generated graphs' geometric embeddings; T=0.4T=0.4 gives smooth gradients and a boundary sharp enough for hyperball separation.

Margin factor λ=0.75\lambda=0.75 enforces strict overlap: an edge exists if ∥xi−xj∥2≤λ(Ri+Rj)\|x_i-x_j\|_2 \le \lambda(R_i+R_j), Ri=f(ri)R_i=f(r_i). With λ=1\lambda=1, tangent spheres would form an edge, but tangency is numerically unstable and sensitive to small perturbations from the autoregressive Transformer decoder. λ=0.75\lambda=0.75 forces overlap of at least 25% of the combined radii: connected hyperballs overlap significantly, disconnected ones are pushed apart, a safety margin against the decoder's continuous reconstruction errors. As raw radii rir_i are free learnable parameters, any global scaling of (Ri+Rj)(R_i+R_j) is compensated during spatial optimization (clarified in Appendix B.4).

Comments on the paper

1 comment

We thank the reviewer for the insightful review and questions.

Q1 - Node ordering

Our autoencoder transforms graphs into distributions of node orderings. Depending on the initialization of the procedure computing the node embeddings, the node order may vary, yielding different embeddings. The ordering need not be unique per graph; however, the less diverse it is, the less capacity the encoder and decoder need to cover all orderings of the same graph.

Since fitting the embedding is permutation-equivariant, the ordering depends only on the embedding points; permuting the input order does not affect it.

To quantify how different orderings of the same graph impact GeoGAE, a model trained on geometric embeddings computed with the global random seed is evaluated on test sets with embeddings recomputed under different seeds. To assess the gap between the most pessimistic and optimistic scenarios, we measure for each graph the difference between the best and worst scores across test re-randomization seeds, then average it over the test set. We use 3 training (global) seeds, each evaluated with 5 test-time embedding seeds.

DatasetF1 std across embedding seeds [pp], mean ± std over train seedsAverage (max−min) F1 across embedding seeds [pp], mean ± std over train seeds% graphs with any change in node ordering
MUTAG0.71±0.342.04±1.0598.3%
IMDB-BINARY0.44±0.471.07±1.12100.0%
AIDS0.31±0.110.83±0.2683.7%
SYNTHETICnew0.18±0.020.49±0.0799.6%

Table 2 splits test graphs by structural symmetry (nontrivial automorphism, found with VF2) and by repeated Laplacian eigenvalues (gap below 10⁻⁶·λ_max).

DatasetSubsetShare of test graphs% graphs with changed orderingMean per-graph ΔF1 [pp]
AIDSsymmetric76%87.5%4.78
AIDSasymmetric24%71.3%5.41
AIDSrepeated eigenvalues46%92.3%4.89
AIDSdistinct eigenvalues54%76.3%4.97
MUTAGrepeated eigenvalues62%98.5%5.70
MUTAGdistinct eigenvalues38%98.1%6.43
MUTAGsymmetric (all graphs)100%98.3%5.98
IMDB-BINARYsymmetric + repeated eigenvalues (all graphs)100%100.0%1.24

Symmetric graphs and graphs with repeated eigenvalues change ordering more often, but their per-graph reconstruction is no more sensitive to it than that of asymmetric graphs. MUTAG and IMDB-BINARY are entirely symmetric, yet their test F1 varies by under 1 pp across embedding seeds (Table 1). Per-graph changes average out at dataset level, so the decoder does not rely on one particular ordering.

Q2 - Selection of the geometric dimension

Our wording was imprecise. The geometric dimension was selected using training and validation graphs only. The hyperball optimization is unsupervised, uses only graph structure (no labels), and is solved independently per graph. With the selected dimension, test graphs also reach 100% sphere F1. We will correct this sentence in Section 3.3.

Q3 - Preprocessing cost

The cost of hyperball cloud generation per graph is noticeable and not included in Table 8, although the evaluation relies on relatively simple algebraic transformations of hyperball coordinates, and therefore it is dwarfed by the computation costs of the transformer training. Preprocessing costs:

DatasetAvg. |V|BTime per graph [ms]Peak VRAM [MB]Total time
MUTAG17.9641,24067≈ 4 min
AIDS15.764788103≈ 26 min
IMDB-BIN19.864848143≈ 14 min
SYNTHETIC NEW100.0321,82285≈ 9 min
QM9†18.0102467123≈ 2.4 h
COLLAB†74.5164,097194≈ 5.7 h
REDDIT-BIN†429.616181,86212,290≈ 101 h

Time per graph = wall-clock time / number of graphs; graphs are optimized in parallel batches.

† Extrapolated from a random 5% sample (QM9: 6,472 graphs, COLLAB: 250, REDDIT-BINARY: 100) as sample time per graph × dataset size.

All embeddings reach 100% sphere F1 (for † datasets, measured on the sample). Added to Appendix D.

Q4 - Downstream utility of graph embeddings

We find this a very interesting experiment. After GeoGAE training (with node and edge features, if present), we trained an MLP graph classifier on the encoder's latent vectors using the same training and validation sets. Test results over 5 seeds:

DatasetF1 macroAUROC
MUTAG0.77±0.130.89±0.09
IMDB-BINARY0.72±0.050.81±0.05
AIDS0.99±0.001.00±0.00
REDDIT-BINARY0.79±0.030.88±0.02

zz retains class-relevant information (added to Appendix F).

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.