\section{Introduction}
\label{sec1}

The nanocrystalline microstructure of inorganic materials (\textit{e.g.}, metals) could directly affect their engineering properties. Even though the grain size of polycrystalline materials can be controlled directly by time and temperature of the annealing process, the mechanism of grain growth is not fully understood \cite{MD3}. Mesoscopic computational methods can be used to study the thermodynamics of grain growth, extract the chemical potential functional of the system, and solve a non-Fickian diffusion equation (\textit{e.g.}, Allen-Cahn or Cahn-Hilliard equations) to obtain the spatial distribution of a multiphase system \cite{Phase-Field, Phase-Field-1, Phase-Field-2}.

Recently, due to the rapid growth of high-performance computing capabilities, it is possible to approach a multiphase system by using atomistic computational methods \cite{MD1, MD2}. This work aims to find a relation between microstructural configurations or morphology of crystalline materials with the engineering controlling variables (\textit{e.g.}, time and temperature). Understanding the microstructural characteristics under varying conditions could help engineers to design polycrystalline materials for applications where a specific morphology is preferable (\textit{e.g.}, turbine blades) \cite{turbine1,turbine2}. In this project, both mesoscopic and atomistic approaches were taken to examine the advantages and limitations of each. The effects of temperature and initial morphology on the final microstructure is studied to find a relation between engineering variables (\textit{e.g.}, temperature) and configuration of the polycrystalline material.

\section{Material and methods}
\label{sec2}

The molecular dynamic simulations were carried out using the LAMMPS (large-scale atomic/molecular massively parallel simulator) software \cite{LAMMPS} with an Embedded Atom Method (EAM) potential \cite{EAM1,EAM2} to elucidate the effects on the grain boundaries (GB) when the number of grains and temperature are increased for a pure aluminum (Al) crystal. The EAM potential can be described by eq. (\ref{eq:1}), where $E_{i}$ is the total energy of atom i, $F_{\alpha}$ is the surrounding energy function, $\rho_{\alpha}$ is the electron density and $\phi_{\alpha \beta}$ is the double-well interaction potential of $\alpha$ and $\beta$ type atoms.\\
\begin{equation} \label{eq:1}
 E_{i} = F_{\alpha} (\sum_{j \neq i} \rho_{\alpha} (r_{ij})) + \frac{1}{2} \phi_{\alpha \beta} (r_{ij})
\end{equation}
The EAM functional form, which is derived from \cite{EAM3, EAM4}, is used for the aluminum pair-wise interaction for all molecular dynamic simulations.

Four 200x200x200 (the length scale is \AA) aluminum polycrystalline structures with 5, 7, 9, or 10 grains were constructed using the Atomsk software \cite{atomsk}, with a 4.046 \AA{} minimum distance between the aluminum atoms. The grains were oriented randomly and the size is distributed along a normal distribution (Figure \ref{fig:1}). The timestep and final run time used for the molecular dynamic simulations were 0.005 ps and 5000 ps, respectively. The simulation box contained 483,115 atoms for all simulations. The NVT ensemble is used to model grain growth and periodic boundary conditions were imposed on the boundaries of the simulation box to mimic an infinite computational domain. Each polycrystalline structure is studied under three different temperatures (\textit{e.g.}, 500K, 600K and 700K) to examine the effect of temperature on the final microstructural morphology of the system.
Furthermore, in order to show the applicability of our computational framework to study more complex systems, particularly multi-components and multi-phases systems, one simulation of Al-Cu system with 10 grains (5 Al grains and 5 Cu grains, 50\%/50\% atomic chemical composition of nanocrystalline alloy) is constructed at 600K for 5000 ps with periodic boundary condition and using same NVT ensemble to study microstructral evolution in this nanocrystalline alloy. In order to model the interaction of Copper-Copper and Copper-Aluminum atoms, an alloy EAM potential, which is constructed based on \cite{ZHOU2016752,apostol2011,LIU19993227}, is added to previous framework for pure Al nanocrystalline materials simulations. The aim is that to show applicability and convenience extension of our multi-scale computational framework to study complex engineering systems.

Due to researches of \cite{doi:10.1021/acs.jpcc.6b10908} and \cite{ZHOU2016752}, where the EAM potentials for Al-Al and Al-Cu interactions are extracted respectively, the developed potentials to capture physical properties of nanocrystalline materials such as their melting point, lattice constant, module of elasticity, etc. are valid in the range of phase-transformation temperatures in this study (500K to 700K) and could capture inter-atomic interactions with reasonable accuracy. We refer readers to the mentioned references (\cite{doi:10.1021/acs.jpcc.6b10908} and \cite{ZHOU2016752}) for more detail information about the construction of these force-fields for Al-Al and Al-Cu interactions.

For the mesoscopic simulations, the continuum-field model \cite{Phase-Field,Phase-Field-1, Phase-Field-2} is used to extract the time evolution of grains under certain kinetically controlled conditions. The Gibbs free energy functional plays a critical role in continuum-field models, as described by the Ginzburg-Landau form (eq. (\ref{eq:2})).
\begin{equation} \label{eq:2}
 F = \int_{\Omega} [f_{local}(\eta_{i} (\vec{r})) + \frac{1}{2} \kappa \sum_{i} \nabla^{2} \eta_{i} (\vec{r})] d^{3} \vec{r}
\end{equation}
The first term in eq. (\ref{eq:2}) is related to the volumetric contribution and the second term, which is proportional to the gradient of curvature, is the surface curvature contribution. Since the surface contribution is much higher than the volumetric contribution, the system will try to minimize its energy functional by growing the grain boundaries which decreases the surface energy. Using the Euler-Lagrange extremum approach, the governing equation could be defined by,
\begin{equation} \label{eq:3}
 \frac{\partial \eta_{i}}{\partial t} = -L (\frac{\delta F}{\delta \eta_{i}}) = -L (\frac{\partial f_{local}}{\partial \eta_{i}} - \kappa \nabla^{2} \eta_{i}).
\end{equation}
The well known double-well potential \cite{Phase-Field,Phase-Field-1,Phase-Field-2} is used to model $f_{local}$, as defined by eq. (\ref{eq:4}).
\begin{equation} \label{eq:4}
 f_{local} = -\frac{\alpha}{2} \sum_{i} \eta_{i}^{2} + \frac{\beta}{4} (\sum_{i} \eta_{i}^{2})^{2} + (\gamma-\frac{\beta}{2}) \sum_{i} \sum_{j \neq i} \eta_{i}^{2} \eta_{j}^{2}
\end{equation}

The dimensionless values used for all mesoscopic simulations are: $\alpha = 1.0$, $\beta = 1.0$, $\gamma = 1.0$, $\kappa = 2.0$ and $L = 1.0$. The initial polycrystalline microstructures are generated using Dream3D software \cite{Dream3D}. Periodic boundary conditions were imposed on all the surfaces of the cubic simulation box (200x200x200 \AA). Equation (\ref{eq:3}) is discretized by using a Python script of the Crank-Nicolson finite difference method, primarily developed by the authors.

At the end all the mentioned steps are constructed based on automatic computational ensemble (i.e. FabSim) \cite{GROEN2016375,doi:10.1021/ci100007w,doi:10.1021/acs.nanolett.5b03547} to construct atomistic (i.e. molecular dynamics) and mesoscale (i.e. phase-field) simulations to ensure all the steps in the modeling pipeline, from initializing the initial microstructure based on user-defined number of grains, phase-transformation temperature, and atomistic potential for molecular dynamics simulations (i.e. in our case EAM pair-wise potential) would be done with minimum user interaction in order to facilitate the use-ability of the proposed framework to extend the materials science research for investigating advanced nanocrystalline materials. The detail of this automatic computational ensemble for both molecular dynamics and phase-field simulations are shown in Figure \ref{fig:ensemble}. Due to Figure \ref{fig:ensemble}, the initial microstructure of atomistic and mesoscopic simulations will be generated by using Atomsk and Dream3D softwares, then phase-transformation temperature and pair-wise potential (i.e. EAM potential) will be chosen based on chemical composition of initial microstructure, and finally these automatically generated microstructure and corresponding potentials will be forwarded to atomistic or phase-field solvers and then final results and analysis will be extracted by using Python bindings in Ovito software \cite{ovito}.

In the next section, the results of both mesoscopic and molecular dynamic simulations will be discussed in terms of their morphology, advantages and limitations, and reliability to deploy them for real industrial cases.

\section{Results}
\label{sec3}

\subsection{Temperature effects}
The results for the polycrystalline structures at different temperatures are visualized using Ovito visualization software \cite{ovito}. The visualization software can identify the types of crystal unit cell structures and the grain boundaries. During the grain growth process, volumetric and surface Gibbs free energies compete against each other to dominate the grain growth mechanism. Since the surface contribution is much higher than the volumetric contribution, the system will try to minimize its energy functional to reduce the surface energy. Surface diffusion might dominate the grain growth as the temperature increases due to the enhanced mobility of atoms.

The observed phase transformation in this Al nanocrystalline system, despite short time-scale of this study (5000 ps), is attributed to higher surface energy of this nanocrystalline materials because of nano size grain boundaries in comparison to bulk materials, which resulted in much lower activation energy for this Al nanocrystalline microstructure. This findings is consistent with several other researches that studies phase-transformation in nanocrystalline materials, specifically grain growth of metallic materials, that short phase-transformation time-scale observed predominantly \cite{MD3,KO201790,doi:10.1063/1.5044792}. As a result, in order to show precise convergence of phase-transformation in our simulation, the evolution of phase-transformation temperature, pair-wise energy, and total energy of the system are plotted in Figures \ref{fig:tempandenergy1}, \ref{fig:tempandenergy2}, and \ref{fig:tempandenergy3} respectively for the simulation of Aluminum with 10 grains at 600K. Due to Figures \ref{fig:tempandenergy1}, \ref{fig:tempandenergy2}, and \ref{fig:tempandenergy3}, phase-transformation temperature, pair-wise energy, and total energy reached a plateau which shows that phase-transformation converged to its physical state, which is consistent with several findings from \cite{HASLAM2001293,MIYOSHI2018118,Okita2016ISIJINT-2016-408,C8CE00767E,foiles2012}.

The initial configuration of the polycrystalline structures (Figure \ref{fig:2}) has four or higher order grain junctions. These higher order grain junctions are not favorable regarding the surface Gibbs free energy. Considering the melting point of aluminum is 933.5 K, the temperatures investigated in this work are lower, impacting the mobility of the atoms in the system. After 5000 ps, the higher order junctions were not eliminated from the 9 grain polycrystalline structure at 500 K (Figure \ref{fig:2}) but the number of three grain junctions increased because the surface energy is minimizing its value across the grain boundaries. Diffusion mechanisms (\textit{e.g.}, creep) could be activated above 0.5$T_{m}$, where $T_{m}$ is the absolute melting point of the material \cite{creep}. Indicating at higher temperatures the increased mobility of the atoms in the system can decrease the grain boundary surfaces. For the 9 grain polycrystalline structure at 600 K (Figure \ref{fig:2}), the higher order grain junctions were eliminated in the final structure. However, at 700 K there is an abnormal grain growth in the final structure due to the lack of higher order junctions in the initial structure. The final 9 grain polycrystalline structure at 600 K is suitable for industrial applications because only three grain junctions exist in the system. A material dominated by three grain junctions is an important characteristic because the three grain junctions balance out the surface tension allowing the microstructure to be isotropic, which implies the mechanical properties of the system are isotropic. The abnormal grain growth (Figure \ref{fig:2}) for the 9 grain polycrystalline structure at 700 K is not desirable because large grains can reduce the mechanical properties of a material significantly.

One of the mechanisms in plastic deformation of polycrystalline materials is dislocations \cite{dislocation}. Dislocations can be interpreted as a missing crystal plane which could facilitate the plastic deformation of polycrystalline materials. If the density of dislocations is high, the dislocations will be fixed, and further movement or distortion is not possible. However, the mechanism of dislocation formation is not fully understood because of the complex morphology in polycrystalline materials. One of the features of Ovito is an algorithm that can identify the dislocations or missing planes in the crystalline structure. According to Figure \ref{fig:3}, the grain boundaries are the source of dislocations, as shown by the red and blue lines. Increasing the temperature from 500 K to 600 K corresponds to an increased number of dislocations (cref. Figure \ref{fig:3}), but at 700 K, the mobility of the aluminum atoms eliminates all the grain boundaries and dislocations which could make the polycrystalline material ductile. Regarding engineering applications, strength is essential (\textit{e.g.}, ductility) and the 9 grain polycrystalline structure at 600 K has the most favorable microstructure because the final system is composed solely of three grain junctions and the density of the dislocations in the system is minimal. In the next section, the results for the mesoscopic simulations will be discussed and compared to the molecular dynamic simulation results.

\subsection{Multi-components nanocrystalline simulation of Al-Cu alloy}

In order to show the applicability of the proposed computational framework to study metallic nanocrystalline materials, a multi-components nanocrystalline structure of Al-Cu alloy (50\%/50\% Al-Cu atomic percentage chemical composition) with 10 initial grains at 600K is investigated and initial and final microstructures are analyzed (cref. Figure \ref{fig:alcu}). Due to Figure \ref{fig:alcu}, it could be understood that presence of high melting point component (i.e. Copper) could prevent abnormal growth observed in 600K of pure Aluminum (cref. Figure \ref{fig:3}), which is consistent with previous research from \cite{Verestek2017}. Furthermore, the final structure of this nanocrystalline Al-Cu alloy (cref. Figure \ref{fig:alcu}d) shows that there is an increase in grain boundary regions in comparison to pure Aluminum at 600K (cref. Figure \ref{fig:3}), which are identified as the  source of dislocation and would help to increase the mechanical strength of Al-Cu nanocrystalline alloy. Also, due to Figure \ref{fig:alcu} and Figure \ref{fig:3}, it could be understood that the presence of high melting component with lower diffusion coefficient limited the mobility of low melting component (i.e. Al) and resulted in a lower grain size at the final stage of phase-transformation, which again would help to increase mechanical strength of this nanocrystalline structure based on Hall-Petch relation.

\subsection{Mesoscopic simulations}
The mesoscopic simulations investigated in this work, can be called an isothermal continuum-field model. Meaning, no temperature gradient exists in the model. Therefore, a heat transfer equation needs to be coupled to a continuum-field equation to account for the temperature gradient. In addition, the semi-empirical variables used in the continuum-field model (\textit{i.e.}, $\alpha$, $\beta$, $\gamma$, $\kappa$ and $L$) should be considered as temperature-dependent kinetic parameters instead of constant values. Unfortunately, extracting the kinetic values for polycrystalline materials is not easy and several microscopic experiments of polycrystalline microstructures are needed to find the relationship between time and temperature. In this particular case, molecular dynamics could be assumed as a first principles approach to the grain growth problem because the only thing that needs to be specified in a molecular dynamic simulation is the pair-wise interaction, which is fully known for metallic materials. This could be considered as an advantage over mesoscopic simulation which suffers from lack of semi-empirical data.

The final microstructures of the mesoscopic simulations are shown in Figure \ref{fig:4} for four different initial grain structures. In comparison to the molecular dynamics model, the mesoscopic simulations do not give the types of crystal unit cell structures. Also, the grain boundary width (\textit{i.e.}, $\kappa$) is taken into account as a parameter which defines the width of the diffusion region or grain boundaries. Referencing Figure \ref{fig:4}, the initial finer microstructure (10 initial grains) could be identified as the reliable microstructure in terms of grain size and three grain junction points. It appears, because the mesoscopic model is isothermal and the kinetic parameters are constant values, mesoscopic simulations cannot predict the observed abnormal grain growth seen in the molecular dynamic simulations (cref. Figures \ref{fig:2} and \ref{fig:3}).

\subsection{Atomistic and mesoscopic simulations: grain size comparison}

In order to compare different microstructures at different phase-transformation temperatures quantitatively for atomistic (MD) and mesoscopic (phase-field) approaches, the grain diameter versus square root of phase-transformation time is plotted in Figure \ref{fig:grainsizes}. Note that the diagrams in Figure \ref{fig:grainsizes} are plotted after 100 ps due to reaching convergence plateu of temperature, pair-wise energy, and total energy according to Figures \ref{fig:tempandenergy1} to \ref{fig:tempandenergy3}.  Due to Figure \ref{fig:grainsizes}, it could be understood that phase-field simulation result of grain size is close to grain size evolution of atomistic simulations at 700K for all the initial microstructure configurations. In fact, this approach could be used to extract kinetic variables of phase-field (mesoscopic) approach at different temperature by matching the grain diameter evolution with molecular dynamics results. The most accurate agreement between molecular dynamics and phase-field simulations is observed at grain diameter evolution diagram of initial 9 grains structure at 700K, which means the kinetic variables that are extracted from \cite{Phase-Field,Phase-Field-1, Phase-Field-2} could capture phase-transformation behavior of pure Aluminum at 700K precisely. At the end, it could be noted that based on findings from Figure \ref{fig:grainsizes}, it could be inferred that molecular dynamics propose much more flexible computational framework, which could capture different phase-transformation regimes of nanocrystalline materials more precisely \cite{Holm1138}.

\subsection{Figures}
\begin{figure}[H]
 \centering
 \includegraphics[width={0.8\textwidth},keepaspectratio]{figure_1.jpg}
 \caption{Grain size distribution for 10 grains randomly oriented; generated using Atomsk software.}
 \label{fig:1}
\end{figure}
\begin{figure}[H]
 \centering
 \includegraphics[width={0.8\textwidth},keepaspectratio]{FabSim-Microstructural.jpg}
 \caption{Automatic pipline to construct atomsitc (molecular dynamics) and mesoscopic (phase-field) simulations based on given initial microstructure, phase-transformation temperature, and atomistic pair-wise potential (in case of molecular dynamics simulations).}
 \label{fig:ensemble}
\end{figure}
\begin{figure}[H]
 \centering
 \includegraphics[width={0.8\textwidth},keepaspectratio]{fig1.jpeg}
 \caption{Phase-transformation temperature for Aluminum nanocrystalline material at 600K with 10 initial grains.}
 \label{fig:tempandenergy1}
\end{figure}
\begin{figure}[H]
 \centering
 \includegraphics[width={0.8\textwidth},keepaspectratio]{fig2.jpeg}
 \caption{Pair-wise energy of the system for Aluminum nanocrystalline material at 600K with 10 initial grains.}
 \label{fig:tempandenergy2}
\end{figure}
\begin{figure}[H]
 \centering
 \includegraphics[width={0.8\textwidth},keepaspectratio]{fig3.jpeg}
 \caption{Total energy of the system for Aluminum nanocrystalline material at 600K with 10 initial grains.}
 \label{fig:tempandenergy3}
\end{figure}
\begin{figure}[H]
 \centering
 \includegraphics[width={0.8\textwidth},keepaspectratio]{figure-2.jpg}
 \caption{Aluminum GB structures with 9 grains at three different temperatures.}
 \label{fig:2}
\end{figure}
\begin{figure}[H]
 \centering
 \includegraphics[width={0.8\textwidth},keepaspectratio]{figure-3.jpg}
 \caption{2D section of the aluminum GB structures with 7 grains at three different temperatures.}
 \label{fig:3}
\end{figure}
\begin{figure}[H]
 \centering
 \includegraphics[width={0.8\textwidth},keepaspectratio]{al-cu.jpg}
 \caption{2D section of the Al-Cu GB structures as well as their coloring based on atom types (blue: Al, red: Cu) with 10 grains at 600K, a) initial microstructure colored by atom types, b) initial microstructure colored by grain boundaries, c) final microstructure colored by atom types, d) final microstructure colored by grain boundaries.}
 \label{fig:alcu}
\end{figure}
\begin{figure}[H]
 \centering
 \includegraphics[width={0.8\textwidth},keepaspectratio]{figure-4.jpg}
 \caption{Final microstructures of the mesoscopic simulations.}
 \label{fig:4}
\end{figure}
\begin{figure}[H]
 \centering
 \includegraphics[width={0.8\textwidth},keepaspectratio]{figure-5.jpg}
 \caption{2D section of the final microstructures for the mesoscopic simulations.}
 \label{fig:5}
\end{figure}
\begin{figure}[H]
 \centering
 \includegraphics[width={0.8\textwidth},keepaspectratio]{grain_sizes.jpg}
 \caption{Grain sizes plotted versus square root of time for different microstructures at different phase-transformation temperatures for both molecular dynamics and phase-field simulations.}
 \label{fig:grainsizes}
\end{figure}

\section{Conclusions}
\label{sec4}

In this research, the grain growth in polycrystalline materials are studied by two different approaches, molecular dynamics and mesoscopic models. According to the results, the mesoscopic simulations are faster than the molecular dynamic simulations. If a study needed to consider a larger spatio-temporal scale, mesoscopic models could be a better fit than molecular dynamics. However, the mesoscopic computational model in this work suffers from the lack of semi-empirical data for the kinetic variables and those values are not easy to extract them for real polycrystalline materials. On the other hand, molecular dynamics could tackle this problem as a first principles approach. Molecular dynamics could predict the effect of temperature and initial grain size on final microstructure precisely by defining the pair-wise interaction between participating atoms in the system. One of the novel ideas in this area could be using coarse-grained molecular dynamics to explore larger entities, such as grain structures, and study those coarse-grained morphologies in terms of their kinetic behavior to tackle the speed limitation of molecular dynamics.

\section*{Conflict of Interest Statement}

The authors declare that the research was conducted in the absence of any commercial or financial relationships that could be construed as a potential conflict of interest.

\section*{Author Contributions}

Mehrdad Yousefi conducted the research and prepared the draft of paper.

\section*{Funding}
No funding.

\section*{Acknowledgments}
No Acknowledgments.

\section*{Supplemental Data}
No Supplemental Data.

\section*{Data Availability Statement}
The datasets generated and analyzed for this study can be found in the [Continuum Field Grain Growth Github Repository.] [https://github.com/myousefi2016/Continuum-Field-Grain-Growth].

\clearpage

\section*{References}

\bibliographystyle{elsarticle-num}


\section{Introduction}

\end{document}

\section{Introduction}

Users on an e-commerce platform typically discover products through search, browsing categories or marketing campaigns. On our platform, search functionality is key to product discovery as each of these channels translates to a search query in the back-end. Search ranking is a critical aspect of our business. Hence any  improvement in the product search ranking, enhances user's experience on the platform and results in better business metrics. Although Learning to Rank (LETOR) has demonstrated the efficacy in the context of web search; it is a relatively new research area to be explored in the e-commerce. One major difference between the web search and e-commerce search lies in the interplay of relevance and popularity features. For example, e-commerce queries like ``tshirts" can yield a recall set of thousands of products which make it indispensable to incorporate popularity features. Also, typical human relevance judgments would not suffice as it would in the context of web search \cite{kumar2018did,karmaker2017application}. Section \ref{related-work} describes more about the work in this area.\par \noindent

Furthermore, in categories like fashion or home goods products lack a distinctive name and a unique identification is not possible. Users typically describe their intent in a search query using product attributes, ex: for purchasing a \textit{Tshirt} user could search for \textit{\{tshirt\}} or \textit{\{\textless brand \textgreater  t-shirts\}} or \textit{\{\textless color \textgreater t-shirts\}}. Each of these queries would typically result in thousands of relevant products from the catalogue as opposed to queries in hard goods categories with well defined products like ``iphone X 64 gb" which would result in few relevant products.
We refer such queries like \textit{\{tshirt\}} as \textit{unnamed queries}. Further exacerbating this situation there exists an infinite virtual shelf space in e-commerce and limited real-estate on user's devices. Therefore, it becomes vital to optimally rank products to enable efficient product discovery. The paper discusses the approach and challenges involved in applying LETOR methods to address search rankings for \textit{unnamed queries} in e-commerce domain.

\begin{figure}[h]
\centering
\includegraphics[height=1.6in, width=2.2in]{cohHist.png}
\caption{Query Distribution basis Coherency Scores}
\label{figure:hist}
\end{figure}

For such queries on our platform we observe a more skewed distribution of traffic across queries, a 90-10 distribution than typical 80-20 distribution where 10\% of queries lead to 90\% of the traffic i.e. number of downstream sessions as a result of query. Also, we observed that traffic and recall set size are strongly correlated. So, the few queries that lead to high traffic would also have a very large recall set. We also inspected the average click depth \footnote{The mean search engine ranking position for all the clicked products} of our queries, which showed significantly different user behavior. This provides a motivation to segment queries into high recall set (aka broad) and low recall set (aka narrow) for the ranking purposes. While the narrow queries have a clear intent and result in low average click depth, the broad queries are the ones which are browse intensive and have large average click depth. Examples of queries which constitute as broad queries are sports shoes, wallets for men, dresses, forever 21 dresses and of narrow queries are longline jacket for men, high rise ripped jeans for women, Blackberrys Charcoal Trousers, deal jeans long sleeves tops, open toe ballerinas etc. We describe our approach and analysis on broad and narrow queries in Section \ref{broad-narrow}.

\begin{figure}[h]
\centering
\includegraphics[height=1.6in, width=2.2in]{cohVsrss.png}
\caption{Coherency Score vs Recall Set Size}
\label{figure:coh-recall}
\end{figure}

Section 4 describes the system architecture and designs and Section 5 discusses the feature engineering and target variables. Finally, Section 6 describes our modeling approach, results and analysis. Our paper makes the following contributions:
\begin{enumerate}
\item We provide an approach to segment our queries into broad and narrow basis how coherent the downstream sessions are. We show that segmenting queries and training different models for each can be a better approach than training single model across the board
    \item Apart from using typical query features, product features and query-product features, we propose a denoising autoencoder based architecture to reduce sparsity of product features and skip gram based word embeddings for query-product features.
    \item We demonstrate the impact of various combinations of different types of features on the model's performance. Further, we study the behaviour of various target variables - CTR, Add to cart ratio, conversion and Revenue Per Impression.
    \item We highlight the differences between broad and narrow queries in terms of modelling approach, feature importance etc. We also show how our model significantly improves NDCG compared to the baseline model built upon style popularity.
\end{enumerate}

\section{Related Work} \label{related-work}

LETOR methods have demonstrated their success in web search \cite{chapelle2011yahoo, azzopardi2016advances}. Various LETOR models like RankNet, LamdaMart, AdaRank and RankBoost have been compared on Web Search data \cite{li2014learning,  liu2009learning,  burges2010ranknet,  chapelle2011yahoo}.  Moreover search has been extensively studied in the e-commerce primarily from the retrieval perspective \cite{agrawal2009diversifying, li2011towards, long2012enhancing, van2016learning, yu2014latent}.

 Karmaker et al.  \cite{karmaker2017application}  attempted to apply LETOR in the e-commerce \footnote{Walmart dataset} setting. They showed how LamdaMart is able to optimize the combination of popularity and relevance based features; and perform the best even in E-commerce ranking. The work also suggested that it might be helpful to segment queries and train separate models for each segment; however it ended up training one model across board.

Researchers have often segregated queries in web search domain too.  Kumaripaba Athukorala et al's presented an interesting work on Broad and Narrow queries in web search \cite{athukorala2014narrow}. Also, Cheng Luo et al. \cite{luo2014query} defines 3 types of queries:
\textit{Ambiguous}: a query that has more than one meaning
\textit{Broad}: a query that covers a variety of subtopics, and a user might look for one of the subtopics by issuing another query
\textit{Clear}: a query that has a specific meaning and covers a narrow topic. Both claim that supporting exploratory search is a very challenging problem,
because of the dynamic nature of the exercise and intent of the users. In e-commerce domain, we tackle this problem by building a classification model as described in Section \ref{broad-narrow}.

\section{Broad and Narrow Queries} \label{broad-narrow}

We randomly sampled 100k queries and labelled them as Broad/Narrow. We have divided the queries into train and test in the ratio of 70:30. Later we have trained a SVM classifier with radial-basis kernel on the train queries. We have considered multiple sets of features - Word2Vec of query, result set size and identified query attributes.

\subsection{Coherency score} \label{coherency-socre}

For every query based on the recall set, we define coherency score which is used as a feature for the classification model. We create an embedding of each product on the platform using Matrix Factorization atop matrix of all user-product clicks on our platform. For a query $q$, and recall set $R = {P_1,P_2,...P_n}$ , we define centroid $R_c$ and coherency score $c_{qr}$ as

\begin{equation}
    R_c = \frac{\sum P_i}{n}
\end{equation}

\begin{equation}
    c_{qr} = \underset{i}{\mathrm{median}} \{<p_i.R_c>\}
\end{equation}

It is the median of inner product of each product with the centroid of all products. Typically, queries with large recall set would contribute to majority of traffic on our platform and would also have low coherency score.

\subsection{Word2Vec Embeddings} \label{word2vec-embeddings}

We use query clickstream logs for training the word embeddings. It is a dataset of all the queries and subsequent downstream sessions as a result of query (specifically the products which were clicked, added to cart and finally purchased). As in \cite{arora2016decoding}, we consider each session i.e. sequence of products $P_1,P_2, ....P_n$ as the document, and the attributes of each product (eg brand-nike, color-red, neck-polo) as the words. Directly using each product as words can induce sparsity because products are separated in the time space. This document is further appended with query words and top-10 synonyms of each word in the query (to augment our vocabulary) from wordnet \cite{miller1995wordnet}. Skip-gram model learns embedding of each query token, external synonyms from wordnet and all the catalogue attributes. The product embedding is computed as the centroid of attribute embeddings. And the query embedding is centroid of all unigrams in query.

Formally, let $q \ \epsilon \  Q$ be a query from the query corpus. $W$ is the set of all unigrams in each query with $S$ as the set of top-10 synonyms of each unigram in query. Further, let $P_1,P_2,...P_n$ be the products clicked in a particular session as a result of the query and $A_i$ be the set of attributes of $P_i$. Then a document $d$ is constructed as:
$d = W \cup S \cup \{A_i\} (1 \leq i \leq n)$
We construct such documents from all query-sessions in our clickstream and train skip-gram model on the same to learn embedding for each attribute ($v_{a_i}$) / query unigram ($v_{w_i}$) / query synonym ($v_{s_i}$).

\begin{equation}
    v_{p_{i}} = \frac{\sum_{a_i \epsilon A_i } {v_{a_i}}}{n}
\end{equation}
\begin{equation}
    v_{q_{i}} = \frac{\sum_{w_i \epsilon W}   {v_{w_i}}}{|W|}
\end{equation}

\subsection{Query Attributes} \label{query-attributes}
Some of the query features include basic attributes like query length, number of words in query, etc. We have fragmented the query and also included features such as the presence of the attributes. Ex: whether the query contains an article type or brand or color.

\subsection{Target Variable} \label{target-classifier}

In order to train the model, we have assigned the labels by a formula based on heuristics which is primarily based on the coherency score. Typically, queries with large recall set would contribute to majority of traffic on our platform and would also have low coherency score.

\begin{table}[hb]
\centering
\begin{tabular}{|l|l|l|l|l|l|}
\hline
\textbf{Metric} & \textbf{Broad} & \textbf{Narrow} \\ \hline
Percent Queries             & 13 \%            & 87 \%                         \\ \hline
Percent Traffic (Sessions)           & 73 \%            & 27 \%                         \\ \hline
Distinct Brands          & 15.2            & 4.26                         \\ \hline
Distinct Article Types          & 2.7            & 1.14                         \\ \hline

\end{tabular}
\caption{Query Segment Statistics}
\label{table:stats}
\end{table}

The figure \ref{figure:hist} shows  the distribution of coherency score (number of distinct queries corresponding to each score) and figure \ref{figure:coh-recall} shows the recall set bin corresponding to each coherency score. We had divided all the recall set sizes into 120 uniform-sized bins for this experiment. We threshold at coherency score of 0.58, basis the elbow shown in figure \ref{figure:coh-recall}. This corresponds to bin number 92; which further corresponds to a recall set size of 1910-2300. Clearly, it can be attributed to \textit{unnamed queries}. So, a query with coherency score $\leq$ 0.58 is referred to as broad query while  query with coherency score $>$ 0.58 is referred to as narrow query. The table \ref{table:stats} shows various statistics regarding both the segments. It is evident that very few broad queries lead to majority of traffic. Also, broad queries often have more number of distinct brands and article types the narrow queries. In order to avoid the outliers, we have considered only queries with coherency scores $\leq$ 0.3 as broad queries and $>$ 0.7 as narrow queries from the train set, rest all queries are filtered out.

\subsection{Performance} \label{performance}

We used accuracy as an indication of model's performance. We generated the predictions on the test queries which achieved an overall accuracy of 0.812. Apart from the test data we further manually evaluated a sample of  10k queries by the experts and the accuracy on those queries was found out to be 0.89. The SVM classifier outperformed the primary heuristics baseline model which had an accuracy of 0.83.

\section{System Design} \label{system-design}

This section discusses the architecture (figure \ref{figure:arch}) involved in retrieval and ranking of search products on our platform. We use SOLR as the underlying search engine with over 3M fashion products indexed.

\begin{figure}[ht]
\includegraphics[height=1.8in, width=3in]{ltr.png}
\caption{Architecture}
\label{figure:arch}
\end{figure}

When a user issues a \textit{query}, the retrieval layer renders a set of top-K (typically 1000) products based on BM-25 score. Traditional BM25 based approaches are quite effective for retrieval; however in broad queries like ``tshirts", it becomes extremely significant to include business metrics like CTR and conversion to optimize the ranking. Not just the demand, it becomes critical for our platform to include the available inventory as an input to the ranking algorithm. To incorporate that we have a basic model which assigns a global score to each product as a weighted combination of various features related to product's performance in past 2 weeks (CTR, revenue, quantity sold etc.) and inventory. \footnote{The primary focus of this paper would be LETOR, instead} Final search recall score is computed as weighted sum of BM25 score and the product performance score. The top-K results are further re-ranked using the trained LETOR model. It is worth mentioning that we have separate models for broad and narrow queries. The LETOR model is invoked accordingly.
The LETOR model is trained using:
\begin{enumerate}
    \item Catalogue Data : Structured information regarding each product's  physical features like  brand, color, mrp etc.
    \item Transactional Data: Product's output business metrics like daywise revenue, CTR etc.
    \item Query-Clickstream logs : Logs each query and information regarding query's downstream sessions like products seen (impressions), clicked, added to cart, wishlisted, liked, purchased etc.
\end{enumerate}

\section{Model}

Learning to rank is a popular approach that provides a principled way to  optimize ranking of search results given various features. This section focuses on various features and  target variables  we used for training our LETOR models. From modelling perspective, we tried 2 pointwise models - Random Forests and Gradient Boosting Model and 2 pairwise models - RankNet and LamdaMart. We built three different types of models - one specific for broad queries, one specific for narrow queries and lastly a combined model across the board.

\subsection{Feature Engineering} \label{feat-eng}

We use three different types of features:

\begin{enumerate}
    \item \textbf{Query Features}: These are features specific to query like total length of query, number of words, is brand (eg Nike, Tommy Hilfiger) present in query, is article type (eg Dresses, Shoes) present in query, the identified article type, brand etc.

    \item \textbf{Product Features}: These are features specific to the products (documents) They can either be popularity related or physical features. The popularity features include features involving past performance of the product's brand or article type (hereafter referred to as entity) like revenue in 15 days, quantity sold in 15 days etc. It is worth mentioning that we do not directly include the performance metrics of each product directly, as suggested in \cite{karmaker2017application}. We observed that this leads to  to overfitting and poor generalisation on unseen products.

    The physical features include feature types which are uniform across article types (eg brand, color, material/fabric etc) and those which are specific to article types. For instance tshirts would have attributes like neck (round/polo) while shoes could have attributes like outsole type (marking/non-marking), cleated (yes/no) etc. The total number of distinct attributes (key-value pairs) on our platform is over 10k. These features are quite sparse in nature and models trained using them don't perform well. We trained a separate denoising autoencoder to reduce the dimensionality of product's physical features.

    The architecture is shown in figure \ref{figure:autoencoder} We consider products from each master category (for eg all tshirts, casual shirts, jackets, sweaters etc. would fall in topwear) and provide one-hot encoded representation of its attributes as the input to the network. A uniform noise from 0 to 1 is added for better generalisation. Post that we have 3 layered encoder and decoder as shown in figure \ref{figure:autoencoder}. The final learnt embeddings consists of 32 dimensions. This greatly captures and embeds the most informative features in the original feature representation as we discuss later in the Results Section where we compare this with normal autoencoder (without the noise layer). The autoencoder based approach would greatly help to reduce sparsity in features and further assist LETOR models to optimise ranking by learning weights (parameters) for different features.

    \begin{figure}
\includegraphics[height=1.8in, width=3in]{autoencoder.png}
\caption{Denoising Autoencoder Architecture}
\label{figure:autoencoder}
\end{figure}

\item \textbf{Query Product Features} The query product features are features which involve both query and product - eg ctr of a tshirt product when the query is ``batman printed tshirt". The query product features can again be of 2 different types: popularity based and relevance based. The popularity features include past performance of product's entity as a result of query. Again, we do not directly include query-product features on product level (eg revenue of product from given query) to avoid overfitting.

The relevance related query product features encompasses features describing the match or similarity between given query and product. BM 25 is a traditional example for the same. To better capture the similarity between query and product, we attempt to embed all our queries and products in a common ``query relevance" space using skip-gram based embeddings as described in Section \ref{word2vec-embeddings}. And the query product relevance score is computed as the inner product of query embedding and the product embedding.

    \end{enumerate}

    \subsection{Targets} \label{target}

   As demonstrated in \cite{kumar2018did}, while effective for web search, crowdsourcing is not a very effective way to obtain relevance judgments for E-com search. This can be attributed to the large recall set in e-commerce and how difficult it is to describe a fashion product - making it indispensable to incorporate business metrics as the relevance.

   For a query $q$, and product $p$, let $I_{qp}$ represent the total number of impressions, $C_{qp}$ be the total numbers clicks, $B_{qp}$ be the total number of add to bag / cart, $Q_{qp}$ be the total products purchased and $R_{qp}$ be the total revenue of product as result of the query. We use the following target variables for our analysis:

   \begin{enumerate}
       \item \textbf{Click-Through Rate} It is the probability of clicking on the listpage (the page as a result of search query). Better the ranking, higher would be the CTR
        \begin{equation}
            CTR_{qp} = \frac{C_{qp}}{I_{qp}}
        \end{equation}

        \item \textbf{Add to cart Rate} It is the probability of adding a product to the cart post the click. It is the perceived utility of click page.
        \begin{equation}
            ATCR_{qp} = \frac{B_{qp}}{C_{qp}}
        \end{equation}

        \item \textbf{Conversion} It is the probability of purchasing a product from listpage. This can be considered as the overall satisfaction of the user.
        \begin{equation}
            Conv_{qp} = \frac{B_{qp}}{I_{qp}}
        \end{equation}

        \item \textbf{Revenue per Impression} It refers to the overall business value (revenue) from each impression as a result of the query.
        \begin{equation}
            RPI_{qp} = \frac{R_{qp}}{I_{qp}}
        \end{equation}

   \end{enumerate}

    \section{Results}

    \subsection{Dataset}

  We randomly sampled 100k queries. We have classified them into broad and narrow using on the model described in Section 3. We resulted 13k broad queries and 87k narrow queries. We sampled queries in 80-20 proportion in stratified manner to collate train (broad and narrow) and test (broad and narrow) queries.

\subsubsection{Train and Test Data}

We use the clickstream logs to  retrieve the list of products which had impressions when the query was fired (for every train query). Every $<query-product>$  pair is represented as a row. For modeling purposes, we pruned the rows with very few or very large number of impressions. We used $\log(ctr)$ as the target variable (computed for each query-product  pair) for all our experiments. Initially we built a model over all the queries and later experimented with two different models on broad and narrow queries separately.

For testing purposes, top 500 products are retrieved for the test queries based on the existing search ranking (as discussed in Section \ref{system-design}) and the features are extracted for all the query-product pairs. We predict $\log(ctr)$ for the query-product and  evaluate the performance using NDCG metric as discussed in next section.

      \subsubsection{Evaluation Metric}

NDCG is the metric used most often in the web search. We used the same in our context; and report the average NDCG over all queries. In our case, the ideal ranking of products is inferred from the product's past performance given the query context. We considered the true realized ctr (or other metrics like atcr, conversion, rpi) of query-product to compute the ideal ranking of products. As in \cite{karmaker2017application}, the ground truth relevance ratings based on the target variable were computed for all products by normalizing and discretizing to a $b$ point integer scale ${1,2,..b}$; where b is the bin size. The relevance score for ground truth ranking in case of ctr can be computed as:

\begin{equation}
    rel_{ctr_{qp}} = ceil(\frac{b.ctr_{qp}}{max_{p|q} ctr_{qp}})
\end{equation}

For computing NDCG@K, we take the top k (we used $K=48$) products for the query and compute relevance scores for each query-product as above.

Let $i_p$ be the predicted rank position for each product and $i_i$ be the ideal rank position. Now for each query $q$, compute

\begin{equation}
    DCG = \sum_p \frac{2^{rel_{qp} - 1}}{log_2(i_p+1)}
\end{equation}

\begin{equation}
    IDCG = \sum_p \frac{2^{rel_{qp} - 1}}{log_2(i_i+1)}
\end{equation}

\begin{equation}
    NDCG = \frac{DCG}{IDCG}
\end{equation}

    \subsection{Cross Target Learning}

In e-commerce, choosing one target variable for LETOR is not easy; especially considering the large correlation between the target variables. We intend to optimize for multiple business metrics (discussed in Section \ref{target}) simultaneously. We  evaluated the performance of LambdaMART models trained using one training target on test datasets based on other target. Also, we have typically transformed all our target variables using logarithm because of an approximate gaussian distribution. The results are tabulated in Table \ref{table:target-study}. We observe that all train metrics perform well when tested on the same metric but experience a drop when tested on others (diagonal entries in Table \ref{table:target-study}). Conversion metric performs the best in terms of robustness, since it performs well across the board. This can be attributed to how conversion captures the entire funnel of user's behaviour on platform (from visit to click, cart, order etc.) However, conversion faces sparsity issues because very few products (amongst the entire catalogue) end up being converted. Hence, we recommend to use CTR to build models initially and transition to conversion once we have enough data. All our experimental results are based on CTR metric.

\begin{table}[ht]
\begin{tabular}{|l|l|l|l|l|}
\hline
\multicolumn{1}{|c|}{\multirow{2}{*}{\textbf{Train Target}}} & \multicolumn{4}{c|}{\textbf{Test Target}}                    \\
\multicolumn{1}{|c|}{}                                       & \textbf{\newline CTR} & \textbf{ATCR} & \textbf{Conv} & \textbf{RPI} \\ \hline
\textbf{log(ctr)}                                            &  0.79&  0.71& 0.69 & 0.71          \\ \hline
\textbf{log(atcr)}                                            & 0.75& 0.82& 0.71 & 0.73          \\ \hline
\textbf{log(conversion)}                                            & 0.71& 0.79& 0.78 & 0.78          \\ \hline
\textbf{log(rpi)}                                            & 0.68 & 0.75 & 0.73 &	0.76          \\ \hline
\end{tabular}
\caption{Cross Target Learning}
\label{table:target-study}
\end{table}

\subsection{Feature Study}

\subsubsection{Reducing Sparsity in Query Product Features}

We took all queries over 15 days for training the skip-gram model with window size 10. We randomly sampled 10M documents (each document is query and corresponding session).  The table \ref{table:w2v} shows few similar attributes to some queries along with cosine similarity. We use these skip-gram embeddings to compute query-product relevance score as described in Section \ref{feat-eng}

\begin{figure}[h]
\includegraphics[height=1.8in, width=3in]{ModelPerformances.png}
\caption{Comparison of different models. All xlabels are explained in Table \ref{table:different_combinations}}
\label{figure:modelcompare}
\end{figure}

 \subsubsection{Feature Combinations and Models}
For all our experiments and analysis, we divided features into 4 different types - query features, query-product features (includes both word2vec based relevance and popularity features), product popularity features and product autoencoder based (physical) features. We experimented with 5 different combinations of features as shown in Table \ref{table:different_combinations}

\begin{table}[b]
\centering
\begin{tabular}{|p{1.5cm}|p{5cm}|}
\hline
\textbf{Query} & \textbf{Similar Attributes with cosine similarity}  \\ \hline
nike & dri-fit(0.72), adidas(0.64), puma(0.58), sportwear(0.55)    \\ \hline
baniyan (hindi word for vest) & vests white(0.57), sando (0.513), cotton vest (0.51), innerwear(0.504)    \\ \hline
swimwear & swimsuit(0.915), swimdress(0.718), tankini(0.701), bikini(0.606)    \\ \hline
party dress & maxis (0.752), short dress (0.674), gown(0.663), black dress(0.65),     \\ \hline
\end{tabular}
\caption{Attributes similar to query}
\label{table:w2v}
\end{table}

\begin{table}[t]
\centering
\begin{tabular}{|p{2cm}|p{1.2cm}|p{1.2cm}|p{1.2cm}|p{1.2cm}|}
\hline
\textbf{Name} & \textbf{Query Features} & \textbf{Query Product Features} & \textbf{Product Popularity Features} & \textbf{Product Physical Features} \\ \hline
Only Relevance features & Y & N & N & Y   \\ \hline
Only Popularity features & N & Y & Y & N   \\ \hline
No Query Product features & Y & N & Y & Y    \\ \hline
No Autoencoder features  & Y & Y & Y & N    \\ \hline
All features & Y & Y & Y & Y    \\ \hline
\end{tabular}
\caption{Different Feature Combinations}
\label{table:different_combinations}
\end{table}

We will constantly use the codes (eg YNYY) mentioned in Table \ref{table:different_combinations} hereafter.

Firstly, we compare different models (2 pointwise - Random Forest, GBM and 2 pairwise - RankNet and LamdaMart). The figure \ref{figure:modelcompare} shows the NDCG of different models across different feature combinations.

 \begin{figure}[hb]
\includegraphics[height=1.8in, width=3in]{broad_narrow_feature_importance.png}
\caption{Broad Vs Narrow}
\label{figure:broadvsnarrow}
\end{figure}

Clearly, LamdaMart performs the best across different feature combinations (except YYYN where RankNet performs marginally better). Considering LamdaMart as the model, we can also study the performance of different feature combinations in figure \ref{figure:modelcompare}. In terms of NDCG performance, $YYYN < YNNY < NYYN < YNYY < YYYY$ Furthermore, introducing autoencoder features helped a lot; as is evident from gain in $YYYN \ to \   YYYY$. Also, popularity features (both product and query-product) helps to improve the performance. We will be studying the importance of each type of feature across broad and narrow queries later in this section.

Next, we attempted to see if training separate models for broad and narrow queries help to improve performance than training just a single model across the board. For this experiment, we used LamdaMart model and feature combination as YYYY.
The table \ref{table:combined} shows the test NDCG values. Clearly, training separate models for broad and narrow queries boost the overall performance of broad and narrow queries. The improvement in narrow queries (12 \%) is much higher than that in broad queries (2.4 \%).

\begin{table}
\centering
\begin{tabular}{|p{3cm}|p{1.5cm}|p{1.5cm}|}
\hline
\textbf{NDCG} & \textbf{Broad Queries} & \textbf{Narrow Queries} \\ \hline
Single Model & 0.81 & 0.74   \\ \hline
Model on Broad Queries & 0.83 & 0.72   \\ \hline
Model on Narrow Queries & 0.79 & 0.83  \\ \hline
\end{tabular}
\caption{Combined vs Individual Model}
\label{table:combined}
\end{table}

We also compared our final model (built separately on broad and narrow queries) to the baseline model (discussed in Section \ref{system-design}). The table \ref{table:baseline} compares our LETOR model with the baseline

\begin{table}
\centering
\begin{tabular}{|p{3cm}|p{1.5cm}|p{1.5cm}|}
\hline
\textbf{Query Type} & \textbf{Baseline} & \textbf{LETOR} \\ \hline
Broad & 0.75 & 0.83  \\ \hline
Narrow & 0.69  & 0.83   \\ \hline
\end{tabular}
\caption{LETOR vs Popularity Based Model}
\label{table:baseline}
\end{table}

We observe that improvement in narrow queries (20.28 \%)  is significantly higher than broad queries (10.67 \%). This can be attributed the role of popularity features in broad features. While popularity plays the major role in broad queries, relevance has a major role to play in narrow queries where the user's intent is quite clear.

Finally, we study the importance of different types of features for broad and narrow queries. Figure \ref{figure:broadvsnarrow} demonstrates how inclusion and exclusion of features affect the performance. Query style popularity features have a important role in the model built over broad queries compared to the one built over narrow queries. Exclusion of this set of features showed a sharp decline in the NDCG. This shows we are able to learn the ranking from the product physical features and query features for narrow queries more accurately. This could be because of the more information in the query and the specific intent of the user.

\section{Conclusions}

We presented a framework for building LETOR models for an e-commerce platform - specifically for the \textit{unnamed queries}. We proposed a notion of coherency score and used it to segment queries into broad and narrow. We discussed the challenges involved in feature representation (query, product and query-product) and target metrics (ctr,atcr,conversion,rpi) in e-commerce. We proposed a denoising auto-encoder based architecture to tackle sparsity in product features and skip-gram based word embeddings for query-product sparsity issues. We compared the performances of both pointwise and pairwise LETOR models on fashion category data set.  We discussed how segmenting queries into broad and narrow (basis ) help in LETOR models for e-commerce. While popularity has a major role to play in broad queries, it is not that significant in narrow queries. We reported NDCG@48 for all the queries, it might be more relevant decide K based on the nature of the query (broad or narrow).

 In future, we intend to remove inherit bias (position, presentation bias etc) from the targets while training. When a new brand is launched, typically the brand based popularity will have zero values and the products of the brand will be penalized. Such cold start problems are to be resolved. We plan to build multiple models by strategically varying features and targets and later combine the predictions by an ensemble model.

\balancecolumns

\clearpage

\bibliographystyle{IEEEtran}


\section{Introduction}\label{se:intro}
\begin{figure}[b!]
\centering
\subfloat[\label{fig:l-drawing-example}]{\includegraphics[page=1,height=0.2\textwidth]{octahedron}}\hfil
\subfloat[\label{fig:nodetrix-example}]{\includegraphics[height=0.2\textwidth,page=1]{nt-representation}}\hfil
\subfloat[\label{fig:clique-example}]{\includegraphics[page=1,height=0.2\textwidth]{clique-planarity}}
\caption{
(a) A planar L-drawing, which determines a $4$-modal embedding. (b) A planar NodeTrix representation. (c) A planar intersection-link representation using comb-shaped polygons.
}
\end{figure}
Computing $k$-modal embeddings of planar digraphs, for some positive even integer $k$ called \emph{modality}, is an important algorithmic task at the basis of several types of graph visualizations.
In \emph{$2$-modal embeddings}, also called \emph{bimodal embeddings}, the outgoing and the incoming edges at each vertex form two disjoint sequences.
Bimodal embeddings are ubiquitous in Graph Drawing.
For instance, level planar drawings~\cite{BattistaN88,JungerLM98} and upward-planar drawings~\cite{BattistaT87,GargTamassia01}---two of the most deeply-studied graph drawing standards---determine bimodal embeddings.
\emph{4-modal embeddings}, where the outgoing and the incoming edges at each vertex form up to four disjoint sequences with alternating orientations, arise in the context of planar \mbox{L-drawings} of digraphs. In an \emph{L-drawing} of an $n$-vertex digraph, introduced by Angelini {\em et al.}\xspace~\cite{AngeliniLBDPRT16}, vertices are placed on the $n \times n$~grid so that each vertex is assigned a unique $x$-coordinate and a unique $y$-coordinate and each edge $uv$ (directed from $u$ to $v$) is represented as a $1$-bend orthogonal polyline composed of a vertical segment incident to $u$ and of a horizontal segment incident to $v$.
Recently, Chaplick {\em et al.}\xspace~\cite{ccdnptw-plddg-17} addressed the question of deciding the existence of \emph{planar L-drawings}, i.e., L-drawings whose edges might possibly overlap but do not cross and observe that the existence of a $4$-modal embedding is a necessary condition for a digraph to admit such a representation (\cref{fig:l-drawing-example}).

To the best of our knowledge, no further relationships have been explicitly pointed out in the literature between modal embeddings and notable drawing models for modality values greater than four, yet they do exist.
\mbox{Da Lozzo} {\em et al.}\xspace~\cite{LozzoBFP18} and Di Giacomo {\em et al.}\xspace~\cite{GiacomoLPT17} study the planarity of \emph{NodeTrix representations} of flat clustered networks, a hybrid representational model introduced by Henry, Fekete, and McGuffin~\cite{DBLP:journals/tvcg/HenryFM07}, where clusters and intra-cluster edges are represented as adjacency-matrices, with rows and columns for the vertices of each cluster, and inter-cluster edges are Jordan arcs connecting different matrices (\cref{fig:nodetrix-example}).
For clusters containing only two vertices, it is possible to show that the problem of computing planar NodeTrix representations coincides with the one of testing whether a special digraph, called the \emph{canonical digraph\xspace}, associated to the network admits a $6$-modal embedding.
For higher values of modality, $k$-modal embeddings occur in the context of Intersection-Link representations of flat clustered networks. In an \emph{intersection-link representation}~\cite{DBLP:journals/jgaa/AngeliniLBFPR17,DBLP:conf/gd/AngeliniEH0KLNT18}, vertices are represented as translates of the same polygon, intra-cluster edges are represented via intersections between the
polygons corresponding to their endpoints, and inter-cluster edges---similarly to NodeTrix representations---are Jordan arcs connecting the polygons corresponding to their endpoints. For any modality $k\geq 2$, it can be shown that testing the existence of a $k$-modal embedding of the canonical digraph\xspace of a flat clustered network with clusters of size two is equivalent to testing the existence of an intersection-link representation in which the curves representing inter-cluster edges do not intersect, when vertices are drawn as comb-shaped polygons (\cref{fig:clique-example}).

{\bf Related Work.}
It is common knowledge that the existence of bimodal embeddings can be tested in linear time: Split each vertex $v$ that has both incoming and outgoing edges into two vertices $v_{in}$ and $v_{out}$, assign the incoming edges~to~$v_{in}$ and the outgoing edges to $v_{out}$,
connect $v_{in}$ and $v_{out}$ with an edge, and test the resulting (undirected) graph \mbox{for planarity using any of} the linear-time planarity-testing algorithms~\cite{BoothL76,HopcroftT74}.
Despite this, most of the planarity variants requiring bimodality are NP-complete; for instance, upward planarity~\cite{GargTamassia01}, windrose planarity~\cite{AngeliniLBDKRR16}, {partial-level planarity}~\cite{BrucknerR17},
clustered-level planarity and $T$-level planarity~\cite{Angelini15,KlemzR17}, ordered-level planarity and bi-monotonicity~\cite{KlemzR17}. In this scenario, a notable exception is represented by the classic level planarity problem, which can be solved in linear time~\cite{JungerLM98}, and its generalizations on the standing cylinder~\cite{BachmaierBF05}, rolling cylinder and the torus~\cite{AngeliniLBFPR16}.
Although the existence of a bimodal embedding is easy to test,  Binucci, Didimo, and Giordano~\cite{BinucciDG08} prove that the related problem of finding the maximum bimodal subgraph of an embedded planar digraph is an NP-hard problem.
Moreover, Binucci, Didimo, and Patrignani~\cite{BinucciDP14} show that, given a \emph{mixed
planar graph}, i.e., a planar graph whose edge set is partitioned into a set of directed edges and a set of undirected edges, orienting the undirected edges in such a way that the whole graph admits a bimodal embedding is an NP-complete problem.
On the other hand, the question regarding the computational complexity of constructing $k$-modal embedding for $k\geq 4$ has not been addressed, although the related problem of testing the existence of \mbox{planar L-drawings has been recently proved NP-complete~\cite{ccdnptw-plddg-17}.}

\paragraph{\bf Our results.}
We study the complexity of the \kmodality{k} problem, which asks for the existence of $k$-modal embeddings of planar digraphs---with an emphasis on $k=4$. \mbox{Our results are as follows:}
\begin{enumerate}[-]
	\item We demonstrate a complexity dichotomy for the \mbox{\sc $4$-Modality}\xspace problem with respect to the maximum degree $\Delta$ of the input digraph. Namely, we show NP-completeness when $\Delta \geq 7$
	\ifshortversion{{\mbox(see
\section{Conclusions}\label{se:conclusions}

In this paper, we studied the complexity of the \kmodality{k} problem, with special emphasis on $k=4$. We provided complexity, algorithmic, and combinatorial results.
Our main algorithmic contribution for $k=4$ and $\Delta \leq 6$ leverages an elegant connection with the {\sc NAE}\xspace-satisfiability of special CNF formulas, whose study allowed us to strengthen a result in~\cite{PorschenRS03}.
Moreover, we showed notable applications of the previous results to some new interesting embedding problems for clustered networks, some of which solve open problems \mbox{in this area~\cite{DBLP:journals/jgaa/AngeliniLBFPR17,GiacomoLPT17}}.

\subsection{Simply-Connected Graphs}\label{se:simply}
We first observe that the \maxkmodality{k} problem is a generalization of the \kmodality{k}problem. In fact, a directed graph $G=(V,E)$ admits a $k$-modal embedding if and only if the pair $\langle G, m \rangle$, with $m(v)=k, \forall v \in V(G)$, is a positive instance of the \maxkmodality{k} problem.

\begin{observation}\label{obs:reduction}
\kmodality{k} reduces in linear time to \maxkmodality{k}.
\end{observation}

Let $\langle G, m: V(G) \rightarrow \even{4} \rangle$ be an instance of \mbox{\sc $4$-MaxModality}\xspace; also, let $\beta$ be a leaf-block of the BC-tree $\calT{}$ of $G$ and let $v$ be the parent cut-vertex of $\beta$ in $\calT{}$. We denote by $G^-_\beta$ the subgraph of $G$ induced by $v$ and the vertices of $G$ not in $\beta$, i.e., $G^-_\beta = G - (\beta - \{v\})$. Also, let $B(\calT{})$ be the set of blocks in $\calT{}$.
We show that \maxkmodality{k}  (and \kmodality{k}, by \cref{obs:reduction}) in simply-connected digraphs is Turing reducible to \maxkmodality{k} in biconnected digraphs.

\begin{theorem}\label{th:simply-to-biconnected}
Given a subroutine {\sc TestBiconnected} that tests \maxkmodality{k} for \linebreak biconnected~instances, there exists a procedure  {\sc TestSimplyConnected} that tests \linebreak \maxkmodality{k} for simply-connected digraphs. Further, given an instance $\langle G, m \rangle$ of \linebreak \maxkmodality{k}, the runtime of {\sc TestSimplyConnected($\langle G, m \rangle$)} is
$$\mathcal{O}\big(|G|+ \log{k}\sum_{\beta \in B(\calT{})} r(\beta)\big),$$ where $r(\beta)$ is the runtime of  {\sc TestBiconnected($\langle \beta, m \rangle$)} and $\calT{}$ is the BC-tree of $G$.
\end{theorem}

\begin{sketch}The algorithm selects a leaf-block $\beta$ of $\mathcal T$, with parent cut-vertex $v$, and finds an embedding of $\beta$ with the minimum modality at $v$ satisfying $m$ at all vertices, by performing a binary search using the {\sc TestBiconnected} procedure. We then remove $\beta$, replace $G$ with $G^-_\beta$, and update the value of $m(v)$, so to account for the alternations at $v$ introduced by $\beta$. The procedure terminates when all the blocks have been processed.
Therefore, since the total number of calls to subroutine {\sc TestBiconnected} is bounded by the number of blocks of $G$, which is ${O}(|\mathcal T|)={O}(|G|)$ multiplied by $\log{k}$, the overall running time is \mbox{${O}(|G|+ \log{k} \sum_{\beta \in B(\calT{})} r(\beta))$}.\end{sketch}

\subsection{Biconnected Graphs} \label{se:bico}

\ifshortversion{
To handle the decomposition of a biconnected digraph into its triconnected components, we use SPQR-trees, a data structure introduced by Di Battista and Tamassia~\cite{BattistaT90}.

\paragraph{\bf SPQR-trees.}
\begin{figure}[t]
\includegraphics[width=\textwidth]{flatSpqr}
\caption{
\ifshortversion{
(left) A $4$-modal embedding of a simply-connected planar digraph $G$. (right) The SPQR $\cal T$ of the block $\cal B$ of $G$ rooted at edge $e=uv$. The extended skeletons of all non-leaf nodes of $\cal T$ are shown; virtual edges corresponding to S-, P-, and R-nodes are thick.
}\fi
}\label{fi:spqr}
\end{figure}
Let $G$ be a biconnected digraph. We consider SPQR-trees that are rooted at an edge $e$ of $G$, called the \emph{reference edge}. The rooted SPQR-tree $\cal T$ of $G$ with respect to $e$ describes a recursive decomposition of $G$ induced by its split pairs. The nodes of $\cal T$ are of four types: S, P, Q, and R.
Each node $\mu$ of $\cal T$ has an associated undirected multigraph $\skel(\mu)$, called the \emph{skeleton} of $\mu$, with two special nodes $u_\mu$ and $v_\mu$ (the \emph{poles} of $\mu$), and an associated subgraph $\pert(\mu)$ of $G$, called \emph{pertinent} of $\mu$. The skeleton graph equipped with the edge $u_\mu v_\mu$, called the \emph{parent edge}, is the \emph{extended skeleton} of $\mu$. Refer to \red{ \cref{fi:spqr}(right)}.
Each edge of $\skel(\mu)$, called \emph{virtual edge}, is associated with a child of $\mu$ in $\cal T$. The skeleton of $\mu$ describes how the pertinent graphs of the children of $\mu$ have to be ``merged'' via their poles to obtain $\pert(\mu)$.
The extended skeleton of an S-, P-, R-, and Q-node is a cycle, parallel, triconnected graph, and a $2$-gon, respectively. It follows that skeleton and pertinent graphs are always biconnected once the parent edge is added.
A \emph{series-parallel digraph} is a biconnected planar digraph whose SPQR-tree only contains S-, P-, and Q-nodes. A \emph{partial 2-tree} is a digraph whose every block is a series-parallel digraph.

A digraph $G$ is planar if and only if the skeleton of each R-node in the SPQR-tree of $G$ is planar.
By selecting \emph{regular embeddings} for the skeletons of the nodes of $\cal T$, that is, embeddings in which the parent edge is incident to the outer face, we can construct any embedding of $G$ with the edge $e$ on the outer face, where the choices for the embeddings of the skeletons are all and only the (i) flips of the R-nodes and the (ii) permutations of the P-nodes.
}\fi

\smallskip
Consider a pair $\langle G, m \rangle$ such that $G$ is biconnected and let $\cal E$ be a planar embedding of $G$. Also, let $\calT{}$ be the SPQR-tree of $G$ rooted at an edge $e$ of $G$ incident to the outer face of~$\cal E$.
We will assume that the virtual edges of the skeletons of the nodes in $\calT{}$ are oriented so that the extended skeleton of each node $\mu$ is a DAG with a single source $u_\mu$ and a single sink $v_\mu$.
 \ifshortversion{}\else{This implies that the virtual edges belonging to the extended skeleton of a P-node have the same orientation, from $u_\mu$ to $v_\mu$, and that the virtual edges of the skeleton of an S-node form a directed path from $u_\mu$ to $v_\mu$.} \fi
Let $\mu$ be a node of $\calT{}$ and let $\cal E_\mu$ be the planar (regular) embedding of $\skel(\mu)$ induced by $\cal E$.
For an oriented edge $d=uv$ of $\skel(\mu)$, the \emph{left} and \emph{right face} of $d$ in $\cal E_\mu$ is the face of $\cal E_\mu$ seen to the left and to the right of $d$, respectively, when traversing this edges from~$u$ to $v$. We define the \emph{outer left (right) face} of $\cal E_\mu$ as the left (right) face of the edge $u_\mu v_\mu$ in $\cal E_\mu$.

\paragraph{\bf Embedding tuples.}
An \emph{embedding tuple} (for short, \emph{tuple}) is a $4$-tuple $\langle \sigma_1, a, \sigma_2, b\rangle$, where $\sigma_1,\sigma_2 \in \{\uparrow, \downarrow\}$ are orientations and $a,b \in \mathds{N}$ are non-negative integers.
Consider two tuples $t=\langle \sigma_1, a, \sigma_2, b \rangle$ and $t'=\langle \sigma'_1, a', \sigma'_2, b' \rangle$. We say that $t$ \emph{dominates} $t'$, denoted as  $t \preceq t'$, if
$\sigma_1 = \sigma'_1$, $\sigma_2 = \sigma'_2$, $a \leq a'$, and $b \leq b'$. Also, we say that $t$ and $t'$ are \emph{incompatible}, if none of them dominates the other.
Since the relationship $\preceq$ is reflexive, antisymmetric, and~transitive,~it~defines~a~poset~$(T, \preceq)$, where $T$ is the set of embedding tuples.
A subset $S \subseteq T$ is \emph{succinct} or an \emph{antichain}, if the tuples in $S$ are pair-wise incompatible.
Consider two subsets $S,S' \subseteq T$ of tuples. We say that $S$ \emph{dominates} $S'$, denoted as $S \preceq S'$, if for any tuples $t' \in S'$ there exists at least one tuple $t \in S$ such that $t \preceq t'$. Also, $S$ \emph{reduces} $S'$ if  $S \preceq S'$ and $S \subseteq S'$. Finally, $S$ is a \emph{gist} of $S'$, \mbox{if $S$ is succinct and reduces~$S'$.}

Let $e_u$ and $e_v$ be the edges of $\pert(\mu)$ incident to the outer left face of $\cal E_\mu$ and to $u_\mu$ and $v_\mu$, respectively, possibly $e_u = e_v$. Also, let $a$ and $b$ be non-negative integers.
We say that the embedding $\cal E_\mu$ \emph{realizes} tuple $\langle \sigma_1, a, \sigma_2, b\rangle$, if $\sigma_1 = \sigma(e_u, u_\mu)$, $\sigma_2 = \sigma(e_v, v_\mu)$, and $a$ and $b$ are the number of inner faces of $\cal E_\mu$ whose (two) edges incident to $u_\mu$ and to $v_\mu$, respectively, form an alternating pair.
A tuple $t=\langle \sigma_1, a, \sigma_2, b \rangle$ is \emph{realizable by} $\mu$, if there exists an embedding of $\pert(\mu)$ that realizes~$t$, and \emph{admissible}, if $a \leq m(u)$ and $b \leq m(v)$.
A tuple is \emph{good for} $\mu$ if it is both admissible and realizable by $\mu$.
We denote by $S(\mu)$ the gist of the set of good tuples for a node $\mu$. Let $e_\mu$ be the virtual edge representing $\mu$ in the skeleton of the parent of $\mu$ in $\calT{}$, with a small overload of notation, we also denote $S(\mu)$ by $S(e_\mu)$.
For a tuple $t=\langle \sigma_1, a, \sigma_2, b \rangle \in S(e_\mu)$, where $e=u_\mu v_\mu$, the pair $(\sigma_1, a)$ is the \emph{embedding pair} of $t$ at $u_\mu$; likewise, the pair $(\sigma_2, b)$ is the \emph{embedding pair} of $t$ at $v_\mu$.
We have the following substitution lemma.

\begin{figure}[tb!]
\centering
    \subfloat
    {\includegraphics[page=2,scale=.9]{substitution}\label{fig:substitutionOrig}} \hfil
    \subfloat
    {\includegraphics[page=3,scale=.9]{substitution}\label{fig:substitutionSwap}}
\caption{ Illustration for the proof of \cref{le:substitution}. The parity of $t$ and $t'$ is the same at $u_\mu$ and different at $v_\mu$; in particular, even if a new alternation is introduced between the pair $(e,e')$ at~$v_\mu$, the different parity guarantees that the modality at~$v_\mu$ does not increase from $\mathcal E$ to $\mathcal E'$.
}
\label{fig:substitution}
\end{figure}

\begin{lemma}\label{le:substitution}

Let $\cal E$ be a planar embedding of $G$ satisfying $m$.
Let $\mu$ be a node of $\calT{}$ and let $\cal E_\mu$ be the embedding of $\pert(\mu)$ induced by $\cal E$. Also, let $\cal E'_\mu \neq \cal E_\mu$ be an embedding of $\pert(\mu)$ satisfying~$m$.
Then, $G$ admits an embedding $\cal E'$ satisfying $m$ in which the embedding of $\pert(\mu)$
is $\cal E'_\mu$, if $t' \preceq t$, where $t$ and $t'$ are the embedding tuples realized by ${\cal E_\mu}$ and by ${\cal E'_\mu}$, respectively.
\end{lemma}

\begin{sketch}
We show how to construct a drawing $\Gamma'_G$ of $G$ satisfying $m$ in which the embedding of $\pert(\mu)$ is $\mathcal E'_\mu$; see \cref{fig:substitution}.
Let $\Gamma_G$ be a drawing of $G$ whose embedding is $\mathcal E$. Remove from $\Gamma_G$ the drawing of all the vertices of $\pert(\mu)$ different from $u_\mu$ and $v_\mu$ and the drawing of all the edges of $\pert(\mu)$. Denote by $f$ the face of the resulting embedded graph $G^-$ that used to contain the removed vertices and edges. We obtain $\Gamma'_G$ by inserting a drawing of $\pert(\mu)$ whose embedding is $\mathcal E'_\mu$ in the interior of $f$ so that vertices $u_\mu$ and $v_\mu$ are identified with their copies in $G^-$.
We can prove that the embedding $\mathcal E'$ of $\Gamma'_G$ satisfies $m$ by exploiting
the interplay between the parity and the number of alternations at $u_\mu$  (at $v_\mu$) in $t'$ and $t$ when $t' \preceq t$.
\end{sketch}

\begin{fullproof}
We show how to construct a drawing $\Gamma'_G$ of $G$ satisfying $m$ in which the embedding of $\pert(\mu)$ is $\mathcal E'_\mu$; see \cref{fig:substitution}.
Let $\Gamma_G$ be a drawing of $G$ whose embedding is $\mathcal E$. Remove from $\Gamma_G$ the drawing of all the vertices of $\pert(\mu)$ different from $u_\mu$ and $v_\mu$ and the drawing of all the edges of $\pert(\mu)$. Denote by $f$ the face of the resulting embedded graph $G^-$ that used to contain the removed vertices and edges. We obtain $\Gamma'_G$ by inserting a drawing of $\pert(\mu)$ whose embedding is $\mathcal E'_\mu$ in the interior of $f$ so that vertices $u_\mu$ and $v_\mu$ are identified with their copies in $G^-$.

We claim that the embedding $\mathcal E'$ of $\Gamma'_G$ satisfies $m$.
First, the modality of each vertex of $G$ not in $\pert(\mu)$ is the same in $\mathcal E'$ as in $\mathcal E$. Second, the modality of each vertex in $\pert(\mu)$ different from $u_\mu$ and $v_\mu$ is the same in $\mathcal E'$ as in $\mathcal E'_\mu$.

We only need to show that $u_\mu$ and $v_\mu$ satisfy $m$ in $\mathcal E'$.
We have that $t = \langle \sigma_1, a, \sigma_2, b\rangle $ and $t = \langle \sigma'_1, a', \sigma'_2, b'\rangle$.
We show that the modality of $u_\mu$ in $\mathcal E'$ is smaller than or equal to the modality of $u_\mu$ in $\mathcal E$; analogous arguments hold for $v_\mu$.
We distinguish two cases.
If $a$ and $a'$ have the same parity, as shown at vertex $u$ in \cref{fig:substitution}, then $\mathcal E'$ contains an alternating pair consisting of an edge in $G'$ and of an edge in $\pert(\mu)$ incident to $u_\mu$ only if  $\mathcal E$ contains an alternating pair consisting of an edge in $G'$ and of an edge in $\pert(\mu)$ incident to $u_\mu$. Therefore, since $a' \leq a$, the modality of $u_\mu$ in $\mathcal E'$ is smaller than or equal to the modality of $u_\mu$ in $\mathcal E$.
Otherwise, if $a$ and $a'$ have the different parity, as shown at vertex $v$ in \cref{fig:substitution}, then $\mathcal E'$ may contain an alternating pair consisting of an edge in $G'$ and of an edge in $\pert(\mu)$ incident to $u_\mu$ and to the right outer face of $\pert(\mu)$ even if $\mathcal E$ does not contain an alternating pair consisting of an edge in $G'$ and of an edge in $\pert(\mu)$ incident to $u_\mu$.
However, in this case, it holds that  $a' < a$, therefore the modality of $u_\mu$ in $\mathcal E'$ is again smaller than or equal to the modality of $u_\mu$ in $\mathcal E$.
\end{fullproof}

Let $\calT{}$ be the SPQR-tree $\calT{}$ of $G$ rooted at a reference edge $e$.
In the remainder of the section, we show how to compute the gist $S(\mu)$ of the set of good tuples for $\mu$, for each non-root node $\mu$ of $\calT{}$. In the subsequent procedures to compute $S(\mu)$ for S-, P-, and R-nodes, we are not going to explicitly avoid set $S(\mu)$ to contain dominated tuples. In fact, this can always be done at the cost of an
additive $O(k^2)$ factor in the running time, by maintaining an hash table that stores the tuples that have been constructed (possibly multiple times) by the procedures and by computing the gist of the constructed set as a final step.

\begin{property}\label{obs:size}
For each node $\mu \in \calT{}$, it holds that $|S(\mu)| \in O(k)$.
\end{property}

\begin{proof}
By the definition of gist, any embedding pair $(\sigma,a)$ has at most two tuples $t',t'' \in S(\mu)$ such that $(\sigma,a)$ is the embedding pair of $t'$ and $t''$ at $u_\mu$; also, the embedding pairs $(\sigma',a')$ of $t'$ and $(\sigma'',a'')$ of $t''$ at $v_\mu$ are such that $\sigma' \neq \sigma''$. Since there exist at most $2k$ realizable embedding pairs $(\sigma,a)$ at $u_\mu$ (as $\sigma \in \{\inn,\out\}$, $a \in \{0,1,\dots,k\}$, and the existence of tuple whose embedding pair at $u_\mu$ is $(\sigma,0)$ implies that all tuples have such an embedding pair at $u_\mu$), we have $|S(\mu)| \leq 4k$.\end{proof}

If $\mu$ is a leaf Q-node in $\calT{}$, then $S(\mu)=\{ \langle \sigma(u_\mu v_\mu), 0,  \sigma(u_\mu v_\mu), 0 \rangle \}$.
If $\mu$ is an internal node of~$\calT{}$, we visit $\calT{}$ bottom-up and compute the set $S(\mu)$ for $\mu$ assuming to have already computed the sets $S(\mu_1),\dots, S(\mu_k)$ for the children $\mu_1,\dots,\mu_k$ of $\mu$
(where $\mu_i$ is the child of $\mu$ corresponding to the edge $e_i$ in $\skel(\mu)$).
Let $\rho$ be the unique child of the root of $\calT{}$.
Once the set $S(\rho)$ has been determined, we can efficiently decide whether $G$ admits an embedding satisfying $m$ in which the reference edge $e$ is incident to the outer face by means of the following lemma.

\begin{lemma}\label{le:rho}
Given $S(\rho)$, we can test whether $G$ has an embedding that satisfies $m$ in $O(k^2)$ time.
\end{lemma}

\begin{fullproof}
Let $t=\langle \sigma_1,a,\sigma_2,b \rangle$ be a realizable tuple in $S(\rho)$ and let ${\cal E}_t$ be the embedding of $G$ obtained by inserting the reference edge $e$ in the outer face of a regular embedding $\cal E_\rho$ of $\pert(\rho)$ realizing $t$ that satisfies $m$. Let $u$ and $v$ be the poles of $\rho$. We have the following claim.

\begin{claim}\label{cl:e_t}
Embedding ${\cal E}_t$ satisfies $m$ if and only if:
\begin{enumerate}[(i)]
    \item
\begin{inparaenum}
    \item $m(u)\geq a+1$, if $a$ is odd, or
    \item $m(u)\geq a$, if $a$ is even and $\sigma_1=\sigma(e)$, \linebreak or
    \item $m(u)\geq a+2$, if $a$ is even and $\sigma_1 \neq \sigma(e)$,
\end{inparaenum}
and
\item
\begin{inparaenum}
    \item $m(v)\geq b+1$, if $b$ is odd, or
    \item $m(v)\geq b$, if $b$ is even and $\sigma_2=\sigma(e)$, \linebreak or
    \item $m(v)\geq b+2$, if $b$ is even and $\sigma_2 \neq \sigma(e)$.
\end{inparaenum}
\end{enumerate}
\end{claim}
\begin{fullproof}
\begin{figure}[tb!]
\centering
\subfloat[]{\includegraphics[page=1,height=.24\textwidth]{rootNode}}\hfil
\subfloat[]{\includegraphics[page=2,height=.24\textwidth]{rootNode}}\hfil
\subfloat[]{\includegraphics[page=3,height=.24\textwidth]{rootNode}}
\caption{Illustrations for the proof of \cref{cl:e_t}. (a) The root edge $e$ and $\rho$ (where the orientation of $\rho$ being arbitrary). (b) A $4$-modal embedding of $G$, where $u$ has $2$ alternations and $v$ has $4$ alternations. (b) A $6$-modal embedding of $G$, where $u$ has $4$ alternations and $v$ has $6$ alternations.}
\label{fi:rootNode}
\end{figure}
To prove the statement for vertex $u$, we just need to observe that, if $a$ is odd, then the edges $e'_u$ and $e''_u$ incident to $u$ and to the left and to the right outer face of ${\cal E}_\rho$, respectively, have opposite orientations, while if $a$ if even, then these edges have the same orientation (in this case, possibly $e'_u = e''_u$). Also, since $a$ is the number of alternations between edges incident to $u$ and to the internal faces of ${\cal E}_\rho$, the modality at $u$ in ${\cal E}_\rho$ is equal to $a+1$, if $a$ is odd, while it is equal to $a$, otherwise.
Therefore, since edge $e$ appears between $e'_u$ and $e''_u$ in embedding ${\cal E}_t$ obtained from ${\cal E}_\rho$, we have that the number of alternations around $u$ in ${\cal E}_t$ is the same as in ${\cal E}_\rho$, if $a$ is odd or if $a$ is even and $\sigma(e) = \sigma_1$, and it is equal to the modality of $u$ in ${\cal E}_\rho$ plus $2$, if $a$ is even and $\sigma(e) \neq \sigma_1$. Refer to  \cref{fi:rootNode}. The proof of the statement for vertex $v$ is analogous.
\end{fullproof}

By  \cref{cl:e_t}, for each realizable tuple $t \in S(\rho)$, we can test whether embedding  ${\cal E}_t$ satisfies $m$ in constant time. Also, $|S(\rho)| \in O(k^2)$, by \cref{obs:size}. Therefore, we can test in $O(k^2)$ time whether there exists an embedding of $\pert(\rho)$ that can be extended to an embedding of $G$ that satisfies $m$ in which $e$ is incident to the outer face.
\end{fullproof}

\ifshortversion{}\else{We remark that the choice of the reference edge does not affect the existence of a $4$-modal embedding. In fact, a change of the outer face such that edge $e$ is incident to such a face can always be performed while preserving the rotation at any vertex.}\fi

\section{Partial 2-trees} \label{se:2trees}
In the following, we describe how to compute $S(\mu)$, if $\mu$ is an S-node (\cref{le:S}) and a P-node (\cref{le:P}) in ${O}(f(k)|\skel(\mu)|)$ time, where $f$ is a computable function.

\begin{lemma}\label{le:S}
Set $S(\mu)$ can be constructed in ${O}(k^2|\skel(\mu)|)$ time for an S-node $\mu$.
\end{lemma}

\begin{sketch}
Let $\mu$ be an S-node with skeleton $\skel(\mu)=(e_1,e_2,\dots,e_h)$. We define $\tau_j$ as the S-node obtained by the series composition of $\mu_1, \mu_2,\dots,\mu_j$, with $j \leq h$. Initially we set $S(\tau_1)=S(e_1)$. Then, we construct $S(\tau_j)$ via dynamic programming, for $j=2,\dots,h$, by
verifying the compatibility of the embedding pairs of the good tuples of the virtual edges of $\skel(\tau_j)$ at the internal vertices of $\skel(\tau_j)$. As $S(\tau_j)=S(\tau_{j-1}) \cup e_j$, we can compute $S(\tau_j)$ by considering all the tuples obtained by combining
every tuple $t' \in S(\tau_{j-1})$ with every tuple $t'' \in S(e_j)$. Since both these sets contain $O(k)$ tuples, by \cref{obs:size}, and since the tuple resulting from the combination of $t'$ and $t''$ can be determined in $O(1)$ time, we have that $S(\tau_j)$ can be computed in $O(k^2)$ time. Therefore, the overall running \mbox{time for computing $S(\mu)=S(\tau_h)$ is ${O}(k^2 |\skel(\mu)|)$.}
\end{sketch}

\begin{lemma}\label{le:P}
Set $S(\mu)$ can be constructed in $O((2k+4)!k^3 + |\skel(\mu)|)$ time for a P-node~$\mu$.
\end{lemma}

\begin{sketch}
Let $\mu$ be a P-node with poles $u_\mu$ and $v_\mu$, whose skeleton $\skel(\mu)$ consists of $h$ parallel virtual edges $e_1,e_2,\dots,e_h$.
It can be shown that the computation of $S(\mu)$ reduces in $O(|\skel(\mu)|)$ time to the computation of $S(\tau)$, where $\tau$ is a P-node whose skeleton consists of at most $2k$ virtual edges of $\skel(\mu)$ that contribute with at least one alternating pair of edges at~$u_\mu$ or~$v_\mu$, plus up to $4$ virtual edges of $\skel(\mu)$ that contribute with no alternating pair at~$u_\mu$ or at~$v_\mu$.
For any permutation $\pi$ of the virtual edges of $\pert(\tau)$, let $\tau^\pi_i$ be the P-node obtained by restricting $\tau$ to the first~$i$ virtual edges in $\pi$.
We fix the embedding of $\skel(\tau^\pi_i)$ in such a way that the virtual edges of $\skel(\tau^\pi_i)$ are ordered according to $\pi$.
Then, in a fashion similar to the S-node case, we can compute~$S(\tau^\pi_i)$ for the given embedding of $\skel(\tau^\pi_i)$ by combining $S(\tau^\pi_{i-1})$ and $S(e_i)$ in $O(k^2)$ time (recall that both these sets have size $O(k)$, by \cref{obs:size}).
Clearly, for any fixed $\pi$, we can compute $S(\tau^h_\pi)$ in $O(k^3)$ time. Thus, by performing the above computation for all the $(2k+4)!$ possible permutations for the virtual edges of $\pert(\tau)$, we can construct $S(\tau)$ in $O((2k+4)!k^3+|\skel(\mu)|)$ time.\end{sketch}

Altogether, \cref{le:S,le:P} yield the following main result.

\begin{theorem}\label{th:sp}
\maxkmodality{k} can be solved in $O((2k+4)!k^3  n)$ for series-parallel digraphs.
\end{theorem}

 \cref{obs:reduction}, \autoref{th:simply-to-biconnected}, and \autoref{th:sp} immediately imply the following.

\begin{corollary}\label{co:2trees}
\kmodality{k} can be solved in $O(((2k+4)!k^3\log{k})  n)$ for directed partial $2$-trees.
\end{corollary}

Due to the special algorithmic framework we are employing,
 we can however turn the multiplicative $O(\log{k})$ factor in the running time into an additive $O(k)$ factor by modifying \ifshortversion{\cref{th:simply-to-biconnected} }\else{\cref{algo:simply-to-bico} }\fi as follows. When considering a cut-vertex $v$\ifshortversion{, }\else{ (line~$4$), }\fi we will execute ``only once'' the function {\sc TestBiconnected} \ifshortversion{}\else{(line~$5$) }\fi
 by rooting the SPQ-tree at a Q-node $\eta$ corresponding to an edge incident to~$v$. This will allow us to compute the minimum modality for cut-vertex $v$ in an embedding that satisfies $m$ at every vertex, by simply scanning the set $S(\eta)$, which takes $O(k)$ time by \cref{obs:size}, rather than by exploiting a logarithmic number of calls to {\sc TestBiconnected}.

\begin{theorem}\label{th:2trees-efficient}
\kmodality{k} can be solved in $O((2k+4)!k^3 n)$ for directed partial $2$-trees.
\end{theorem}

\section{A Linear-time Algorithm for 4-MaxModality when $\mathbf{\Delta \leq 6}$} \label{se:deg6}

In this section, we show that in the special case when $k=4$ and $G$ has maximum degree~$\Delta \leq 6$, it is possible to compute the set $S(\mu)$ when $\mu$ is an R-node in linear time in the size of $\skel(\mu)$.

Our strategy to compute $S(\mu)$ is as follows.  We select a single tuple from the admissible set of each virtual edge incident to $u_\mu$ and $v_\mu$, in every possible way. Each selection determines a ``\emph{candidate tuple}'' $t$ for $S(\mu)$.
First, we check if $t$ is admissible at both $u$ and $v$.
Second, we restrict the tuples of the edges incident to the poles to only the tuples that form $t$ and check if there is a way of satisfying $m$ at the (inner) vertices of $\skel(\mu)$.
If both the poles and the inner vertices are satisfiable, then we add $t$ to $S(\mu)$. Since the degrees of the poles are bounded, there is at most a constant number of candidate tuples which must be checked. The complexity lies in this check.

    We now formally describe how to compute $S(\mu)$.
First, for each virtual edge $e_i$ of $\skel(\mu)$ incident to the poles of $\mu$, we select a tuple $t_i$ from $S(\mu_i)$.
Let $T_u = [t_{u,1},t_{u,2},\dots,t_{u,\ell}]$ and $T_v=[t_{v,1},t_{v,2},\dots,t_{v,h}]$ be the list of tuples selected for the virtual edges incident to $u_\mu$ and to $v_\mu$, respectively.
Each pair of lists $T_u$ and $T_v$ yields a {\em candidate tuple} $t = \langle \sigma_1, a, \sigma_2, b \rangle$ for $\mu$.
However, the tuples selected to construct $T_u$ and $T_v$ allow for an admissible embedding of $\pert(\mu)$ \mbox{realizing tuple $t$ {\em if and only if}:}
\begin{inparaenum}
    \item[{\bf (Condition~1)}] tuple $t$ satisfies $m$ at $u_\mu$ and at $v_\mu$, and
    \item[{\bf (Condition~2)}] it is possible to select tuples for each of the remaining virtual edges of $\skel(\mu)$ that satisfy $m$ at every internal vertex of $\skel(\mu)$.
\end{inparaenum}
Let $\mathcal P(\mu)$ be the set of candidate tuples for $\mu$ constructed as described above.
We can easily filter out the candidate tuples that do not satisfy Condition~1.
For each pair of lists $T_u$ and $T_v$ yielding a tuple $t \in \mathcal P(\mu)$, we will show how to test Condition~2 for $\mu$ in linear time. This and the fact that $|\mathcal P(\mu)| \in O(1)$ imply the following.

\begin{lemma}\label{le:R}
Set $S(\mu)$ can be constructed in ${O}(|\skel(\mu)|)$ time for an \mbox{R-node}~$\mu$, if $\Delta\leq 6$.
\end{lemma}

Altogether, \cref{le:S,,le:P,,le:R} yield the following main result.

\begin{lemma}\label{le:bico-max-degree}
\maxkmodality{4} can be solved in linear time for biconnected digraphs with $\Delta \leq 6$
\end{lemma}

\cref{obs:reduction}, \cref{th:simply-to-biconnected}, and \cref{le:bico-max-degree} immediately imply the following.

\begin{theorem}\label{th:max-degree}
\mbox{\sc $4$-Modality}\xspace{} can be solved linear time for digraphs with $\Delta \leq 6$
\end{theorem}

To prove \cref{le:R}, we show how to solve the following auxiliary problem for special instances.

\problemdef{\sc $4$-MaxSkelModality}{A triple $\langle G=(V,E), {\cal S}=\{S(e_1),\dots,S(e_{|E|})\}, m \rangle$ where
$G$ is an embedded directed graph, each $S(e_i)$ is a set containing embedding tuples for the virtual edge $e_i \in E$, and $m: V \rightarrow \even{4}$ is the \emph{maximum-modality function}.}{
Can we select a tuple from each set $S(e_i)$ in such a way that the modality at each vertex $v \in V$ is at most $m(v)$?}

\medskip
For each pair of lists $T_u$ and $T_v$ yielding a candidate tuple in $\mathcal P(\mu)$, we will construct an instance $I_\mu(T_u,T_v)=(G,\mathcal S, m)$ of {\sc $4$-MaxSkelModality} as follows.
\begin{inparaenum}
\item We set $G=\skel(\mu)$ and we fix the embedding of $G$ to be equal to the unique regular embedding of $\skel(\mu)$;
\item for each virtual edge $e_{u,i}$ incident to $u_\mu$, with $i=1,\dots,\ell$, we set $S(e_{u,i})=\{t_{u,i}\}$; for each virtual edge $e_{v,j}$ incident to $v_\mu$, with $j=1,\dots,h$, we set $S(e_{v,j})=\{t_{v,j}\}$; for each of the remaining virtual edges $e_d$ of $\skel(\mu)$, we set $S(e_d) = S(\mu_d)$; finally,
\item \mbox{the maximum-modality function of $I_\mu$ coincides with $m$.}
\end{inparaenum}

Clearly, $I_\mu(T_u,T_v)$ is a positive instance of {\sc $4$-MaxSkelModality} if and only if, given the constrains imposed by the tuples in $T_u$ and in $T_v$, there exists a selection of tuples for the edges of $G$ not incident to $u_\mu$ or $v_\mu$ that satisfies $m$ at all the \mbox{internal vertices of $G$, i.e., Condition~2 holds.}

Let $v$ be a vertex of $G$ and let $e$ be an edge in $E(v)$, we denote by $A_v(e)$ the maximum number of alternations at $v$ over all the tuples in~$S(e)$.

\begin{definition}[Good instances]\label{prop:max6}
An instance of {\sc $4$-MaxSkelModality} is \emph{good} if, for any vertex $v$ in $G$, it holds
$\sum_{e\in E(v)} (A_v(e)+1) \leq 6$.
\end{definition}

Note that, for each edge $e$ in $ske(\mu)$ incident to a vertex $v$, $\pert(e)$ contributes at least $A_v(e)+1$ edges to $d_{\pert(e)}(v)$. Thus, we have
$\sum_{e\in E(v)} (A_v(e)+1) \leq \sum_{e\in E(v)} d_{\pert(e)}(v) \leq 6$.
Therefore, instance $I_\mu(T_u,T_v)$ is good.
Although {\sc $4$-MaxSkelModality} turns out to be NP-complete in general \ifshortversion{(