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

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.