%Version 3 October 2023
% See section 11 of the User Manual for version history
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%                                                                 %%
%% Please do not use \input{...} to include other tex files.       %%
%% Submit your LaTeX manuscript as one .tex document.              %%
%%                                                                 %%
%% All additional figures and files should be attached             %%
%% separately and not embedded in the \TeX\ document itself.       %%
%%                                                                 %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%\documentclass[referee,sn-basic]{sn-jnl}% referee option is meant for double line spacing

%%=======================================================%%
%% to print line numbers in the margin use lineno option %%
%%=======================================================%%

%%\documentclass[lineno,sn-basic]{sn-jnl}% Basic Springer Nature Reference Style/Chemistry Reference Style

%%======================================================%%
%% to compile with pdflatex/xelatex use pdflatex option %%
%%======================================================%%

%%\documentclass[pdflatex,sn-basic]{sn-jnl}% Basic Springer Nature Reference Style/Chemistry Reference Style


%%Note: the following reference styles support Namedate and Numbered referencing. By default the style follows the most common style. To switch between the options you can add or remove 揘umbered?in the optional parenthesis.
%%The option is available for: sn-basic.bst, sn-vancouver.bst, sn-chicago.bst%

%%\documentclass[sn-nature]{sn-jnl}% Style for submissions to Nature Portfolio journals
\documentclass[sn-basic, Numbered]{sn-jnl}% Basic Springer Nature Reference Style/Chemistry Reference Style
%% \documentclass[sn-mathphys-num]{sn-jnl}% Math and Physical Sciences Numbered Reference Style
%%\documentclass[sn-mathphys-ay]{sn-jnl}% Math and Physical Sciences Author Year Reference Style
%%\documentclass[sn-aps]{sn-jnl}% American Physical Society (APS) Reference Style
%%\documentclass[sn-vancouver,Numbered]{sn-jnl}% Vancouver Reference Style
%%\documentclass[sn-apa]{sn-jnl}% APA Reference Style
%%\documentclass[sn-chicago]{sn-jnl}% Chicago-based Humanities Reference Style

%%%% Standard Packages
%%<additional latex packages if required can be included here>

\usepackage{graphicx}%
\usepackage{multirow}%
\usepackage{amsmath,amssymb,amsfonts}%
\usepackage{amsthm}%
\usepackage{mathrsfs}%
\usepackage[title]{appendix}%
\usepackage{xcolor}%
\usepackage{textcomp}%
\usepackage{manyfoot}%
\usepackage{booktabs}%
\usepackage{algorithm}%
\usepackage{algorithmicx}%
\usepackage{algpseudocode}%
\usepackage{listings}%
\usepackage{natbib}
\usepackage{makecell}
\usepackage{caption}
\usepackage{natbib}
\usepackage{bbm}
%%%%

%%%%%=============================================================================%%%%
%%%%  Remarks: This template is provided to aid authors with the preparation
%%%%  of original research articles intended for submission to journals published
%%%%  by Springer Nature. The guidance has been prepared in partnership with
%%%%  production teams to conform to Springer Nature technical requirements.
%%%%  Editorial and presentation requirements differ among journal portfolios and
%%%%  research disciplines. You may find sections in this template are irrelevant
%%%%  to your work and are empowered to omit any such section if allowed by the
%%%%  journal you intend to submit to. The submission guidelines and policies
%%%%  of the journal take precedence. A detailed User Manual is available in the
%%%%  template package for technical guidance.
%%%%%=============================================================================%%%%

%% as per the requirement new theorem styles can be included as shown below
\theoremstyle{thmstyleone}%
\newtheorem{theorem}{Theorem}%  meant for continuous numbers
%%\newtheorem{theorem}{Theorem}[section]% meant for sectionwise numbers
%% optional argument [theorem] produces theorem numbering sequence instead of independent numbers for Proposition
\newtheorem{proposition}[theorem]{Proposition}%
%%\newtheorem{proposition}{Proposition}% to get separate numbers for theorem and proposition etc.

\theoremstyle{thmstyletwo}%
\newtheorem{example}{Example}%
\newtheorem{remark}{Remark}%

\theoremstyle{thmstylethree}%
\newtheorem{definition}{Definition}%

\raggedbottom
%%\unnumbered% uncomment this for unnumbered level heads





\begin{document}

\title[Article Title]{\normalsize{Supplementary material of} 

{\ } 

{\ }

\LARGE{
UAlign: Pushing the Limit of Template-free Retrosynthesis Prediction with Unsupervised SMILES Alignment}}

%%=============================================================%%
%% GivenName	-> \fnm{Joergen W.}
%% Particle	-> \spfx{van der} -> surname prefix
%% FamilyName	-> \sur{Ploeg}
%% Suffix	-> \sfx{IV}
%% \author*[1,2]{\fnm{Joergen W.} \spfx{van der} \sur{Ploeg}
%%  \sfx{IV}}\email{iauthor@gmail.com}
%%=============================================================%%

\author[1]{\fnm{Kaipeng} \sur{Zeng}}%\email{zengkaipeng@sjtu.edu.cn}
\author[2]{\fnm{Bo} \sur{Yang}}%\email{yangbo71@sjtu.edu.cn}
\author[1]{\fnm{Xin} \sur{Zhao}}%\email{zhaoxin0807@sjtu.edu.cn}
% \equalcont{These authors contributed equally to this work.}
\author[1]{\fnm{Yu} \sur{Zhang}}%\email{cynthiazhang@sjtu.edu.cn}
\author[3]{\fnm{Fan} \sur{Nie}}%\email{youluo2001@sjtu.edu.cn}
\author[1]{\fnm{Xiaokang} \sur{Yang}}%\email{xkyang@sjtu.edu.cn}
\author*[1]{\fnm{Yaohui} \sur{Jin}}\email{jinyh@sjtu.edu.cn}
% \equalcont{These authors contributed equally to this work.}
\author*[1]{\fnm{Yanyan} \sur{Xu}}\email{yanyanxu@sjtu.edu.cn}
\affil*[1]{\orgdiv{MoE Key Laboratory of Artificial Intelligence, AI Institute}, \orgname{Shanghai Jiao Tong University}, \orgaddress{\city{Shanghai}, \postcode{200240}, \state{Shanghai}, \country{China}}}

%\affil[2]{\orgdiv{Data-Driven Management Decision Making Laboratory}, \orgname{Shanghai Jiao Tong University}, \orgaddress{\street{Dongchuan Road}, \city{Shanghai}, \postcode{200240}, \state{Shanghai}, \country{China}}}
\affil[2]{\orgdiv{Frontiers Science Center for Transformative Molecules (FSCTM), Zhangjiang Institute for Advanced Study}, \orgname{Shanghai Jiao Tong University}, \orgaddress{\city{Shanghai}, \postcode{200240}, \state{Shanghai}, \country{China}}}
\affil[3]{\orgdiv{Department of Computer Science and Engineering}, \orgname{Shanghai Jiao Tong University}, \orgaddress{\city{Shanghai}, \postcode{200240}, \state{Shanghai}, \country{China}}}

%%==================================%%
%% Sample for unstructured abstract %%
%%==================================%%

% \abstract{The abstract serves both as a general introduction to the topic and as a brief, non-technical summary of the main results and their implications. Authors are advised to check the author instructions for the journal they are submitting to for word limits and if structural elements like subheadings, citations, or equations are permitted.}

%%================================%%
%% Sample for structured abstract %%
%%================================%%

% \abstract{\textbf{Purpose:} The abstract serves both as a general introduction to the topic and as a brief, non-technical summary of the main results and their implications. The abstract must not include subheadings (unless expressly permitted in the journal's Instructions to Authors), equations or citations. As a guide the abstract should not exceed 200 words. Most journals do not set a hard limit however authors are advised to check the author instructions for the journal they are submitting to.
%
% \textbf{Methods:} The abstract serves both as a general introduction to the topic and as a brief, non-technical summary of the main results and their implications. The abstract must not include subheadings (unless expressly permitted in the journal's Instructions to Authors), equations or citations. As a guide the abstract should not exceed 200 words. Most journals do not set a hard limit however authors are advised to check the author instructions for the journal they are submitting to.
%
% \textbf{Results:} The abstract serves both as a general introduction to the topic and as a brief, non-technical summary of the main results and their implications. The abstract must not include subheadings (unless expressly permitted in the journal's Instructions to Authors), equations or citations. As a guide the abstract should not exceed 200 words. Most journals do not set a hard limit however authors are advised to check the author instructions for the journal they are submitting to.
%
% \textbf{Conclusion:} The abstract serves both as a general introduction to the topic and as a brief, non-technical summary of the main results and their implications. The abstract must not include subheadings (unless expressly permitted in the journal's Instructions to Authors), equations or citations. As a guide the abstract should not exceed 200 words. Most journals do not set a hard limit however authors are advised to check the author instructions for the journal they are submitting to.}


%%\pacs[JEL Classification]{D8, H51}

%%\pacs[MSC Classification]{35A01, 65L10, 65L12, 65L20, 65L70}

\maketitle

\section{Notations}
Supplementary Table~\ref{tab:notations} lists the notations used to facilitate reading.
\begin{sidewaystable}[htbp]
\centering
\captionsetup{name={Supplementary Table}}
\caption{Notations for facilitating reading.}
\label{tab:notations}
\begin{tabular}{c|l}
\hline
\textbf{Notation}  & \makecell[l]{\textbf{Description}} \\
\hline
$G=(V,E)$& a graph with nodes $V$ and edges $E$\\
$rank(a, O)$& the position of atom $a$ in DFS order $O$ \\
$root(G,O)$& the atom (node) of G with the minal rank in $O$\\
$Smiles(G,O)$& The SMILES of molecule graph $G$ generated via DFS order $O$\\
\hline
$M=(V_M,E_M)$ & a molecule graphs\\
$M'=(V_{M'}, E_{M'})$ & a molecule graph\\
$\tilde{M}=(V_M \cup V_{M'}, E_M \cup E_{M'})$& a molecule graph consist of two isolated molecules $M$ and $M'$\\
$O_M$ & a DFS order of molecule graph $M$\\
$O_{\tilde{M}}$& a DFS order for molecule graph $\tilde{M}$\\
\hline
$\mathcal{R}$& the set of all reactant molecule graphs\\
$P=(V_P, E_P)$       &  the product molecule graph \\
$R=(V_R, E_R)$ & a single reactant molecule graph\\
$\mathcal{D}(V_P), \mathcal{D}(V_R)$ & the set of all possible DFS order for product molecule graph / a single reactant molecule graph\\
$O_P, O_R$ & a DFS order of product, a DFS order of reactant molecule graphs\\
$CO(R,O_P)$ & the DFS order of reactant $R$ that has a nearly consistent atomic appearance sequence with $O_P$ \\
$OPSmiles(\mathcal{R}, O_P)$ & the order-preserving reactants SMILES of $\mathcal{R}$ based on DFS order $O_P$\\
\hline
$h^{(k)}_u$ & the node feature of node $u$ at $k$-th iteration of message passing.\\
$e^{(k)}_{u,v}$ & the edge feature of edge between node $u$ and $v$ at $k$-th iteration of message passing.\\
$H$&the output of the encoder, i.e. the encoded node features\\
\hline
$Z$ & the input token embedding for Transformer decoder\\
$\hat{H}$& the order-aware node features\\
$\hat{Z}$ & the output token embedding of Transformer decoder\\
\hline
$\hat{T}$& the predicted token logits list \\
$\hat{t}_i$& the $i$-th token logits in the predicted token list\\
$T$& the ground truth token list\\
$t_i$& the $i$-th ground truth token\\
\hline
\end{tabular}
\end{sidewaystable}



\section{Dataset}\label{app: data}

The open benchmark datasets are presented as follows.

\textbf{USPTO-50K.} The USPTO-50K is of high quality, we only remove the reactions whose products only contain a single atom from the dataset.

\textbf{USPTO-FULL.} The raw data of USPTO-FULL provided by \citeauthor{gln} has error annotations and other problems. Thus we perform the following steps to clean up the data.
\begin{itemize}
    \item remove the reactions where different atoms share the same atom map number.
    \item remove the reactions whose product is consist of a single atom.
    \item remove the reactions with invalid SMILES. The empty SMILES is considered as invalid SMILES too.
    \item remove the reactions where product contains atoms that do not appear in reactants.
    \item remove the reactants that all atoms do not appear in the product.
\end{itemize}

\textbf{USPTO-MIT.} The raw data of USPTO-MIT provided by~\cite{jin2017predicting}. The original dataset contains reactions that have multiple product molecules. And the reagents are put together with reactions. Thus we perform the following steps to make the dataset more suitable for retrosynthesis prediction task.
\begin{itemize}
    \item remove the reactions whose product is consist of a single atom
    \item remove the reagents from the reactants. We consider the molecules whose atoms have no intersection with the product as reagents.
    \item remove the reactions with multiple product molecules. 
\end{itemize}

The statistical information of the datasets used in this work is summarized in Supplementary Table~\ref{tab:dataset}.

\begin{table}[htbp]
\captionsetup{name={Supplementary Table}}
    \caption{\textbf{Summary of datasets used in this paper. }\#Train/\#Valid/\#Test denotes the number of samples in the training/validation/test set, respectively. \#Total is the sum of \#Train, \#Valid and \#Test. }\label{tab:dataset}
    \centering
     \begin{tabular}{ccccc} 
     \toprule
         \textbf{Dataset} & 
         \textbf{\#Train} &
         \textbf{\#Valid} &
         \textbf{\#Test} &
         \textbf{\#Total} \\
         \hline
        \textbf{USPTO-50K} & 40,006 
         & 5,001
         & 5,007
         & 50,016
         \\
         \textbf{USPTO-MIT} & 395,498 & 29,076 & 38,648 & 453,222\\
          \textbf{USPTO-FULL}
         & 768,679
         & 96,076
         & 96,015
         & 960,770\\
         \bottomrule
    \end{tabular}
\end{table}


\section{Evaluation Metrics}\label{sec: eval metric}
\textbf{Top-$k$ Accuracy.} We use the conventional top-$k$ accuracy to evaluate the performance of model. A prediction result is considered as correct if and only if all the reactants are correctly predicted.

\textbf{Top-$k$ SMILES Validity.} As SMILES is considered as correct when it can be identified by RDKit~\cite{landrum2013rdkit}. The top-$k$ SMILES validity is calculated as $\frac{1}{N\times k}\sum_{i=1}^N\sum_{j=1}^k \mathbbm{1}(\mathrm{SMILES\ is\ valid})$, where $N$ is the number of evaluated samples.

\textbf{Top-$k$ round-trip Accuracy.} There may be multiple methods to synthesize a given product. Evaluating the model's performance solely based on top-k accuracy may lead to biased results. Therefore, in addition to top-k accuracy, we also employ top-k round-trip accuracy as an extra metric to evaluate the model's performance. Top-k round-trip accuracy measures the percentage of predicted reactants that can undergo a reaction and yield the given product. To align with our baseline, we use the Molecule Transformer~\cite{schwaller2019molecular} as the forward reaction prediction model. The calculation of top-k round-trip accuracy follows the same approach as described in~\cite{wan2022retroformer}.


\section{Visualization of the Cross-Attention Coefficients}
We visualize the cross-attention maps across different transformer decoder layers using the checkpoint trained on the USPTO-50K dataset. The outcomes are depicted in Supplementary  Fig.~\ref{fig: sup_crs}.
\begin{figure}[htbp]
    \centering
    \includegraphics[width=\linewidth]{figs/full_attention_sample5.pdf}
    \captionsetup{name={Supplementary Fig}}
    \caption{Visualization of cross attention over product atoms and predicted tokens of different Transformer decoder layers. The number on the y-axis is the map number of atoms in the product. The reactants atoms that not appear in product is colored red in the x-axis. $\circ$ represents the end token.}
    \label{fig: sup_crs}
\end{figure}

\section{Implementation details} \label{impdetail}
\subsection{Generation of Order-Preserving Reactant SMILES}\label{opsmildetail}
Given a traversal order $O_P$ of product $P$, there might be multiple DFS orders of a reactant molecule that satisfy the condition to be the $O_P$-corresponding order. This is because reactants might contain atoms and substructures that are not present in the final product. Also, directly solving this problems is very difficult. Thus, we use an approximate  algorithm, which is shown in Algorithm~\ref{alg: CO} to generate the corresponding order defined in Eq. 2 given product molecule $P$, reactant molecule $R$ and a DFS order $O_P$ of $P$, where $am(i)$ represents the atom map number of atom $i$.



\begin{algorithm}[htbp]
   \caption{Get Corresponding Order}
   \label{alg: CO}
    \begin{algorithmic}
       \State {\bfseries Input:} product graph $P=(V_P, E_P)$, DFS order of product $O_P$, reactant $R=(V_R, E_R)$.
       \Function{get\_rank}{$O_P$: DFS order of $P$, $x$: atom, $R$: reactant, $AMRank$: a dict, $Vis$: a set}
       \State Add $x$ into $Vis$.
       \State Initialize $min\_son$ as $\infty$.
       \For{$y\in \mathrm{GET\_NEIGHBOR(x, R)}$}
            \If{$y\notin Vis$}
            \State GET\_RANK($O_P$, y, $R$, $AMRank$, $Vis$).
            \State $min\_son = \min(min\_son, AMRank[am(y)])$.
            \EndIf
       \EndFor
       \If{$x \in O_P$}
        \State $AMRank[am(x)]=rank(x, O_P)$. 
        \Else
        \State $AMRank[am(x)]= min\_son$.
        \EndIf
       \EndFunction
       \Function{get\_CO}{$CO$: a list, $x$: atom, $R$: reactant, $AMRank$: a dict, $Vis$: a set}
        \State Add $x$ into $Vis$.
        \State Append $x$ to $CO$.
        \State Initialize $N$ as an empty list.
        \For{$y\in \mathrm{GET\_NEIGHBOR(x, R)}$}
            \If{$y\notin Vis$}
                \State Append $y$ to $N$.
            \EndIf
       \EndFor
       \State Sort $N$ in ascending order according to $AMRank[am(x)], x\in N$.
       \For{$y\in N$}
        \State GET\_CO($CO$, $y$, $R$, $AMRank$, $Vis$).
       \EndFor
       \EndFunction
       \State Initialize $Vis$ as an empty set.
       \State Initialize $CO$ as an empty list.
       \State Initialize $AMRank$ as a empty dict.
       \State Set $root$ as the atom $x\in V_R$ that $am(x) = am(root(P, O_P))$.
       \State GET\_RANK($O_P$, $root$, $R$, $AMRank$, $Vis$)
       \State Reset $Vis$ as an empty set.
       \State GET\_CO($CO$, $root$, $R$, $AMRank$, $Vis$).
       \State {\bfseries Output:} $CO(R, O_P)=CO$
    \end{algorithmic}
\end{algorithm}


\subsection{Model Implementation details (Training and Inference)}
We implement our model based on \texttt{Pytorch 1.13}~\cite{paszke2019pytorch} and \texttt{torch\_geometric 2.2.0}~\cite{Fey/Lenssen/2019pyg}.  For model for USPTO-50K, we set the hidden size as 512, encoder layer as 8, decoder layer as 8 and the number of attention heads as 8. For model for USPTO-FULL, we set the hidden size as 768, encoder layer as 8, decoder layer as 8 and the number of attention heads as 12. The dropout ratio for both model is set  as 0.1. The highest learning rate of each model as set as 1.25e-4. We slowly increase our learning rate to the highest in the first few epochs and slowly decrease it using exponential decay. The model is trained with Adam optimizer~\cite{kingma2014adam}. The maximum number of training epochs for both stages is established at 300, and an early stopping strategy is implemented, which terminates the training process if the model fails to demonstrate performance improvement on the validation set for ten consecutive epochs.

It is important to note that a prescribed DFS order may implicitly capture the distribution of reactant sub-groups within the product, which could inadvertently result in information leakage.  To mitigate this issue, we employ a DFS order during the inference process that generates a canonical SMILES representation for the product molecule, ensuring a standardized input that precludes information leakage.

\section{Initial Node Features and Edge Features}\label{init_feat}
We use the atom and bond descriptors provided by \texttt{Open Graph Benchmark}~\cite{hu2020open}. There are nine atom descriptors including atomic number, chirality, formal charge and other properties that can be calculated by RDKit~\cite{landrum2013rdkit}. And three bond descriptors are used,  containing bond type, bond stereochemistry as well as whether the bond is conjugated. All the descriptors provide integer outputs. Thus we set up learnable embedding tables for each descriptor.  The initial node features and edge features are then obtained by summing up the embedding corresponding to the output of each descriptor.
\bibliography{sn-bibliography}
\end{document}
