- Rating
- 2(+1)
- Confidence
- 2
- Informativeness
- 2(+1)
- Presentation
- 2
- Soundness
- 2(+1)
Read review
Paper summary
In this paper, the authors propose the binary vector representation method that can handle the embedding task. They claim that using binary representation can significantly reduce the memory space consumption, which can be used in edge devices.
Critical strengths
S1: Reducing the space consumption of using the embedding method is very useful in practice.
S2: Experimental results show that their methods can be better than the existing methods in terms of both accuracy and efficiency.
Critical weaknesses
W1: The technical novelty of this paper is very limited. After reading Sections 3.1 to Section 3.5 (including those equations and Algorithm 1), I cannot see anything new here. The authors claim that they use "binary" vectors. But those equations and the algorithm 1 does not show how they are related to the binary vectors. It looks like they are from the standard equations used in GNN and SVD. What I think is the authors replace the original floating-point vectors to the binary vectors. But the authors do not show why it is better in terms of accuracy.
W2: I think the main contribution is from Section 3.6, which states that the time complexity and the memory storage are reduced. But it is very obvious as the authors have replaced the floating-point vectors by the binary vectors.
W3: I can see some sections with a few sentences, e.g., Section 3.2 and Section 3.6. In Section 3.2, it just have a few sentences for discussing the transition operators. I believe that this is also not very new. Why does the authors need to write this? In Section 3.6, this kind of time and space complexity analysis are also so simple. I do not know why the authors need to write them (or as a new section).
W4: I really doubt whether the "method" proposed in this paper is simply the existing method but the authors replace the floating-point vectors by the binary vectors. If yes, this is simply an engineering work with no theory.
Questions for authors
Q1: Does this work simply replace the floating-point vector by the binary vector in the existing method?
Q2: Is there any theoretical analysis related to accuracy?
Q3: Is the transition operator the contribution of this work?
Q4: What is the theory behind this work?
Q5: What are the main contributions of this work?
4 comments
W1. Please refer to our answers to Q1 and Q3.
W2. We agree that binary storage is more compact than floating-point, but this is not the point of our complexity analysis, and NyS-Binary does not simply threshold an existing continuous embedding. The codes come from a sequence of closed-form steps, each with a clear meaning: (i) a Nyström-inspired landmark sketch of the multi-hop transition operator, which gives a structural encoding whose bits depend only on random-walk proximities to the landmarks (Lemma C.1); (ii) a separate semantic encoding built on an orthogonal hypercube codebook, whose bits act as an error-correcting code (Theorem C.2); (iii) polynomial diffusion of both channels; and (iv) a column-adaptive median quantizer that is invariant to positive rescaling, so no normalization is needed. Each channel has its own bit budget. Theorems C.1 and C.3 further characterise when the bits are informative and stable (Sec. 3.5, App. C).
The complexity analysis (Sec. 3.6) is about how long it takes to generate these codes, and binarisation alone does not make that fast. Existing binary methods are themselves slow to generate: node2binary takes 1,740 s and Bi-GCN 5.35 s on average, while NyS-Binary takes 0.33 s (Table 2). The speed comes from the landmark construction, which costs (near-linear in for sparse graphs) and needs no training.
Generation cost matters in practice. Neuromorphic and edge platforms naturally consume binary inputs, but they usually cannot run gradient-based training. A training-free, closed-form encoder that runs in near-linear time can therefore compute or refresh the codes with modest resources. This is important when the graph changes over time (e.g., new edges or nodes in a sensor or communication network), since codes from a trained encoder would need retraining. Please also refer to our answers to Q1 and Q5.
W3. Following the reviewer's suggestion, the transition operator no longer has its own section. It is now briefly introduced (Eq. 1) at the start of Sec. 3.1, Notation and Problem Setting, since every subsequent step uses it. Please also refer to our answer to Q3. We keep the short complexity section (Sec. 3.6) because applications are the motivation for this work, and practitioners need to see that construction scales near-linearly in . Together with the reported generation times (Table 2), it shows the method is practical for large graphs and edge devices; storage details are in App. A.1.
W4. Please refer to our answers to Q1 and Q4.
Reply to the Rebuttals
I have read the rebuttals from the authors and think that some of the comments have been addressed. Therefore, I have increased the score in this paper.
We sincerely thank Reviewer bUeb for engaging with our rebuttal, increasing the score, and acknowledging that some of the comments have been addressed. Since you noted that some points were resolved, we would appreciate knowing which aspects from your review still feel incomplete:
- Technical distinction from post-hoc binarisation (W1, W4, Q1, Q5): We sharpened Sections 1 and 3 to distinguish our closed-form pipeline (Sections 3.2–3.4) from binarising floating-point vectors, backed by Table 1 (
Raw Features Bin). Please let us know if any part of the algorithmic motivation remains unclear. - Theoretical characterisation and scope (W1, Q2, Q4): We added pointers to Lemma C.1 and Theorem C.3 in Section 3.4. Section 3.5 and Appendix C cover channel factorisation (Proposition C.1), scale invariance and column-space geometry (Lemma C.1), landmark coverage (Theorem C.1), semantic error tolerance (Theorem C.2), and quantisation stability (Theorem C.3). Appendix C.6 explains the scope of these guarantees. We would be glad to expand on any specific point that still feels incomplete.
- Presentation clarity and generation efficiency (Presentation, W2, W3): We streamlined Section 3 and paired the near-linear complexity analysis (Section 3.6) with empirical runtime benchmarks against slower learned and recursive baselines (Section 4.3, Table 3). Please let us know if any specific sections or equations still need clearer exposition.
Thank you once again for your feedback and time. We remain fully open to refining our work and clarifying any remaining concerns.
Q1. Does this work simply replace floating-point vectors with binary vectors in an existing method?
We thank the reviewer for raising this; it is a legitimate concern. A natural approach would be to learn structural embeddings with an unsupervised/SSL method and binarise them, or simply to binarise the available node features. The first route requires training (and post-hoc binarisation of a representation that was never optimised for it); the second requires node attributes, which many graphs lack. Both lose accuracy: binarizing raw features drops LogReg/MLP accuracy from 68.09/69.45 to 53.90/51.48 (Table 1) versus 73.98/75.69 for NyS-Binary.
Our goal is different. Applications such as neuromorphic and edge inference need representations that are binary, training-free, feature-free, and fast to generate. NyS-Binary produces them in closed form: a landmark (Nyström-inspired) sketch of the multi-hop transition operator, a semantic channel built on an orthogonal hypercube codebook, polynomial diffusion, and an adaptive median quantizer. It runs in 0.33 s on average, versus 5.35 s for Bi-GCN and 1,740 s for node2binary (Table 2).
Beyond the algorithm, we show that the embeddings have a theoretical interpretation both before and after discretization (Sec. 3.5, App. C):
Q2. Is there any theoretical analysis related to accuracy?
We do not claim an end-to-end guarantee on downstream classification accuracy, and the paper says so explicitly (Sec. 3.5, App. C.6). Such guarantees are rare for training-free embeddings in general, because accuracy also depends on the downstream classifier, the split, and how well graph structure aligns with labels. Comparative accuracy is therefore established empirically (Table 1: 10 datasets, 9 probes, 3 seeds; ablations in App. A–B).
However, we provide theoretical interpretations of the embeddings generated by NyS-Binary, as summarized in our answer to Q1.
Q3. Is the transition operator the contribution of this work?
No. The self-loop–augmented random-walk operator (Eq. 1, Sec. 3.1) is standard (as used in, e.g., GCN and SGC), and we do not claim it as a contribution.
Our methodological contributions are as follows:
Q4. What is the theory behind this work?
The theory is summarised in our answer to Q1 (Sec. 3.5: Lemma C.1 and Theorems C.1–C.3; full proofs in App. C).
Q5. What are the main contributions of this work?
Please see the list at the end of our answer to Q3: a training-free landmark construction for binary codes, decoupled structural and semantic channels with error-correcting codewords, a feature-free (optionally label-free) setting, normalisation-free adaptive quantisation, and a theoretical characterisation of the resulting bits (Q1).