# FraGNNet: A Deep Probabilistic Model for Mass Spectrum Prediction

Adamo Young  Fei Wang  David Wishart  Bo Wang  Hannes Röst  Russ Greiner

###### Abstract

The process of identifying a compound from its mass spectrum is a critical
step in the analysis of complex mixtures. Typical solutions for the mass
spectrum to compound (MS2C) problem involve matching the unknown spectrum
against a library of known spectrum-molecule pairs, an approach that is
limited by incomplete library coverage. Compound to mass spectrum (C2MS)
models can improve retrieval rates by augmenting real libraries with predicted
spectra. Unfortunately, many existing C2MS models suffer from problems with
prediction resolution, scalability, or interpretability. We develop a new
probabilistic method for C2MS prediction, FraGNNet, that can efficiently and
accurately predict high-resolution spectra. FraGNNet uses a structured latent
space to provide insight into the underlying processes that define the
spectrum. Our model achieves state-of-the-art performance in terms of
prediction error, and surpasses existing C2MS models as a tool for retrieval-
based MS2C.

Machine Learning, ICML

##  1 Introduction

Small molecule identification from complex mixtures is a challenging problem
with far-reaching implications. Determining the chemical composition of a
liquid sample is a critical step not only in the discovery of novel compounds
but also in the recognition of known compounds within new contexts. Tandem
mass spectrometry (MS/MS) is a widely employed tool for molecule
identification, with applications ranking from drug discovery to environmental
science to metabolism research (Dueñas et al., 2022; Gowda & Djukovic, 2014;
Peters, 2011; Lebedev, 2013). Analyzing the set of MS/MS spectra measured from
a liquid sample (such as human blood or plant extract) can reveal important
information about its constitution.

The mass spectrum to compound (MS2C) problem refers to the task of identifying
a molecule from its mass spectrum. Existing MS2C workflows often rely on
comparing the spectrum of an unknown molecule against a library of reference
spectra with known identities. However, spectral libraries are far from
comprehensive, so retrieval-based MS2C might not work even for molecules that
are otherwise well-characterized.

Many computational approaches attack the MS2C problem head-on by attempting to
predict structural features of the molecule directly from the spectrum. Some
models infer high-level chemical properties from the spectrum (Dührkop et al.,
2015; Voronov et al., 2022) and use these features to recommend likely
candidate structures from existing chemical databases (Dührkop et al., 2015,
2019; Goldman et al., 2023b, c) or guide generative models towards potential
matches (Stravs et al., 2022). Other methods formulate the problem as
sequence-to-sequence translation (Butler et al., 2023; Shrivastava et al.,
2021) and attempt to predict a string representation of the structure from the
spectrum.

Compound to mass spectrum (C2MS) prediction can be viewed as an indirect
approach for solving the MS2C problem. Instead of attempting to infer
structural features from the spectrum, C2MS models work by boosting the
effectiveness of existing retrieval-based MS2C workflows. Accurate C2MS models
can predict spectra for millions of molecules that are missing from spectral
libraries, improving coverage by orders of magnitude. This kind of library
augmentation has been a mainstay in retrieval-based MS2C workflows for over a
decade (Wolf et al., 2010; Allen et al., 2015; Wishart et al., 2018) and has
lead to the successful identification of novel compounds (Skinnider et al.,
2021; Wang et al., 2023).

Despite numerous advances, challenges with MS2C remain (Schymanski et al.,
2017), motivating the development of better C2MS models. Ideally, mass spectra
should be predicted at a high resolution, to avoid loss of information. The
prediction model itself must be reasonably fast, so that large-scale library
generation for MS2C is feasible. Finally, model predictions should be
interpretable enough to facilitate manual validation of MS2C identifications.

In this work, we make the following contributions:

  * •

We introduce FraGNNet, a novel method for mass spectrum prediction that
integrates combinatorial bond-breaking methods with principled probabilistic
modelling.

  * •

We argue that this approach meets key requirements in the areas of resolution,
scalability, and interpretability.

  * •

Through comparisons with strong baseline models, we demonstrate that FraGNNet
achieves state-of-the-art performance on spectrum prediction and compound
retrieval tasks.

##  2 Background

At a high level, tandem mass spectrometry provides information about a
molecule’s structure by measuring how it fragments. The experimental process
is outlined in Figure 1. First, molecules in the sample are ionized: at this
stage they are referred to as precursor ions, because they have not yet
undergone fragmentation. In liquid samples, each molecule may become
associated with a charged adduct during ionization. For example, if the adduct
is a hydrogen ion H+, an [M+H]+ precursor ion will form. Following ionization,
the mass to charge ratio ($m/z$) of each precursor ion is subsequently
measured using a mass analyzer. After the precursor $m/z$ values are are
recorded, ions with a particular $m/z$ are selected for further analysis in
the form of fragmentation. The fragmentation process is typically facilitated
by energetic collisions with neutral gas particles, and can be influenced by
experimental parameters such as collision energy.

After fragmentation, the resulting charged ions are sent back to the mass
analyzer for $m/z$ measurement, producing a distribution over fragment $m/z$
values that reflects how often each fragment was formed. Often there are
multiple fragments with nearly identical $m/z$, complicating analysis of the
spectrum. Since the fragmentation process is stochastic, an individual
precursor ion can break down into different fragments with different
probabilities. However, with a sufficiently high precursor ion concentration,
enough independent fragmentations can occur such that sampling error is no
longer a concern. The mass spectrum is defined as the probability distribution
over the fragment $m/z$ values. Since the charge $z$ is usually $+1$ or $-1$
for small molecules, the spectrum can also be interpreted as a distribution
over masses, where each mass is measured in Daltons (Da). Throughout this
work, we focus our analysis on [M+H]+ spectra (where $z$ is always $+1$),
although our methods can easily be extended to other types of precursor ions.

Figure 1: Overview of MS/MS: molecules in the sample are ionized to form
precursors, filtered by precursor $m/z$ (100 Da), and sent for fragmentation.
The fragmentation process stochastically produces fragments with $m/z$ values
of 20, 40, 65 Da. The distribution of precursor and fragment $m/z$ values
forms the spectrum.

The process of fragmentation involves breakage and formation of bonds between
atoms in the molecule. Each fragment is, by definition, composed of a subset
of the atoms in the original precursor. Fragmentation is typically modelled as
a sequence of high-energy reactions. Generally, a reaction involves a charged
fragment (which could be the precursor) being converted into two sub-
fragments, only one of which is charged. The neutral (uncharged) sub-fragment
is described as a neutral loss because it cannot be measured by the mass
spectrometer and ends up getting discarded. The charged sub-fragment may
undergo further reactions to produce additional fragments. The most common
type of reaction is an $\alpha$-Cleavage, which results in the removal of a
single bond. More complicated reactions are possible (McLafferty, 1959;
Biemann, 1962; van Tetering et al., 2024), but in many cases these reactions
can be approximated as sequences of bond breakages.

Mathematically, a mass spectrum $Y$ can be represented as a finite set of
tuples $\left\\{\left(m_{j},P(m_{j})\right)\right\\}_{j}$ where each mass
$m_{j}$ has an associated probability $P(m_{j})$. Individual tuples
$\left(m_{j},P(m_{j})\right)$ are often referred to as peaks, with the mass
$m_{j}$ being called the peak location and the probability $P(m_{j})$ being
called the peak intensity. The problem of spectrum prediction can be
formulated as a standard supervised learning task. The dataset is composed of
$N$ tuples $\left\\{(X_{i},Y_{i})\right\\}_{i=1}^{N}$ where $X_{i}$ is a
molecule and $Y_{i}$ is its associated mass spectrum. The set of masses in a
particular spectrum $Y_{i}$ is denoted as $M_{i}$. The goal of a C2MS model is
to predict $Y_{i}$ from $X_{i}$.

##  3 Related Work

The increasing availability of small molecule MS/MS data has lead to a
proliferation of machine learning models for spectrum prediction. Existing
methods can be broadly grouped into two categories, binned and structured,
based on how they represent the spectrum.

Binned methods approximate the spectrum as a sequence of discrete mass bins
with associated peak intensities. This reduces the spectrum prediction problem
to a vector regression task, which can be readily solved without extensive
domain-specific model customization. Binned approaches generally vary based on
the strategy they employ for encoding the input molecule: multi-layer
percetprons (Wei et al., 2019), 2D (Zhu et al., 2020; Li et al., 2022) and 3D
(Hong et al., 2023) graph neural networks, and graph transformers (Young et
al., 2023) have all been used successfully. However, selecting an appropriate
bin size can be challenging: bins that are too large result in loss of
information, while bins that are too small can be overly sensitive to
measurement error and yield high-dimensional spectrum vectors that are
impractical to model. This presents a fundamental roadblock for the
application of binned models in retrieval-based MS2C.

Structured approaches sidestep the binning problem by modelling the spectrum
as a distribution over chemical formulae, whose masses can be calculated
trivially with extremely high precision. Some methods predict the formula
distribution directly, using either autoregressive formula generation (Goldman
et al., 2023a) or a large fixed formula vocabulary (Murphy et al., 2023).
Others rely on recursive fragmentation (Wang et al., 2021; Zhu & Jonas, 2023)
or autoregressive generation (Goldman et al., 2024) to model a distribution
over fragments, which induces a distribution over formulae. While structured
MS2C models can generate very high resolution spectra, they tend to be slower
than binned approaches due to the increased complexity of the output space.

There is a natural trade-off between a model’s scalability and the amount of
information it can provide about the fragmentation process. Methods that infer
fragment distributions are most informative, since they explicitly describe
how the molecule breaks apart. However, these models tend to involve stronger
priors and more complex prediction schemes (Wang et al., 2021; Zhu & Jonas,
2023; Goldman et al., 2024) to facilitate efficient exploration of the
combinatorial fragment space. FraGNNet takes a pragmatic approach, achieving a
level of interpretability that approaches that of the most sophisticated
fragmentation models, while maintaining high performance and scalability (see
Appendix C).

Figure 2: Overview of the FraGNNet C2MS model. The input molecule ($G$, red
box) is processed into an approximate Fragmentation DAG
($G_{\mathcal{F}^{d}}$, yellow box) and independently embedded by the Molecule
GNN ($g_{\theta}^{\texttt{MOL}}$, orange box). Information from the DAG is
combined with the molecule embedding and processed by the Fragment GNN
($g_{\theta}^{\texttt{FRAG}}$, blue box). Output MLPs (brown boxes) are
applied to each fragment node $n$ in the DAG to predict a per-node
distribution over formulae (purple boxes), which can be mapped to a
distribution over masses (green boxes) and summed across nodes to create the
MS/MS spectrum.

##  4 Methods

###  4.1 Overview

The goal of our method is to predict a high resolution MS/MS spectrum based on
an input molecular structure. The model works in two stages: first, a
heuristic bond-breaking algorithm (Section 4.2) generates a set of plausible
molecule fragments. Then, a probabilistic model (Section 4.3) parameterized by
a graph neural network (Section 4.4) predicts a distribution over these
fragments. The fragment distribution induces a distribution over chemical
formulae, which is converted to a mass spectrum by mapping formula masses.
This approach allows for extremely high resolution peak predictions with
built-in formula and fragment annotations.

###  4.2 Recursive Fragmentation

A small organic molecule can be represented as an undirected graph $G=(V,E)$.
Each node $a\in V$ represents an atom in the molecule with an associated
element label $\omega_{a}\in\Omega$ (where
$\Omega=\left\\{\ce{C},\ce{H},\ce{N},\ce{O},\ce{P},\ce{S},\ldots\right\\}$ is
a finite set of common elements) and each edge $b\in E$ represents a covalent
bond between atoms. Let $S(G)$ be the set of connected subgraphs of the graph
$G$.

######  Definition 4.1.

The graph $\mathcal{F}(G)=\left(\mathcal{F}_{1}(V),\mathcal{F}_{2}(E)\right)$
is called a fragmentation DAG with respect to the graph $G$ if the following
properties hold:

  1. 1.

Each node $n\in\mathcal{F}_{1}(V)$ maps to a connected subgraph $G_{n}\in
S(G)$

  2. 2.

A directed edge $e\in\mathcal{F}_{2}(E)$ from node $u\in\mathcal{F}_{1}(V)$ to
node $v\in\mathcal{F}_{1}(V)$ can exist if and only if $G_{v}\in S(G)$ is a
connected subgraph of $G_{u}\in S(G)$.

Note that the root node $r$ of $\mathcal{F}(G)$ always maps to the original
graph $G$, and the leaves of $\mathcal{F}(G)$ correspond to individual atoms
$a\in V$.

Most fragments in a mass spectrum can be modelled as products of a series of
bond breakages. Such fragments will thus appear as nodes
$n\in\mathcal{F}_{1}(V)$, and their fragmentation history can be represented
as a path from the root $r$ to $n$. It is possible to derive a set of chemical
formulae $F(\mathcal{F}(G))=\left\\{f_{n}:n\in\mathcal{F}_{1}(V)\right\\}$,
where each formula $f_{n}$ is a $|\Omega|$-dimensional vector representing the
element counts of atoms in $G_{n}$. This set $F(\mathcal{F}(G))$ can be used
to calculate the set of possible peak locations in the spectrum,
$M(G)=\left\\{m_{n}:n\in\mathcal{F}_{1}(V)\right\\}$ where
$m_{n}=\text{mass}(f_{n})$ is the mass of formula $f_{n}$.

The fragmentation DAG $\mathcal{F}(G)$ can be a useful tool for spectrum
prediction (Wang et al., 2021; Goldman et al., 2023a, 2024), providing
information about peak locations and relationships between fragments in the
spectrum. However, computing $\mathcal{F}(G)$ from $G$ through exhaustive edge
removal can be expensive, requiring on the order of
$\mathcal{O}\left(2^{|E|}\right)$ operations. Inspired by previous approaches
from the literature (Wolf et al., 2010; Ruttkies et al., 2016; Allen et al.,
2015; Ridder et al., 2014; Goldman et al., 2024), we approximate
$\mathcal{F}(G)$ using a few simplifying assumptions.

######  Definition 4.2.

The graph $\mathcal{H}(G)=\left(\mathcal{H}_{1}(V),\mathcal{H}_{2}(E)\right)$
is called a heavy atom skeleton of $G$ if $\mathcal{H}(G)$ is the largest
connected subgraph of $G$ such that $\omega_{a}\neq\ce{H}$ (hydrogen) for all
$a\in\mathcal{H}_{1}(V)$.

Since $|\mathcal{H}_{2}(E)|$ is often smaller than $|E|$ by a factor of 2-3,
calculating $\mathcal{F}(\mathcal{H}(G))$ is considerably faster than
calculating $\mathcal{F}(G)$. We employ a recursive edge removal (i.e. bond-
breaking) algorithm that only considers nodes that are at most $d$ hops away
from the root $r$, producing a connected subgraph
$\mathcal{F}^{d}(\mathcal{H}(G))$.

For simplicity of notation, we refer to $\mathcal{F}^{d}(\mathcal{H}(G))$ as
$G_{\mathcal{F}^{d}}$, with vertex set $V_{\mathcal{F}^{d}}$ and edge set
$E_{\mathcal{F}^{d}}$. Since, by definition, each node $n\in
V_{\mathcal{F}^{d}}$ corresponds to a subgraph $G_{n}\in S(G)$ that does not
contain any hydrogen atoms, we employ a heuristic to model the possible number
of hydrogens associated with each $G_{n}$. Let $h_{n}$ be the number of
hydrogen atoms in $G$ that are connected to the subgraph $G_{n}$. We define
the set $\left\\{h_{n}-j,\ldots,h_{n}+j\right\\}$ as the range of hydrogen
counts for the subgraph $G_{n}$, where $j$ is a tolerance parameter.

This induces a set of possible formulae
$\left\\{f_{n}^{-j},\ldots,f_{n}^{j}\right\\}$ and associated masses
$\left\\{m_{n}^{-j},\ldots,m_{n}^{j}\right\\}$, where $f_{n}^{i}$ is a formula
with the same heavy atom counts as $f_{n}$ and $h_{n}+i$ hydrogens, and
$m_{n}^{i}$ is its corresponding mass. Hydrogen transfers are common in
fragmentation, so allowing for flexibility in the hydrogen counts can result
in a more representative set of formulae.

######  Definition 4.3.

The set

$\hat{M}(G,d,j)=\bigcup_{n\in
V_{\mathcal{F}^{d}}}\left\\{m_{n}^{-j},\ldots,m_{n}^{j}\right\\}$

is the set of masses derived from the approximate heavy-atom fragmentation DAG
$G_{\mathcal{F}^{d}}$ with hydrogen tolerance $j$.

Empirically, we find that calculating $\hat{M}(G,d,j)$ (Definition 4.3) with
$d\in\left\\{3,4\right\\}$ and $j=4$ can effectively capture most of the total
peak intensity in real MS data (see Appendix B).

###  4.3 Probabilistic Formulation

Our model can be interpreted as a structured latent variable model whose
latent distributions depend on a molecular graph $G$ and its approximate
fragmentation DAG $G_{\mathcal{F}^{d}}$.

To begin, we define the following latent probability distributions:

######  Definition 4.4.

Let $P_{\theta}(n)$ be a discrete finite probability distribution over the DAG
nodes $n\in V_{\mathcal{F}^{d}}$, parameterized by a neural network
$g_{\theta}$.

######  Definition 4.5.

Let $P_{\theta}(f|n)$ be a discrete finite conditional distribution between
DAG nodes $n\in V_{\mathcal{F}^{d}}$ and associated formulae
$\left\\{f_{n}^{-j},\ldots,f_{n}^{j}\right\\}$, parameterized by a neural
network $g_{\theta}$.

Both distributions depend implicitly on the molecular graph $G$, but for
clarity of notation we have omitted this. Note that for each node $n$,
$P_{\theta}(f|n)$ has support over $2j+1$ formulae.111There is additional
filtering for chemical validity which may mask out some formulae, but for
clarity this has been omitted.

The joint distribution $P_{\theta}(n,f)\,=\,P_{\theta}(n)\,P_{\theta}(f|n)$
can be loosely interpreted as identifying which substructures are generated
during fragmentation, with $P_{\theta}(n)$ modelling the heavy atom structures
of the probable fragments and $P_{\theta}(f|n)$ identifying the number of
hydrogens associated with each of those fragments.

By marginalizing $P_{\theta}(n,f)$ over the nodes $n$, it is possible to
calculate a distribution over formulae $P_{\theta}(f)$. Since each formula $f$
has an associated mass, the discrete distribution $P_{\theta}(f)$ can be
easily converted to a continuous distribution $P_{\theta}(m)$ over masses.
Following (Allen et al., 2015), we formulate $P_{\theta}(m)$ as a mixture of
univariate Gaussians as outlined in Equation 1:

$\displaystyle P_{\theta}(m)$ $\displaystyle=\ \sum_{f}P_{\theta}(f)\ P(m|f)$
(1) $\displaystyle=\ \sum_{f}P_{\theta}(f)\ \mathcal{N}(\mu(f),\sigma(f))$

The conditional $P(m|f)$ is a narrow truncated Gaussian centered on the
formula mass, $\mu(f)=\text{mass}(f)$, with variance $\sigma(f)$ proportional
to $f$ and truncation occurring at $\pm 1$ standard deviation from the mean.
This Gaussian model approximates the typical error distribution of the mass
analyzer (Allen et al., 2015). At inference time it is convenient to
approximate $P(m)$ as a discrete distribution with
$P(m|f)=\delta(\text{mass}(f))$, where $\delta$ is the Dirac delta function.

It is possible to calculate another distribution $P_{\theta}(n|f)$ using Bayes
Theorem. Intuitively $P_{\theta}(n|f)$ identifies which fragments $n$ are
contributing to a predicted peak centered at formula $f$ – for this reason we
refer to it as the peak annotation distribution. While not directly used to
generate the spectrum, $P_{\theta}(n|f)$ can be helpful for interpreting model
behaviour (see Section 5.3, Figure 3).

In Appendix D, we describe alternate versions of $P_{\theta}(n)$,
$P_{\theta}(f|n)$, and $P_{\theta}(n|f)$ that account for fragment subgraph
isomorphism.

###  4.4 Neural Network Parameterization

The distributions $P_{\theta}(n)$ and $P_{\theta}(f|n)$ are parameterized by a
two-stage graph neural network (GNN, Battaglia et al. 2018) as defined by
Equation 2:

$g_{\theta}(G,G_{\mathcal{F}^{d}})\ =\
g_{\theta}^{\texttt{FRAG}}\left(\,g_{\theta}^{\texttt{MOL}}(G),\,G_{\mathcal{F}^{d}}\,\right)$
(2)

The first stage $g_{\theta}^{\texttt{MOL}}$, called the Molecule GNN, operates
on the input molecular graph $G$. The second stage
$g_{\theta}^{\texttt{FRAG}}$, called the Fragment GNN, combines information
from the fragmentation DAG and the molecule embeddings to predict the
distributions $P_{\theta}(n)$ and $P_{\theta}(f|n)$.

####  4.4.1 Molecule GNN

The Molecule GNN $g_{\theta}^{\texttt{MOL}}$ takes the input molecular graph
$G$ and outputs embeddings for the atoms in the graph. The atom embeddings
$\bar{h}_{a}^{(0)}$ and bond embeddings $\bar{h}_{b}^{(0)}$ are initialized
with specific features from $G$ (see Appendix E).

GNN models work by iteratively updating node states through the aggregation of
neighbourhood information. $g_{\theta}^{\texttt{MOL}}$ uses the GINE
architecture (Xu et al., 2018; Fey & Lenssen, 2019), which incorporates both
node and edge information in its updates. The GINE update rule is given by
equation 3, where $l$ is the GNN layer index, $l\in\\{1,\ldots,L_{1}\\}$, and
$q_{\theta}$ is a standard multi-layer perceptron (MLP):

$\bar{h}_{a}^{(l+1)}=q_{\theta}\left(\bar{h}_{a}^{(l)}+\sum_{u\in\mathbb{N}(a)}\text{ReLU}(\bar{h}_{u}^{(l)}+\bar{h}_{b}^{(l)})\right)$
(3)

The final atom embeddings $\bar{h}_{a}^{(L_{1})}$ are subsequently passed to
the Fragment GNN $g_{\theta}^{\texttt{FRAG}}$ for further processing.

####  4.4.2 Fragment GNN

The Fragment GNN $g_{\theta}^{\texttt{FRAG}}$ is another GINE network that
propagates information along the approximate fragmentation DAG. Each DAG node
$n\in V_{\mathcal{F}^{d}}$ is featurized using information about its
associated subgraph $G_{n}$, precisely described in Equations 4 and 5. The
vector $\bar{h}_{n}^{(0)}$ is a concatenation of three terms:
$\hat{h}_{n}^{s}$ is the average atom embedding for atoms in $G_{n}$;
$\hat{h}_{n}^{f}$ is an embedding of the subgraph formula $f_{n}$; and
$\hat{h}_{n}^{d}$ is an embedding of the depth in the DAG at which node $n$ is
located.

$\displaystyle\bar{h}_{n}^{(0)}\ $ $\displaystyle=\ \hat{h}_{n}^{s}\ \
\mathbin{\|}\ \hat{h}_{n}^{f}\ \mathbin{\|}\ \hat{h}_{n}^{d}$ (4)
$\displaystyle\hat{h}_{n}^{s}\ $ $\displaystyle=\ \frac{1}{|V_{n}|}\sum_{a\in
V_{n}}\bar{h}_{a}^{(L_{1})}$ (5)

The edge embeddings $\bar{h}_{e}^{(0)}$ are also initialized with subgraph
information: they capture differences between adjacent DAG nodes. Refer to
Appendix F for full details.

The DAG nodes are processed by the Fragment GNN in a manner that is similar to
Equation 3. After $L_{2}$ layers of processing, a small output MLP is applied
to each node embedding $\bar{h}_{n}^{(L_{2})}$, producing a $2j+1$ dimensional
vector representing the unnormalized logits for $P_{\theta}(n,f_{n}^{i})$ for
each $i\in\left\\{-j,\ldots,j\right\\}$. The other latent distributions in
Section 4.3 are calculated from the joint through normalization,
marginalization, and application of Bayes Theorem.

While performing model ablations (see Appendix H), we discovered that edge
information could be omitted without degradation in performance, allowing for
2x faster training and inference. As a result, the experiments in Section 5
use a variant of $g_{\theta}^{FRAG}$ that excludes the neighbourhood
aggregation term from the GINE update.

Figure 3: Example Spectrum Prediction with Fragment Annotations: A real
spectrum (green) for a molecule from the test set, Adiphenine, is compared
with its corresponding FraGNNet-D4 prediction (red). The five most intense
peak predictions are annotated with formulae and up to three probable fragment
structures. The structure annotation for peak 5 clearly corresponds to the
precursor ion (i.e. the entire graph). The model is uncertain about the
annotation for peak 4, giving equal probability to related structures.

###  4.5 Loss Function

We fit the parameters of the model $\theta$ with maximum likelihood
estimation, using stochastic gradient descent. The loss function is based on
the negative log-likelihood of the data, defined in Equation 6:

$\mathcal{L}_{\texttt{NLL}}(\theta)\ =\ \frac{1}{N}\sum_{i=1}^{N}\sum_{m\in
M_{i}}-P_{i}(m)\log P_{\theta}(m)$ (6)

For each spectrum, a subset of the peak masses $M^{\text{OS}}_{i}\subseteq
M_{i}$ are defined to be Outside of the Support (OS) if they are far enough
from away the predicted set of masses $\hat{M}(G_{i},d,j)$ such that their
predicted probability is 0 (Equation 7). The rest of the masses
$M^{\text{IS}}_{i}=M_{i}-M_{i}^{OS}$ are deemed to be Inside of the Support
(IS).

$P_{i}(M^{\text{OS}}_{i})=\sum_{m\in M_{i}:P_{\theta}(m)=0}P_{i}(m)$ (7)

Modelling the OS probability can provide useful information about the
reliability of the predicted spectrum. With slight modification, FraGNNet can
be adapted to predict $P_{\theta}(M^{\text{OS}}_{i})$, an estimation of
$P_{i}(M^{\text{OS}}_{i})$. Adjusting the loss function
$\mathcal{L}_{\texttt{NLL}}(\theta)$ to incorporate an OS cross-entropy term
yields Equation 8:

$\small\begin{split}\mathcal{L}(\theta)\ =\
\frac{1}{N}\sum_{i=1}^{N}\sum_{m\in M_{i}^{IS}}&-P_{i}(m)\ \log
P_{\theta}(m)\\\ &-P_{i}(M^{\text{OS}}_{i})\ \log
P_{\theta}(M^{\text{OS}}_{i})\end{split}$ (8)

In cases where $P_{i}(M^{\text{OS}}_{i})>0$, perfectly optimizing
$\mathcal{L}_{\texttt{NLL}}(\theta)$ yields predictions which have
(incorrectly) redistributed $P_{i}(M^{\text{OS}}_{i})$ to other peaks. This
undesirable behaviour can be avoided by minimizing $\mathcal{L}(\theta)$
instead.

###  4.6 Latent Entropy Regularization

Latent entropies can provide insight into the model’s understanding of the
fragmentation process. $H_{\theta}(n)$ describes the diversity of fragment
skeletons that were generated; $H_{\theta}(f|n)$ describes variability in
hydrogen configurations for each skeleton; $H_{\theta}(n|f)$ describes
variability in peak annotations.

Since entropy is differentiable, joint optimization of latent entropy and
prediction error is possible using gradient-based methods. The normalized
entropy $\hat{H}(x)=H(x)/\log(|X|)$ is preferable for optimization since it
accounts for differences in latent support size caused by variations in the
size of the input molecule. Incorporating normalized entropy into the
objective function, as demonstrated in Equation 9, effectively imposes entropy
regularization on the latent distributions:

$\begin{split}\mathcal{L}_{\texttt{REG}}(\theta)\ &=\ \mathcal{L}(\theta)\\\
&+\ \alpha_{n}\,\hat{H}_{\theta}(n)\ +\ \alpha_{f}\,\hat{H}_{\theta}(f)\\\ &+\
\alpha_{f|n}\,\hat{H}_{\theta}(f|n)\ +\
\alpha_{n|f}\,\hat{H}_{\theta}(n|f)\end{split}$ (9)

The tunable hyperparameters
$\\{\alpha_{n},\alpha_{f},\alpha_{f|n},\alpha_{n|f}\\}$ control the influence
of the entropy regularizers. Since $\mathcal{L}_{\texttt{REG}}(\theta)$ is
minimized, setting $\alpha_{x}<0$ will maximize the corresponding normalized
entropy $\hat{H}_{\theta}(x)$, and vice versa. Entropy regularization can be
useful when assessing consistency of peak annotations, as demonstrated in
Section 5.3.

Table 1: Spectrum Prediction Performance on the NIST20 Dataset. Means and
standard deviations are reported for 5 random seeds, with best scores in bold.
As NEIMS and MassFormer are binned models, they cannot be scored with
$COS_{\text{HUN}}$ and have no notion of $P(M^{\text{OS}})$. ICEBERG and
ICEBERG-ADV do not predict $P_{\theta}(M^{\text{OS}})$ so they cannot be
scored with $|P(M^{\text{OS}})-P_{\theta}(M^{\text{OS}})|$.
Split | Model | $COS_{0.01}\Uparrow$ | $COS_{\text{HUN}}\Uparrow$ | $P(M^{\text{OS}})\Downarrow$ | $|P(M^{\text{OS}})-P_{\theta}(M^{\text{OS}})|\Downarrow$
---|---|---|---|---|---
InChIKey | FragNet-D4 | $\bm{0.717\pm 0.001}$ | $\bm{0.691\pm 0.001}$ | $\bm{0.097\pm 0.000}$ | $\bm{0.053\pm 0.002}$
InChIKey | FragNet-D3 | $0.702\pm 0.002$ | $0.675\pm 0.001$ | $0.171\pm 0.000$ | $0.078\pm 0.001$
InChIKey | Iceberg-ADV | $0.702\pm 0.002$ | $0.666\pm 0.002$ | $0.158\pm 0.000$ | -
InChIKey | Iceberg | $0.681\pm 0.002$ | $0.645\pm 0.002$ | $0.178\pm 0.000$ | -
InChIKey | MassFormer | $0.653\pm 0.003$ | - | - | -
InChIKey | NEIMS | $0.642\pm 0.001$ | - | - | -
Scaffold | FragNet-D4 | $\bm{0.654\pm 0.003}$ | $\bm{0.630\pm 0.004}$ | $\bm{0.109\pm 0.000}$ | $\bm{0.063\pm 0.001}$
Scaffold | FragNet-D3 | $0.637\pm 0.003$ | $0.612\pm 0.003$ | $0.192\pm 0.000$ | $0.095\pm 0.002$
Scaffold | Iceberg-ADV | $0.643\pm 0.002$ | $0.611\pm 0.002$ | $0.175\pm 0.000$ | -
Scaffold | Iceberg | $0.618\pm 0.001$ | $0.586\pm 0.001$ | $0.200\pm 0.000$ | -
Scaffold | MassFormer | $0.600\pm 0.001$ | - | - | -
Scaffold | NEIMS | $0.582\pm 0.003$ | - | - | -

##  5 Experiments

###  5.1 Spectrum Prediction (C2MS)

FraGNNet’s C2MS performance is evaluated on a heldout portion of the NIST20
MS/MS dataset (Appendix I), to allow for comparison with other binned and
structured prediction models from the literature.

ICEBERG (Goldman et al., 2024) is a structured method for high-resolution
spectrum prediction that uses a two-stage model. The first stage
autoregressively predicts a set of fragments, and the second stage predicts a
mapping between those fragments and the peaks in the spectrum (see Appendix
C). The stages are trained independently, with the first stage approximating
the output of a heuristic fragmenter, MAGMa (Ridder et al., 2014), that uses
signals from the spectrum to find a minimal set of fragments that explain the
peaks. We introduce ICEBERG-ADV (advantaged), a variant of ICEBERG that
replaces the first stage of the model with the exact MAGMa output. This
modification removes sampling error in the fragment generation process,
creating an artificially easier learning problem that should result in better
performance. We emphasize that ICEBERG-ADV is only suitable for benchmarking:
in most realistic C2MS problems ground truth spectra are not available at
inference time, meaning that MAGMa cannot be applied.

The other baseline models, MassFormer (Young et al., 2023) and NEIMS (Wei et
al., 2019), both predict binned spectra at a lower resolution. The former uses
a pretrained graph transformer model (Ying et al., 2021) to encode the
molecule, while the latter relies on domain-specific chemical fingerprint
representations (Rogers & Hahn, 2010).

The results are summarized in Table 1. FraGNNet-D4, a version of our model
that uses a $d=4$ approximation of the fragmentation DAG, clearly outperforms
other models in terms of cosine similarity. The binned spectrum approaches
(NEIMS and MassFormer) score much worse in terms of cosine hungarian
similarity (Appendix G) due to the limited resolution afforded by their binned
spectrum representation.

Increasing fragmentation depth from $d=3$ to $d=4$ seems to have a positive
impact on performance. Lower $P(M^{\text{OS}})$ with FraGNNet-D4 is indicative
of better mass coverage when compared to FraGNNet-D3, leading to better
similarity scores. Both models are able to estimate $P(M^{\text{OS}})$ to some
degree, suggesting that FraGNNet can identify situations at inference time
where its fragmentation model will be inaccurate.

###  5.2 Compound Retrieval (MS2C)

FraGNNet was also evaluated in a retrieval-based MS2C task. Our setup is
similar to previous methods (Goldman et al., 2024; Murphy et al., 2023): for
each $(X_{i},Y_{i})$ in the NIST20 Test set (roughly 4000 pairs, Appendix I) a
candidate set $\mathcal{C}_{i}$ is constructed from $X_{i}$ and 49 other
compounds sampled from PubChem (Kim et al., 2019). Each
$C_{i}\in\mathcal{C}_{i}-\left\\{X_{i}\right\\}$ is selected to have high
chemical similarity with $X_{i}$ as measured by Tanimoto similarity between
chemical fingerprints (Rogers & Hahn, 2010). The C2MS models are tasked with
predicting a set of spectra $\hat{Y}_{i}$ for molecules
$C_{i}\in\mathcal{C}_{i}$. The spectra $\hat{Y}_{i}$ are ranked by their
cosine hungarian similarity (Appendix G) with the real spectrum $Y_{i}$,
inducing a ranking on the molecules $C_{i}$. The models are scored based on
their ability to correctly rank $X_{i}$ in the Top-$k$ for
$k\in\\{1,3,5,10\\}$. FraGNNet outperform all baseline models for for all
values of $k$ (see Tables 2 and 8).

Table 2: Compound Retrieval (InChIKey Split): Top-$k$ Accuracy for different
values of $k$, best scores are in bold.

Model |  Top-1 $\Uparrow$ |  Top-3 $\Uparrow$ |  Top-5 $\Uparrow$ |  Top-10 $\Uparrow$
---|---|---|---|---
FraGNNet-D4 | $\bm{23.8\%}$ | $\bm{50.4\%}$ | $\bm{65.2\%}$ | $\bm{83.1\%}$
FraGNNet-D3 | $23.3\%$ | $50.1\%$ | $63.8\%$ | $81.2\%$
ICEBERG | $23.0\%$ | $48.5\%$ | $62.1\%$ | $78.9\%$
MassFormer | $12.0\%$ | $30.4\%$ | $43.0\%$ | $62.9\%$
NEIMS | $13.6\%$ | $32.3\%$ | $43.5\%$ | $62.7\%$

###  5.3 Annotation Consistency

When interpreting mass spectral data, practitioners will annotate each peak in
the spectrum with a substructure to explain what happened during
fragmentation. FraGNNet’s latent distribution $P_{\theta}(n|f)$ provides a map
from formulae $f$ to DAG nodes $n$ and their associated subgraphs $G_{n}$.
$P_{\theta}(n|f)$ can be interpreted as a peak annotation distribution (see
Figure 3 for an example), with the mode
$\operatorname*{arg\,max}_{n}P_{\theta}(n|f)$ identifying the subgraph that
contributes most to the peak located at $\text{mass}(f)$.

It is difficult to evaluate the correctness of peak annotations (human-derived
or otherwise) without additional experimental analysis (van Tetering et al.,
2024). However, we can measure the consistency of annotations across models
that perform equally well. Inter-model differences in latent distributions
that do not affect overall C2MS performance are indicative of ambiguity in the
fragmentation process. Similar to how ensembles can be used to estimate
prediction uncertainty (Lakshminarayanan et al., 2017), identifying annotation
inconsistencies across a group of models with comparable average performance
could be a useful strategy for flagging unreliable annotations.

To investigate annotation consistency, we trained two separate ensembles of 15
FraGNNet-D3 models. The Standard Ensemble is composed of models without
entropy regularization ($\alpha_{n|f}=0$). The Entropy Ensemble is composed of
five models with high entropy ($\alpha_{n|f}<0$), five models with low entropy
($\alpha_{n|f}>0$), and five models without regularization ($\alpha_{n|f}=0$).
Aside from entropy regularization, all models use the same optimization
hyperparameters and only differ by initialization seed.

Table 3: Ensemble Annotation Consistency Comparison: CV is coefficient of
variation, CONS is annotation consensus, MAJ is agreement with majority
annotation.

Metric | Entropy Ens | Standard Ens
---|---|---
Mean $COS_{\text{HUN}}$ | $0.667$ | $0.669$
CV $COS_{\text{HUN}}$ | $0.116$ | $0.115$
Mean $\hat{H}_{\theta}(n|f)$ | $0.464$ | $0.450$
CV $\hat{H}_{\theta}(n|f)$ | $0.512$ | $0.216$
Cons $\operatorname*{arg\,max}_{n}P_{\theta}(n|f)$ | $0.745$ | $0.818$
Maj $\operatorname*{arg\,max}_{n}P_{\theta}(n|f)$ | $0.922$ | $0.939$

Table 3 demonstrates how these two ensembles achieve comparable average cosine
similarity, but differ significantly in annotation distribution
$P_{\theta}(n|f)$. The Entropy Ensemble experiences more variability in latent
entropy $\hat{H}_{\theta}(n|f)$, with a coefficient of variation that is
roughly twice as large as that of the Standard Ensemble. Trends in entropy are
reflected in annotation agreement: the Entropy Ensemble has a lower average
rate of annotation consensus than the Standard Ensemble (0.745 vs 0.818).
Additionally, the average fraction of individual models that agree with the
ensemble majority vote is lower in the Entropy Ensemble (0.922 vs 0.939).
These trends are also reflected in the isomorphic annotation distribution
$P_{\theta}(\tilde{n}|f)$ (Appendix J), although the entropy variations and
resulting annotation disagreements are lower in comparison to those associated
with $P_{\theta}(n|f)$.

Altogether, these results demonstrate how ensembles can be used to identify
unreliable FraGNNet structure annotations. Furthermore, they suggest that
ensembling models with different latent entropies can improve sensitivity to
annotation ambiguity without sacrificing performance.

##  6 Discussion

In this work we introduce FraGNNet, a deep probabilistic model for spectrum
prediction. Our work shows that pairing combinatorial fragmentation with
neural networks can achieve state-of-the-art C2MS performance. FraGNNet is
unique in its interpretable latent representation of the fragmentation DAG.
Features such as OS prediction and tunable entropy regularization further
differentiate it from existing models. Strong results in the compound
retrieval task demonstrate potential utility in MS2C applications.

Several aspects of our approach could be improved. The DAG calculation is a
computational bottleneck, requiring recursive bond-removal operations.
Additionally, the presence of OS peaks are a reflection of an imperfect
fragmentation model, which cannot be fixed with better optimization or more
data. Complex reactions like cyclizations are difficult to model, since they
introduce an explosion in the size of the fragment space. Developing a method
that samples chemical reactions could be a viable solution for identifying
fragments that cannot be generated by simple bond-breaking. Alternatively,
ensembling FraGNNet with a more flexible C2MS model, such as a binned
predictor, could be an effective method of capturing OS peaks. Finally, adding
support for unmerged spectrum prediction and increasing precursor adduct
coverage are straightforward improvements that would broaden FraGNNet’s
practical applicability to MS2C tasks.

## References

  * Allen et al. (2015) Allen, F., Greiner, R., and Wishart, D.  Competitive fragmentation modeling of ESI-MS/MS spectra for putative metabolite identification.  _Metabolomics_ , 11(1):98–110, February 2015.  ISSN 1573-3890.  doi: 10.1007/s11306-014-0676-4.  URL https://doi.org/10.1007/s11306-014-0676-4.
  * Battaglia et al. (2018) Battaglia, P. W., Hamrick, J. B., Bapst, V., Sanchez-Gonzalez, A., Zambaldi, V., Malinowski, M., Tacchetti, A., Raposo, D., Santoro, A., Faulkner, R., Gulcehre, C., Song, F., Ballard, A., Gilmer, J., Dahl, G., Vaswani, A., Allen, K., Nash, C., Langston, V., Dyer, C., Heess, N., Wierstra, D., Kohli, P., Botvinick, M., Vinyals, O., Li, Y., and Pascanu, R.  Relational inductive biases, deep learning, and graph networks.  _arXiv:1806.01261 [cs, stat]_ , October 2018.  URL http://arxiv.org/abs/1806.01261.
  * Behnel et al. (2011) Behnel, S., Bradshaw, R., Citro, C., Dalcin, L., Seljebotn, D. S., and Smith, K.  Cython: The best of both worlds.  _Computing in Science & Engineering_, 13(2):31–39, 2011.
  * Bemis & Murcko (1996) Bemis, G. W. and Murcko, M. A.  The Properties of Known Drugs. 1. Molecular Frameworks.  _Journal of Medicinal Chemistry_ , 39(15):2887–2893, January 1996.  ISSN 0022-2623.  doi: 10.1021/jm9602928.  URL https://doi.org/10.1021/jm9602928.
  * Biemann (1962) Biemann, K.  The application of mass spectrometry in organic chemistry: Determination of the structure of natural products.  _Angewandte Chemie International Edition in English_ , 1(2):98–111, 1962.  doi: https://doi.org/10.1002/anie.196200981.  URL https://onlinelibrary.wiley.com/doi/abs/10.1002/anie.196200981.
  * Biewald (2020) Biewald, L.  Experiment tracking with weights and biases, 2020.  URL https://www.wandb.com/.  Software available from wandb.com.
  * Butler et al. (2023) Butler, T., Frandsen, A., Lightheart, R., Bargh, B., Taylor, J., Bollerman, T. J., Kerby, T., West, K., Voronov, G., Moon, K., Kind, T., Dorrestein, P., Allen, A., Colluru, V., and Healey, D.  MS2mol: A transformer model for illuminating dark chemical space from mass spectra, 2023.  URL https://chemrxiv.org/engage/chemrxiv/article-details/6492507524989702c2b082fc.
  * Dueñas et al. (2022) Dueñas, M. E., Peltier‐Heap, R. E., Leveridge, M., Annan, R. S., Büttner, F. H., and Trost, M.  Advances in high‐throughput mass spectrometry in drug discovery.  _EMBO Molecular Medicine_ , 15(1):e14850, December 2022.  ISSN 1757-4676.  doi: 10.15252/emmm.202114850.  URL https://www.ncbi.nlm.nih.gov/pmc/articles/PMC9832828/.
  * Dührkop et al. (2015) Dührkop, K., Shen, H., Meusel, M., Rousu, J., and Böcker, S.  Searching molecular structure databases with tandem mass spectra using csi:fingerid.  _Proceedings of the National Academy of Sciences_ , 112(41):12580–12585, 2015.  ISSN 0027-8424.  doi: 10.1073/pnas.1509788112.  URL https://www.pnas.org/content/112/41/12580.
  * Durant et al. (2002) Durant, J. L., Leland, B. A., Henry, D. R., and Nourse, J. G.  Reoptimization of MDL keys for use in drug discovery.  _Journal of Chemical Information and Computer Sciences_ , 42(6):1273–1280, 2002.  ISSN 0095-2338.  doi: 10.1021/ci010132r.
  * Dührkop et al. (2019) Dührkop, K., Fleischauer, M., Ludwig, M., Aksenov, A. A., Melnik, A. V., Meusel, M., Dorrestein, P. C., Rousu, J., and Böcker, S.  SIRIUS 4: a rapid tool for turning tandem mass spectra into metabolite structure information.  _Nature Methods_ , 16(4):299–302, April 2019.  ISSN 1548-7105.  doi: 10.1038/s41592-019-0344-8.  URL http://www.nature.com/articles/s41592-019-0344-8.
  * Falcon & The PyTorch Lightning team (2019) Falcon, W. and The PyTorch Lightning team.  PyTorch Lightning, March 2019.  URL https://github.com/Lightning-AI/lightning.
  * Fey & Lenssen (2019) Fey, M. and Lenssen, J. E.  Fast graph representation learning with pytorch geometric.  _CoRR_ , abs/1903.02428, 2019.  URL http://arxiv.org/abs/1903.02428.
  * Goldman et al. (2023a) Goldman, S., Bradshaw, J., Xin, J., and Coley, C.  Prefix-Tree Decoding for Predicting Mass Spectra from Molecules.  In Oh, A., Neumann, T., Globerson, A., Saenko, K., Hardt, M., and Levine, S. (eds.), _Advances in Neural Information Processing Systems_ , volume 36, pp. 48548–48572. Curran Associates, Inc., 2023a.  URL https://proceedings.neurips.cc/paper_files/paper/2023/file/97d596ca21d0751ba2c633bad696cf7f-Paper-Conference.pdf.
  * Goldman et al. (2023b) Goldman, S., Wohlwend, J., Stražar, M., Haroush, G., Xavier, R. J., and Coley, C. W.  Annotating metabolite mass spectra with domain-inspired chemical formula transformers.  _Nature Machine Intelligence_ , 5(9):965–979, 2023b.  ISSN 2522-5839.  doi: 10.1038/s42256-023-00708-3.  URL https://www.nature.com/articles/s42256-023-00708-3.  Number: 9 Publisher: Nature Publishing Group.
  * Goldman et al. (2023c) Goldman, S., Xin, J., Provenzano, J., and Coley, C. W.  MIST-CF: Chemical Formula Inference from Tandem Mass Spectra.  _Journal of Chemical Information and Modeling_ , September 2023c.  ISSN 1549-9596.  doi: 10.1021/acs.jcim.3c01082.  URL https://doi.org/10.1021/acs.jcim.3c01082.  Publisher: American Chemical Society.
  * Goldman et al. (2024) Goldman, S., Li, J., and Coley, C. W.  Generating Molecular Fragmentation Graphs with Autoregressive Neural Networks.  _Analytical Chemistry_ , 96(8):3419–3428, February 2024.  ISSN 0003-2700.  doi: 10.1021/acs.analchem.3c04654.  URL https://doi.org/10.1021/acs.analchem.3c04654.  Publisher: American Chemical Society.
  * Gowda & Djukovic (2014) Gowda, G. N. and Djukovic, D.  Overview of Mass Spectrometry-Based Metabolomics: Opportunities and Challenges.  _Methods in molecular biology (Clifton, N.J.)_ , 1198:3–12, 2014.  ISSN 1064-3745.  doi: 10.1007/978-1-4939-1258-2“˙1.  URL https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4336784/.
  * Hagberg et al. (2008) Hagberg, A., Swart, P., and S Chult, D.  Exploring network structure, dynamics, and function using networkx.  Technical report, Los Alamos National Lab.(LANL), Los Alamos, NM (United States), 2008.
  * Heller et al. (2015) Heller, S. R., McNaught, A., Pletnev, I., Stein, S., and Tchekhovskoi, D.  InChI, the IUPAC International Chemical Identifier.  _Journal of Cheminformatics_ , 7(1):23, May 2015.  ISSN 1758-2946.  doi: 10.1186/s13321-015-0068-4.  URL https://doi.org/10.1186/s13321-015-0068-4.
  * Hong et al. (2023) Hong, Y., Li, S., Welch, C. J., Tichy, S., Ye, Y., and Tang, H.  3DMolMS: prediction of tandem mass spectra from 3D molecular conformations.  _Bioinformatics_ , 39(6):btad354, May 2023.  ISSN 1367-4811.  doi: 10.1093/bioinformatics/btad354.  URL https://doi.org/10.1093/bioinformatics/btad354.  _eprint: https://academic.oup.com/bioinformatics/article-pdf/39/6/btad354/50661428/btad354.pdf.
  * Huber et al. (2020) Huber, F., Verhoeven, S., Meijer, C., Spreeuw, H., Castilla, E. M. V., Geng, C., Hooft, J. J. j. v. d., Rogers, S., Belloum, A., Diblen, F., and Spaaks, J. H.  matchms - processing and similarity evaluation of mass spectrometry data.  _Journal of Open Source Software_ , 5(52):2411, August 2020.  ISSN 2475-9066.  doi: 10.21105/joss.02411.  URL https://joss.theoj.org/papers/10.21105/joss.02411.
  * Kim et al. (2019) Kim, S., Chen, J., Cheng, T., Gindulyte, A., He, J., He, S., Li, Q., Shoemaker, B. A., Thiessen, P. A., Yu, B., Zaslavsky, L., Zhang, J., and Bolton, E. E.  PubChem 2019 update: improved access to chemical data.  _Nucleic Acids Research_ , 47(Database issue):D1102–D1109, January 2019.  ISSN 0305-1048.  doi: 10.1093/nar/gky1033.  URL https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6324075/.
  * Kong et al. (2022) Kong, K., Li, G., Ding, M., Wu, Z., Zhu, C., Ghanem, B., Taylor, G., and Goldstein, T.  Robust optimization as data augmentation for large-scale graphs.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 60–69, 2022.
  * Kuhn (1955) Kuhn, H. W.  The Hungarian method for the assignment problem.  _Naval Research Logistics Quarterly_ , 2(1-2):83–97, March 1955.  ISSN 0028-1441, 1931-9193.  doi: 10.1002/nav.3800020109.  URL https://onlinelibrary.wiley.com/doi/10.1002/nav.3800020109.
  * Lakshminarayanan et al. (2017) Lakshminarayanan, B., Pritzel, A., and Blundell, C.  Simple and Scalable Predictive Uncertainty Estimation using Deep Ensembles.  In _Advances in Neural Information Processing Systems_ , volume 30. Curran Associates, Inc., 2017.  URL https://proceedings.neurips.cc/paper_files/paper/2017/hash/9ef2ed4b7fd2c810847ffa5fa85bce38-Abstract.html.
  * Landrum (2022) Landrum, G.  Rdkit: Open-source cheminformatics, 2022.  URL http://www.rdkit.org.
  * Lebedev (2013) Lebedev, A. T.  Environmental Mass Spectrometry.  _Annual Review of Analytical Chemistry_ , 6(1):163–189, 2013.  doi: 10.1146/annurev-anchem-062012-092604.  URL https://doi.org/10.1146/annurev-anchem-062012-092604.
  * Li et al. (2022) Li, X., Zhu, H., Liu, L.-p., and Hassoun, S.  Ensemble Spectral Prediction (ESP) Model for Metabolite Annotation.  _arXiv:2203.13783 [cs, q-bio]_ , March 2022.  URL http://arxiv.org/abs/2203.13783.  arXiv: 2203.13783.
  * McLafferty (1959) McLafferty, F. W.  Mass Spectrometric Analysis. Molecular Rearrangements.  _Analytical Chemistry_ , 31(1):82–87, January 1959.  ISSN 0003-2700.  doi: 10.1021/ac60145a015.  URL https://doi.org/10.1021/ac60145a015.  Publisher: American Chemical Society.
  * Murphy et al. (2023) Murphy, M., Jegelka, S., Fraenkel, E., Kind, T., Healey, D., and Butler, T.  Efficiently predicting high resolution mass spectra with graph neural networks.  In Krause, A., Brunskill, E., Cho, K., Engelhardt, B., Sabato, S., and Scarlett, J. (eds.), _Proceedings of the 40th International Conference on Machine Learning_ , volume 202 of _Proceedings of Machine Learning Research_ , pp. 25549–25562. PMLR, July 2023.  URL https://proceedings.mlr.press/v202/murphy23a.html.
  * Nakata & Shimazaki (2017) Nakata, M. and Shimazaki, T.  PubChemQC Project: A Large-Scale First-Principles Electronic Structure Database for Data-Driven Chemistry.  _Journal of Chemical Information and Modeling_ , 57(6):1300–1308, June 2017.  ISSN 1549-9596.  doi: 10.1021/acs.jcim.7b00083.  URL https://doi.org/10.1021/acs.jcim.7b00083.
  * Paszke et al. (2019) Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., Desmaison, A., Köpf, A., Yang, E., DeVito, Z., Raison, M., Tejani, A., Chilamkurthy, S., Steiner, B., Fang, L., Bai, J., and Chintala, S.  PyTorch: An Imperative Style, High-Performance Deep Learning Library.  _arXiv:1912.01703 [cs, stat]_ , December 2019.  URL http://arxiv.org/abs/1912.01703.
  * Peters (2011) Peters, F. T.  Recent advances of liquid chromatography–(tandem) mass spectrometry in clinical and forensic toxicology.  _Clinical Biochemistry_ , 44(1):54–65, January 2011.  ISSN 0009-9120.  doi: 10.1016/j.clinbiochem.2010.08.008.  URL https://www.sciencedirect.com/science/article/pii/S0009912010003486.
  * Python Core Team (2021) Python Core Team.  _Python: A dynamic, open source programming language_.  Python Software Foundation, 2021.  URL https://www.python.org/.
  * Ridder et al. (2014) Ridder, L., Hooft, J. J. J. v. d., and Verhoeven, S.  Automatic Compound Annotation from Mass Spectrometry Data Using MAGMa.  _Mass Spectrometry_ , 3(Special_Issue_2):S0033–S0033, 2014.  doi: 10.5702/massspectrometry.S0033.
  * Rogers & Hahn (2010) Rogers, D. and Hahn, M.  Extended-Connectivity Fingerprints.  _Journal of Chemical Information and Modeling_ , 50(5):742–754, May 2010.  ISSN 1549-9596.  doi: 10.1021/ci100050t.  URL https://doi.org/10.1021/ci100050t.
  * Ruttkies et al. (2016) Ruttkies, C., Schymanski, E. L., Wolf, S., Hollender, J., and Neumann, S.  MetFrag relaunched: incorporating strategies beyond in silico fragmentation.  _Journal of Cheminformatics_ , 8(1):3, January 2016.  ISSN 1758-2946.  doi: 10.1186/s13321-016-0115-9.  URL https://doi.org/10.1186/s13321-016-0115-9.
  * Schymanski et al. (2017) Schymanski, E. L., Ruttkies, C., Krauss, M., Brouard, C., Kind, T., Dührkop, K., Allen, F., Vaniya, A., Verdegem, D., Böcker, S., Rousu, J., Shen, H., Tsugawa, H., Sajed, T., Fiehn, O., Ghesquière, B., and Neumann, S.  Critical Assessment of Small Molecule Identification 2016: automated methods.  _Journal of Cheminformatics_ , 9(1):22, March 2017.  ISSN 1758-2946.  doi: 10.1186/s13321-017-0207-1.  URL https://doi.org/10.1186/s13321-017-0207-1.
  * Shervashidze et al. (2011) Shervashidze, N., Schweitzer, P., Leeuwen, E. J. v., Mehlhorn, K., and Borgwardt, K. M.  Weisfeiler-Lehman Graph Kernels.  _Journal of Machine Learning Research_ , 12(77):2539–2561, 2011.  URL http://jmlr.org/papers/v12/shervashidze11a.html.
  * Shrivastava et al. (2021) Shrivastava, A. D., Swainston, N., Samanta, S., Roberts, I., Wright Muelas, M., and Kell, D. B.  MassGenie: A Transformer-Based Deep Learning Method for Identifying Small Molecules from Their Mass Spectra.  _Biomolecules_ , 11(12):1793, November 2021.  ISSN 2218-273X.  doi: 10.3390/biom11121793.  URL https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8699281/.
  * Skinnider et al. (2021) Skinnider, M. A., Wang, F., Pasin, D., Greiner, R., Foster, L. J., Dalsgaard, P. W., and Wishart, D. S.  A deep generative model enables automated structure elucidation of novel psychoactive substances.  _Nature Machine Intelligence_ , 3(11):973–984, November 2021.  ISSN 2522-5839.  doi: 10.1038/s42256-021-00407-x.  URL https://www.nature.com/articles/s42256-021-00407-x.  Number: 11 Publisher: Nature Publishing Group.
  * Stein (2012) Stein, S.  Mass Spectral Reference Libraries: An Ever-Expanding Resource for Chemical Identification.  _Analytical Chemistry_ , 84(17):7274–7282, September 2012.  ISSN 0003-2700.  doi: 10.1021/ac301205z.  URL https://doi.org/10.1021/ac301205z.
  * Stein & Scott (1994) Stein, S. E. and Scott, D. R.  Optimization and testing of mass spectral library search algorithms for compound identification.  _Journal of the American Society for Mass Spectrometry_ , 5(9):859–866, September 1994.  ISSN 1044-0305.  doi: 10.1016/1044-0305(94)87009-8.  URL https://pubs.acs.org/doi/10.1016/1044-0305%2894%2987009-8.
  * Stravs et al. (2022) Stravs, M. A., Dührkop, K., Böcker, S., and Zamboni, N.  MSNovelist: de novo structure generation from mass spectra.  _Nature Methods_ , 19(7):865–870, July 2022.  ISSN 1548-7105.  doi: 10.1038/s41592-022-01486-3.  URL https://www.nature.com/articles/s41592-022-01486-3.  Number: 7 Publisher: Nature Publishing Group.
  * Tancik et al. (2020) Tancik, M., Srinivasan, P. P., Mildenhall, B., Fridovich-Keil, S., Raghavan, N., Singhal, U., Ramamoorthi, R., Barron, J. T., and Ng, R.  Fourier features let networks learn high frequency functions in low dimensional domains.  _CoRR_ , abs/2006.10739, 2020.  URL https://arxiv.org/abs/2006.10739.
  * van Tetering et al. (2024) van Tetering, L., Spies, S., Wildeman, Q. D. K., Houthuijs, K. J., van Outersterp, R. E., Martens, J., Wevers, R. A., Wishart, D. S., Berden, G., and Oomens, J.  A spectroscopic test suggests that fragment ion structure annotations in MS/MS libraries are frequently incorrect.  _Communications Chemistry_ , 7(1):1–11, February 2024.  ISSN 2399-3669.  doi: 10.1038/s42004-024-01112-7.  URL https://www.nature.com/articles/s42004-024-01112-7.  Number: 1 Publisher: Nature Publishing Group.
  * Voronov et al. (2022) Voronov, G., Frandsen, A., Bargh, B., Healey, D., Lightheart, R., Kind, T., Dorrestein, P., Colluru, V., and Butler, T.  Ms2prop: A machine learning model that directly predicts chemical properties from mass spectrometry data for novel compounds.  _bioRxiv_ , 2022.  doi: 10.1101/2022.10.09.511482.  URL https://www.biorxiv.org/content/early/2022/10/11/2022.10.09.511482.
  * Wang et al. (2021) Wang, F., Liigand, J., Tian, S., Arndt, D., Greiner, R., and Wishart, D. S.  CFM-ID 4.0: More Accurate ESI-MS/MS Spectral Prediction and Compound Identification.  _Analytical Chemistry_ , August 2021.  ISSN 0003-2700.  doi: 10.1021/acs.analchem.1c01465.  URL https://doi.org/10.1021/acs.analchem.1c01465.
  * Wang et al. (2023) Wang, F., Pasin, D., Skinnider, M. A., Liigand, J., Kleis, J.-N., Brown, D., Oler, E., Sajed, T., Gautam, V., Harrison, S., Greiner, R., Foster, L. J., Dalsgaard, P. W., and Wishart, D. S.  Deep Learning-Enabled MS/MS Spectrum Prediction Facilitates Automated Identification Of Novel Psychoactive Substances.  _Analytical Chemistry_ , 95(50):18326–18334, December 2023.  ISSN 0003-2700.  doi: 10.1021/acs.analchem.3c02413.  URL https://doi.org/10.1021/acs.analchem.3c02413.  Publisher: American Chemical Society.
  * Wei et al. (2019) Wei, J. N., Belanger, D., Adams, R. P., and Sculley, D.  Rapid prediction of electron–ionization mass spectrometry using neural networks.  _ACS Central Science_ , 5(4):700–708, April 2019.  ISSN 2374-7943, 2374-7951.  doi: 10.1021/acscentsci.9b00085.  URL https://pubs.acs.org/doi/10.1021/acscentsci.9b00085.
  * Wishart et al. (2018) Wishart, D. S., Feunang, Y. D., Marcu, A., Guo, A. C., Liang, K., Vázquez-Fresno, R., Sajed, T., Johnson, D., Li, C., Karu, N., Sayeeda, Z., Lo, E., Assempour, N., Berjanskii, M., Singhal, S., Arndt, D., Liang, Y., Badran, H., Grant, J., Serra-Cayuela, A., Liu, Y., Mandal, R., Neveu, V., Pon, A., Knox, C., Wilson, M., Manach, C., and Scalbert, A.  HMDB 4.0: the human metabolome database for 2018.  _Nucleic Acids Research_ , 46(D1):D608–D617, January 2018.  ISSN 1362-4962.  doi: 10.1093/nar/gkx1089.
  * Wolf et al. (2010) Wolf, S., Schmidt, S., Müller-Hannemann, M., and Neumann, S.  In silico fragmentation for computer assisted identification of metabolite mass spectra.  _BMC Bioinformatics_ , 11(1):148, March 2010.  ISSN 1471-2105.  doi: 10.1186/1471-2105-11-148.  URL https://doi.org/10.1186/1471-2105-11-148.
  * Wu et al. (2018) Wu, Z., Ramsundar, B., Feinberg, E. N., Gomes, J., Geniesse, C., Pappu, A. S., Leswing, K., and Pande, V.  MoleculeNet: a benchmark for molecular machine learning.  _Chemical Science_ , 9(2):513–530, January 2018.  ISSN 2041-6539.  doi: 10.1039/C7SC02664A.  URL https://pubs.rsc.org/en/content/articlelanding/2018/sc/c7sc02664a.  Publisher: The Royal Society of Chemistry.
  * Xu et al. (2018) Xu, K., Hu, W., Leskovec, J., and Jegelka, S.  How Powerful are Graph Neural Networks?  September 2018.  URL https://openreview.net/forum?id=ryGs6iA5Km.
  * Yang et al. (2014) Yang, X., Neta, P., and Stein, S. E.  Quality Control for Building Libraries from Electrospray Ionization Tandem Mass Spectra.  _Analytical Chemistry_ , 86(13):6393–6400, July 2014.  ISSN 0003-2700, 1520-6882.  doi: 10.1021/ac500711m.  URL https://pubs.acs.org/doi/10.1021/ac500711m.
  * Ying et al. (2021) Ying, C., Cai, T., Luo, S., Zheng, S., Ke, G., He, D., Shen, Y., and Liu, T.-Y.  Do transformers really perform bad for graph representation?  _Neural Information Processing Systems (NeurIPS)_ , 2021.
  * Young et al. (2023) Young, A., Wang, B., and Röst, H.  MassFormer: Tandem Mass Spectrum Prediction for Small Molecules using Graph Transformers, May 2023.  URL http://arxiv.org/abs/2111.04824.  arXiv:2111.04824 [cs, q-bio].
  * Zhu et al. (2020) Zhu, H., Liu, L., and Hassoun, S.  Using Graph Neural Networks for Mass Spectrometry Prediction.  _arXiv:2010.04661 [cs]_ , October 2020.  URL http://arxiv.org/abs/2010.04661.
  * Zhu & Jonas (2023) Zhu, R. L. and Jonas, E.  Rapid Approximate Subset-Based Spectra Prediction for Electron Ionization–Mass Spectrometry.  _Analytical Chemistry_ , 95(5):2653–2663, February 2023.  ISSN 0003-2700.  doi: 10.1021/acs.analchem.2c02093.  URL https://doi.org/10.1021/acs.analchem.2c02093.  Publisher: American Chemical Society.

##  Appendix A Recursive Fragmentation Algorithm

Algorithm 1 RecFrag

Input: heavy-atom subgraph $G=(V,E)$, max depth $d$, current depth
$d^{\prime}$

Initialize DAG nodes $V_{F}=\\{\\}$, DAG edges $E_{F}=\\{\\}$

if $d^{\prime}\leq d$ then

$I=\text{ID}(V)$

for $e=(u,v)\in E$ do

$E^{\prime}=E-\\{e\\}$

$(V^{u},E^{u})=\text{BFSCC}(u,V,E^{\prime})$

$I^{u}=\text{ID}(V^{u})$

$(V^{v},E^{v})=\text{BFSCC}(v,V,E^{\prime})$

$I^{v}=\text{ID}(V^{v})$

$S=S\cup\\{(V^{u},E^{u}),(V^{v},E^{v})\\}$

$V_{F}=V_{F}\cup\\{I^{u},I^{v}\\}$

$E_{F}=E_{F}\cup\\{(I,I^{u}),(I,I^{v})\\}$

end for

for $G^{s}=(V^{s},E^{s})\in S$ do

$(V_{F}^{s},E_{F}^{s})=\text{RecFrag}(G^{s},d,d^{\prime}+1)$

$V_{F}=V_{F}\cup V_{F}^{s}$

$E_{F}=E_{F}\cup E_{F}^{s}$

end for

end if

Return $(V_{F},E_{F})$

The approximate fragmentation DAG $G_{\mathcal{F}^{d}}$ is constructed by
calling Algorithm 1 on the heavy-atom skeleton of the molecule
$\mathcal{H}(G)$, with initial depth parameter $d^{\prime}=1$. BFSCC is a
breadth-first search algorithm that returns the set of nodes and edges in a
graph that can be reached from a given input node. ID is a function that takes
a subset of the (ordered) graph nodes and maps them to a unique integer id
(our implementation simply converts the binary representation of the subgraph
node mask to a decimal integer).

Figure 4: DAG Visualization: the approximate fragmentation DAG
$\mathcal{G}_{\mathcal{F}^{d}}$ ($d=3$) for a small molecule,
methylaminomethanol. The root node is represented by the heavy-atom skeleton
of the molecule $\mathcal{H}(G)$, and each other node is represented by a
subgraph of $\mathcal{H}(G)$. Carbon atoms are represented by “C”, nitrogen
atoms by “N”, oxygen atoms by “O”.

Figure 4 is a visualization of the full fragmentation DAG $\mathcal{F}_{G}$
for an example molecule. Since this molecule is small and linear, the
resulting DAG consists of only 10 nodes and 19 edges.

##  Appendix B Fragmentation DAG Statistics

Table 4: Fragmentation DAG Statistics over the NIST20 Dataset (first and third
quartiles).
Statistic | $d=3,j=4$ | $d=4,j=4$
---|---|---
# Formulae $f$ | $325-849$ | $390-1179$
# Nodes $n$ | $167-482$ | $334-1425$
# Nodes $\tilde{n}$ | $104-313$ | $184-886$
# Edges $e$ | $662-2170$ | $2296-10251$
Recall (0.01 Da) | $0.600-0.821$ | $0.727-0.898$
Recall (10 ppm) | $0.485-0.733$ | $0.597-0.817$
Weighted recall (0.01 Da) | $0.773-0.967$ | $0.885-0.985$
Weighted recall (10 ppm) | $0.730-0.952$ | $0.846-0.973$

Table 4 describes the size of approximate fragmentation DAG
$G_{\mathcal{F}^{d}}$ and the coverage of its associated mass set
$\hat{M}(G,d,j)$ under two different parameterizations. $d=3,j=4$ is the
configuration used by FraGNNet-D3, and $d=4,j=4$ is the configuration for
FraGNNet-D4.

Recall ($R$) is measured as the fraction of peaks in the spectrum that can be
explained by a mass (Equation 10) while weighted recall ($WR$) incorporates
peak intensities (Equation 11).

$R\left(G_{\mathcal{F}^{d}},P(m)\right)=\sum_{m\in M}\mathbb{I}\left[\exists
n\in V_{\mathcal{F}^{d}}:\lVert m_{n}-m\lVert\leq\tau_{m_{n},m}\right]$ (10)

$WR\left(G_{\mathcal{F}^{d}},P(m)\right)=\sum_{m\in M}P(m)\
\mathbb{I}\left[\exists n\in V_{\mathcal{F}^{d}}:\lVert
m_{n}-m\lVert\leq\tau_{m_{n},m}\right]$ (11)

For the 0.01 Da approach $\tau_{m_{n},m}=0.01$, while for the 10 ppm approach
$\tau_{m_{n},m}=10^{-5}\max(m_{n},m)$. In our experiments, the output
distribution $P_{\theta}(m)$ is defined such that $P_{\theta}(m)=0$ iff
$\nexists n\in V_{\mathcal{F}^{d}}:\lVert m_{n}-m\lVert\leq
10^{-5}\max(m_{n},m)$. Under this definition of the output distribution,
weighted recall with 10ppm tolerance is equivalent to the probability
$P(M^{\text{IS}})=1-P(M^{\text{OS}})$.

##  Appendix C Conceptual Comparisons with Related C2MS Models

In this section, we contrast FraGNNet with two other closely-related
structured C2MS models: CFM and ICEBERG.

CFM (Competitive Fragmentation Modelling, Allen et al. 2015; Wang et al. 2021)
is the most widely used C2MS tool. Like FraGNNet, it uses a combinatorially
generated fragmentation DAG to model a distribution over fragments. However,
the level of detail in the DAG is much greater. CFM explicitly models the
location of hydrogens and higher order bonds, and implements several complex
fragmentation reactions (McLafferty, 1959; Biemann, 1962) that our method does
not. In principle, CFM can produce higher quality peak annotations than
FraGNNet, since each fragment is (likely) a valid chemical chemical structure
and not simply a heavy-atom subgraph and associated hydrogen count. However,
this interpretability comes at a cost: the DAG construction step can last over
an hour for very large molecules due to its complexity. We do not directly
compare with CFM due to difficulties in scaling the model training to larger
datasets such as NIST20 (Goldman et al., 2023a, 2024; Murphy et al., 2023).
Furthermore, previous work from the literature has demonstrated that it is
outperformed by more recent C2MS models (Young et al., 2023; Murphy et al.,
2023; Goldman et al., 2024).

ICEBERG (Inferring Collision-induced-dissociation by Estimating Breakage
Events and Reconstructing their Graphs, Goldman et al. 2024) is a state-of-
the-art C2MS model. As outlined in Section 5.1, ICEBERG is composed of two
sub-modules. The first module (the fragment generator) autoregressively
predicts a simplified fragmentation DAG, and the second module (the intensity
predictor) outputs a distribution over those fragments. The fragment generator
is trained to approximate a fragmentation tree that is constructed by a
variant of the MAGMa algorithm (Ridder et al., 2014). MAGMa applies a
combinatorial atom removal strategy to generate a fragmentation DAG from an
input molecular graph $G$: the resulting DAG has a similar set of fragment
nodes to $G_{\mathcal{F}^{d}}$, but may contain different edges (refer to
Ridder et al. 2014; Goldman et al. 2024 for full details). The MAGMa DAG is
then simplified using a number of pruning strategies. Fragments with masses
that are not represented by any peak in the spectrum are removed, as are
fragments that map to same peak as another (chemical heuristics are used to
determine which fragment should be kept in such cases). Unlike our approach,
no distinction is made between isomorphic fragments that originate from
different parts of the molecule. Redundant paths between fragments are removed
to convert the DAG into a proper tree, which is required for autoregressive
generation.

ICEBERG’s aggressive pruning removes information from the DAG that could be
important for correctly predicting the spectrum. However, this pruning also
facilitates more expressive representations of the fragments that remain:
since the total number of fragments is lower, the computational and memory
cost per fragment can be much higher. This tradeoff underlines the key
conceptual difference between FraGNNet and ICEBERG. The former uses a more
complete fragmentation DAG but must employ a simpler representation for each
individual fragment. The latter can afford a more complex fragment
representation but only considers a small subset of the DAG. Our experiments
in Section 5.1 suggest that retaining DAG information may be important, since
FraGNNet outperforms both ICEBERG (which uses a stochastic approximation to
the pruned DAG) and ICEBERG-ADV (which uses extra information from the
spectrum to exactly calculate the pruned DAG).

Note that DAG node pruning might also affect predicted peak annotations. Our
experiments in Section 5.3 suggest that it is plausible for a single peak to
map to multiple fragments, as indicated by non-zero annotation entropies
$H_{\theta}(n|f)$. Compared to FraGNNet, ICEBERG is much more restricted in
its ability to model such fragments, preventing it from considering the entire
set of plausible annotations.

##  Appendix D Fragment Subgraph Isomorphism

In mass spectrometry, it is possible for fragments with identical molecular
structure to originate from different parts of the molecular graph, having
been created through distinct sequences of fragmentation steps. In our model,
this phenomenon is represented by pairs of DAG nodes $n_{1},n_{2}\in
V_{\mathcal{F}^{d}}$ whose corresponding subgraphs $G_{n_{1}}\cong G_{n_{2}}$
are isomorphic (i.e. there exists a node bijection between $G_{n_{1}}$ and
$G_{n_{2}}$ that is both label-preserving and edge-preserving).

With the exception of $P_{\theta}(f)$ (which does not involve fragments), each
of the latent distributions from Section 4.3 can be adapted to account for
fragment graph isomorphism. To describe this process precisely, we rely on
Definition D.1 and Corollary D.2:

######  Definition D.1.

Let $\mathcal{G}$ be a finite set of labelled graphs $\\{G_{i}\\}_{i=1}^{I}$.
Each $G_{i}$ is a member of one of $K$ isomorphism classes
$\\{\mathcal{G}_{k}\\}_{k=1}^{K}$, $K\leq I$. Assume an arbitrary total
ordering $\prec_{k}$ for each isomorphic class $\mathcal{G}_{k}$. Let
$\mathcal{I}(\mathcal{G})\subseteq\mathcal{G}$ be the set of graphs such that
$\forall G_{k}\in\mathcal{I}(\mathcal{G}):\nexists
G_{i}\in\mathcal{G}:G_{i}\in\mathcal{G}_{k}\land G_{i}\prec_{k}G_{k}$.

######  Corollary D.2.

$\forall G_{1},G_{2}\in\mathcal{I}(\mathcal{G}):G_{1}\neq G_{2}\rightarrow
G_{1}\ncong G_{2}$.

For each DAG node $\tilde{n}$ such that
$G_{\tilde{n}}\in\mathcal{I}(\\{G_{n}:n\in V_{\mathcal{F}^{d}}\\})$, we define
$P_{\theta}(\tilde{n})$ as the total probability of all subgraphs isomorphic
to $G_{\tilde{n}}$ using Equation 12:

$P_{\theta}(\tilde{n})=\sum_{n\in V_{\mathcal{F}^{d}}:G_{n}\cong
G_{\tilde{n}}}P_{\theta}(n)$ (12)

The conditional distributions $P_{\theta}(f|\tilde{n})$ and
$P_{\theta}(\tilde{n}|f)$ are defined in a similar manner using Equations 13
and 14 respectively:

$\displaystyle P_{\theta}(f|\tilde{n})$ $\displaystyle=\sum_{n\in
V_{\mathcal{F}^{d}}:G_{n}\cong
G_{\tilde{n}}}\frac{P_{\theta}(f|n)P_{\theta}(n)}{P_{\theta}(\tilde{n})}$ (13)
$\displaystyle P_{\theta}(\tilde{n}|f)$ $\displaystyle=\sum_{n\in
V_{\mathcal{F}^{d}}:G_{n}\cong G_{\tilde{n}}}P_{\theta}(n|f)$ (14)

These distributions can provide additional insight into model behaviour, as
demonstrated in Appendix J. Intuitively, they remove excess entropy caused by
uncertainty over the location in the molecule from which a particular fragment
originated.

In practice, we calculate the set $\mathcal{I}(\\{G_{n}:n\in
V_{\mathcal{F}^{d}}\\})$ by applying an approximate Weisfeiler-Lehman hashing
algorithm (Shervashidze et al., 2011; Hagberg et al., 2008) to each subgraph
$G_{n}:n\in V_{\mathcal{F}^{d}}$ and identify isomorphism class membership
using the resulting hashes.

##  Appendix E Molecule Features

Table 5: Input Features for the Molecule GNN
Feature | Values
---|---
Atom Type (Element) | $\\{\ce{C},\ce{O},\ce{N},\ce{P},\ce{S},\ce{F},\ce{Cl},\ce{Br},\ce{I},\ce{Se},\ce{Si}\\}$
Atom Degree | $\\{0,\ldots,10\\}$
Atom Orbital Hybridization | $\\{\text{SP},\text{SP2},\text{SP3},\text{SP3D},\text{SP3D2}\\}$
Atom Formal Charge | $\\{-2,\ldots,+2\\}$
Atom Radical State | $\\{0,\ldots,4\\}$
Atom Ring Membership | $\\{\text{True},\text{False}\\}$
Atom Aromatic | $\\{\text{True},\text{False}\\}$
Atom Mass | $\mathbb{R}^{+}$
Atom Chirality | $\\{\text{Unspecified},\text{Tetrahedral CW},\text{Tetrahedral CCW}\\}$
Bond Degree | $\\{\text{Single},\text{Double},\text{Triple},\text{Aromatic}\\}$

Our method for atom and bond featurization follows the approach taken by
(Goldman et al., 2024). The features are summarized in Table 5. All discrete
features are encoded using a standard one-hot representation. The only
continuous feature (Atom Mass) is scaled by a factor of $0.01$.

##  Appendix F Fragment Features

###  F.1 Fourier Embeddings

We use Fourier embeddings (Goldman et al., 2023a; Tancik et al., 2020) to
represent certain ordinal features such as mass formulae and collision
energies. Given an integer feature $z\in\mathbb{R}$, the corresponding Fourier
embedding $\phi(z)$ can be calculated using Equation 15:

$\phi(z)=\left[\,\,\left|\sin\left(\frac{2\pi
z}{\tau_{1}}\right)\right|,\,\ldots,\left|\sin\left(\frac{2\pi
z}{\tau_{T}}\right)\right|\,\,\right]$ (15)

In principle, it may be easier for the model to handle inputs $z$ at inference
that have not been seen in training when compared with a standard one-hot
encoding scheme. The periods $\tau_{t}$ are increasing powers of 2 (we use
$T=10$ for our experiments).

###  F.2 DAG Node Features

The DAG node embeddings (Equation 4) are initialized with formula information
$\hat{h}_{n}^{f}$ and fragmentation depth information $\hat{h}_{n}^{d}$. The
formula embedding for DAG node $n$ is a concatenation of Fourier embeddings
corresponding to heavy atom counts in $G_{n}$, described in Equation 16:

$\hat{h}_{n}^{f}=\mathop{\mathchoice{\vbox{\hbox{$\displaystyle\Big{|}\mkern
1.0mu\Big{|}$}}}{\vbox{\hbox{$\textstyle\big{|}\mkern
1.0mu\big{|}$}}}{\vbox{\hbox{$\scriptstyle|\mkern
1.0mu|$}}}{\vbox{\hbox{$\scriptscriptstyle|\mkern
1.0mu|$}}}}_{\omega\in\Omega}\phi\left(\sum_{v\in
V_{n}}\omega_{v}=\omega\right)$ (16)

The depth embedding $\hat{h}_{n}^{d}$ is a multi-hot representation of the
fragment node’s depth in the DAG. The depth set is defined as the set of path
lengths between the root node and the fragment node $n$, and is always a
subset of $\\{0,...,d\\}$ where $d$ is the fragmentation depth.

###  F.3 DAG Edge Features

The embeddings $\bar{h}_{e}^{(0)}$ are initialized for each directed edge
$e\in E_{\mathcal{F}^{d}}$ using Equation 17. Assuming $e$ travels from node
$n$ to node $t$, let $V_{e}=V_{n}-V_{t}$ be the set of atoms in $G_{n}$ that
are not in $G_{t}$. As described in Equation 18, $\hat{h}_{e}^{s}$ is simply
the average of the atom embeddings in $V_{e}$.

$\displaystyle\bar{h}_{e}^{(0)}$ $\displaystyle=\hat{h}_{e}^{s}\ \mathbin{\|}\
\hat{h}_{e}^{f}$ (17) $\displaystyle\hat{h}_{e}^{s}$
$\displaystyle=\frac{1}{|V_{e}|}\sum_{a\in V_{e}}\bar{h}_{a}^{(L_{1})}$ (18)

The $\hat{h}_{e}^{f}$ term is an embedding of the difference of node formulas
$f_{n}-f_{t}$ using Fourier embeddings, similar to $\hat{h}_{e}^{f}$. These
features explicitly capture neutral loss information that would otherwise need
to be inferred from the DAG.

###  F.4 Collision Energy Embedding

Let $Z_{i}$ be the set of collision energies that were merged to create
spectrum $Y_{i}$ for molecule $X_{i}$ in the dataset. The collision energy
embedding is a representation of $Z_{i}$. Each collision energy $z\in Z_{i}$
is a positive integer ranging from 0 to 200 (they are normalized relative to
the mass of the precursor, see Young et al. 2023 for more details). The
collision energy embedding $\hat{h}_{Z}$ is simply an average of Fourier
embeddings for each collision energy, described by Equation 19:

$\hat{h}_{Z}=\frac{1}{|Z|}\sum_{z\in Z}f(z)$ (19)

The collision energy embedding $\hat{h}_{Z}$ is concatenated with the output
Fragment GNN embedding $\bar{h}^{(L_{2})}_{n}$ for each DAG node $n\in
G_{\mathcal{F}^{d}}$ before being passed to the output MLP.

##  Appendix G Spectrum Similarity Metrics

Mass spectra are typically compared using a form of cosine similarity (Stein &
Scott, 1994). The binned approach involves discretizing each spectrum into a
1-dimensional vector of intensities, and calculating the cosine similarity
between the spectrum vectors (Wei et al., 2019; Young et al., 2023; Zhu et
al., 2020). In our experiments, binned cosine similarity $COS_{0.01}$ is
calculated with a bin size of 0.01 Da. An alternate approach measures
similarity by matching peaks that are close in mass (Huber et al., 2020;
Murphy et al., 2023). This can be formalized as the linear sum assignment
problem below, where $i$ indexes spectrum $Y$, $j$ indexes spectrum $\hat{Y}$
and $p_{i},\hat{p}_{j}$ are shorthand for $P(m_{i}),\hat{P}(\hat{m}_{j})$
respectively:

$\displaystyle COS_{\text{HUN}}(Y,\hat{Y})=$
$\displaystyle\max_{w_{ij}\in\\{0,1\\}}\quad\sum_{i,j}w_{ij}\frac{p_{i}}{\lVert
p\lVert_{2}}\frac{\hat{p}_{j}}{\lVert\hat{p}\lVert_{2}}$ (20) s.t.
$\displaystyle\left\\{\begin{array}[]{l}\sum_{i}w_{ij}\leq 1\\\
\sum_{j}w_{ij}\leq 1\\\ |m_{i}-\hat{m}_{j}|\leq\tau_{ij}\end{array}\right.$

We set the tolerance parameter $\tau_{ij}=10^{-5}\max(m_{i},\hat{m}_{j})$ to
reflect a 10ppm mass error. This maximization problem can be solved
efficiently using the Hungarian algorithm (Kuhn, 1955).

##  Appendix H Model Ablations

Table 6: Model Ablations: Performance reported on validation set, mean and
standard of 5 random seeds. Best scores are in bold
Model | $COS_{0.01}\Uparrow$ | $COS_{\text{HUN}}\Uparrow$
---|---|---
FraGNNet-D3 | $\bm{.693\pm.003}$ | $\bm{.668\pm.001}$
FraGNNet-D3 (-CE) | $.681\pm.002$ | $.656\pm.001$
FraGNNet-D3 (+Edges) | $\bm{.693\pm.003}$ | $.667\pm.001$
FraGNNet-D4 | $.709\pm.001$ | $.684\pm.001$
FraGNNet-D4 (-CE) | $.693\pm.001$ | $.670\pm.001$
FraGNNet-D4 (+Edges) | $\bm{.711\pm.002}$ | $\bm{.687\pm.001}$

We perform two kinds of ablations: (-CE) corresponds to the removal of merged
collision energy information (Appendix F.4), (+Edges) corresponds to the
addition of edge embeddings and message passing in the Fragment GNN. The
removal of collision energy information seems to have a significant impact on
both FraGNNet-D3 and FraGNNet-D4 performance, while the addition of DAG edge
information does not seem to have a strong effect.

##  Appendix I Datasets and Splits

We train and evaluate all models on the NIST 2020 MS/MS dataset (Stein, 2012;
Yang et al., 2014), a large commercial library of MS data. To ensure
homogeneity, the original dataset is filtered for [M+H]+ spectra from Orbitrap
instruments. Following (Young et al., 2023; Goldman et al., 2024), spectra for
the same compound acquired at different collision energies are averaged (a
process commonly referred to as collision energy merging). The resulting
dataset contains 21,114 unique molecules and their merged spectra. Models are
trained using $60\%$ of the data, with $20\%$ for validation and $20\%$ used
as a heldout test set. Two strategies for data splitting are employed: a
simple random split by molecule ID using the InChIKey hashing algorithm
(Heller et al., 2015), and a more challenging split that clusters molecules
based on their Murcko Scaffold (Bemis & Murcko, 1996), a coarse representation
of 2D molecular structure. Scaffold splits are commonly used to evaluate
generalization of deep learning models in cheminformatics applications (Wu et
al., 2018).

##  Appendix J Annotation Consistency Continued

###  J.1 Isomorphic Distribution Results

Table 7: Ensemble Annotation Comparison: CV is coefficient of variation, CONS
is annotation consensus, MAJ is agreement with majority annotation. Focus is
on the isomorphic annotation distribution $P(\tilde{n}|f)$.
Metric | Entropy Ens | Standard Ens
---|---|---
Mean $COS_{\text{HUN}}$ | $0.667$ | $0.669$
CV $COS_{\text{HUN}}$ | $0.116$ | $0.115$
Mean $\hat{H}(\tilde{n}|f)$ | $0.373$ | $0.347$
CV $\hat{H}(\tilde{n}|f)$ | $0.628$ | $0.340$
CONS $\operatorname*{arg\,max}_{\tilde{n}}P(\tilde{n}|f)$ | $0.874$ | $0.930$
MAJ $\operatorname*{arg\,max}_{\tilde{n}}P(\tilde{n}|f)$ | $0.970$ | $0.982$

The isomorphic distributions $P(\tilde{n}|f)$ have lower average normalized
entropy than their counterparts $P_{\theta}(n|f)$. Intuitively this is because
part of the entropy $\hat{H}_{\theta}(n|f)$ can be explained as distributing
probability over subgraphs that are isomorphic. Note that the Entropy Ensemble
still has twice the amount of entropy variation (in terms of CV
$\hat{H}_{\theta}(\tilde{n}|f)$) than the Standard Ensemble, and lower CONS
and MAJ metrics. These results are consistent with the analysis of the non-
isomorphic distributions presented in Table 3.

###  J.2 Metric Definitions

Consider an ensemble of $K$ models
$P_{\theta}^{(1:K)}=\\{P^{(1)}_{\theta},\ldots,P^{(K)}_{\theta}\\}$. Let
$\hat{F}(G,d,j)=\bigcup_{n\in
V_{\mathcal{F}^{d}}}\\{f_{n}^{-j},\ldots,f_{n}^{j}\\}$ be the set of formulae
derived from the approximate heavy-atom fragmentation DAG
$G_{\mathcal{F}^{d}}$ with hydrogen tolerance $j$ (similar to $\hat{M}(G,d,j)$
in Definition 4.3, but for formulae).

For molecule $G_{i}$ in the dataset, the ensemble annotation consensus metric
CONS $\operatorname*{arg\,max}_{n}P(n|f)$ is defined in Equation 21:

$\displaystyle\text{CONS}\left(P_{\theta}^{(1:K)},G_{i},d,j\right)$
$\displaystyle=\frac{1}{|\hat{F}(G_{i},d,j)|}\sum_{f_{n}\in\hat{F}(G_{i},d,j)}\text{CONS}\left(P_{\theta}^{(1:K)},f_{n}\right)$
(21) $\displaystyle\text{CONS}\left(P_{\theta}^{(1:K)},f_{n}\right)$
$\displaystyle=\mathbb{I}\left[\frac{K(K-1)}{2}=\sum_{k=1}^{K}\sum_{k^{\prime}=k+1}^{K}\mathbb{I}\left[\operatorname*{arg\,max}_{t}P^{(k)}_{\theta}(t|f_{n})=\operatorname*{arg\,max}_{t}P^{(k^{\prime})}_{\theta}(t|f_{n})\right]\right]$

The majority agreement metric MAJ $\operatorname*{arg\,max}_{n}P(n|f)$, which
measures the fraction of models in the ensemble that agree with the most
common annotation, is defined in Equation 22:

$\displaystyle\text{MAJ}\left(P_{\theta}^{(1:K)},G_{i},d,j\right)$
$\displaystyle=\frac{1}{|\hat{F}(G_{i},d,j)|}\sum_{f_{n}\in\hat{F}(G_{i},d,j)}\text{MAJ}\left(P_{\theta}^{(1:K)},f_{n}\right)$
(22) $\displaystyle\text{MAJ}\left(P_{\theta}^{(1:K)},f_{n}\right)$
$\displaystyle=\frac{1}{K}\sum_{k=1}^{K}\mathbb{I}\left[\operatorname*{arg\,max}_{t}P^{(k)}_{\theta}(t|f_{n})=\text{mode}_{k^{\prime}}\left(\operatorname*{arg\,max}_{t}P^{(k^{\prime})}_{\theta}(t|f_{n})\right)\right]$

In practice, instead of using the full formula set $\hat{F}(G_{i},d,j)$, we
restrict the set to formulae $f_{n}$ that satisfy
$\min_{k}P_{\theta}^{(k)}(f_{n})\geq 0.05$.

##  Appendix K Compound Retrieval Continued

Table 8: Compound Retrieval (Scaffold Split): Top-$k$ Accuracy for different
values of $k$, best scores are in bold.
Model |  Top-1 $\Uparrow$ |  Top-3 $\Uparrow$ |  Top-5 $\Uparrow$ |  Top-10 $\Uparrow$
---|---|---|---|---
FraGNNet-D4 | $\bm{21.1\%}$ | $\bm{46.3\%}$ | $\bm{60.0\%}$ | $\bm{79.3\%}$
FraGNNet-D3 | $18.8\%$ | $43.9\%$ | $59.3\%$ | $77.8\%$
ICEBERG | $18.3\%$ | $41.8\%$ | $55.0\%$ | $73.8\%$
MassFormer | $10.1\%$ | $26.0\%$ | $39.5\%$ | $59.1\%$
NEIMS | $10.2\%$ | $24.9\%$ | $35.9\%$ | $54.8\%$

The retrieval results on the Scaffold split are largely consistent with the
results on the InChIKey split (Table 2), although the improvement of
FraGNNet-D4 over the other models is more pronounced. All models perform worse
on the Scaffold split than they do on the InChIKey split, as expected.

##  Appendix L Implementation Details

The FraGNNet model and baselines were implemented in Python (Python Core Team
2021, version 3.10.13), using Pytorch (Paszke et al. 2019, version 2.1.0, CUDA
11.8) and Pytorch Lightning (Falcon & The PyTorch Lightning team 2019, version
2.1.2). Weights and Biases (Biewald 2020, version 0.16.1) was used to track
model performance. The recursive fragmentation algorithm was implemented in
Cython (Behnel et al. 2011, version 3.0.6). The graph neural network modules
in FraGNNet were implemented using Pytorch Geometric (Fey & Lenssen 2019,
version 2.4.0). The data preprocessing and molecule featurization used RDKit
(Landrum 2022, version 2022.09.4).

##  Appendix M Parameter Counts

Table 9: Parameter Counts: the -OUT entries for the binned models (NEIMS and
MassFormer) correspond to counts which exclude the final projection into the
output spectrum. Counts are reported in millions.
Model |  $\\#$ Parameters
---|---
FraGNNet-D4 | $1.6$
FraGNNet-D3 | $1.6$
ICEBERG-ADV | $3.5$
ICEBERG | $7.1$
MassFormer | $166.9$
MassFormer (-OUT) | $50.4$
NEIMS | $126.4$
NEIMS (-OUT) | $9.9$

The parameter counts for the all of the models are summarized in Table 9. Note
that ICEBERG-ADV has fewer parameters than ICEBERG since it does not use
autoregressive fragment generation. The parameter counts for the binned models
(MassFormer and NEIMS) are dominated by the weights for the final fully
connected layer that maps to the 150,000 dimensional output spectrum. These
approaches were originally designed for lower resolutions (0.1 Da binning),
where the output spectrum has fewer bins.

##  Appendix N Baseline Model Implementation Details

All baseline models were re-implemented in our framework, to facilitate fair
comparison across methods. Some of the models were originally designed to
support additional covariates such as precursor adduct and instrument type: as
our experiments were restricted to MS/MS data of a single precursor adduct
([M+H]+) and instrument type (Orbitrap), we excluded these features in our
implementations.

  * •

NEIMS: Neural Electron Ionization Mass Spectrometry (NEIMS, Wei et al. 2019)
was the first deep learning C2MS model, originally designed for low resolution
(1.0 Da bins) electron-ionization mass spectrometry (EI-MS) prediction. NEIMS
represents the input molecule using a domain-specific featurization method
called a molecular fingerprint, which capture useful properties of the
molecule such as the presence or absence of various substructures. More recent
works (Zhu et al., 2020; Young et al., 2023; Goldman et al., 2023a) have
adapted NEIMS to ESI-MS/MS prediction at higher resolutions (0.1 Da bins). We
based our implementation on the version from Young et al. 2023 which uses
three different kinds of molecular fingerprint representations: the Extended
Connectivity (Morgan) fingerprint (Rogers & Hahn, 2010), the RDKit fingerprint
(Landrum, 2022), and the Molecular Access Systems (MACCS) fingerprint (Durant
et al., 2002). We adapted the model to use the same collision energy
featurization strategy as FraGNNet (Equation 19). Finally, to avoid an excess
of parameters, we replaced the final fully-connected layer’s weight matrix
with a low-rank approximation. This layer maps from the latent dimension
$d_{h}=1024$ to the output dimension $d_{o}=150000$, corresponding to the mass
range $[0,1500]$ with 0.01 Da bins. The low-rank approximation was implemented
as product of two learnable weight matrices: a $d_{h}\times d_{r}$ matrix and
a $d_{r}\times d_{o}$ matrix, where $d_{r}=256$.

  * •

MassFormer: The MassFormer model (Young et al., 2023) is a binned C2MS method
originally designed for low resolution (1.0 Da bins) ESI-MS/MS prediction. It
uses a graph transformer architecture (Ying et al., 2021) that is pre-trained
on a large chemical dataset (Nakata & Shimazaki, 2017) and then fine-tuned on
spectrum prediction. We preserved most aspects of the model’s original
implementation but adapted the collision energy featurization and low rank
output matrix approximation ($d_{r}=128$) from the NEIMS baseline. Unlike the
original MassFormer paper, we did not employ FLAG (Kong et al., 2022), a
strategy for adversarial data augmentation in graphs, since none of the other
models were using data augmentation.

  * •

ICEBERG: We describe the ICEBERG model (Goldman et al., 2024) in the main text
(Section 5.1) and discuss it further in Appendix C. Our implementation is
essentially unchanged from the original version, although in our experiments
the model is trained using binned cosine similarity with 0.01 Da bins
(previously, it was trained using 0.1 Da bins).