acceptodds
Under review as a conference paper at ICLR 2027

GRAFT: Hyperdimensional Computing-based Graph Reconstruction via Algebraic Fixed Transformations

Abstract

Many scientific domains, chemistry foremost among them, represent their primary objects as attributed graphs, and learning on these objects typically requires mapping them to and from a fixed-dimensional continuous space. One important capability such representations support is graph reconstruction - encoding an attributed graph into a single vector and recovering it exactly - which underpins retrieval and structure generation. Existing solutions are learned encoder-decoder models, with graph autoencoders as the canonical example: training takes hundreds of GPU-hours and yields codecs that are confined to the distribution they were trained on. We introduce GRAFT (Graph Reconstruction via Algebraic Fixed Transformations), a graph encoder-decoder architecture that maps graphs to fixed-dimensional hypervectors and back through deterministic binding, bundling, and message-passing operations over a fixed set of random reference vectors: the encoder and decoder contain no trainable parameters. On a standard molecular-graph reconstruction benchmark, GRAFT recovers 93% of molecular graphs with up to 32 heavy atoms exactly and 91% of graphs with up to 64 heavy atoms, substantially improving on state-of-the-art learned autoencoders without any encoder or decoder training. Paired with standard task-specific learned heads, GRAFT is suitable for MoleculeNet property prediction, supports molecular generation on ZINC250K, and substantially outperforms baselines on the Fingerprint2Graph translation task.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
graph autoencoder, hyperdimensional computing, vector symbolic architectures, graph reconstruction, training-free, molecular graphs, graph generation

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_6rNgOpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper proposes GRAFT, a training-free graph encoder–decoder based on hyperdimensional computing and holographic reduced representations (HRRs). It encodes attributed graphs into fixed-size hypervectors using a random node codebook and fixed binding and bundling operations. For reconstruction, it first recovers edge-type information through matching pursuit and then uses beam search to infer the graph topology. The paper evaluates GRAFT on exact graph reconstruction on PubChem16/32/64 using graph-isomorphism accuracy, as well as on Fingerprint2Graph task, molecular property prediction, and unconditional generation. The results show strong reconstruction accuracy and strong performance on Fingerprint2Graph. Although the graph codec itself requires no training, the downstream prediction heads and generation model are learned.

Critical strengths

GRAFT is a training-free HDC codec that combines fixed HRR bind/bundle message passing, a dual-stack readout, matching-pursuit edge recovery, and beam-search assembly. The design is a structurally different, non-learned alternative to graph autoencoders. On PubChem16 and PubChem32, its reported exact graph-isomorphism accuracies exceed the cited GRALE results by 5.5 and 26.1 points, respectively, and it retains 90.7% on PubChem64, where no learned baseline has been reported. The HRR capacity analysis and the f1/f2a/f2b error decomposition make the failure modes explicit and easy to inspect, and the Fingerprint2Graph results are well above the reported baselines, subject to protocol validation.

Critical weaknesses

The HRR algebra is internally inconsistent: Eq. (1)'s circular convolution is commutative (x⊛y = y⊛x), yet D.3–D.4 calls it non-commutative and builds an ordered-pair edge codebook. Under the stated operation, (a,b) and (b,a) are identical, so duplicate entries and argmax ties need explanation; the derivation and results should be reconciled.

The "training-free / dataset-independent" claim is overstated: D.3 builds the vocabulary from the observed support, not the full Cartesian product; unseen tuples have no vector and no OOV test is reported. E.7's ρ=+0.95 saturates above |X*|≈5,000 and the headline is past saturation, so a key untested limitation is the pool-constructed support, not vocabulary size. The ~350 GPU-hours includes tuning/ablations, so training-free ≠ zero cost. Baselines are from GRALE (Table 1; G.9 notes no rerun), with no 64 baseline, no comparison at matched codebook size or compute, and no ablation replacing the HDC edge code with an edge-type histogram under the same search; the 26.1-point PubChem32 gap therefore does not by itself isolate the HDC algebra from the descriptors and search.

Questions for authors
  1. Is the 250k codebook-construction pool in Table D.1 drawn exclusively from the training split, and what fraction of test molecules contain node tuples or edge-type pairs absent from the codebook?
  2. Since Table G.9 says the baselines were not rerun, were their reported numbers evaluated on the same 10k test lists? Please define GI Acc., including whether bond orders are compared, and report PubChem64 accuracy at n=64 with sample size and a size-macro average.
  3. Is f2a exact vector equality or a cosine threshold, and is the claimed 1-WL ceiling stated for standard 1-WL or for 1-WL with the same RW-augmented initial features? 4.D.3 says binding is non-commutative, but circular convolution is commutative, so the bound vectors for (a,b) and (b,a) are identical. Does C_edge store both ordered entries—if so, how are the duplicate vectors and argmax ties handled; if only one, why does D.4 subtract both orientations?
  4. Why does Sec. 5.1 say "roughly an order of magnitude" when, even against G.8's GRALE training-step times (not inference-only), GRAFT decoding is 29× slower at N=16 and 4,069× at N=64? 6.B.2 states node degree as the minimum requirement; on non-molecular attributed graphs without the chemistry-specific D.6 heuristic, how are edge labels recovered, or are edge labels out of scope?
Reviewer_2equOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper use introduce an autoencoder architecture (GRAFT) for graph data that require no training. GRAFT reconstructs molecule graphs using fixed high dimensional representations. It combines an edge representation given by matching pursuit and a grpah representation that is obtained by a constrained beam search over possible topologies.

Critical strengths

The paper proposed an autoencoder architecture that needs no training and the decoder provides an interpretable reconstruction procedure. The paper included a wide range of experiments over different molecule size and different downstream tasks. Furtherly, the paper shows a promising reconstruction accuracies on PubChem dataset. The Fingerprint2Graph results also show that the representation can support prediction from external inputs.

Critical weaknesses

GRAFT uses a 2048 dimensional representation, but the cited PubChem32 GRALE configuration uses 512 dimensions. The gain of proposed method is unclear comparing with the baseline method GRALE. Also, this paper has missed a few predecessors include [1] for HDC graph decoding, [2] for matching-pursuit decoding for hypervector, and [3] for deterministic molecular reconstruction. References: [1] Ali Zakeri, Zhuowen Zou, Hanning Chen, and Mohsen Imani. Configurable hyperdimensional graph representation. Artificial Intelligence, 347:104384, 2025. https://doi.org/10.1016/j.artint.2025.104384 [2] Denis Kleyko, Connor Bybee, Ping-Chen Huang, Christopher J. Kymn, Bruno A. Olshausen, E. Paxon Frady, and Friedrich T. Sommer. Efficient Decoding of Compositional Structure in Holistic Representations. Neural Computation, 35(7):1159–1186, 2023. https://doi.org/10.1162/neco_a_01590 [3] Philippe Meyer, Thomas Duigou, Guillaume Gricourt, and Jean-Loup Faulon. Reverse engineering molecules from fingerprints through deterministic enumeration and generative models. Journal of Cheminformatics, 17:157, 2025. https://doi.org/10.1186/s13321-025-01074-5

Questions for authors

What exact encoder equations were used in the experiments? Does Table 1 require correct bond labels after post-processing, with all decoding and sanitization failures included?

Reviewer_v4bZOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes GRAFT. It uses fixed hyperdimensional operations to encode and decode a graph, so no parameters trained. It achieves high reconstruction accuracy in some molecule benchmarks. It’s encoder and decoder can be used for downstream tasks, such as molecule property prediction and molecule generation.

Critical strengths

GRAFT turns a fixed HDC representation into an operational attributed-graph codec, avoiding gradient training of the encoder and decoder. The reconstruction results are compelling: it reports 93% graph-isomorphism accuracy on PubChem32 versus 66.8% for baseline. The encoder and decoder can be used in various downstream tasks.

Critical weaknesses

a. It does not experiment on graphs other than molecules, not sure whether it can be widely applied on other types of graphs.

b. No experiments to show the retrieval capability of the encoded representations.

Questions for authors

a. In the llm era, is it really useful and does it have real applications? For example, in real application, does Graft bring additional benefits to these benchmark tasks compare to other methods and be actually employed?

b. Why choose D=1024? For larger molecules, will larger dim be better?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.