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