Trusting Assembly-Graph Edges by Where Composition and Coverage Disagree

Metagenomic binning sorts the DNA fragments assembled from a mixed microbial sample into per-genome groups. Two kinds of evidence drive it. The first is sequence composition, meaning short-word (k-mer) frequencies that act as a genomic signature. The second is coverage, meaning how many reads land on a fragment in each sample, which tracks how abundant its organism is. The assembler also leaves behind an assembly graph whose edges record which fragments physically overlap. Graph-based binners pass information along these edges, but some edges are wrong. Repeats, conserved genes, and chimeric overlaps join fragments from different species, and averaging across them blurs genomes together. Learned attention should be the fix, yet on real wastewater data the standard graph attention network did worse than plain uniform averaging (Graph Neural Networks for Metagenomic Binning).

We propose that an edge's trustworthiness is best read from how the two evidence types agree or disagree across it, measured in separate spaces, not from the jointly encoded hidden state that current binners produce. A conserved gene shared by two species tends to look compositionally plausible while its coverage jumps across the edge. A repeat shows coverage roughly equal to the sum of its neighbours. A short fragment has noisy composition but reliable coverage. We build a tiny edge gate, a logistic function of a handful of per-modality disagreement features. It is trained from weak biological labels and frozen with respect to the network's hidden states, and it sets neighbour weights in an otherwise ordinary graph convolution. The cross-modal gap is not something to close here. Keeping the two modalities apart is what makes their disagreement visible.

Core Claim

Current graph binners, including GraphMB (Metagenomic binning with assembly graph embeddings), CCVAE (Metagenomic Binning using Connectivity-constrained Variational Autoencoders), and the GNN study of Lamúrias et al., concatenate k-mer frequencies and coverage into a single autoencoder. That autoencoder turns raw features into compact vectors. Any edge weighting then sees only the fused vector. We claim three things. First, per-edge, per-modality disagreement predicts inter-genome edges substantially better than distance in the fused embedding. Second, a gate with roughly ten parameters built on those features avoids the instability that made graph attention fail on real data. Third, the resulting neighbour weighting recovers more high-quality genomes than isotropic graph convolution and CCVAE on real samples.

Each direction plays a different role here. Coverage-aware graph binning is the application and supplies the repeat-coverage logic of GraphBin2 (GraphBin2: Refined and Overlapped Binning of Metagenomic Contigs Using Assembly Graphs), which assigns a contig to several bins when its coverage matches the sum of its neighbouring paths. Dynamic neighbour weighting is the mechanism. The cross-modal gap literature is the lens. Mind the Gap (Mind the Gap: Understanding the Modality Gap in Multi-modal Contrastive Representation Learning) showed that jointly trained encoders keep modalities in geometrically separate regions and that the gap distance materially changes downstream behaviour. We test the corresponding failure in binning: a joint encoder lets one modality dominate for exactly the contigs where the other is the reliable one.

Mechanism

For each edge $(i,j)$ we compute a feature vector $\phi_{ij}$ from quantities the GNN does not optimize. These are the composition distance between $i$ and $j$ in a composition-only encoder, the coverage distance in a coverage-only encoder, the absolute log coverage ratio in each sample, the edge's read support, the shorter contig's length, and a repeat residual. The repeat residual measures how closely a node's coverage matches the sum of its neighbours' coverages. We also include products of the two distances with contig length, so that the gate can lean on coverage for short contigs. The gate is

$$w_{ij} = \sigma(\theta^\top \phi_{ij}),$$

where $\sigma$ is the logistic function and $\theta$ is the gate's only parameter vector. Message passing is a standard graph convolution with neighbour coefficients $w_{ij}$ normalized over each node's neighbourhood. GAT (Graph Attention Networks) scores edges from the hidden states being trained. Our gate's inputs are fixed, so the edge-reconstruction objective cannot reshape them. We read this as the most direct response to the overfitting diagnosis of Lamúrias et al.

The gate is trained under two regimes, which we compare. In the transfer regime it is fit on simulated communities where every edge's true label is known, then frozen and applied to real samples. The small parameter count makes transfer plausible. In the on-sample regime it is fit to weak labels from the target sample itself. Negatives come from edges and short paths joining contigs that carry the same single-copy marker gene, the cannot-link signal used by RepBin (RepBin: Constraint-Based Graph Representation Learning for Metagenomic Binning) and CCVAE. Positives come from edges inside high-confidence bins of a base binner. Downstream we keep the rest of the Lamúrias et al. pipeline unchanged so that only the neighbour weights differ: the local encoder, the marker-gene penalty, and iterative medoid clustering.

Research Program

The work proceeds in three stages. The first is diagnostic. On STRONG100, where every contig's origin is known, we label each assembly edge as intra- or inter-genome. We then compute how well single features separate the two classes, measured by area under the ROC curve. The features compared are fused-embedding distance, each per-modality distance, the coverage ratio, and the gate. We stratify the results by contig length and coverage. We also run a Mind-the-Gap-style geometric analysis of the joint autoencoder: within short or low-coverage strata, does the fused embedding track one modality's distance almost exclusively? That analysis tests whether the "representation gap" in binning is real or only an analogy.

The second stage builds the gated convolution described above and compares the two training regimes. The third stage evaluates end-to-end binning on simulated and real data and reports the learned $\theta$, because a gate this small is interpretable. For example, we can see whether the gate learns to ignore composition below some length.

Baselines

The naive reference point is VAMB-style binning with no graph: concatenated features, a single autoencoder, and medoid clustering. It reached F1 0.849 on STRONG100 in Lamúrias et al. and 0.870 in the CCVAE paper, and CCVAE reports it recovering 256.3 high-quality bins across six wastewater datasets. Any graph method must clear it by a wide margin.

The strongest graph competitors are three. The first is the isotropic GCN of Lamúrias et al., which recovered 54 high-quality bins on DAMH against 50 for MetaBAT2 and 23 for GraphBin. The second is the GAT variant from the same paper, which reached F1 0.904 on STRONG100. The third is CCVAE, which reported F1 0.903 on STRONG100 and 266.2 high-quality bins across the six wastewater datasets. CCVAE is the strongest real-data number in the file, and the isotropic GCN is the closest architectural competitor. We also run GraphMB, whose fixed weighting by edge read coverage is the existing form of coverage-based neighbour weighting. Every method receives the same assemblies, the same coverage tables, the same marker-gene annotations, and the same number of hyperparameter trials. Where public code permits, we rerun rather than copy numbers.

The key ablations are two. The first is a hand-set heuristic gate, $\exp(-|\Delta \log c|)$ on the coverage ratio, with no learning. The second is the same logistic gate fed only fused-embedding distances. Only the per-modality version isolates the cross-modal ingredient.

Beating the baselines means two results. First, more high-quality bins than CCVAE's 266.2 summed over the six wastewater samples, and more than 54 on DAMH. Second, F1 above 0.904 on STRONG100. The per-modality gate must also beat both ablations in edge-level ROC area and in high-quality bin count, with a gain larger than the spread across random seeds.

Why not just…?

Why not just weight edges by a fixed coverage-ratio rule? This is the most serious threat. GraphBin2 already shows that coverage consistency alone carries much of the signal. If the heuristic gate matches the learned per-modality gate in edge ROC area and in high-quality bins, then the learned part adds nothing and we will report the heuristic as the result. Our expectation that it falls short rests on the stratified diagnostic. The coverage ratio cannot tell a repeat (coverage equals the neighbour sum) from a conserved inter-species region (coverage differs but composition is plausible). It also has no way to use composition when two co-abundant species share an edge. The decisive comparison is the stratum of inter-genome edges whose endpoints have similar coverage.

Why not just use edge-feature attention, as in EGAT? EGAT (Interpretable Multimodality Embedding Of Cerebral Cortex Using Attention Graph Network For Identifying Bipolar Disorder) injects continuous edge weights into GAT attention on brain graphs. However, it still scores edges from trainable hidden states, and that is the component Lamúrias et al. found unstable under edge-reconstruction training on assembly graphs. We run an EGAT-style variant with edge read support and coverage ratio as edge attributes. If it matches our gate on real data, the "fixed inputs" argument fails.

Why not just fix the encoder by aligning the two modalities contrastively? Mind the Gap shows contrastive objectives preserve, rather than remove, the separation between modalities. FindRec (FindRec: Stein-Guided Entropic Flow for Multi-Modal Sequential Recommendation) found that naive alignment collapses modality-specific detail. More fundamentally, aligning the modalities would erase the disagreement signal our gate depends on. We nonetheless include a two-encoder model with an InfoNCE alignment term, a standard contrastive loss, fed to an isotropic GCN. This tests whether separate encoders alone, without gating, explain any gain.

Why not just prune suspicious edges and run GraphBin2 refinement? Hard pruning is a thresholded version of our gate and is cheap. Still, GraphBin-style propagation recovered only 23 high-quality bins on DAMH against 54 for a learned GCN in Lamúrias et al., which suggests that propagation cannot repair a flawed starting binning. We include gate-thresholded pruning followed by GraphBin2 as a baseline.

Proposed Experiments

On STRONG100 we report edge-level ROC area for every edge-scoring method, then binning F1 and counts of high-quality bins (above 90% completeness and below 5% contamination) and medium-quality bins. On Sim-5G, Sim-10G and Sim-20G we compare against RepBin, which reported F1 97.15% on Sim-20G. We also test multi-label assignment of repeat contigs against GraphBin2's balanced accuracy. On the six wastewater datasets, including AALE, MARI and DAMH, we count marker-gene-assessed high-quality and medium-quality bins. On CAMI we report recall against RepBin's 92.84%.

The decisive checks are four. The first is whether the per-modality gate beats both the fused-distance gate and the coverage-ratio heuristic on inter-genome edges between co-abundant contigs. The second is whether a gate trained only on simulated data transfers to wastewater samples without loss relative to on-sample marker-gene training. The third is whether the gated GCN stays stable across seeds on real data, where GAT did not. The fourth is whether the full pipeline exceeds CCVAE's 266.2 high-quality bins. A negative result on the first check would falsify the core claim, whatever the end-to-end numbers show.