Gas chromatography–mass spectrometry (GC-MS) is an instrument pair used to identify the chemicals in a mixture. A column separates compounds by the time they take to pass through it, and a mass spectrometer then breaks each compound into charged fragments, recording how much of each fragment mass appears. When two compounds leave the column at nearly the same moment, their fragment patterns add together into a "chimeric" spectrum that matches nothing in a reference library. Current automated pipelines untangle these mixtures with matrix factorization. Musicians' software faces the same problem when two instruments play the same note. The trick that works there is to stop tracking pitch and instead track the ratio between overtones, which stays fixed for a given instrument (its timbre) while everything else fluctuates. A compound's fragment pattern is its timbre: the ratio between any two of its fragments is set by chemistry and stays constant across the elution peak and across every sample in which the compound appears.
We propose to separate co-eluting compounds by building a graph whose nodes are fragment-mass traces and whose edges record how persistently the log-ratio of two traces stays constant. Persistence is measured scan by scan within a peak, after discarding unstable scans, and across many samples. Compounds are then found as communities in this graph using a degree-corrected block model. The central claim is about identifiability. Two compounds with identical elution profiles cannot be told apart within one run, because every ratio between their fragments is also constant in time. They can be told apart across a collection of samples, provided their abundances vary independently. A persistence-filtered ratio graph extracts exactly this signal. We predict it will recover compounds that single-run deconvolution merges, and that it will fail in a specific, testable regime: when the two compounds' abundances are correlated across samples.
Where this sits relative to existing work
The closest system is MSHub, described in Algorithmic Learning for Auto-deconvolution of GC-MS Data to Enable Molecular Networking within GNPS. MSHub runs unsupervised non-negative matrix factorization (NMF, which splits a data matrix into a small set of non-negative spectra and their abundances) on co-eluting ions. It aligns thousands of files, scores fragment reproducibility across samples with a "balance score," and reports about one minute per file with 99.17% correlation to manually tuned XCMS. MSHub already uses cross-sample information, so our novelty cannot be "use many samples." It lies in three places. The first is the evidence each pair of ions contributes: a stability test on intensity ratios, borrowed from music, rather than raw co-variation. The second is scan-level persistence filtering, which removes the distorted scans at the rising and falling edges of a peak before any grouping happens. The third is letting community structure decide how many components exist and which ions each may use, with factorization confined to apportioning shared fragments. In MSHub, as in Feature-based Molecular Networking in the GNPS Analysis Environment, graph analysis happens only after deconvolution, on molecules rather than fragments. That paper showed that resolving features by retention time and peak shape separates seven isomers that classical networking collapsed into one. It motivates the idea that finer upstream structure pays off downstream, but it hands deconvolution to external, parameter-heavy tools.
The mechanism borrows from two audio papers. Separation of Music Signals by Harmonic Structure Modeling separated instruments playing identical pitches by clustering stable overtone-amplitude ratios, the "average harmonic structure," and treating unstable components as noise. It reported a 29.2 dB SNR gain on synthetic voice, piccolo and organ mixtures. We reuse its central move of grouping by ratio stability. We replace its density clustering with a block model that tolerates highly unequal node strengths, and its audio frames with chromatographic scans and samples. An Efficient Temporally-Constrained Probabilistic Model for Multiple-Instrument Music Transcription shows that modeling attack, sustain and decay states separately helps under overlap. That supports our choice to treat peak fronts and tails as a distinct, less trustworthy state rather than averaging over them.
The persistence filter itself comes from phonetics and music analysis. Identifying Stable Sections for Formant Frequency Extraction of French Nasal Vowels Based on Difference Thresholds keeps only contiguous intervals where consecutive formant differences stay below fixed thresholds (60 Hz for F1, 200 Hz for F2). It shows this yields cleaner measurements than taking the temporal midpoint. Three-sectional-staff characterization of Cantonese level tones instead bounds the standard deviation of pitch over a token. We need both tests. A step-difference test alone accepts slow monotone drift, and slow monotone drift in a cross-compound ratio is precisely the signature of two slightly offset peaks. The acknowledged failure of such filters on short transients is a real constraint here, because at 2–20 scans per second a narrow peak may yield only a handful of usable scans. The cross-sample term is what rescues those peaks.
On the graph side, On equivalence of likelihood maximization of stochastic block model and constrained nonnegative matrix factorization proves that fitting several stochastic block models (generative models in which edge probability depends only on the groups of the two endpoints) is the same optimization as constrained NMF. It finds empirically that block models win when groups are cleanly separated, while least-squares NMF wins when node degrees are skewed and boundaries are fuzzy. This result constrains us strongly. If the objective is equivalent, then "graph instead of NMF" is not itself a contribution, so any gain must come from the edge evidence and the persistence filter. The result also predicts a split. The block model should suit compounds with distinctive fragments, while shared fragments, such as the ion common to all trimethylsilyl derivatives, create exactly the fuzzy regime where NMF is expected to do better. Our design follows that prediction rather than arguing with it.
Core Claim
Consider a fixed retention window across $N$ aligned samples, and let $x_{a,s}(t)$ be the intensity of fragment mass $a$ at scan $t$ in sample $s$. For each pair of fragment masses $(a,b)$ we form the log-ratio $r_{ab,s}(t) = \log x_{a,s}(t) - \log x_{b,s}(t)$. We use only scans where both intensities exceed the noise floor and lie inside a persistent segment. A persistent segment is a run of at least $L$ consecutive scans with step changes below $\tau$ and within-segment standard deviation below $\sigma$. The edge weight is
$$w_{ab} = c_{ab}\,\exp\!\left(-\frac{\mathrm{Var}_s\left[\bar r_{ab,s}\right]}{\sigma_x^2}\right),$$
where $\bar r_{ab,s}$ is the mean log-ratio over the persistent scans of sample $s$, $c_{ab}$ is the fraction of samples in which $a$ and $b$ co-occur with a persistent segment, and $\sigma_x$ sets how much cross-sample spread in ratio is tolerated. Fragments of one compound have near-zero cross-sample ratio variance. Fragments of two different compounds have a variance that grows with how independently the compounds' abundances vary. The standard error of that variance estimate shrinks roughly as $1/\sqrt{N}$, because it is an average over independent samples, so the separability of exactly co-eluting pairs should improve predictably with repository size.
We partition this graph with a degree-corrected block model. Ions whose assignment is ambiguous are allowed membership in more than one block. The resulting memberships then act as a support mask for a small non-negative factorization that splits shared ions' intensity among the compounds claiming them.
Research Program
We will build the pipeline in three layers. The first layer is the scan-level persistence filter on log-ratios. The second is the cross-sample ratio-stability graph. The third is block-model partitioning followed by support-masked factorization, which produces per-compound spectra and per-sample abundances.
The analysis has three parts. First, we map the identifiability boundary in two variables: retention offset between compounds (from zero to one peak width) and cross-sample abundance correlation $\rho$. Single-run methods should succeed only at large offsets. Our method should succeed at zero offset whenever $\rho$ is low. Second, we test the equivalence-paper prediction directly, by measuring where the block model beats NMF and where it loses, as a function of how many fragments the compounds share. Third, we measure how sensitive results are to the thresholds $\tau$, $\sigma$ and $L$. This matters because the whole point is to reduce the parameter tuning burden that the MSHub authors identify in AMDIS, XCMS and MS-DIAL. We will set thresholds once, from instrument scan rate and noise floor, and hold them fixed across datasets.
Baselines
The naive reference points are the apex-scan spectrum and the peak-averaged spectrum for each detected peak. These are the chromatographic analogues of midpoint extraction, which the French-vowel study showed distorts features. Any method that does not beat them on co-eluting pairs has no claim.
The strongest existing competitor is MSHub, because it is automated, unsupervised, cross-sample and repository-scale, which is the same regime we target. We will run it through its public GNPS workflow on identical aligned inputs, with the same retention windows and default settings. The comparison also includes a tuned variant given the same hyperparameter search budget as our three thresholds. The only reported figure found on Lacuna is 99.17% correlation to XCMS at about one minute per file (Algorithmic Learning for Auto-deconvolution of GC-MS Data to Enable Molecular Networking within GNPS). No reported result was found on Lacuna for MSHub's spectral recovery on co-eluting compound pairs, so we will measure it ourselves. Beating MSHub means higher mean cosine similarity between recovered and true spectra, and a higher top-1 library match rate, specifically in the zero-to-half-peak-width offset regime. At the same time we must lose no more than one percentage point of agreement elsewhere and stay within a factor of two of its runtime.
We will also run MS-DIAL, a widely used, manually parameterized deconvolution tool, on the same data. It gets a fixed tuning budget of a few hours of expert parameter adjustment per dataset. This baseline tests whether careful manual tuning already closes the gap.
Two ablations isolate our key ingredient. The first is Leiden community detection on a plain Pearson correlation graph of ion traces, with no ratio test and no persistence filter. The second is MSHub-style NMF applied to the persistence-filtered, ratio-weighted data. Further ablations remove the cross-sample term, which should collapse performance at zero offset, and remove the persistence filter, which should hurt most at low scan rates and on skewed peak fronts.
Why not just…?
Why not just add the persistence filter as preprocessing to MSHub's NMF? This is the most serious threat. Given the proven equivalence between block-model likelihood and constrained NMF (On equivalence of likelihood maximization of stochastic block model and constrained nonnegative matrix factorization), it may capture most of the gain. The ablation that feeds filtered, ratio-weighted data to NMF settles the question. If it matches the full method, we will report that the contribution is the filter and the ratio-stability evidence, not the graph. What the graph might still add is choosing the number of components and restricting which ions each component may use. We expect that to matter where NMF tends to split one compound into chimeric fragments, but this is a hypothesis to test, not a premise.
Why not just run Louvain or Leiden on an ion correlation graph? Raw correlation of intensity traces is high for any two ions that elute together, including ions from different compounds with identical profiles. It therefore carries no information in exactly the case we care about. Modularity-based methods also have a resolution limit that merges small groups, and minor compounds contribute few fragments. The plain-correlation Leiden ablation measures this directly.
Why not just rely on well-tuned AMDIS or MS-DIAL? The MSHub authors document the manual tuning cost that makes these tools impractical at repository scale. More fundamentally, any single-run method faces a rank problem when two compounds share an elution profile, and tuning cannot fix a rank problem. If MS-DIAL under its tuning budget matches us at nonzero offsets but fails at zero offset, our identifiability claim is supported. If it matches us at zero offset, the claim is wrong.
Why not just take the apex spectrum? At the apex, co-eluting spectra are maximally mixed. At low scan rates the apex scan also carries skew from concentration changing during the scan, which is the chromatographic counterpart of the midpoint distortion the vowel study documents. The naive baselines quantify this.
Proposed Experiments
We cannot evaluate spectral recovery on real data alone because no GC-MS benchmark in our sources provides ground truth for co-eluting compounds. The first experiment is therefore simulation. We take electron-ionization reference spectra from a public library, pair compounds of varying spectral similarity, and generate tailed Gaussian elution peaks. We vary retention offset, cross-sample abundance correlation $\rho$, sample count $N$ from 5 to 500, scan rate from 2 to 20 Hz, and noise level. Metrics are spectral cosine to ground truth, top-1 library match, number of false or chimeric components, and abundance correlation with the truth.
The second experiment is a physical spike-in design. Standards chosen to co-elute on a common column, including a derivatized set sharing trimethylsilyl fragments, are run across roughly fifty mixtures with concentrations drawn independently. Some mixtures also include a deliberately correlated subset. Single-standard runs supply true spectra.
The third experiment uses the MSHub breathomics data. With no ground truth, we measure agreement with MSHub and XCMS, the fraction of components matching a library entry, and whether previously unmatched components split into matchable ones.
The decisive check is the zero-offset slice of the simulation and the spike-in. The full method should recover both spectra when $\rho$ is low and should degrade toward single-run baselines as $\rho$ approaches one. The degradation should track $\rho$, not offset. Its separability should also improve with $N$ at roughly the $1/\sqrt{N}$ rate. If recovery does not depend on $\rho$, or the NMF-on-filtered-data ablation matches the full method everywhere, the graph component of the claim fails and we will say so.
References
- Algorithmic Learning for Auto-deconvolution of GC-MS Data to Enable Molecular Networking within GNPS
- Feature-based molecular networking in the GNPS analysis environment
- Separation of Music Signals by Harmonic Structure Modeling
- An Efficient Temporally-Constrained Probabilistic Model for Multiple-Instrument Music Transcription
- Identifying Stable Sections for Formant Frequency Extraction of French Nasal Vowels Based on Difference Thresholds
- Three-sectional-staff characterization of Cantonese level tones
- On equivalence of likelihood maximization of stochastic block model and constrained nonnegative matrix factorization