acceptodds
Under review as a conference paper at ICLR 2027

NyS-Binary: A Feature-Free, Algebraic Framework for Binary Node Representation Learning

Abstract

Graph neural networks deliver strong node representations, but their high-dimensional floating-point embeddings are costly to store and slow to serve on resource-constrained devices. Binary graph hashing addresses this by mapping each node to a compact bitcode, yet existing methods force an uncomfortable choice: random-walk and sketching approaches such as node2binary and NodeSketch are slow to construct and discard global structure, while shallow linear hashes such as NodeSig trade away accuracy on harder graphs. We present **NyS-Binary**, a feature-free, algebraic, and sparsely supervised hashing framework that operates purely on graph topology without requiring any node attributes, combines a randomized Nystrom-inspired low-rank sketch of a higher-order graph transition operator with a leakage-safe label-diffusion channel, fuses the two via a convex blend, and quantizes the result with an adaptive per-column median rule. Across ten node-classification benchmarks and diverse downstream classifiers, **NyS-Binary** consistently attains the highest average accuracy among all binary hashing methods, substantially outperforming the strongest feature-free binary baselines on both standard neural probes and spiking neuromorphic classifiers, while producing compact bitcodes in fractions of a second, over an order of magnitude faster than NodeSketch and up to three orders of magnitude faster than learned iterative baselines. Crucially, because the landmark structural channel provides a strong topological foundation independent of supervision, **NyS-Binary** operates in a semi-supervised regime and maintains competitive accuracy even under extreme label scarcity. Because the representations are strictly binary, they also natively support neuromorphic classifiers built on gradient-free learning and surrogate-gradient spiking networks, which compute via binary spike accumulation rather than floating-point arithmetic. We report where the method is strong, where it is not (notably extreme heterophily), and view it as evidence that principled algebraic sketching remains a competitive, scalable alternative to learned binarization.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Binary representation learning, Gradient free graph learning, Lightweight Node Embeddings

Reviews

Among:
Shape:
1234this paper, Top 17%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.75 over 4 reviews, above 83% of the others.
Reviewer_bUebOpenReview ↗
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

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

  • What the continuous structural embedding encodes (Lemma C.1). Its column space equals that of CL=MHSLC_L = M_H S_L, the multi-hop (H+1H{+}1 to H+3H{+}3 step) random-walk proximities from every node to the landmarks. The structural bits are invariant to the singular-value scaling and stabilizer, so they depend only on this landmark proximity geometry.
  • Which nodes receive informative codes (Theorem C.1). A node has a non-zero structural code iff it lies within H+3H{+}3 hops of a landmark; all uncovered nodes collapse to one identical code. We give the exact probability of non-coverage and the landmark budget m≥Nbln⁡1ηm \ge \frac{N}{b}\ln\frac{1}{\eta} that guarantees coverage with probability 1−η1-\eta.
  • What the semantic bits encode (Theorem C.2). A node's label bits equal its class codeword when its true-class margin is large enough, and decode to the correct class whenever 2Ni<dmin⁡2N_i < d_{\min}, i.e., they behave as an error-correcting code.
  • Stability of the bits (Theorem C.3). Numerical perturbations cannot flip a bit whose margin exceeds (1+μ)ed(1+\mu)e_d.

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:

  • Training-free landmark-based binary codes: an asymmetric, Nyström-inspired landmark sketch of the operator, used for binary node codes, at cost O(m3+NmK+∣E∣KH)O(m^3 + NmK + |E|KH), i.e., near-linear in NN for sparse graphs (Sec. 3.6).
  • Decoupled channels: separate structural and semantic channels, each with its own bit budget. The semantic channel encodes classes as orthogonal hypercube codewords, so its bits act as an error-correcting code (Theorem C.2). It is fed by ground-truth labels and confidence-gated pseudo-labels.
  • Feature-free setting: codes are built from topology alone, and the unsupervised variant (klabel=0k_{\text{label}}=0) also needs no labels. This matters for graphs without node attributes, where binarizing features is either impossible or loses accuracy (Table 1).
  • Normalization-free quantization: a column-adaptive median quantizer that is invariant to positive rescaling (Lemma C.1), so no normalization or tuning of the spectral scale is needed.
  • Interpretable bits: a characterisation of what the bits encode and when they are reliable (see Q1).

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

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 O(m3+NmK+∣E∣KH)O(m^3 + NmK + |E|KH) (near-linear in NN 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 NN. 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.

Reviewer_bUebOpenReview ↗

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.

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

NyS-Binary generates 250-bit topology-based node representations. The manuscript builds landmark reconstruction, combines structural and label-informed codes, applies diffusion and thresholding, and evaluates the representations on ten datasets. The study reports results with nine classifiers, ablations, heterophily analysis, and large-graph experiments.

Critical strengths
  1. NyS-Binary presents a compact topology-based representation pipeline with structural and label-informed components. The design directly addresses the cost of dense node representations.
  2. The empirical study covers ten datasets, diverse classifiers, heterophily analysis, ablations, and large graphs. This scope provides a useful view of the representation across graph settings.
Critical weaknesses
  1. The code differs from the p. 4 method. In advanced_baselines.py, get_v1_blend_from_r_struct differs from Eq. (4)’s averaged diffusion, and the threshold calculation applies α even though Eq. (5) separates α and μ. rigorous_ablation_system.py also uses different m and τ defaults.
  2. The experimental results are valuable, and the release needs a direct table-to-command mapping. Each main table, ablation, and OGB result requires the commit, configuration file, and execution command that produced it.
Questions for authors
  1. Please provide a versioned reproduction package for every main-table, ablation, and appendix result. Include the commit, command, configuration, and the corresponding manuscript formula and parameter values.
  2. Please state which implementation path generated Tables 1--2 and provide regenerated tables using the released configuration.
2 comments

We thank the reviewer kGXB for identifying these inconsistencies and for recognising the value of the experimental evaluation. We have addressed the reported discrepancies in both the code and the revised manuscript.

The diffusion formula on page 4 has been updated to explicitly describe the accumulated form implemented in the code and its relationship to the averaged form. We have also clarified the distinction between α\alpha, which controls semantic blending, and μ\mu, which controls the median-based quantisation threshold. The code now makes this separation explicit. The landmark-budget mm and confidence-threshold τ\tau settings have likewise been aligned and documented, including experiment-specific overrides.

We have introduced REPRODUCE.md to provide the relevant implementation paths, parameter settings, and execution instructions for the main benchmark, ablations, and appendix experiments, together with the corresponding table and figure generation.

The main benchmark underlying Tables 1–2 uses benchmark_new_algebraic.py, which dispatches NyS-Binary to fuse_alg_v1_nystrom_blend and then get_v1_blend_from_r_struct. Please follow the reproduction guide to execute the released evaluation pipeline and regenerate the corresponding results.

Thank you for your response and clarifications. After considering the rebuttal, I have decided to maintain my original score.

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

The paper implements an algebraic framework that performs binarization of node representations constructed from the graph topology. They capture the graph structural features through a low-rank structural sketching and incorporate semantics through incorporating training labels in a test-label-free diffused representation. Authors carried out technical analysis showcasing the time and memory construction constraints of their approach along with a methodological analysis by evaluating the binarization framework over a benchmark of ten datasets consisting of homophilous and heterophilous graphs. The framework shows an edge in maintaining similar accuracies in comparison with full floating point node features considering homophilous graphs while mentioning the limitations it has over heterophilous graphs

Critical strengths

The paper is well written, with a logical flow and a clear explanation of the proposed framework. Its contributions are clearly articulated, and the methodological choices are supported by ablation studies examining the structural and semantic components, diffusion, and quantization settings.

Critical weaknesses

Table 1 reports overall mean accuracy across datasets for nine downstream classifiers. However, as acknowledged in the limitations and Appendix A.6, the relative performance of the supervised and unsupervised variants depends on graph homophily. The main manuscript should state the overall averages with separate results for homophilous and heterophilous datasets, making this distinction visible.

Questions for authors

Could the authors include the future work discussion to explain how signed filters might address label information in heterophilous graphs, and whether the supervised variant would benefit more than the unsupervised variant?

2 comments

We thank the reviewer 4riq for the positive assessment and constructive suggestions.

Separate results by graph homophily: We have added Table 2 to the main manuscript, reporting separate averages for homophilous and heterophilous datasets across all nine downstream classifiers, in addition to the overall averages in Table 1.

Signed filters and future work: We have added a discussion in Section 5.3 explaining how signed polynomial filters could assign positive or negative weights to different neighbourhood scales, counteracting conflicting neighbour-label signals while retaining useful structural differences. The supervised variant may benefit more directly because its semantic channel explicitly propagates class information. The unsupervised variant could also benefit through improved structural contrast. We present these as potential benefits for future evaluation; their relative magnitude will depend on graph structure and label availability.

Thank you for your response. I believe my issues have been resolved.

Reviewer_FiByOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper presents a binary node hashing framework for GNN, aimed at improving learning accuracy, inspired from the Nystrom- technique. The experiments show that the proposed method outperforms the baselines.

Critical strengths

The paper contains several experiments and baselines, which is its main strength. However, these experiments are not well supported by an analytical model. Faire comparison is also questionable. The Nystrom-inspired structural channel can be considered new. But its performance is not proven theoretically.

Critical weaknesses

The primary weakness of the paper is the lack of a mathematical framework to support the claimed advantages. The baselines are not strong. For example, NodeSig is reduced to 250 bits, and NodeSketch is reduced to least-significant bits.

Questions for authors

Why does SADP give below-chance accuracy for several methods?

2 comments

We thank Reviewer FiBy for their assessment and constructive questions. We address the representation budgets used for the baselines, the mathematical foundation added to the revised manuscript, and the interpretation of below-chance accuracy under Graph SADP.

Q1. NodeSig: common code length and native 256-bit comparison

Our main benchmark evaluates representations at a common logical code length of K=250K=250 bits per node. The official NodeSig executable used in our experiments produces byte-packed outputs with dimensions that are divisible by 8. We therefore generate 256 bits and retain the first 250 bits, removing six bits, approximately 2.34% of the generated representation.

To directly assess this choice, we additionally evaluated NodeSig at 256 bits across the same ten datasets and three random seeds:

ClassifierNodeSig: 256 bitsNodeSig: 250 bitsDifference (250 − 256), percentage points
GCN70.39 ± 17.46%70.68 ± 17.31%+0.29
GraphSAGE71.02 ± 17.08%71.54 ± 16.95%+0.52
LINKX71.18 ± 15.33%70.72 ± 15.18%−0.46
Logistic Regression64.09 ± 17.12%64.05 ± 17.20%−0.04
MLP65.45 ± 15.04%65.98 ± 14.89%+0.53

The largest absolute change in aggregate mean accuracy is 0.53 percentage points, with changes occurring in both directions. These measurements indicate a modest effect on the reported aggregate means.

Q2. NodeSketch: evaluation under a common binary representation budget

As mentioned previously, our benchmark evaluates the accuracy and construction cost of representations constrained to K=250K=250 binary coordinates per node. This common output format enables consistent evaluation across conventional classifiers and binary-input spiking probes.

NodeSketch natively outputs integer-valued sketch coordinates. Comparing 250 such coordinates directly with 250 binary coordinates would assign different storage capacities to the methods: under 32-bit integer storage, the former requires 8,000 bits per node. We therefore apply an explicitly documented least-significant-bit conversion, Bid=1[Hid mod 2=1]B_{id}=\mathbf{1}[H_{id}\bmod 2=1], to obtain the required 250-bit representation.

This choice is motivated by compact hashing approaches, including b-bit minwise hashing (Li & König, 2010). Our implementation uses the official NodeSketch generator followed by this binary conversion, and evaluates the resulting representation under the same downstream protocol as the other methods.

Accordingly, the reported results assess NodeSketch’s binary adaptation within a common representation budget. This makes the comparison directly relevant to the paper’s objective: constructing accurate, compact binary node representations.

Q3. Mathematical foundation added to the revised manuscript

Beyond the algorithm, we show that the embeddings have a theoretical interpretation both before and after discretization (Sec. 3.5, App. C). Together, these results characterize what the binary codes encode before and after quantization, when they are informative, and when they are stable. Please refer to our answers to Q1 of reviewer bUeb for further details.

Q4. Why can Graph SADP produce below-chance accuracy?

Graph SADP is a gradient-free spiking classifier, included to demonstrate the applicability of binary representations to neuromorphic architectures. It is a weaker downstream probe in our evaluation than the surrogate-gradient classifier.

SADP selects the class with the highest output spike count. When no output neuron fires, argmax selects Class 0. Repeated silent outputs can therefore produce predominantly Class-0 predictions and below-chance accuracy when this class is rare:

DatasetClass-0 sharenode2binary SADP accuracy
WikiCS2.52%2.47%
Computers3.17%3.33%
Photo4.82%4.82%

Surrogate-gradient training substantially mitigates this poor performance: the same node2binary representations achieve 52.08% on WikiCS and 64.59% on Photo. Thus, the low SADP scores reflect limitations of the downstream training configuration rather than an inherent failure of the representations. Under SADP, NyS-Binary achieves 56.27%, 66.66%, and 80.70% on WikiCS, Computers, and Photo, respectively.

We thank the reviewer for raising these concerns. In our rebuttal and revised manuscript, we added a theoretical characterisation of the binary codes (Section 3.5 and Appendix C), compared NodeSig at 250 and 256 bits, clarified how we adapted NodeSketch to the shared 250-bit budget, and explained how silent SADP outputs can lead to below-chance accuracy.

We would appreciate hearing whether these clarifications address your concerns or whether any point would benefit from further discussion. Thank you for your time and feedback.

Comments on the paper

2 comments

As only a few days remain in the author-reviewer discussion period, I encourage reviewers to review the authors' rebuttal and actively participate in the discussion. In particular, please clarify which concerns have been addressed and identify any remaining concerns or questions that may require further discussion.

We thank the reviewers for their feedback on our paper. We added a theoretical characterisation of the binary codes, explaining what the structural and semantic embeddings encode and when the semantic bits can be decoded correctly. We also aligned the method description with the released implementation and added separate results for homophilous and heterophilous graphs.

  1. Method and theory (bUeb, FiBy). We clarified how NyS-Binary constructs binary codes directly from graph topology using a Nyström-inspired landmark sketch, an optional label-informed channel, diffusion, and adaptive median quantisation. Section 3.5 and Appendix C now characterise the structural information captured by the codes, landmark coverage, the conditions for correct semantic decoding, and the stability of quantised bits under perturbations. Downstream classification accuracy is evaluated empirically.
  2. Baseline comparisons and Graph SADP (FiBy). In the rebuttal, we compared NodeSig at its native 256-bit length and at 250 bits across all ten datasets and three seeds. We explained the least-significant-bit conversion used to evaluate NodeSketch under the existing 250-bit budget. We also clarified why Graph SADP can score below chance. When no output neuron fires, the prediction defaults to Class 0. For any seed where all predictions default to Class 0, the accuracy equals the share of Class 0 nodes in that seed’s test split.
  3. Implementation and reproducibility (kGXB). We aligned the diffusion description with the implementation, clarified the roles of the semantic blending weight α\alpha and the quantisation threshold parameter μ\mu, and documented the landmark-budget and confidence-threshold settings. We regenerated Tables 1–2 and included the results in the revised manuscript. REPRODUCE.md identifies the benchmark code path and provides versioned configurations and commands for the main results, ablations, and OGB experiments.
  4. Performance across graph types (4riq). The new Table 2 reports separate averages for homophilous and heterophilous datasets across all nine downstream classifiers. Section 5.3 discusses signed filters as future work and explains why they could more directly benefit the supervised variant through its label-informed channel.

In the follow-up discussion, Reviewer bUeb noted that the rebuttal addressed some of their concerns and slightly raised their rating. Reviewer kGXB acknowledged the clarifications and retained their original rating. We appreciate the reviewers’ engagement and the Area Chair’s consideration of the revised submission.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.