Biological interaction databases are almost entirely empty. Confirmed drug-microbe-disease triplets make up 0.11% of possible combinations, and the BioSNAP molecular networks have edge densities between 0.03% and 4.23%. What little is known is concentrated on a few heavily studied "celebrity" molecules. Models that learn a free vector for each drug, gene or disease tend to give these hubs large, confident embeddings, rank them highly for almost any query, and learn very little about the long tail of rarely assayed entities. The tail is where new drug leads would come from. This note proposes a direct test: restrict every entity's representation to a short string of bits ($\pm1$ codes) and train those bits natively on the space of bit strings. Each entity then has a hard, equal information budget, and no entity can raise its scores simply by growing its vector.
The core claim is narrow and falsifiable. At a matched storage budget, binary entity codes trained with a bit-flip-based flatness objective will rank held-out interactions for low-degree entities better than continuous embeddings, including continuous embeddings that are normalized or shrunk to the same number of bits. As a side effect, Hamming-distance scoring becomes cheap enough for proteome-scale screening. The proposal treats discrete optimization as the mechanism and biological sparsity as the regime. Efficiency is a secondary payoff, not the motivation.
Why this intersection, and what already exists
The two literatures have not met. On the discrete side, Binarized Graph Neural Network binarizes the weights and activations of graph attention networks. It uses a mean-centering "balance function" to stop binary features from collapsing into identical strings, and it trains through straight-through estimators, which pass gradients through the sign function as if it were the identity. On Cora it gets a 19× speedup and 28× smaller storage at 77.7–80.5% accuracy versus 84.0% for full precision. Its experiments cover node classification only, and the authors name link prediction as future work. This paper supplies the balance-function method we reuse. It also constrains the proposal: its accuracy deficit is the most direct evidence that discreteness may simply hurt. We address this head on below.
Sharpness-Aware Minimization Directly on the Boolean Hypercube (BOLD-SAM) shows two problems with training binary networks through continuous "shadow" weights. First, as shadow weights grow, small continuous perturbations stop flipping any bits. Second, Euclidean distance between shadow weights does not track Hamming distance between the bits. BOLD-SAM instead searches for the worst-case configuration within a $k$-bit Hamming ball and descends from there. Its robustness gains under distribution shift are 2–3× its clean-accuracy gains. It was tested only on vision networks. We adapt its optimizer to embedding tables and graph propagation.
On the biological side, CSGNN, SGCLDGA, MKDTI, and MCHNN fight sparsity in different ways. CSGNN uses multi-hop aggregation plus contrastive self-supervision. SGCLDGA contrasts a graph-convolution view against a truncated-SVD view of the adjacency matrix and decodes with an inner product. MKDTI fuses per-layer Gaussian kernels into a least-squares predictor. MCHNN uses hypergraph contrastive views. All of them use continuous representations, and all report aggregate AUC or AUPR rather than performance stratified by node degree. They motivate the problem and serve as baselines. None of them asks whether the form of the per-entity representation drives the hub bias.
The obvious combination is "binarize a GNN for drug-target prediction to make it faster." This proposal differs from that in three ways. It discretizes the entity codes, which is where per-entity memorization lives, rather than only the shared weights. It trains them with hypercube-native flatness rather than straight-through estimators alone. And it is judged on tail-entity ranking at matched bit budgets, not on speed.
Core Claim and Mechanism
In inner-product link predictors such as SGCLDGA and LightGCN-style models, the score for a pair is
$$s(u,v) = \langle z_u, z_v \rangle = \|z_u\|\,\|z_v\|\cos\theta_{uv},$$
where $z_u$ is entity $u$'s embedding and $\theta_{uv}$ the angle between the two embeddings. A hub can raise all of its scores by growing $\|z_u\|$, since this "norm channel" is what absorbs popularity. With binary codes $b_u \in \{-1,+1\}^d$, the score becomes $d - 2\,\mathrm{Ham}(b_u,b_v)$. Here $\mathrm{Ham}$ counts the positions where the two codes differ, and $\|b_u\| = \sqrt{d}$ for every entity. The norm channel disappears, and each entity can store at most $d$ bits regardless of how many training edges it has.
This raises two hypotheses that the experiments must separate. The first is that removing the norm channel is what matters, in which case normalized continuous embeddings would do just as well. The second is that the discrete capacity cap, combined with flat-minimum training on the hypercube, provides additional regularization for the tail. BOLD-SAM's argument that bit strings have no scaling symmetry to exploit, and the finding in Expectation Backpropagation that binary-weight networks beat continuous ones on sparse, high-dimensional text, are suggestive for the second hypothesis but not decisive. Neither tested relational data.
Research Program
We will build a binary link predictor with three parts. The encoder is a two-layer light graph convolution over the bipartite interaction graph. It acts on binary entity codes and carries the balance function from BGN, which re-binarizes after mean-centering at each layer to prevent collapse. The decoder scores pairs by Hamming distance. The optimizer is BOLD-SAM adapted to embedding tables: the Hamming ball is restricted to the code rows touched by the current minibatch, the radius $k$ is set as a fraction of those touched bits, and Boolean-variation derivatives are used for the worst-case ascent step. We will also implement the same model trained with plain straight-through estimators and with tanh continuation in the style of HashNet, which smoothly sharpens tanh toward a sign function. These variants test whether the optimizer matters or only the final representation.
The analysis has three strands. First, we stratify held-out edges by the training degree of their endpoints (0–2, 3–10, more than 10). Second, we measure popularity bias as the rank correlation between an entity's training degree and its mean predicted score over random partners. Third, we track how the Hamming radius $k$ interacts with sparsity, because BOLD-SAM's default of 0.01% of parameters was tuned for images and may not transfer.
Baselines
The naive reference is a popularity predictor that scores a pair by the product of the endpoints' training degrees. On hub-skewed data it is often embarrassingly competitive in aggregate AUC, and any method that cannot beat it on the low-degree stratum has learned nothing about the tail.
The strongest existing method on DGIdb 4.0 is SGCLDGA. Its reported 5-fold results are AUC 0.8864 and AUPR 0.9086 (SGCLDGA), with a 16-minute runtime matching LightGCN. It is the closest competitor because it uses the same inner-product decoder family and already fights sparsity through SVD contrast. We will rerun the released configuration under our splits and negative-sampling protocol rather than copy numbers, since aggregate AUC depends heavily on how negatives are drawn. On the DrugBank/STRING drug-target data, MKDTI reports AUC 0.942 and AUPR 0.964 (MKDTI). On BioSNAP, CSGNN reports average AUC gains of 2.58% over GCN and 1.7% over GIN, but no reported result was found on Lacuna for its per-dataset AUC values, so we will rerun it.
The key ablations are continuous models matched to the binary model's storage. One gives each entity a continuous embedding with $d/32$ float32 dimensions, so it uses the same $d$ bits. Another uses L2-normalized $d$-dimensional embeddings, which have the norm channel removed but no capacity cap. Two further ablations isolate the optimizer: the binary model trained with straight-through estimators alone, and with continuous SAM on its shadow weights.
Every model gets the same splits, the same negatives, and the same 40-trial hyperparameter search on a validation fold, using identical GPU time limits. Beating a baseline means a statistically significant improvement in low-degree-stratum AUPR across five seeds, while staying within one AUPR point of the best continuous model in aggregate.
Why not just…?
Why not just L2-normalize continuous embeddings? This is the most serious threat, because it removes the norm channel that our mechanism blames. If normalized continuous embeddings match binary codes on the low-degree stratum, the honest conclusion is that discreteness adds nothing beyond normalization, and the proposal reduces to an efficiency paper. The normalized-embedding ablation exists to settle exactly this question. Our prediction is that it closes part of the gap but not all of it, since a normalized embedding can still encode an unbounded amount of hub-specific detail in its direction.
Why not just use a smaller continuous embedding with the same bit budget? This tests whether the capacity cap alone does the work. A four-dimensional float embedding has the same storage as 128 bits, but it has continuous norm and very few directions, so we expect it to underfit the hubs and the tail together. If it instead matches binary codes, then discreteness is just a convenient way to buy small capacity, and we will report that.
Why not just train a continuous model and binarize or hash it afterward? This is the standard route to efficiency. The evidence in the file is against it for representations that must preserve similarity: HashNet's end-to-end continuation reached 0.5059 mean average precision on ImageNet retrieval at 16 bits versus 0.3106 for DHN (HashNet). Training Quantized Nets also shows that training without high-precision accumulation stalls, with 20.56% versus 8.21% error on CIFAR-10. We include post-hoc sign binarization of the SGCLDGA embeddings as a baseline. Even if it holds up in aggregate, it inherits the continuous model's hub bias, which the stratified metrics will expose.
Why not just use matrix factorization or truncated SVD? These methods are cheap and naturally low-rank. However, MCHNN outperformed CP and Tucker tensor factorizations on the drug-microbe-disease data, and SGCLDGA uses SVD only as an auxiliary view. We include truncated SVD scoring as a baseline.
Proposed Experiments and Decisive Checks
The main experiments run on DGIdb 4.0, which has 46,892 edges among 10,690 drugs and 3,227 genes. They also run on the seven BioSNAP/CCSB networks, whose densities span two orders of magnitude, and on the DrugBank/STRING drug-target set. Splits are degree-stratified, with an additional "few-shot entity" split that keeps only one or two training edges for 10% of drugs. The three LncRNADisease versions, with 276–621 edges, serve as an extreme-small-data check against MCGLLDA's reported LOOCV AUCs of 0.917, 0.922 and 0.954 (Multiview Consensus Graph Learning).
The first decisive check is the low-degree-stratum AUPR of BOLD-SAM-trained binary codes against both continuous ablations. The second is whether this advantage grows as density falls across the BioSNAP networks. If the binary-over-continuous gap widens as the graph gets sparser, that supports the regularization claim. If the gap is flat or reversed, that refutes it. The third is the degree-to-score rank correlation, which should drop for binary codes if the norm-channel story is right. The fourth is whether binary codes with straight-through estimators alone lose the tail advantage, which would show that hypercube-native training, not just the bit representation, is responsible.
The proposal also has to answer the BGN deficit. A global accuracy drop of the 3.5–6.3 point size BGN saw on Cora, combined with no tail gain, would count as a clean negative result. In that case we would conclude that discrete codes are an efficiency tool for this domain and not a regularizer. Finally, we report storage and Hamming-scoring throughput against SGCLDGA's 16-minute runtime, as a secondary outcome.
References
- Binarized graph neural network
- Sharpness-Aware Minimization Directly on the Boolean Hypercube
- CSGNN: Contrastive Self-Supervised Graph Neural Network for Molecular Interaction Prediction
- SGCLDGA: unveiling drug-gene associations through simple graph contrastive learning
- MKDTI: Predicting Drug-Target Interactions via Multiple Kernel Fusion on Graph Attention Network
- Multi-view Contrastive Learning Hypergraph Neural Network for Drug-Microbe-Disease Association Prediction
- Expectation Backpropagation: Parameter-Free Training of Multilayer Neural Networks with Continuous or Discrete Weights
- HashNet: Deep Learning to Hash by Continuation
- Training Quantized Nets: A Deeper Understanding
- Multiview Consensus Graph Learning for lncRNA–Disease Association Prediction