\section{Problem Definition}
\label{sec:problem}

Network alignment is problem of identifying a bijection mapping between nodes in two structurally similar graphs. Let $G_a(\mathcal{V}_a,\mathcal{E}_a)$ and $G_b(\mathcal{V}_b,\mathcal{E}_b)$ be two graphs with node sets $\mathcal{V}_a$ and $\mathcal{V}_b$ of size $n$, and edge sets $\mathcal{E}_a$ and $\mathcal{E}_b$. We denote the edge between nodes $i$ and $j$ by $(i,j)$.
Let mapping function $\pi:\mathcal{V}_a \rightarrow \mathcal{V}_b$ denote a one-to-one mapping between nodes of $G_a$ and $G_b$.
The goal in the graph matching problem is to select a matching $\hat{\pi}$ from  $n!$ different possible mapping functions in the symmetric group $S_n$ such that:

\begin{equation}
\hat{\pi} = \underset{\pi\in S_n}{\operatorname{argmin}} \; \|A(G_b)-P_{\pi}^{T}A(G_a)P_{\pi}\|^2_F,
\label{eq:problem_def}
\end{equation}

\noindent where $\|.\|_F$ is Frobenius norm and $A(G_a)$ and $A(G_b)$ are the adjacency matrices for $G_a$ and $G_b$, respectively. Moreover, the matrix $P_{\pi}^{T}A(G_a)P_{\pi}$ is a simultaneous row/column  permuted version of $A(G_a)$, and $P_{\pi}$ is the permutation matrix corresponding to mapping $\pi$ which is defined as:

\begin{equation}
P_{\pi}[i,j] = \left\{
\begin{array}{lcl}
1 & : & i\in \mathcal{V}_a,~ j\in \mathcal{V}_b,~ j = \pi(i),\\
0 & : & \text{otherwise.}
\end{array}
\right.
\end{equation}

In other words, the objective function in \mRefEq{eq:problem_def} measures the number of mis-matched edges between relabeled version of graph $G_a$ based on mapping $\pi$ and graph $G_b$. In the worst case, solving the above optimization problem is NP-hard \cite{rendl1994quadratic}.

For synthetic graphs, we assume that $G_a$ and $G_b$ are two correlated  Erd\H{o}s-R$\acute{\text{e}}$nyi  graphs where the original graph \linebreak $G(\mathcal{V},\mathcal{E})$ is generated with parameter $p$, i.e, there is an edge between any two nodes with probability $p$. Then, two correlated graphs $G_a$ and $G_b$ are constructed where edge sets $\mathcal{E}_a$ and $\mathcal{E}_b$ are sampled from $\mathcal{E}$ with probability $s$. In other words, every edge in edge set $\mathcal{E}$ is in $\mathcal{E}_a$ and $\mathcal{E}_b$ with probability $s$, independently. The vertex set $\mathcal{V}_a$ is the same as $\mathcal{V}$, but $\mathcal{V}_b$ is a permuted version of $\mathcal{V}$ according to mapping $\pi^{*}$. The matching algorithm tries to recover $\pi^{*}$ given only $G_a$ and $G_b$. For correlated Erd\H{o}s-R$\acute{\text{e}}$nyi  graphs, it can be shown \cite{kazemi2016network} that maximum a-posteriori (MAP) estimation is equivalent to minimizing the objective function in \mRefEq{eq:problem_def}. Furthermore, MAP estimator finds the ground truth matching, i.e., $\hat{\pi}=\pi^*$ with high probability if and only if $ps^2=\Omega(\log(n)/n)$ \cite{cullina2016improved}. Hence,  no matching algorithm can return the correct output for values less than $\Omega(\log(n)/n)$.

\section{Tail Degree Signature (TDS) Algorithm}
\label{sec:alg}

Our proposed graph matching algorithm consists of two steps: I) For every node in both graphs, a feature vector is extracted. II) Based on these feature vectors, the nodes in the two subsets are matched.

\subsection{Feature Extraction}
\label{sec:alg:feature}

\noindent \textbf{Method:}
For every node $i\in \mathcal{V}_a$, we extract a feature vector $\mFtr^a_i$ based on its neighbor nodes in $G_a$ as follows:
Let $\mNbrC{a}{\mDist}{i}$ be the set of nodes in graph $G_a$ whose distance from node $i$ is exactly equal to $\mDist$, where $\mDist \in [1,\mMaxDist]$, and $\mMaxDist$ is the maximum distance that is considered in the feature extraction procedure. For every node $i\in \mathcal{V}_a$ and every $\mDist \in [1,\mMaxDist]$, set $\mDeg(\mNbrC{a}{\mDist}{i})$ is formed as the  degrees of the nodes in $\mNbrC{a}{\mDist}{i}$, i.e.,

\begin{equation}
\mDeg(\mNbrC{a}{\mDist}{i}) = \{
\mdeg^{a}_{i'} ~\vert~ i' \in \mNbrC{a}{\mDist}{i}
\}.
\end{equation}

Next, for a given integer parameter $\theta$, we pick $\mFtrLen$ of the smallest and $\mFtrLen$ of the largest elements in $\mDeg(\mNbrC{a}{\mDist}{i})$ and put them in feature vector $\mFtr^{a,\mDist}_i$ of size $2 \, \mFtrLen$.
Finally, feature vector $\mFtr^a_i$ is formed by concatenating vectors $\mFtr^{a,\mDist}_i$ as follows:

\begin{equation}
\mFtr^a_i = \mFtr^{a,1}_i ~|~ \mFtr^{a,2}_i ~|~ \cdots ~|~ \mFtr^{a,\mMaxDist}_i.
\end{equation}

Thus, $\mFtr^a_i$ is a vector of size $2 \, \mFtrLen  \mMaxDist$. By a similar procedure, for every node $j\in \mathcal{V}_b$, feature vector $\mFtr^b_j$ is also formed.
\mRefFig{fig:methodParts}(a) shows two example graphs $G_a$ and $G_b$.
\mRefFig{fig:methodParts}(b) shows the construction procedure of $\mFtr^a_{18}$ where $\mNbrC{a}{t}{18}$ and $\mDeg(\mNbrC{a}{t}{18})$ are generated according to \mRefFig{fig:methodParts}(a). As few other examples, $\mFtr^a_{5}$, $\mFtr^b_{12}$ and $\mFtr^b_{9}$ are also shown in \mRefFig{fig:methodParts}(b).

\vskip 2mm
\noindent \textbf{Rationale:}
In constructing the vector $\mFtr^a_i$, we select the degree of nodes in $\mNbrC{a}{\mDist}{i}$ which are in the \textbf{tail} region of empirical degree distribution of nodes in $\mNbrC{a}{\mDist}{i}$. Herein, we give an intuition why such selection is more preferable than considering nodes' degrees outside of this region for $t=1$.  For the original graph $G(\mathcal{V},\mathcal{E})$, i.e, there is an edge between any two nodes in $G(\mathcal{V},\mathcal{E})$ with probability $p$. Then $G_a$ and $G_b$ are constructed where edge sets $\mathcal{E}_a$ and $\mathcal{E}_b$ are sampled from $\mathcal{E}$ with probability $s$. Thus, $G_a$ and $G_b$ are two Erd\H{o}s-R$\acute{\text{e}}$nyi  graphs with $\sp$ probability. It can be seen that the degree distribution of node $i$ in graph $G_a$ or $G_b$ is approximately a normal distribution $N(\mu,\sigma^2)$ with parameters $\mu=(n-1)ps$ and $\sigma=\sqrt{(n-1)(1-ps)ps}$. Let $U_i^a$ be the normalized degree of node $i$ in graph $G_a$, i.e., $U_i^a=(\mdeg_{i}^{a}-\mu)/\sigma$. $U_i^b$ is defined similarly in graph $G_b$.

\begin{proposition}
If node $j\in\mathcal{V}_b$ is the corresponding node of a node $i\in \mathcal{V}_a$, i.e., $j=\pi^*(i)$, then $U_i^a$ and $U_j^b$ are two correlated random variables with the  correlation coefficient:  $\rho=s(1-p)/(1-ps)$. Otherwise, they are approximately uncorrelated for large $n$.
\label{Prop:2}
\end{proposition}

\begin{proof}
To prove the above statement, it is just needed to compute the following term for the two correlated random variables $U_i^a$ and $U_{\pi^*(i)}^b$:
\begin{equation}
\begin{split}
\mathbb{E}\Big[\mdeg_{i}^{a} &\mathcal{D}^b_{\pi^*(i)}\Big]\\
&=\mathbb{E}\Bigg[\sum_{k\neq i} \mathbbm{1}[(i,k)\in \mathcal{E}_a]  \sum_{k'\neq \pi^*(i)}\mathbbm{1}[(\pi^*(i),k')\in \mathcal{E}_b]\Bigg]\\
&\stackrel{(a)}{=}\big((n-1)^2-(n-1)\big)(ps)^2\\
&\qquad+\sum_{k\neq i}\mathbb{E}\Big[\mathbbm{1}[(i,k)\in \mathcal{E}_a] \mathbbm{1}[(\pi^*(i),\pi^*(k))\in \mathcal{E}_b]\Big]\\
&\stackrel{(b)}{=}\big((n-1)^2-(n-1)\big)(ps)^2 +(n-1)ps^2,
\end{split}
\end{equation}
where $\mathbbm{1}[.]$ is the indicator function.\\
(a) Due to the fact that the events ${1}[(i,k)\in \mathcal{E}_a]$ and \linebreak $\mathbbm{1}[(\pi^*(i),k')\in \mathcal{E}_b]$ are independent for $k'\neq\pi^*(k)$.\\
(b) The probability of existing an edge between nodes $i$ and $k$ in the original graph $G$ is equal to $p$. Moreover, the probability of having that edge in both graphs $G_a$ and $G_b$ is $s^2$. Hence, the expectation of event in the second sum would be $ps^2$.

Thus, the correlation coefficient between $\mdeg_{i}^{a}$ and $\mathcal{D}^b_{\pi^*(i)}$ would be:
\begin{equation}
\begin{split}
\rho=\frac{\mathbb{E}\Big[\mdeg_{i}^{a} \mathcal{D}^b_{\pi^*(i)}\Big]-\mu^2}{\sigma^2}=s(1-p)/(1-ps).
\end{split}
\end{equation}
Similarly, for the case of $j\neq \pi^*(i)$, it can be shown that $\rho=s(1-p)/((n-1)(1-ps))$. Hence, the two random variables are approximately uncorrelated for large $n$ if $j\neq \pi^*(i)$.
\end{proof}

Based on the above observation, we can model the two random variables $U_i^a$ and  $U^b_{\pi^*(i)}$ as  $U^b_{\pi^*(i)}=\rho U_i^a + \sqrt{1-\rho^2} Z$ where $Z$ is an independent standard normal variable. To show the advantage of selecting nodes' degrees in the tail of degree distribution, we define the following two metrics between any two nodes $i\in \mathcal{V}_a$ and $j\in \mathcal{V}_b$:
\begin{equation}
\begin{split}
\Delta^{i,j}_{tail}&= \frac{1}{2}\int^{-\frac{1}{2}}_{-\infty} |\hat{p}_{U_i^a}(x)-\hat{p}_{U_j^b}(x)|dx\\
&+ \frac{1}{2}\int_{\frac{1}{2}}^{\infty} |\hat{p}_{U_i^a}(x)-\hat{p}_{U_j^b}(x)|dx\\
\Delta^{i,j}_{center}&=\frac{1}{2}\int^{\frac{1}{2}}_{-\frac{1}{2}} |\hat{p}_{U_i^a}(x)-\hat{p}_{U_j^b}(x)|dx,
\end{split}
\end{equation}
where $\hat{p}_{U_i^a}(x)$ and $\hat{p}_{U_j^b}(x)$ are the empirical distribution obtained from observing samples of $U_i^a$ and $U_j^b$, respectively. In fact, $\Delta^{i,j}_{tail}$ and $\Delta^{i,j}_{center}$ represent the total variation distances \cite{levin2017markov} of $\hat{p}_{U_i^a}(x)$ and $\hat{p}_{U_j^b}(x)$  in the tail and central domains of distributions, respectively. For a given node $i$, we are interested in comparing $\Delta_{tail}^{i,\pi^*(i)}$ with $\Delta_{tail}^{i,j}$ for any $j\neq \pi^*(i)$. We define the score  $s^{i,j}_{tail}=\Delta_{tail}^{i,\pi^*(i)}/\Delta_{tail}^{i,j}$ for any $j\neq \pi^*(i)$ and $j\in \mathcal{V}_b$. We expect to have better matching results for higher $s^{i,j}_{tail}$. The score $s^{i,j}_{center}$ is defined similarly. We compare the average of $s^{i,j}_{tail}$ and $s^{i,j}_{center}$ experimentally by generating $100$ samples of $U_i^a$ and $U_j^b$ for two correlation coefficients $\rho=s(1-p)/(1-ps)$ and $\rho=0$. From these samples, one instance of $s^{i,j}_{tail}$ and $s^{i,j}_{center}$ can be computed. \mRefFig{fig:tail_score} shows the average of $s^{i,j}_{tail}$ and $s^{i,j}_{center}$ over $100$ instances against parameter $s$ for $n=1000$ and $p=\log(n)/n$. As can be seen, the score of tail region is about $40\%$ greater than the one for the central region. This observation illustrates that the empirical degree distribution in the tail region is much more robust to sampling parameter $s$.

\begin{figure}[tp]
	\begin{center}
		\includegraphics[width = 0.95\columnwidth]{pic/score.pdf}
	\end{center}
	\vskip -4mm
	\caption{The average of $s^{i,j}_{tail}$ and $s^{i,j}_{center}$ over $100$ instances against parameter $s$ for $n=1000$ and $p=\log(n)/n$.
	}
	\vskip -1mm
	\label{fig:tail_score}
\end{figure}

\vskip 2mm
\noindent \textbf{Complexity Analysis:}
For every node $i\in \mathcal{V}_a$, we run BFS algorithm with root node $i$ and obtain all nodes in $\mNbrC{a}{\mDist}{i}$ for every $t\in [1,\lambda]$. Since the average degree of each node is in the order of $O((n-1)ps)$, the average number of neighbor nodes up to distance $\lambda$ is in the order of $O((nps)^{\lambda})$. Thus, the time complexity of this part is $O((nps)^{2\lambda})$. Moreover, it takes $O(t(nps)^t\log(nps))$ to sort the nodes in $\mNbrC{a}{\mDist}{i}$ and construct $\mFtr^{a,t}_i$. Therefore, the total time complexity of the feature extraction step for all $n$ nodes is in the order of $O \Big( \big( (nps)^{2\lambda}+\lambda (nps)^{\lambda} \log(nps) \big) \times n \Big)$. For $p=\log(n)/n$ and $\lambda=2$, the time complexity is simplified to $O(n\log^4(n))$. For $p=\log^2(n)/n$, it is in the order of $O(n\log^8(n))$.

\subsection{Matching Method}
\label{sec:alg:seed}

First, we compute similarity matrix (or distance matrix) $\mSim$ between $\mathcal{V}_a$ and $\mathcal{V}_b$. In particular, element $(i,j)$ in this matrix is equal to: $\mSim_{ij} = \mNormC{i}{j}$ where $i \in \mathcal{V}_a$ and $j \in \mathcal{V}_b$.

Next, we form the set of matched pairs between $\mathcal{V}_a$ and $\mathcal{V}_b$, by executing Hungarian algorithm on the similarity matrix $X$. More specifically, Hungarian algorithm selects $n$ number of entries from matrix $X$, where from each column and each row, exactly one entry is chosen and the selected entries minimize the following cost:
\begin{equation}
cost=\frac{1}{n}\sum X_{ij}.
\label{eq:hungarian_cost}
\end{equation}

In other words, by running Hungarian algorithm, we form a mapping $\pi$ between $\mathcal{V}_a$ and $\mathcal{V}_b$ that has minimum mean of similarity distance over all possible choices. We call this version of the proposed method as ``TDS-h algorithm''.

Another option, instead of using Hungarian algorithm, is to use the following simple greedy algorithm. We select the minimun element $X_{ij}$ in matrix $X$ and align node $i \in G_a$ with node $j \in G_b$, and delete row $i$ and column $j$ from matrix $X$. This process is repeated $n$ times.  We call this version of the proposed method as ``TDS-g algorithm''.

As an example, \mRefFig{fig:methodParts}(c) shows $l_2$-norm distances between constructed feature vectors $\mFtr^{a}_{i}$ and $\mFtr^{b}_{j}$ from \mRefFig{fig:methodParts}(b). Four elements of the similarity matrix are shown in the figure. Either of the two matching methods can be applied. In this example, nodes $5$ and $18$ in graph $G_a$ are matched to nodes $12$ and $9$ in graph $G_b$, respectively.

\vskip 2mm
\noindent \textbf{Complexity Analysis:}
Time complexity of finding similarity matrix $X$ is in the order of $O(n^{2})$. Both matching methods are in the order of $O(n^{3})$.

\section{Conclusion}
In this paper, we proposed a seedless graph matching algorithm for correlated Erd\H{o}s-R$\acute{\text{e}}$nyi  graphs. We introduced node features based on tail of degree distribution. We showed that this approach has advantages with respect to matching nodes based on center of degree distributions. Our experiments showed that the proposed algorithm outperforms other related works for several real networks as well as Erd\H{o}s-R$\acute{\text{e}}$nyi  graphs with average degree of order $\Theta(\log(n))$ and $\Theta(\log^2(n))$.

\bibliographystyle{cas-model2-names}

\section{Experimental Evaluation}
\label{sec:exp}

The proposed seedless graph matching algorithm, called tail degree signature (TDS), is experimentally evaluated in this section.
The constant parameters $\mMaxDist$ and $\mFtrLen$ are set to $2$ and $10$, respectively.
The algorithm is implemented in Python language.

\begin{figure*}
	\centering
		\includegraphics[width=.95\textwidth]{pic/fig_acc_lgn_lg2n.pdf}
		\caption{Accuracy of the proposed TDS algorithm and previous seedless algorithms, versus different values of $s$, for Erd\H{o}s-R$\acute{\text{e}}$nyi  graphs with (a) $p = \log(n)/n$ and (b) $p = \log^2(n)/n$, and $n=1000$. The lower the value of $s$ the more difficult it becomes to match the graphs.}
		\vskip -2mm
	\label{figaccerdos}
\end{figure*}

\subsection{Accuracy}

The two versions of TDS algorithm (TDS-h and TDS-g) are compared with recent seedless graph matching algorithms on Erd\H{o}s-R$\acute{\text{e}}$nyi  graphs with $p=\log(n)/n$ and $p=\log^2(n)/n$.
In particular, we consider Degree Profile (DP) \cite{degreeProfile}, Laplacian \cite{carcassoni2002alignment, leordeanu2005spectral}, Canonical labeling \cite{dai2018performance}, IsoRank \cite{singh2008global}, Final \cite{zhang2016final}, and Moana \cite{zhang2019multilevel} algorithms.

\mRefFig{figaccerdos}(a) shows accuracy of TDS algorithms and the other methods versus $s$. Every value in this figure shows the average accuracy for $50$ randomly generated Erd\H{o}s-R$\acute{\text{e}}$nyi  graphs with $p = \log(n)/n$ and $n=1000$.
As shown in the figure, both versions of TDS algorithm achieve much higher accuracy compared to the other algorithms. Moreover, they yield accurate solutions for lower values of $s$.
For instance, at $s=0.98$, TDS-h and TDS-g achieve about $80\%$ accuracy, while DP and Laplacian reach about $40\%$ and $20\%$ accuracy, respectively, and the accuracy of all the other methods are less than $10\%$.
At $s=0.95$, TDS-h and TDS-g achieve about $45\%$ accuracy, while the accuracy of all the other methods are about or less than $10\%$.

\mRefFig{figaccerdos}(b) presents the same comparisons as above for Erd\H{o}s-R$\acute{\text{e}}$nyi  graphs with $p = \log^{2}(n)/n$. In this region, TDS-h has higher accuracy than TDS-g for lower values of $s$. Both versions of TDS algorithm achieve much higher accuracy compared to the other algorithms.
For instance, at $s=0.98$, TDS-h and TDS-g achieve about $90\%$ and $50\%$ accuracy, respectively, while all the other methods are about or less than $10\%$.

\begin{figure}[tp]
	\centering
	\includegraphics[width=.82\columnwidth]{pic/fig_time_lgn_lg2n_max.pdf}
	\vskip -1mm
	\caption{Runtime of the proposed TDS algorithm and previous seedless algorithms (in seconds), versus different values of $n$, for Erd\H{o}s-R$\acute{\text{e}}$nyi  graphs with (a) $p = \log(n)/n$ and (b) $p = \log^2(n)/n$, and $s=0.99$. }
	\label{fig:runtime:erdos}
\end{figure}

\subsection{Runtime}

\mRefFig{fig:runtime:erdos} compares runtimes of the considered algorithms on Erd\H{o}s-R$\acute{\text{e}}$nyi  graphs with $p = \log(n)/n$ and $p = \log^2(n)/n$ for $n=\{1000, 2000, 4000, 8000\}$ and $s=0.99$. An empty value in \mRefFig{fig:runtime:erdos} denotes that we stopped (killed) the process because the runtime exceeded 16 hours.

As can be seen, for $p = \log^2(n)/n$, IsoRank, Final, and Moana have smaller runtimes compared to the other methods. TDS-g, Laplacian, and Canonical have comparable runtimes, while TDS-g have much higher accuracy (\mRefFig{figaccerdos}(b)). The runtimes of TDS-h and DP grow dramatically as the number of nodes increases.

\begin{figure*}
	\centering
	\includegraphics[width=0.6\textwidth]{pic/fig_acc_real_mean.pdf}
	\vskip -1mm
	\caption{Comparing accuracy of TDS with previous seedless algorithms, in real-world networks. The last column shows the mean accuracy, i.e., the geometric mean of all the other columns.}
	\label{fig:acc:real}
\end{figure*}

\subsection{Real-world Networks}

In addition to Erd\H{o}s-R$\acute{\text{e}}$nyi  graphs, we also evaluated the proposed TDS algorithm on the following three real-world networks and compared it with previous seedless algorithms.

\begin{itemize}

	\item Bitcoin-OTC \cite{data-bitcoin1, data-bitcoin2}: This is who-trusts-whom network of people who traded using Bitcoin cryptocurrency on a platform called Bitcoin-OTC. It contains 5,881 nodes and 35,592 edges. Members (nodes) on this platform can rate other members (nodes) in the range -10 to 10. To use Bitcoin-OTC as a benchmark for evaluating graph matching algorithms, we consider the following two unweighted networks. The first network contains all the nodes and edges in the original graph, and the second network contains only the positive edges.

	\item GR-QC \cite{data-GR-QC}: arXiv GR-QC (General Relativity and Quantum Cosmology) collaboration network contains 5241 nodes and 11,923 edges. Each author is represented by a node. Two nodes are connected if the authors have at least one common paper on GR-QC category from January 1993 to April 2003. This dataset contains two networks which are permuted version of one another, i.e., $s=1$ \cite{data-GR-QC}.

	\item Facebook \cite{data-facebook}: This dataset contains ``friends lists" from Facebook, which was collected from a survey using a Facebook app. The dataset includes 4039 nodes and 88234 edges. For the task of network alignment, we added some noises to the Facebook network edges, i.e, we constructed a new network with the same set of nodes as Facebook network while each edge in Facebook network is preserved in the new network with probability $s$.
\end{itemize}

In \mRefFig{fig:acc:real}, we compare the accuracy of TDS with other seedless algorithms. In almost all cases,  the proposed algorithm outperforms the other algorithms.
For instance, in GR-QC benchmark, the accuracy is around $70\%$ in TDS-h, TDS-g,  Laplacian, IsoRank, and Final algorithms, while the other methods have less than $5\%$ accuracy.
In Bitcoin-OTC and Facebook benchmarks, TDS-h, TDS-g, and DP have much higher accuracy compared to the other methods.

The last column in \mRefFig{fig:acc:real} shows the geometric mean of the other columns. As it can be seen, TDS-h and TDS-g achieve the mean accuracy of about $60\%$, while the mean accuracy of DP is about $30\%$, and the other methods have less than $20\%$ accuracy.

\section{Introduction}
\label{sec:introduction}

Graph  matching (or network alignment) between two correlated networks is the problem of finding bijection mapping between the nodes in one network to the nodes in the other network according to structural similarities between them.
If the two networks have exactly the same structure, the problem reduces to the graph isomorphism problem, but in general, the two networks are only similar, which makes the problem more challenging.

Network alignment arises in various applications in different fields including computer vision \cite{cho2012progressive},  pattern recognition \cite{conte2004thirty}, autonomous driving \cite{slam_2019}, computational biology \cite{elmsallati2016global,seah2014dualaligner}, and social networks \cite{narayanan2009anonymizing}.
For instance, in computational biology, protein-protein interactions (PPI) can be modeled as networks. PPI networks of different species can be aligned by solving the network alignment problem which can be useful in investigating evolutionary conserved pathways or reconstructing phylogenetic trees \cite{kuchaiev2010topological}.

Network alignment algorithms can be classified from different aspects like seed-based algorithms, and seedless algorithms. Seed-based network alignment algorithms work based on a set of pre-matched nodes from the two networks, called seeds \cite{kazemi2016network,mossel2019seeded,zhang2018efficient}, while seedless algorithms do not require any seed set as input \cite{conte2004thirty}.
Moreover, in order to assist the matching procedure, some algorithms employ node or edge features as a side information (e.g., user names or locations in de-anonymization of social networks \cite{malhotra2012studying, nunes2012resolving}), while some other matching algorithms do not require such prior knowledge and only utilize the structural similarities between the two networks as the most important feature in solving the problem \cite{henderson2011s}.
In this paper, we propose a \textbf{seedless} network alignment algorithm which \textbf{does not require} either any input seed set, or any input features for the nodes or edges as side information. In other words, the proposed algorithm works solely based on structural similarities between the two correlated networks.

Most of the seed-based network alignment algorithms rely on the idea of percolation, in which the algorithm starts from a small set of pre-matched nodes (seeds), and gradually expands the set of matched nodes by applying some rules on the neighbor nodes of previously matched nodes.
The pioneering method in this category, which succeeded in de-anonymizing a social network with millions of nodes, was introduced by Narayanan and Shmatikov \cite{narayanan2009anonymizing}. They empirically observed that the proposed algorithm is very sensitive to the size of the seed set. If the size of seed set is too small, the algorithm could not percolate, but if the size exceeds a threshold, the algorithm could successfully percolate and de-anonymize a large portion of the entire network.
Yartseva and Grossglauser \cite{yartseva2013performance} later proved that such phenomenon happens in random bigraph models.
Later, Kazemi et al. \cite{kazemi2015growing} proposed a percolation-based method called NoisySeed algorithm. The main advantage of this algorithm, as the name implies, is that the initial seed set can include some incorrectly matched pairs as well. The required size for the seed set as well as the tolerable number of incorrect matches have been investigated in \cite{kazemi2015growing}.

Compared with the above solutions, the seedless algorithms do not require pre-matched node pairs as an input.
In the literature, several seedless methods have been proposed based on convex relaxations of network alignment problem. For instance, in \cite{lyzinski2015graph}, alignment problem is relaxed as a \linebreak quadratic programming problem, and then, the solution is projected into zeros and ones in order to recover the mapping between nodes of two networks.
Some other seedless algorithms rely on computing graph edit distance between the two networks, which is basically the minimum number of edge deletions or insertions required to convert one of the networks to the other one \cite{conte2004thirty, fernandez2001graph}.
Methods based on convex relaxations or graph edit distance are often much more time consuming than other seedless network alignment algorithms \cite{degreeProfile}.

Spectral methods are another type of seedless algorithms which align nodes based on eigenvalues and eigenvectors of a transformation of the network's adjacency matrix \cite{carcassoni2002alignment, leordeanu2005spectral}. The main idea in these methods is to obtain Laplacian matrices from adjacency matrices of the two networks and then compute the eigenvectors and eigenvalues of these Laplacian matrices. Next, $k$ number of eigenvectors corresponding to top $k$ eigenvalues are selected to construct a $k$-dimensional feature vector for every node. From these feature vectors, the nodes in two networks can be aligned based on a distance metric.

Besides to the above seedless algorithms, several \linebreak machine-learning based algorithms have been proposed that match nodes based on a set of features which are extracted by processing additional information from nodes, e.g., user-names or locations in social networks \cite{abel2010interweaving, egozi2013probabilistic, nunes2012resolving}. As mentioned before, the proposed method in this paper works \linebreak merely based on structural similarities between the two networks, and does not require any additional features.

Recently, few seedless network alignment algorithms \linebreak have been proposed for Erd\H{o}s-R$\acute{\text{e}}$nyi  graphs.
Barak et al. \cite{barak2018nearly} presented a matching algorithm that finds certain small sub-networks that appear in both networks, based on which a set of seeds is formed accordingly. Next, a percolation algorithm extends the selected seeds to match all the nodes.
This algorithm is designed for Erd\H{o}s-R$\acute{\text{e}}$nyi  graphs with average node degrees in the range $[n^{o(1)}, n^{1/153}]$ or $[n^{2/3}, n^{1-\epsilon}]$, where $\epsilon$ is a small positive constant. This range covers very sparse or very dense Erd\H{o}s-R$\acute{\text{e}}$nyi  graphs. Compared with this algorithm, the proposed solution in this paper works on Erd\H{o}s-R$\acute{\text{e}}$nyi  graphs with average node degrees of order $\log(n)$. In fact, it has been shown that the true graph matching can be recovered with high probability if and only if the average node degree is in the order of $\Omega(\log(n))$ \cite{cullina2016improved}. Thus, our proposed algorithm can work for the minimum value of average node degree that is possible to find the correct matching.

Dai et al. \cite{dai2018performance} proposed another network alignment algorithm for Erd\H{o}s-R$\acute{\text{e}}$nyi  graphs called canonical labeling. In the first step of this algorithm, the nodes in the two networks are sorted according to their degrees. Then, the top $h$ highest degree nodes in two networks are aligned based on the sorted lists.
In the second step, each remaining node $j$ gets a binary vector of length $h$. Entry $i$ of this vector is equal to one if node $j$ is connected to $i$-th node in the sorted list. Otherwise, this entry is set to zero. The nodes are then aligned according to these binary feature vectors. Our experiments show that the canonical labeling does not have good performance in the networks with average node degrees of order $\log(n)$ or even $\log^{2}(n)$.
Ding et al. \cite{degreeProfile} proposed a network alignment algorithm for Erd\H{o}s-R$\acute{\text{e}}$nyi  graphs with average node degree in three regions including $\Theta(\log^{2}(n))$. In this algorithm, every node is assigned a feature vector containing empirical degree distribution of its neighbors. Then, the minimum distance on these features are used to match the nodes. This algorithm has a relatively higher accuracy in Erd\H{o}s-R$\acute{\text{e}}$nyi  graphs with average degree of $\log(n)$, but our experiments show that it has lower performance for the graphs with average node degree of order $\log^2(n)$.

Beside to the mentioned algorithms for Erd\H{o}s-R$\acute{\text{e}}$nyi  \linebreak graphs, several graph matching algorithms have been proposed with specific applications in PPI networks, social networks, and image databases. Singh et al. \cite{singh2008global} introduced a well-known network alignment algorithm in PPI networks, which is named IsoRank. In this algorithm, the similarity of a node $i$ in one of the network to a node $j$ in the other network depends on how similar are the neighbor nodes of node $i$ to the neighbor nodes of node $j$. More specifically, in the first step of this algorithm, the similarity matrix $R$ is constructed iteratively where entry $R_{ij}$ indicates similarity of node $i$ in one of the network to node $j$ in the other network. In each iteration, entry $R_{ij}$  is computed from other entries in $R$ like $R_{uv}$, where $u$ and $v$ are neighbor nodes of $i$ and $j$ in the two networks, respectively. In the second step, nodes in two networks are aligned according to $R$.
Later, Zhang et al. \cite{zhang2016final} proposed a network alignment algorithm, called Final algorithm. The Final algorithm can work on both node and edge attributed networks or simple networks without any auxiliary information. Furthermore, this algorithm uses prior knowledge of pairwise alignment preference $H$ matrix, where each entry in this matrix shows likelihood of aligning two corresponding nodes from two input networks. If this prior knowledge is not given, all entries of $H$ are set to the same value, i.e., a uniform distribution. This algorithm iteratively minimizes an objective function, which is constructed from network structure (i.e, adjacency matrix) and nodes and edges attributes.
Zhang et al. \cite{zhang2019multilevel} proposed another network algorithm called Moana. This algorithm aligns nodes in three steps. First, it coarsens the input networks to a structured representation. Next, it aligns the coarsened representation. Finally, the alignment at multi levels is obtained including node level by interpolation.

Recently, several works \cite{Fey2020Deep,Yu2020Learning} with the applications in the fields of computer vision, used graph neural networks in order to obtain node embedding vectors and match the nodes based on them. These works utilized extracted features from images as inputs to the graph neural network to facilitate the process of graph matching.

In this paper, we propose a seedless network alignment algorithm, which works without any auxiliary information.
The proposed algorithm has two main steps: In the first step, for each node $i$ in any of two correlated networks, we construct a feature vector containing degrees of nodes like $j$ having the following two properties: I) Node $j$ should be in the neighborhood of node $i$. II) Its degrees is in the tail of empirical degree distribution of nodes in neighborhood of node $i$. Due to this property of the proposed algorithm, we call it ``Tail Degree Signature (TDS)" network alignment algorithm. In the second step, we compute a distance metrix between any pair of feature vectors to generate the matrix of distances. Then we use a greedy algorithm or the Hungarian algorithm \cite{kuhn1955hungarian}) to align nodes from the constructed distance matrix. We evaluate the performance of TDS algorithm for both synthetic and real networks. For synthetic networks we select Erd\H{o}s-R$\acute{\text{e}}$nyi  graphs with average degree of order $\log(n)$ and $\log^2(n)$, which are difficult regions for the network alignment problem \cite{cullina2016improved}.
Experiments show that the proposed TDS algorithm outperforms other related works in both real-world networks and synthetic Erd\H{o}s-R$\acute{\text{e}}$nyi  graphs with average node degree of order $\log(n)$ and also $\log^2(n)$.


\section{Introduction}
\label{introduction}

Voice pathology can be caused by the presence of tissue infection, systemic changes, mechanical stress, surface irritation, tissue changes, neurological and muscular changes, and other factors~\cite{Titze1994}. Due to vocal pathology, the mobility, functionality and shape of the vocal folds are affected resulting into irregular vibrations and increased acoustic noise. Such a~voice sounds strained, harsh, weak, and breathy~\cite{Teager1980,Hillenbrand1996}, which significantly contributes to the overall poor voice quality~\cite{brabenec2017speech,mekyska2015robust}.

Up to this day, vocal pathology detection has been approached by subjective and objective evaluations~\cite{mehta2008voice}. The first category (subjective evaluation) consists of so called in-hospital auditory-perceptual and visual examination of the vocal folds~\cite{oates2009auditory,song2013assessment}. For the visual examination laryngostroboscopy is commonly used~\cite{Uloza2015}. For the auditory-perceptual examination several clinical rating scales to diagnose and rate severity of vocal pathologies have been developed~\cite{de1997test,Gerratt1993,Kreiman1993,de1997test,Dejonckere2001}. Methods for subjective evaluation are, however, subject to inter-rater variability~\cite{armstrong1997place,gwet2014handbook}. Furthermore, they require patients' presence at the clinic, which can be a~serious problem especially in more severe stages of a~disease. This type of evaluation is also time costly, and it requires careful evaluation and scoring by clinicians.

\begin{table*}[htb!]
	\caption{Overview of related works focused on voice pathology detection.}
	\label{tab:related_Work}

	\scriptsize

	\begin{tabular}{p{2.1cm} l l l l l l}

		\hline\noalign{\smallskip}
		First author & Year & Ref. & Database & Input vowels & Classifier & Accuracy [\%] \\
		\hline\noalign{\smallskip}

			Hemmerling & 2016 & \cite{Hemmerling2016} & SVD & /a, i, u/ & KM, RF & 100.00 \\
			Muhammad & 2017 & \cite{Muhammad2017B} & SVD & /a/ & GMM & 99.98 \\
			Al-nasheri & 2017 & \cite{Alnasheri2017A} & MEEI, SVD, AVPD & /a/ & SVM & 99.81\,(MEEI), 91.17\,(AVPD), 90.98\,(SVD) \\
			Al-nasheri & 2017 & \cite{AlNasheri2017} & MEEI, SVD, AVPD & /a/ & SVM & 99.79\,(AVPD), 99.69\,(MEEI), 92.79\,(SVD) \\
			Al-nasheri & 2017 & \cite{Alnasheri2017B} & MEEI, SVD, AVPD & /a/ & SVM & 99.68\,(SVD), 88.21\,(MEEI), 72.53\,(AVPD) \\
			Eskidere & 2015 & \cite{Eskidere2015} & SVD & /a, i, u/ & GMM & 99.00 \\
			Amami & 2017 & \cite{amami2017incremental} & MEEI & /a/ & SVM & 98.00 \\
			Sabir & 2017 & \cite{sabir2017improved} & SVD & /a/ & ANN & 97.90 \\
			Hossain & 2016 & \cite{Hossain2016} & MEEI, SVD & /a, i, o/ & SVM, ELM, GMM & 95.00 \\
			Ali & 2017 & \cite{ali2017intra} & MEEI, SVD, AVPD & /a/ & GMM & 94.60\,(MEEI), 83.65\,(AVPD), 80.20\,(SVD) \\
			Muhammad & 2017 & \cite{Muhammad2017A} & MEEI, SVD, AVPD & /a/ & SVM & 99.40\,(MEEI), 93.20\,(SVD), 91.50\,(AVPD) \\
			Dahmani & 2017 & \cite{dahmani2017vocal} & SVD & /a/ & NB & 90.00 \\
			Souissi & 2016 & \cite{Souissi2016} & SVD & /a/ & ANN & 87.82 \\
			Hemmerling & 2017 & \cite{hemmerling2017voice} & SVD & /a/ & ANN & 87.50 \\
			Souissi & 2015 & \cite{Souissi2015} & SVD & /a/ & SVM & 86.44 \\

		\hline
	\end{tabular}

\vspace{0.5em}
Table notation: Ref.\,--\,reference, MEEI\,--\,Massachusetts Eye and Ear Infirmary Database~\cite{eye1994voice,mekyska2015robust}, SVD\,--\,Saarbruecken Voice Database~\cite{Woldert2007,Muhammad2017A,Alnasheri2017A}, AVPD\,--\,Arabic Voice Pathology Database~\cite{mesallam2017development,Muhammad2017A}, KM\,--\,K-means~\cite{hartigan1979algorithm}, RF\,--\,Random Forests~\cite{breiman2001random}, GMM\,--\,Gaussian Mixture Models~\cite{reynolds2015gaussian}, SVM\,--\,Support Vector Machines~\cite{hearst1998support}, NB\,--\,Naive Bayes~\cite{murphy2006naive}, ELM\,--\,Extreme Learning Machine~\cite{huang2006extreme}, and ANN\,--\,Artificial Neural Networks~\cite{schalkoff1997artificial}.

\end{table*}

The second category (objective evaluation) is based on the automatic non-invasive computerized analysis of acoustic signals to quantify and identify the underlying vocal pathology that may not even be audible to a~human being~\cite{mekyska2015robust}. This type of evaluation is therefore inherently free from the subjective bias. Moreover, voice can be nowadays easily recorded using a~variety of smart devices, and processed remotely using cloud technologies. From these reasons, works such as~\cite{Eskidere2015,Hemmerling2016,Muhammad2017A,Alnasheri2017A} focused on using signal processing techniques (to quantify vocal-manifestations of the pathology under focus) and machine learning algorithms (to automate the process of voice pathology detection) to build a~system capable of accurate discrimination of healthy and pathological voices. In Table~\ref{tab:related_Work}, we summarize recent (2015\,--\,now) related works focused on the objective voice pathology detection.

For the purpose of the objective voice pathology evaluation, several databases have been frequently used by the researchers. Massachusetts Eye and Ear Infirmary Database (MEEI)~\cite{eye1994voice,mekyska2015robust}, Saarbruecken Voice Database (SVD)~\cite{Woldert2007,Muhammad2017A,Alnasheri2017A}, and Arabic Voice Pathology Database (AVPD)~\cite{mesallam2017development,Muhammad2017A} are among the most commonly used ones. More specifically, most researchers have analyzed sustained phonation of the vowel /a/, e.g.~\cite{Alnasheri2014,Muhammad2017B,amami2017incremental,dahmani2017vocal} due to its presence in most databases (language-independent speech task~\cite{Titze1994}). Some researchers also analyzed a~combination of the vowels, e.g.~\cite{Martinez2012,Eskidere2015,Hemmerling2016}, etc. From the voice pathologies point of view, most researchers restricted the dataset to a~limited set of pathologies~\cite{amami2017incremental,Muhammad2017B,dahmani2017vocal,hemmerling2017voice,sabir2017improved,Muhammad2017A,ali2017intra,AlNasheri2017,Alnasheri2017B,Alnasheri2017A}.

Next, conventional and clinically interpretable~\cite{brabenec2017speech}) acoustic features were usually computed prior to pathology detection~\cite{Muhammad2017B,dahmani2017vocal,sabir2017improved}. The acoustic features such as multidimensional voice program parameters (MDVP)~\cite{Alnasheri2017B}, mel-frequency cepstral coefficients (MFCC)~\cite{saldanha2014vocal}, glottal-to-noise excitation ratio (GNE)~\cite{michaelis1997glottal}, etc. were usually extracted. For more information about methods for pathological speech parametrization, see~\cite{mekyska2015robust}. After the feature extraction, multiple conventional classifiers have been used to detect the presence of voice pathology. Most authors relied on the following algorithms: Support Vector Machines (SVM), Gaussian Mixture Models (GMM), Random Forests (RF), and Artificial Neural Networks (ANN)~\cite{hemmerling2017voice,ali2017intra,amami2017incremental,dahmani2017vocal}, etc.

As can be seen, the results vary greatly between the published papers mainly due to differences in selected voice pathology samples, acoustic features, and classifiers that were used for the experiment. However, we can conclude that:
\begin{enumerate}
	\item most works analyzed a~single speech task, mainly the sustained phonation of the vowel /a/ (language independent speech task)
	\item most works analyzed datasets that were restricted to a~subset of vocal pathologies from 1~to 3~databases (MEEI, SVD, AVPD)
	\item most works extracted conventional dysphonic features to quantify major vocal-manifestations of specific vocal pathologies
	\item most works employed conventional supervised learning algorithms such as the following: SVM, GMM, RF, ANN, and others
\end{enumerate}

\begin{figure*}[tb!]
	\centering
	\begin{subfigure}[t]{0.45\textwidth}
			\includegraphics[width=\textwidth]{images/avpd.pdf}
			\caption{AVPD}
			\label{fig:avpd}
	\end{subfigure}
	\quad
	\begin{subfigure}[t]{0.45\textwidth}
			\includegraphics[width=\textwidth]{images/meei.pdf}
			\caption{MEEI}
			\label{fig:meei}
	\end{subfigure}

	\begin{subfigure}[t]{0.45\textwidth}
			\includegraphics[width=\textwidth]{images/pda.pdf}
			\caption{PDA}
			\label{fig:pda}
	\end{subfigure}
	\quad
	\begin{subfigure}[t]{0.45\textwidth}
			\includegraphics[width=\textwidth]{images/svd.pdf}
			\caption{SVD}
			\label{fig:svd}
	\end{subfigure}

	\label{fig:databases}
	\caption{Visualization of inequality of samples per vocal pathology in the datasets used in this work (only 5~most common pathologies in each database are present in the legend), and healthy samples. Databases: a) AVPD~\cite{mesallam2017development,Muhammad2017A}, b) MEEI~\cite{eye1994voice,mekyska2015robust}, PDA~\cite{godino2010pathological,arias2011combining,mekyska2015robust}, and SVD~\cite{Woldert2007,Muhammad2017A,Alnasheri2017A}.}

\end{figure*}

To propose results comparable with the previously published works, we analyze voice recordings of sustained phonation of the vowel /a/ as well. However, unlike the previous works, we analyze a~larger dataset composed of 4~different databases, namely: MEEI~\cite{eye1994voice,mekyska2015robust}, SVD~\cite{Woldert2007,Muhammad2017A,Muhammad2017A,Alnasheri2017A}, AVPD~\cite{mesallam2017development,Muhammad2017A} (these databases are commonly used by the community), and Pr\'{i}ncipe de Asturias Database (PDA)~\cite{godino2010pathological,arias2011combining,mekyska2015robust}. Furthermore, to propose models capable of robust voice pathology detection, we do not restrict the dataset to only a~subset of common vocal pathologies. With this approach, our dataset does contain a~large number of pathologies with only few recordings. To see the sparsity of distribution and inequality of the number of pathologies in the databases, see Figures~\ref{fig:avpd} (AVPD),~\ref{fig:meei} (MEEI),~\ref{fig:pda} (PDA), and~\ref{fig:svd} (SVD).

By using 4~different databases, we aim to increase the size of our dataset to enable exploring possibilities of using supervised deep learning techniques that delivered state-of-the-art results in many domains including speech processing. To our best knowledge, despite our previous work~\cite{harar2017voice}, there are no other papers using deep learning algorithms for voice pathology detection. Next, we also employ the conventional voice pathology detection approach based on acoustic feature extraction procedure. However, unlike previous works, we use gradient boosting techniques for classification. To tackle the problem of sparse distribution of a~variety of vocal pathologies with only few recordings across the databases, we also investigate usage of anomaly detection procedure.

The rest of this paper is organized as follows. Section \ref{databases} introduces databases utilized in this article. In Section \ref{methodology}, the methodology of the experiment is discussed. The results are presented in Section \ref{results}. Conclusions are drawn in Section \ref{conclusions}.

\section{Databases}
\label{databases}

As mentioned previously, we chose the following speech task: sustained phonation of the vowel /a/ as a~basis for our experiments. During this particular speech task a~speaker is asked to sustain phonation of a~vowel, attempting to maintain steady frequency and amplitude at a~comfortable level~\cite{Titze1994}. The advantage of this speech task in comparison with other common speech tasks such as reading tasks, or a~running speech is that it is free of articulatory and other linguistic confounds~\cite{Titze1994}. This independence makes this task an ideal choice to construct a~large dataset that is necessary for supervised deep learning algorithms. In fact, sustained /a/ vowel phonation is the only speech task that is present in all databases used in this work. The contents of the databases relevant to this work can be seen in Table\,\ref{tab:contents}.

\subsection{AVPD database}
\label{avpd}

Arabic Voice Pathology Database (AVPD)~\cite{mesallam2017development,Muhammad2017A} was developed at the Communication and Swallowing Disorders Unit of King Abdul Aziz University Hospital, Riyadh, Saudi Arabia. The database contains recordings (366 samples: 188 healthy, 178 pathological) of sustained phonation of the vowels /a, e, o/, counting from 0-10, standardized Arabic passage, and reading three words. All recordings are sampled at $f_s = 48\,000$\,Hz with a bit depth of 16 bits. The database comprises five organic voice disorders: vocal fold cysts, nodules, paralysis, polyps, and sulcus. Multiple recordings of the same vowel were taken to help model the intra-speaker variability.

\subsection{MEEI database}
\label{meei}

Massachusetts Eye and Ear Infirmary Database (MEEI) \cite{eye1994voice,mekyska2015robust} is one of the most popular and most widely-used database (used for many years as a~benchmark in the field of pathological speech analysis). It contains more than 1\,400 recordings of sustained phonation of the vowel /a/ (recorded from 657 pathological speakers with different types of pathologies and 53 healthy speakers). This database has several disadvantages such as the fact that recordings of the normophonic voice were recorded in different conditions (e.g. different environment, recordings are sampled at: $f_s = 50\,000$\,Hz, $f_s = 25\,000$\,Hz, and $f_s = 10\,000$\,Hz) when compared to pathological recordings. The database is also gender-unbalanced, etc.

\subsection{PDA database}
\label{pda}

Pr\'{i}ncipe de Asturias Database (PDA)~\cite{godino2010pathological,arias2011combining,mekyska2015robust} contains recordings of 200 pathological speakers with different types of organic pathologies (e.g. nodules, polyps, oedemas, and carcinomas, etc.) and 239 healthy speakers. For each speaker, sustained phonation of the vowel /a/ is recorded. All recordings are sampled at $f_s = 25\,000$\,Hz. This database contains more speakers than a~balanced version of MEEI database that according to~\cite{Parsa2003} comprise only 173 recordings of pathological speakers.

\subsection{SVD database}
\label{svd}

Saarbruecken Voice Database (SVD)~\cite{Woldert2007,Muhammad2017A,Alnasheri2017A} is a~collection of voice recordings and electroglottography (EGG) signals from more than 2\,000 speakers. It contains recordings of 687 healthy persons (428 females and 259 males) and 1356 patients (727 females and 629 males) with one or more of the 71 different pathologies. One session contains the recordings of the following components: a) vowels /i, a, u/ produced at normal, high and low pitch; vowels /i, a, u/ with rising-falling pitch; and c) sentence ``Guten Morgen, wie geht es Ihnen?'' (``Good morning, how are you?''). All samples of the sustained vowels are between 1~to 3~seconds long, sampled at $f_s = 50\,000$\,Hz with 16-bit resolution~\cite{Woldert2007}. In contrary to MEEI database, all audio samples (healthy and pathological) in SVD were recorded in the same environment.

\begin{table}[tb!]
	\caption{Contents of the databases used in this work.}
	\label{tab:contents}

	\begin{tabular}{p{2.4cm} r r r r}
		\hline\noalign{\smallskip}
		& AVPD & MEEI & PDA & SVD \\
		\noalign{\smallskip}\hline\noalign{\smallskip}

		H samples & 188 & 53 & 239 & 687 \\
		P samples & 178 & 657 & 200 & 1356 \\
		vowels & /a, e, o/ & /a/ & /a/ & /a, i, u/ \\
		running speech & yes & yes & no & yes \\
		EGG & no & no & no & yes \\
		GRBAS & yes & no & no & no \\
		\noalign{\smallskip}\hline\noalign{\smallskip}

	\end{tabular}

\vspace{0.5em}
Table notation: PDA\,--\,Pr\'{i}ncipe de Asturias Database (PDA)~\cite{godino2010pathological,arias2011combining,mekyska2015robust}, MEEI\,--\,Massachusetts Eye and Ear Infirmary Database~\cite{eye1994voice,mekyska2015robust}, SVD\,--\,Saarbruecken Voice Database~\cite{Woldert2007,Muhammad2017A,Alnasheri2017A}, AVPD\,--\,Arabic Voice Pathology Database~\cite{mesallam2017development,Muhammad2017A}, H\,--\,healthy, P\,--\,pathological, and GRBAS\,--\,Grade, Roughness, Breathiness, Asthenia, Strain scale~\cite{de1997test}.

\end{table}

\section{Methodology}
\label{methodology}

\subsection{Data processing}
\label{data_processing}

We used 720 recordings from AVPD, 709 recordings from MEEI, 422 from PDA and 2\,040 from SVD. We only excluded samples that were shorter than 0.750\,s in length (removed 319 recordings). We also excluded all recordings of speakers bellow the age of 19 and also above the age of 60 (it is known that the most significant changes of voice happen during adulthood until the voice matures at around age of 20 and remains relatively stable until around age of 60) \cite{stathopoulos2011changes}. After these restrictions, the final number of samples equaled to 2\,707.

Using \href{http://sox.sourceforge.net/}{SOX library} (version 14.4.2), we re-sampled each recording to $f_s = 16\,000$\,Hz. Then we trimmed each sample to exactly 0.750\,s in duration. If a~recording was below 0.950\,s in duration, we extracted only one sample from the middle of it. For longer recordings we trimmed each end by 0.100\,s and extracted as many 0.750\,s long chunks as possible without overlap with stride of 0.375\,s. Using this approach, the total number of 8\,042 chunks was obtained. Further details regarding the number of chunks used can be found in Table\,\ref{tab:nchunks}.

\begin{table}[tb!]
	\caption{Number of chunks used in the experiments.}
	\label{tab:nchunks}

	\begin{tabular}{p{1.8cm} r r r r r}
		\hline\noalign{\smallskip}
		Database & H (M) & P (M) & H (F) & P (F) & Total \\
		\noalign{\smallskip}\hline\noalign{\smallskip}

		AVPD & 625 & 509 & 872 & 804 & 2810 \\
		MEEI & 126 & 114 & 185 & 168 & 593 \\
		PDA & 1158 & 331 & 5 & 605 & 2099 \\
		SVD & 400	& 645	& 624	& 871 & 2540 \\

		\noalign{\smallskip}\hline\noalign{\smallskip}
		Total	& 2309 & 1599 & 1686 & 2448 & \textbf{8042} \\
		\noalign{\smallskip}\hline\noalign{\smallskip}
	\end{tabular}

\vspace{0.5em}
Table notation: PDA\,--\,Pr\'{i}ncipe de Asturias Database (PDA)~\cite{godino2010pathological,arias2011combining,mekyska2015robust}, MEEI\,--\,Massachusetts Eye and Ear Infirmary Database~\cite{eye1994voice,mekyska2015robust}, SVD\,--\,Saarbruecken Voice Database~\cite{Woldert2007,Muhammad2017A,Alnasheri2017A}, AVPD\,--\,Arabic Voice Pathology Database~\cite{mesallam2017development,Muhammad2017A}, H\,--\,healthy, P\,--\,pathological, M\,--\,males, and F\,--\,females.

\end{table}

\subsection{Feature extraction}
\label{feature_extraction}

At first, we considered raw audio samples as an input data for the voice pathology detection model. Each file (the 0.750\,s chunk) was therefore inserted to the input of the neural network as a~vector of 12\,000 features (computed as: 0.750\,s $\cdot$ 16\,000\,Hz = 12\,000 features). Additionally, we normalized each sample using min-max scaling to a~range $\langle 0, 1 \rangle$.

Next, we extracted a~set of conventional commonly-used acoustic (dysphonic) features~\cite{brabenec2017speech,mekyska2015robust} using Neurological Disorder Analysis Tool (NDAT)~\cite{Smekal2015b,mekyska2015robust} written in MATLAB and developed at the Brno University of Technology. Specifically, we computed the following acoustic features: pitch, jitter, shimmer, harmonic-to-noise ratio, detrended fluctuation analysis parameters, glottis quotients (open, closed), glottal-to-noise excitation ratio, Teager-Kaiser energy operator, modulation energy, and normalized noise energy. We further applied the following statistical properties: mean, standard deviation, coefficient of variation, quartiles ($1^{\mathrm{st}}$, $2^{\mathrm{nd}}$, $3^{\mathrm{rd}}$), interquartile range, kurtosis, and skewness.

Moreover, we computed spectrograms using \href{https://matplotlib.org/}{Matplotlib} (version 2.1.2) library for Python. The computation setup: mode (power spectral density), no windowing, no overlap, and NFFT ($512$\,samples). Following Ali et al.~\cite{ali2017automatic}, we used data up to 1\,500\,Hz (1\,150 features). Furthermore, we normalized the values of this matrix with min-max scaling to a~range between 0~and 1 as well.

At last, we computed most commonly used perceptual~\cite{Smekal2015b} acoustic feature: MFCC using \href{https://github.com/jameslyons/python_speech_features/}{Python Speech Features library}. The computation setup: length of a~window function ($0.025$\,s), step size ($0.010$\,s), number of filters in the filter-bank ($26$), number of coefficients ($13$), and NFFT ($512$\,samples). With this approach, we obtained a~matrix consisting of 962 features (13\,coefficients $\times$ 74\,time steps). We also computed the mean and standard deviation of the 13 coefficients along the time axis, which resulted into additional 26 features per sample. Next, we scaled the MFCC feature matrix by min-max algorithm (means and standard deviations were computed before scaling). The statistical features were scaled separately to have 0~mean and unit variance before classification.

\subsection{Experiments}
\label{experiments}

As mentioned previously, there is a~wide range of pathologies present in the databases used in this work. For more information, see Figures~\ref{fig:avpd} (AVPD),~\ref{fig:meei} (MEEI),~\ref{fig:pda} (PDA), and~\ref{fig:svd} (SVD). Each database was labelled in different language and with different experts by different criteria. Therefore, it is almost impossible to combine these databases to obtain one consistent database of multiple pathologies with reasonable number of samples. Only feasible way of combining the samples seems to be the exhaustive manual pairing by an expert clinician, which is also rather difficult since lots of recordings are labelled with multiple pathologies. In order to conduct inter-database experiments, authors therefore usually pick a~smaller sub-sample of 2~to 5~pathology types that are relatively easier to pair.

Next, most of these pathologies are very sparsely distributed across the databases. Searching for an ideal subset of acoustic features that would yield a~good classification performance for each voice pathology is therefore almost impossible. Furthermore, it is not well-known if these pathologies present in the databases have similar vocal-manifestations.

In contrast to the previous works, we aim to investigate possibilities of robust voice pathology detection using a~set of 4~almost unrestricted databases comprising a~large number of pathologies. From these reasons, we decided to conduct several experiments: a) supervised learning (assuming the pathologies have similar manifestations and therefore the number of samples per pathology type is irrelevant), b) anomaly detection (assuming the pathologies do not have similar manifestations and therefore the number of samples per pathology type cannot be neglected).

Regarding the supervised learning approach, we used the state-of-the-art gradient boosting algorithm: XGBoost~\cite{chen2016xgboost} (version 0.6) for its current successes in many Kaggle competitions, fast training and model interpretability. Additionally, we explored possibilities of deep learning approach for its ability to robustly model complex relationships when optimized using enough data. However, the equation for computing the sufficient size of training dataset has not been formally described yet. Generally established rule of thumb in machine learning community is to have more training samples than trainable parameters. For this reason, we used the DenseNet~\cite{huang2016densely} architecture, which succeeded in overcoming the problem of having too many trainable parameters by densely connecting the convolutional layers. We adjusted \href{https://github.com/tdeboissiere/DeepLearningImplementations/tree/master/DenseNet}{Thibault de Boissiere's Keras implementation of the DenseNet} (Keras framework~\cite{Chollet2015}, version 2.1.2), to process 1D signals treating raw audio as 1D vector. Spectrograms were processed as a~matrix using the frequency bins not as y~dimension, but rather as a~stack of channels in the same way the 3~RGB channels are stacked in an image \cite{wyse2017audio}. The MFCC were processed the same way as spectrograms. Since we are not able to say with 100\% certainty that healthy examples are not polluted by deviant samples, we decided to use anomaly detection in favor of novelty detection in which case it is important to model the non-deviant samples. In this case, we chose Isolation Forest~\cite{liu2008isolation,liu2012isolation} classifier implemented in scikit-learn library~\cite{scikit-learn} (version 0.19.1).

For the above mentioned experiments, we decided to analyze the performance of the voice pathology detection models using multiple types of input data: a)~raw audio samples to follow our previous work~\cite{harar2017voice} and further explore possibilities of robust voice pathology detection without manually-selected features (DenseNet), b)~conventional acoustic (dysphonic) features to follow the previously published works and quantify most common vocal pathologies (XGBoost, Isolation Forest), c)~spectrograms to achieve a~reasonable trade-off between dimensionality of the data and amount of information (DenseNet), and d)~MFCC to follow the previous works focusing on voice and speech modelling, and voice pathology detection (all models).

\subsection{Training and validation}
\label{training_and_validation}

To train and validate the models, we split the data to training, validation and testing sets. On top of that, we generated 10-fold validation indices using training and validation sets, so we can use exactly the same sets of data for each experiment. The test set was left for final evaluation of the models. Next, we stratified the testing and validation sets by medical state (healthy\,--\,H, pathological\,--\,P), gender, age, and gender-age group. Since the longer recordings were split into multiple chunks, we had to prevent the samples with chunks in the test or validation sets from leaking into the training set. Such chunks were carefully removed from the set. All other chunks were used in the training set.

At this point there is an unequal distribution of samples within the training set. We reacted to this fact by computing sample weights that can be used during training as a~compensation measure for under-represented groups. The final sample weight is a~product of 3~partial weights. Each of the partial weights quantifies the ratio between subgroups within the selected group (e.g. the ratio between the number of normophonic and pathological samples). For this purpose, we introduced a~class weight $\alpha$, gender weight $\beta$, and gender-age group weight $\gamma$ resulting in final sample weight $\omega$ that is computed as $\omega = \alpha \cdot \beta \cdot \gamma$. Weight for a~particular sample that belongs to subgroup $\alpha_i$ within group $\alpha$, $\beta_i$ within group $\beta$, and $\gamma_i$ within group $\gamma$ can be computed as follows:

\begin{equation} \label{eq:1}
\omega_{\alpha_i, \beta_i, \gamma_i} = \frac{n_{\alpha_i}}{\textrm{max}(n_{\alpha})} \cdot \frac{n_{\beta_i}}{\textrm{max}(n_{\beta})} \cdot \frac{n_{\gamma_i}}{\textrm{max}(n_{\gamma})}
\end{equation}
where $n$ represents the total number of samples: $n_{\alpha_i}$ is the number of samples in a~particular class; $n_{\beta_i}$ is the number of samples in a~particular gender; and $n_{\gamma_i}$ is the number of samples in a~particular gender-age group.

We used 30 to 100 iterations of randomized cross-validation search for hyper-parameter optimization for both XGBoost and Isolation Forest classifiers. The number of iterations did depend on the fitting time. More specifically, in the case of XGBoost, we were searching over the following hyper-parameters: number of estimators~$\langle 3, 300 \rangle$, learning rate~$\langle 0.006, 1 \rangle$, gamma~$\langle 10, 60 \rangle$, maximum depth $\langle 0, 9 \rangle$, minimum child weight $\langle 1, 3 \rangle$, sub-sample ratio $\langle 0.3, 1 \rangle$ and colsample bytree (sub-sample ratio of columns when constructing each tree) $\langle 0.1, 1 \rangle$. Regarding Isolation Forest we were searching over the following hyper-parameters: number of estimators~$\langle 6, 200 \rangle$, maximum samples $\langle 8, 64 \rangle$, contamination~$\langle 0.40, 0.76 \rangle$ and maximum features~$\langle 0.05, 1 \rangle$. As a~performance measure, we used F1 micro score as a~criteria of choosing the best hyper-parameters in the cross-validation setup. After the search for hyper-parameter, we re-fitted the models with the best hyper-parameters on the entire training set, and consequently evaluated on the testing set. The final results are presented in the form of confusion matrix (CM), and classification report (CR) tables. The formulas \ref{eq:2}, \ref{eq:3} and \ref{eq:4} describe the way of computing the precision, recall and F1 score (weighted average of the precision and recall) metrics presented in CR tables.

\begin{equation} \label{eq:2}
precision = \frac{tp}{tp + fp},
\end{equation}
where $tp$ denotes the number of correct predictions (observed class), and $fp$ determines the number of incorrect predictions (observed class). The precision is a ratio between the number of correct predictions of the observed class and the total number of predictions of the observed class.

\begin{equation} \label{eq:3}
recall = \frac{tp}{tp + fn},
\end{equation}
where $tp$ denotes the number of correct predictions (observed class), and $fn$ determines the number of incorrect predictions (opposing class). The recall is a ratio between the number of correct predictions of the observed class and the total number of samples in the observed class.

\begin{equation} \label{eq:4}
F1 = 2 \cdot \frac{precision \cdot recall}{precision + recall}
\end{equation}

\section{Results}
\label{results}

XGBoost~\cite{chen2016xgboost} trained (10-fold validation) with all features (consisting of 96 conventional dysphonic features and 26 MFCC coefficients) yielded an average F1 score of $0.922\,(\pm\,0.004)$ on the training set, and $0.829\,(\pm\,0.028)$ on the validation set. The final F1 score on the dedicated testing set was $0.733$. Performance details (classification matrix and classification report) can be found in Table~\ref{tab:xgbconf}, and Table~\ref{tab:xgbreport}. Based upon the performance on the development set (training and validation sets) the 50 iterations of randomized cross-validated search selected the following hyper-parameters: number of estimators ($294$), learning rate ($0.3$), gamma ($10$), max. depth ($3$), sub-sample ($0.5$), minimum child weight ($1$), colsample bytree ($1$). Details regarding the classification performance in relation to input data can be found in Table~\ref{tab:xgboostinputdata}.

\begin{table}[htb!]
\caption{Testing CM for XGBoost}
\label{tab:xgbconf}
\begin{tabular}{p{2.6cm} l l l}
\hline\noalign{\smallskip}
& true H & true P & total predicted \\
\noalign{\smallskip}\hline\noalign{\smallskip}
predicted H & \textbf{82} & 26 & 108 \\
predicted P & 38 & \textbf{94} & 132 \\
\noalign{\smallskip}\hline\noalign{\smallskip}
total true & 120 & 120 & accuracy: \textbf{0.733} \\
\noalign{\smallskip}\hline\noalign{\smallskip}
\end{tabular}
\end{table}

\begin{table}[htb!]
\caption{Testing CR for XGBoost}
\label{tab:xgbreport}
\begin{tabular}{lllll}
\hline\noalign{\smallskip}
& precision & recall & f1-score & no. samples \\
\noalign{\smallskip}\hline\noalign{\smallskip}
class H & 0.759 & 0.683 & 0.719 & 120\\
class P & 0.712 & 0.783 & 0.746 & 120\\
\noalign{\smallskip}\hline\noalign{\smallskip}
avg. / total & 0.736 & 0.733 & \textbf{0.733} & 240 \\
\noalign{\smallskip}\hline
\end{tabular}
\end{table}

Regarding deep learning approach, we used the adjusted DenseNet~\cite{huang2016densely} architecture with the binary cross-entropy loss optimized using Adam optimizer \cite{Kingma2014}. The initial learning rate was set to $0.01$ with decay of $1\textrm{e}-04$ on each epoch. Hyper-parameter optimization was done using training and validation sets, and the final parameters of the DenseNet network were set as follows: depth ($4$), number of dense blocks ($2$), growth rate ($5$), number of filters ($10$), drop-out rate ($0.3$), l2~weight decay ($1\textrm{e}-04$). The input shape of this network was $(13 \times 47)$ with one neuron in the last layer with sigmoid activation function, and the total of $1\,629$ trainable parameters. For this particular setup with MFCC as the input data, the system yielded F1 score of $0.595$ on the training set, and $0.648$ on the validation set. After the hyper-parameter optimization, we retrained the network on all data from the training and validation sets (the development set), and the system yielded the final F1 score on the dedicated testing set of $0.621$. Performance details (classification matrix and classification report) can be found in Table\,\ref{tab:densenetconf} and Table\,\ref{tab:densenetreport}.

\begin{table}[tb!]
\caption{XGBoost performance related to input data}
\label{tab:xgboostinputdata}
\begin{tabular}{llll}
\hline\noalign{\smallskip}
Input data & F1 CV train & F1 CV valid & F1 test \\
\noalign{\smallskip}\hline\noalign{\smallskip}
ALL 		& $0.922\,(\pm\,0.004)$ & $0.829\,(\pm\,0.028)$ & \textbf{$0.733$}\\
AF stats 	& $0.886\,(\pm\,0.004)$ & $0.791\,(\pm\,0.034)$ & $0.686$\\
AF			& $0.892\,(\pm\,0.006)$ & $0.798\,(\pm\,0.025)$ & $0.658$\\
AF base 	& $0.745\,(\pm\,0.009)$ & $0.689\,(\pm\,0.036)$ & $0.646$\\
MFCC		& $0.680\,(\pm\,0.010)$ & $0.769\,(\pm\,0.037)$ & $0.623$\\
\noalign{\smallskip}\hline\noalign{\smallskip}
\end{tabular}

\vspace{0.5em}
Table notation and description of acoustic features used to build XGBoost model: MFCC\,--\,26 Mel Frequency Spectral Coefficients (13 means \& 13 standard deviations), AF base\,--\,12 common acoustic (dysphonic) features, AF stats.\,--\,84 acoustic features' statistics, AF\,--\, AF base \& AF stats, ALL\,--\, AF \& MFCC.
\end{table}

DenseNet trained with spectrograms had input shape $(46 \times 25)$ and total of $301$ trainable parameters. Even though this setup was considerably less complex, and regularized with drop-out ($0.3$) and l2~weight decay ($1\textrm{e}-04$), the network tended to over-fit after enough training epochs, which we prevented using early stopping that monitored changes in the validation accuracy. This system yielded F1 score of $0.635$ and $0.531$ on the training and validation sets, respectively. The performance on the testing set was $0.562$ (F1 score $0.514$ for class H and $0.609$ for class P). After refitting on the whole development set, the final F1 score got worse on the dedicated testing set to $0.460$ due to difficulties with classification of healthy voices (F1 score $0.239$ for class H and $0.680$ for class P). With raw input data, the network failed to learn any meaningful features (the size of out training dataset is still too small to provide deep learning algorithm to overcome more conventional approaches).

Hyper-parameter optimization for Isolation Forest trained (10-fold validation) with $96$ speech parameters was done the same way as for XGBoost. The best parameters selected upon performance on the development set were as follows: number of estimators ($200$), contamination ($0.4$), maximum features ($0.3$), maximum samples was set to ``auto''. The system yielded F1 score of $0.576\,(\pm\,0.005)$ on the training set and $0.578\,(\pm\,0.023)$ on the validation set. The final F1 score on the dedicated testing set was $0.610$. The performance details (classification matrix and classification report) can be found in Table\,\ref{tab:isolfconf} and Table\,\ref{tab:isolfreport}. This system showed to be sensitive to the number of input features and the performance raised when we selected just a~subset of them.

\begin{table}[htb!]
\caption{Testing CM for DenseNet (MFCC)}
\label{tab:densenetconf}
	\begin{tabular}{p{2.6cm} l l l}
		\hline\noalign{\smallskip}
			& true H & true P & total predicted \\
		\noalign{\smallskip}\hline\noalign{\smallskip}
		predicted H & \textbf{73} & 44 & 117\\
		predicted P & 47 & \textbf{76} & 123\\
		\noalign{\smallskip}\hline\noalign{\smallskip}
		total true & 120 & 120 & accuracy: \textbf{0.621}\\
		\noalign{\smallskip}\hline
	\end{tabular}
\end{table}

\begin{table}[htb!]
\caption{Testing CR for DenseNet (MFCC)}
\label{tab:densenetreport}
\begin{tabular}{lllll}
\hline\noalign{\smallskip}
& precision & recall & f1-score & no. samples \\
\noalign{\smallskip}\hline\noalign{\smallskip}
class H & 0.624 & 0.608 & 0.616 & 120\\
class P & 0.618 & 0.633 & 0.626 & 120\\
\noalign{\smallskip}\hline\noalign{\smallskip}
avg. / total & 0.621 & 0.621 & \textbf{0.621} & 240 \\
\noalign{\smallskip}\hline
\end{tabular}
\end{table}

\begin{table}[htb!]
\caption{Testing CM for Isolation Forest}
\label{tab:isolfconf}
\begin{tabular}{p{2.6cm} l l l}
\hline\noalign{\smallskip}
  & true H & true P & total predicted \\
\noalign{\smallskip}\hline\noalign{\smallskip}
predicted H & \textbf{58} & 30 & 88\\
predicted P & 62 & \textbf{90} & 152\\
\noalign{\smallskip}\hline\noalign{\smallskip}
total true & 120 & 120 & accuracy: \textbf{0.617}\\
\noalign{\smallskip}\hline
\end{tabular}
\end{table}

\begin{table}[htb!]
\caption{Testing CR for Isolation Forest}
\label{tab:isolfreport}
\begin{tabular}{lllll}
\hline\noalign{\smallskip}
  & precision & recall & f1-score & no. samples \\
\noalign{\smallskip}\hline\noalign{\smallskip}
class H & 0.659 & 0.483 & 0.558 & 120\\
class P & 0.592 & 0.750 & 0.662 & 120\\
\noalign{\smallskip}\hline\noalign{\smallskip}
avg. / total & 0.626 & 0.617 & \textbf{0.610} & 240 \\
\noalign{\smallskip}\hline
\end{tabular}
\end{table}

\section{Conclusions}
\label{conclusions}

In search towards robust voice pathology detection system using acoustic (voice) signals, researchers face a~variety of problems. One of the major problems in this field of science is the limited number of available databases. Moreover, commonly used databases~\cite{eye1994voice,Muhammad2017A,mesallam2017development,godino2010pathological} are very hard to combine because of various distinctions such as: a) the databases are labeled in different languages, b) the databases do not comprise same set of speech tasks, c) there is a~variety of voice pathologies unequally distributed across the databases, etc. For these reasons, researchers have used only a~subset of the databases for their experiments providing results related to those carefully selected subset of data. However, this approach limits the possibilities of creating a~robust voice pathology detector. Therefore, in this work, we have conducted experiments on recordings of sustained phonation of the vowel /a/ produced at normal pitch from 4~different databases trying to eliminate those limitation. To the best of our knowledge, this is the first work that uses such a~large set of data to build mathematical models for computerized, objective voice pathology detection.

We researched 3~distinct classifiers within supervised learning and anomaly detection paradigms. We have explored raw waveforms, spectrograms, MFCC and conventional dysphonic features as input data. All experiments were evaluated by the same criteria on the same dedicated testing set. We observed that XGBoost classifier achieved the best results amongst DenseNet and Isolation Forest classifiers. We also observed that not only XGBoost provided the best performance, it could also handle the feature selection (input: all features) by itself in contrary to Isolation Forest classifier, which showed to be sensitive on the feature selection (input: manually selected subset of features). Overall advantage of using speech features and MFCC with XGBoost was the computation speed that allowed us to use exhaustive randomized cross-validated search to optimize the hyper-parameters, as well as the possibility to sort features by importance. This property is useful for clinical interpretability. Nevertheless, we consider these results exploratory due to the limitations of the databases. Reviewing the performances achieved in scenarios with MFCC as input data we conclude that MFCC alone are not reliable enough for robust voice pathology detection, which was also concluded by Ali et al. in~\cite{ali2017intra}. Regarding the DenseNet, we conclude that in voice pathology detection scenarios with this little training data it is better to use inputs with reduced dimensionality in contrary to raw waveform inputs, or make use of transfer learning or data augmentation.

In this article there are several limitations. Firstly, there are limitations inherited from the databases along with new limitations caused by their combination. For instance, some databases have extremely unequal distribution of healthy and pathological classes, most of the databases have alarming inequalities between the number of samples per pathology type (e.g. many pathologies are present less than 3~times in the database), see Figures~\ref{fig:avpd} (AVPD),~\ref{fig:meei} (MEEI),~\ref{fig:pda} (PDA), and~\ref{fig:svd} (SVD). Most databases have no information about severity of the pathology, nor they have information about manifestation of the pathology in phonation, which means that some of the samples might sound as healthy even though they are labelled as pathological and vice versa. Not to mention that recordings are labelled with more than 1~type of pathology, and in different languages, which makes it especially hard to combine or exclude the samples. Since we used 4~available databases, we utilized only the speech task available in all of them: sustained phonation of the vowel /a/ produced at normal pitch. Secondly, even though we have taken countermeasures to balance the classes with sample weights, we did not conduct our experiments separately on subsets of data for different genders.

Up to this point, most papers focused on voice pathology detection used conventional dysphonic features to quantify the underlying voice pathology. In general, these features are conceptually simple, which on one hand is an advantage as these features are clinically interpretable (i.e. clinicians are able to associate the values of the features with known physiological phenomena inside human body)~\cite{Smekal2015b}, but on the other hand these features are often unable to describe the exact voice pathology under focus in a more complex way, especially in advanced stages of the disease (high level of acoustic noise, irregularity of voice, etc.). In future studies, researchers may consider exploring usage of a~more sophisticated set of acoustic features to complexly and robustly describe the voice and speech production deterioration. For instance, such features have already been successfully applied in the field of non-invasive assessment of Parkinson's disease~\cite{Little2009,Tsanas2010,Smekal2015c}.

With the previously mentioned facts in mind, we think that recordings of the databases commonly used for automatic voice pathology detection should be consulted with clinicians to evaluate the severity of vocal manifestation of the present pathologies. There are standard metrics, which are used to evaluate the quality of voice that can be used for this purpose~\cite{de1997test,Gerratt1993,Kreiman1993,de1997test,Dejonckere2001}. Addition of such information to the databases could provide researchers with a~unique possibility to build models capable of classification and prediction emphasizing the severity of the exact vocal-manifestation (increased acoustic tremor, roughness, breathiness, etc.) of these pathologies.

We also anticipate that deep learning will play its role in robust voice pathology detection on the assumption that more data will be available, or at least reasonable combination of available databases will be made and limitations of these databases will be partially diminished by data augmentation and other countermeasures. In addition, we presume that use of deep learning methods for novelty detection such as deep autoencoder~\cite{pimentel2014review} for modelling the normophonic voice could be an interesting idea for future investigation with prospect to identify even disordered voices that are sparsely distributed across databases.

In summary, acoustic (voice) signals can nowadays be recorded using a~variety of smart devices and processed remotely using modern cloud technologies. In comparison with the conventional perceptual voice quality examination, computerized acoustic analysis of voice signals can provide clinicians with fast, supportive methodology of objective voice pathology detection, assessment, and monitoring that can be used on everyday basis (see Health 4.0). However, to take advantage of such methodology, robust mathematical models capable of precise voice pathology detection must be introduced. Our work proposes the next step towards this goal using various state-of-the-art machine learning algorithms applied to the largest dataset that have been used for the purpose of automatic voice pathology detection.

\begin{acknowledgements}
This study was funded by the grant of the Czech Ministry of Health 16-30805A (Effects of non-invasive brain stimulation on hypokinetic dysarthria, micrographia, and brain plasticity in patients with Parkinson's disease) and the following projects: SIX (CZ.1.05/2.1.00/03.0072), and LO1401. For the research, infrastructure of the SIX Center was used. The authors (P. Harar, Z. Galaz) of this study also acknowledge the financial support of Erwin Schr\"{o}dinger International Institute for Mathematics and Physics during their stay at the "Systematic approaches to deep learning methods for audio" workshop held from September 11, 2017 to September 15, 2017 in Vienna.\\
\end{acknowledgements}

{\small
\noindent
\textbf{Compliance with Ethical Standards}\ \
}

\vspace{1em}

{\small
\noindent
\textbf{Conflict of Interest}\ \ The authors declare that they have no conflict of interest.
}

\bibliographystyle{spmpsci}


\section{Introduction}

Explaining the mass of a hadron  from the  underlying QCD dynamics is one of the fundamental problems in QCD\cite{Wilczek:1999be,Wilczek:2012sb}.
The phenomenological success of constituent quark model or effective chiral models   lead us to believe that spontaneous chiral symmetry breaking\cite{Nambu:1961tp,Nambu:1961fr} is partly responsible for generating hadron masses \cite{Hatsuda:1985eb,Brown:1991kk,Hatsuda:1991ez,Leupold:2009kz}.

As a means to understand the origin of hadron mass, experiments have been performed worldwide to observe mass shift of hadrons at finite temperature or density \cite{Hayano:2008vn,Metag:2017yuh,Ichikawa:2018woh}.
This is so because the initial condition at heavy ion collision is expected to probe the quark-gluon plasma phase where chiral symmetry is expected to be restored.  Furthermore, nuclear target experiments can probe the nuclear matter environment, where the order parameter is known to decease by almost 30$\%$.  Hence, measuring the property change of hadron related to chiral symmetry restoration effects is one of the future aims at  Hadron physics program at J-PARC\cite{Ohnishi:2019cif} and heavy ion programs world wide\cite{Salabura:2020tou}.

The mass difference between the chiral partners are known to be due to the chiral symmetry breaking\cite{Weinberg:1967kj}.
Hence, if chiral symmetry is restored, the mass difference between chiral partners should vanish.  For example, the $K^*$ and $K_1$ meson masses will  become degenerate if chiral symmetry gets restored, which could be observed due to their small vacuum width\cite{Song:2018plu,Lee:2019tvt}.
However, with confinement phenomena and scale breaking in QCD\cite{Collins:1976yq}, how much of the total hadron mass comes from chiral symmetry breaking is still far from being understood.

In the original in-medium QCD sum rules for the light vector mesons\cite{Hatsuda:1991ez},
the changes of the masses were dominantly due to the change of the  four-quark condensate, whose medium expectation value was extracted under the so called vacuum saturation hypothesis so that it is proportional to the square of the quark condensate\cite{Shifman:1978bx}.  Hence, in this approximation, the four quark condensate vanishes if the quark condensate vanishes leading to a small vector meson mass sustained only by the small contribution from the gluon condensate.
However, it is not clear if all the four quark operators vanish if chiral symmetry is restored as only the difference between the four quark operators appearing in the vector and axial vector meson sum rule is an order parameter of chiral symmetry breaking.

Models for the vector mesons based on chiral symmetry satisfy the Weinberg type relation for the vector and axial vector meson mass.  But the common mass has to be assumed and it is not clear how that part changes when chiral symmetry is restored.  The question of whether chiral symmetry breaking is the origin of the hadron mass can be answered by isolating the chiral symmetry breaking effects in the vacuum.  In the past, a similar question has been addressed using the lattice gauge theory, where the hadronic correlation functions have been studied after the  lattice cooling process\cite{Chu:1994vi} that eleminated the short distance Coulomb and confinement physics.

In this work, we calculate the mass of the vector and axial vector meson mass
in the chiral symmetry restored vacuum.  This is accomplished by identifying the chiral symmetric and breaking part of the four quark operators through their dependencies on the fermion zero mode\cite{BC} and then estimating their magnitudes by fitting to the vector and axial vector meson mass via QCD sum rule method.
Applying the QCD sum rule approach when the chiral symmetry breaking operator is taken to be zero while keeping  the chiral symmetric four quark operator to its vacuum value, we find that that the vector meson mass  becomes  about 550 to  600 MeV.
Our result suggest that chiral symmetry breaking is responsible for the mass difference between chiral partners but has only a small contribution to the common vector and axial vector meson mass.

{\it Operator product expansion (OPE) for vector and axial vector current: }
The commonly known chiral order parameter can be rewritten in several forms.
\begin{eqnarray}
\langle \bar{q} q \rangle &  = &  \lim_{x \rightarrow 0}
- \frac{1}{2} \langle {\rm Tr} [ S(0,x)- i\gamma_5  S(0,x) i \gamma_5 ] ] \rangle  \nonumber \\
&  = & -\pi \langle \rho(\lambda=0) \rangle,
\label{BC-0}
\end{eqnarray}
where the second line shows the density of zero eigenvalue in the Euclidean formalism known as the Banks-Casher formula\cite{BC}.
The formula is useful as it identifies the origin of chiral symmetry breaking, and further can be used to isolate the chiral symmetry breaking part of any quark operator: a set of order parameters  can be obtained by looking at the difference in the four quark operators\cite{Cohen:1996ng,Lee:2019tvt}.

In the two point correlation functions of the vector current $J^\rho_\mu =\bar{q} \tau^3 \gamma_\mu q$ and the axial vector current $J^{a_1}_\mu =\bar{q} \tau^3 \gamma_\mu \gamma^5 q$ current, the relevant matrix elements of dimension 6 operators contributing as ${\cal M}/Q^6$ to the transverse part of the correlation function $\Pi=\Pi_\mu^\mu/(-3q^2)$, in the SU(2) flavor limit, are respectively given for the $\rho$ and $a_1$ channel as\cite{Shifman:1978bx}
\begin{eqnarray}
{\cal M}_\rho  & = & - 2 \pi \alpha_s
\langle ( \bar{q} \gamma_\mu \gamma^5 \lambda^a \tau^3 q )^2 \rangle
\nonumber \\
&&
-\frac{4 \pi \alpha_s}{9}
\langle (\sum_{ud} \bar{q} \gamma_\mu \lambda^a  q )(\sum_{uds} \bar{q} \gamma_\mu \lambda^a  q ) \rangle,
\label{rho} \\
{\cal M}_{a_1} & =  & -
2 \pi \alpha_s
\langle ( \bar{q} \gamma_\mu  \lambda^a \tau^3 q )^2 \rangle
\nonumber \\
&&
- \frac{4 \pi \alpha_s}{9}
\langle (\sum_{ud} \bar{q} \gamma_\mu \lambda^a  q )(\sum_{uds} \bar{q} \gamma_\mu \lambda^a  q ) \rangle .
\label{a1}
\end{eqnarray}

For the first operators appearing in both channels, one can define the following operators
\begin{eqnarray}
\langle ( \bar{q} \gamma_\mu \gamma^5 \lambda^a \tau^3 q )^2 \rangle_{S,B}  =
\frac{1}{2}
\langle ( \bar{q} \gamma_\mu \gamma^5 \lambda^a \tau^3 q )^2
\pm ( \bar{q} \gamma_\mu  \lambda^a \tau^3 q )^2 \rangle,
\nonumber  \\
\langle ( \bar{q} \gamma_\mu  \lambda^a \tau^3 q )^2 \rangle_{S,B}  =
\frac{1}{2}
\langle ( \bar{q} \gamma_\mu  \lambda^a \tau^3 q )^2
\pm ( \bar{q} \gamma_\mu \gamma^5 \lambda^a \tau^3 q )^2 \rangle,
\nonumber  \\ \label{decomposition}
\end{eqnarray}
where the subscript $S,B$ refers to chiral symmetric and breaking operators.  The fermion zero modes only contribute to the chiral symmetry breaking operator, which therefore constitute a chiral order parameter.

As for the last operators appearing in Eq.~(\ref{rho}) and in Eq.~(\ref{a1}), one notes that they are identical.  Furthermore, performing chiral symmetry transformation would leave the operator invariant.  However, spontaneous chiral symmetry will introduce non-vanishing contribution to the expectation value of this operator.  This is so because the zero modes contributes to this operator.
Keeping this in mind, we rewrite the non-strangeness part as
\begin{eqnarray}
\langle ( \bar{q} \gamma_\mu \lambda^a  q )^2 \rangle  & = &
\langle ( \bar{q} \gamma_\mu \lambda^a  q )^2 \rangle_d
+  \langle ( \bar{q} \gamma_\mu \lambda^a \tau^3 q )^2 \rangle,
\label{singlet-four}
\end{eqnarray}
where $
\langle ( \bar{q} \gamma_\mu \lambda^a  q )^2 \rangle_d =
\langle ( \bar{q} \gamma_\mu \lambda^a  q )^2 \rangle- \langle ( \bar{q} \gamma_\mu \lambda^a \tau^3 q )^2 \rangle $ represents the disconnected contribution with no contribution from the fermion zero mode.
Here, $q$ runs over the $(u,d)$ quarks.     Eq.~(\ref{decomposition}) can be used in the last term of  Eq.~(\ref{singlet-four}) to extract the chiral symmetry breaking part.

Hence, we can rewrite the dimension 6 contributions as
\begin{eqnarray}
{\cal M}_\rho & =  &
\frac{14  }{9} B + S,
 \nonumber \\
{\cal M}_{a_1} & =  &
-\frac{22  }{9} B+   S,
\end{eqnarray}
where
\begin{eqnarray}
B &  = &  -
\pi \alpha_s  \langle ( \bar{q} \gamma_\mu \gamma^5 \lambda^a \tau^3 q )^2 \rangle_B  \nonumber \\
S & = & -
\frac{22 \pi \alpha_s}{9} \langle ( \bar{q} \gamma_\mu \gamma^5 \lambda^a \tau^3 q )^2 \rangle_S   \nonumber \\
&& - \frac{4 \pi \alpha_s}{9} \bigg(
 \langle ( \bar{q} \gamma_\mu  \lambda^a  q )^2 \rangle_d  + \langle
 ( \bar{q} \gamma_\mu  \lambda^a  q )( \bar{s} \gamma_\mu  \lambda^a  s )
 \rangle_S  \bigg).
\label{BS}
\end{eqnarray}
The ferimon zero mode only contributes in $B$ making it a chiral symmetry breaking operator.  The operators in  $S$ are chiral symmetric operators.
One notes that the chiral symmetric operators are identical in the $\rho,a_1$ sum rule, while the chiral symmetry breaking operator contribute with different sign and coefficients.  This is expected as the chiral symmetry breaking operator $B$ is responsible for the $\rho-a_1$ difference, while the symmetric operators $S$ contribute universally to both sum rules. We will now use the QCD sum rule for $\rho$ and $a_1$ to determine the magnitude of both operators $B$ and $S$.

{\it Sum rule analysis}
One starts with the Borel transformed dispersion relation for the invariant part of the correlation function
\begin{eqnarray}
\widehat{\Pi}(M^2) = \int_{0}^{\infty} ds e^{-s/M^2} \rho(s),
\label{sum_rules}
\end{eqnarray}
where $\widehat{\Pi}(M^2)$ represents the Borel transformed OPE  of the correlator $\Pi$ and $M$ stands for the Borel mass.  $\rho(s)$ is the spectral function for either the $\rho$ or $a_1$ meson.
We will take the spectral function to have the following pole and continuum contribution
\begin{eqnarray}
\rho^{\mathrm{pole}}(s) &=& \frac{1}{\pi}
\frac{f \Gamma \sqrt{s}}{(s - m^2)^2 + s\Gamma^2},  \label{pheno_side_pole}
\\
\rho^{\mathrm{cont}}(s) &=& \frac{1}{\pi} \theta(s - s_0) \mathrm{Im} \tilde{\Pi}^{\mathrm{pert}}(s).
\label{pheno_side_2}
\end{eqnarray}
We substitute the spectral density into Eq.~(\ref{sum_rules}) and take the OPE up to dimension 6 operators.  We then take the ratio of the pole contribution to its derivative with respect to the inverse Borel mass to eliminate the dependence on $f$. For the $a_1$ meson sum rule, we take further derivative to eliminate the pion contribution\cite{Hatsuda:1992bv}. We can then obtain sum rules for the four quark condensate for the $\rho$ and $a_1$ meson. Normalized to the vacuum saturation hypothesis, we find
\begin{widetext}
\begin{eqnarray}
\kappa_\rho & = &  \bigg[ I^{(1)} \bigg( (1+\frac{\alpha_s}{\pi})E_0+ \frac{a+b}{M^4} \bigg) -I^{(0)}\bigg( (1+\frac{\alpha_s}{\pi})E_1 M^2- \frac{a+b}{M^2} \bigg) \bigg] \times \bigg[ 2I^{(0)}\frac{d_\rho}{M^4} + I^{(1)}\frac{d_\rho}{M^6} \bigg]^{-1}
\nonumber \\
\kappa_{a_1} & = & \bigg[ -2 I^{(1)} \bigg( (1+\frac{\alpha_s}{\pi})E_2M^2 \bigg) + I^{(2)}\bigg( (1+\frac{\alpha_s}{\pi})E_1 - \frac{-a+b}{M^4} \bigg) \bigg] \times \bigg[ 2I^{(2)}\frac{d_{a_1}}{M^6} + 2I^{(1)}\frac{d_{a_1}}{M^4} \bigg]^{-1} , \label{kappa-sumrule}
\end{eqnarray}
\end{widetext}
where
\begin{eqnarray}
I^{(n)} & = &\int_{4 m_\pi^2}^{s_0} \rho^{\rm pole} (s) s^n ds, \nonumber
\\
E_{n} &=& 1 - e^{-s_{0}/M^{2}}\sum_{k=0}^{n}\frac{1}{k!}\bigg(\frac{s_{0}}{M^{2}}\bigg)^{k}
\end{eqnarray}
and
$a=8\pi m_q \langle \bar{u}u \rangle$, $
b=\frac{\pi^3}{3} \langle \frac{\alpha_s}{\pi} G^2 \rangle$, $d_\rho=\frac{448 \pi^2 \alpha_s}{81 } \langle \bar{u}u \rangle^2$ and $d_{a_1}=\frac{704 \pi^2 \alpha_s}{81 } \langle \bar{u}u \rangle^2 $, $\alpha_{s} = 0.36$, $\langle \bar{u}u \rangle = (-0.23\; \text{GeV})^{3}$ and $\langle \frac{\alpha_{s}}{\pi} G^{2}  \rangle =  (0.35 \; \text{GeV})^{4}$.  It should be noted that although we use the vacuum saturation for the purpose of normalization, we are calculating the total value of the four quark condensates without any approximation through the $\kappa$ factors.  The  need of an effective $\kappa$ factor that is larger than 1 to correctly obtain the  $\rho$ meson mass in QCD sum rules was noticed previously in Ref. \cite{Klingl:1997kf}.

We substitute the physical meson masses and analyze the sum rule within the acceptable Borel mass range.   The lower boundary of the Borel window, $M_{\mathrm{min}}$, is determined from the condition of sufficient convergence of the OPE in Eq. ~(\ref{sum_rules}),
namely
\begin{eqnarray}
\frac{\widehat{\Pi}^{\mathrm{OPE}}_{\mathrm{cond\,terms}}(M^2)}{ \widehat{\Pi}^{\mathrm{OPE}}_{\mathrm{pert\,terms}}(M^2) } < 0.15.
\label{Borel_window_1}
\end{eqnarray}
Here, $\widehat{\Pi}^{\mathrm{OPE}}_{\mathrm{cond\,terms}}(M^2)$ is the sum of the condensate terms considered, while the denominator is the perturbative term only.  For the upper boundary, $M_{\mathrm{max}}$,
we employ the condition that the pole contribution in the integral of Eq.\,(\ref{sum_rules}) should be sufficiently large in the sum rule.
\begin{eqnarray}
\frac{  \int_{0}^{s_0} ds e^{-s/M^2} \rho(s)  }{ \int_{0}^{\infty} ds e^{-s/M^2} \rho^{OPE}(s) }
 > 0.3,
\label{Borel_window_2}
\end{eqnarray}
where the denominator is the total OPE contribution.
The threshold is determined to obtain the most stable Borel curve.

\begin{figure}[h]
\centerline{
\includegraphics[width=9 cm]{kappa1.eps}}
\caption{(Color online) Values of the four quark condensate in the $\rho$ and $a_1$ meson channel normalized to the vacuum saturation value.}
\label{kappa}
\end{figure}

\begin{figure}[h]
\centerline{
\includegraphics[width=9 cm]{rho-a1-pole-mass.eps}}
\caption{(Color online)  Borel curves for the mass of $\rho$ and $a_1$ meson with zero and non-zero width using the corresponding $\kappa$ values.}
\label{rho-a1-pole}
\end{figure}

Fig.~(\ref{kappa}) shows the $\kappa$ values in Eq.~(\ref{kappa-sumrule}).  The Borel windows are identified with solid lines with symbols.  The sum rule with a delta function pole, where the widths are taken to be zero (labeled $\delta$), are marked by open square symbols. The times symbols are for $\rho$ width of 150 MeV (labeled B-W) , while the diamond and triangle are for $a_1$ width of 200 (B-W$^1$) and 400 MeV (B-W$^2$), respectively.   Taking the $\kappa$ values at the extremum point, one notes that the values for the $\rho$ meson are systematically larger than those for $a_1$ meson, suggesting that the vacuum saturation is violated and that there are large contributions coming from the chiral symmetric operators.
The different approximations are taken to asses the degree of uncertainty in our final result for the mass in the chiral symmetric vacuum.

\begin{figure}[h]
\centerline{
\includegraphics[width=9 cm]{mass1.eps}}
\caption{(Color online) Borel curves for the mass of the $\rho$ and $a_1$ meson in the vaccum (square) and when the chiral symmetry broken matrix element $B$ is reduced to 70\% (circle) and 0\% (star) of its vacuum value.}
\label{mass}
\end{figure}

Using these four quark condensate values, one can verify that the  corresponding Borel curve for the masses well reproduces the vacuum values.
In the lines with solid boxes in Fig.~(\ref{rho-a1-pole}), we show the masses when the delta function approximation is taken for the poles  and their corresponding $\kappa$ values are used.  The curves with the Breit-Winger type pole contributions with the corresponding $\kappa$ values give equally good Borel curves for the masses as shown in Fig.~(\ref{rho-a1-pole}) with different symbols.  In fact, one could have used the most stable Borel curves for the masses to extract the $\kappa$ values,  with which one finds similar results.
Table \ref{table1} summarizes the $\kappa$ values and the corresponding threshold parameters in the brackets.  Also given are the matrix elements defined in Eqs.~(\ref{rho}),(\ref{a1}) and (\ref{BS}).

We finally show  in Fig.~(\ref{mass}), the Borel curve for the masses when we take $S$ to be the same as its vacuum value but take the chiral symmetry broken four quark condensate  $B$  to be 70\% (open circle) and  0\% (star) of its vacuum value in the delta function approximation with the threshold values of 1.12 and 0.75 GeV$^2$, respectively.  As expected, the masses of the $\rho$ and $a_1$ decrease and eventually become degenerate at around 550 MeV.
The mass at the chiral symmetry restored limit using parameter obtained with  physical widths are given in the  last column in Table. \ref{table1}.  The threshold values at the symmetric limit are 0.89 and 0.93 GeV$^2$ in the second and third row.
When we use the $\kappa$ values obtained with non-zero widths labeled B-W$^1$ and B-W$^2$ but use the delta function ansatz for the $\rho$ pole, we find the chiral symmetric mass to be 570 and 590 MeV, respectively.  The last approximation is reasonable because when chiral symmetry is restored, the pions will become massive and restrict the phase space of the vacuum decay of both the $\rho$ and $a_1$.
For all cases, one notes that the mass of vector meson in the chiral symmetry restored vacuum lies between 550 and 600 MeV.

Our result, explicitly demonstrates the merging of the vector and axial vector meson mass to an  universal non vanishing value when the chiral symmetry breaking effects are restored in the vacuum.  Therefore, one can conclude that while the mass difference between chiral partners are coming from chiral symmetry breaking, the bulk part of the common mass has other non-perturbative origin.

\begin{widetext}
\begin{center}
\begin{table}[htbp]
\begin{tabular}{c c c c c c c c} \hline
	\hline
	Pole & $\kappa_{\rho}\, (s_{0})$& $\kappa_{a_{1}}\, (s_{0})$& $\mathcal{M}_{\rho}(\text{GeV}^{6})$ &$\mathcal{M}_{a_{1}}(\text{GeV}^{6})$ & $B\,(\text{GeV}^{6})$ & $S\,(\text{GeV}^{6})$ & $m_{sym}$(MeV) 	\\
	\hline
	$\delta$ & 2.1(1.31)  & 0.97(2.38) & $1.72\times 10^{-3}$ & $ -1.25 \times 10^{-3}$ & $7.42 \times 10^{-4}$ & $5.65 \times 10^{-4}$ & 550 \\
	B-W$^{1}$ & 1.96(1.38) & 0.75(2.48) & $1.60\times 10^{-3}$ & $-0.96\times 10^{-3}$ & $6.42 \times 10^{-4}$ & $6.05 \times 10^{-4}$ & 580
	\\
	B-W$^{2}$ & 1.96(1.38) & 0.54(2.5) & $1.60 \times 10^{-3}$ & $-0.69\times 10^{-3} $ & $5.75 \times 10^{-4}$ & $7.11 \times 10^{-4}$ & 600   \\
	\hline
\end{tabular}
\caption{The four quark operators for $(\Gamma_\rho, \Gamma_{a_1})=$(0,0), (150,200)MeV  and (150,400)MeV for rows labeled ($\delta$), (B-W$^{1}$) and (B-W$^{2}$), respectively.
The last column represents the mass in the chiral symmetric vacuum obtained with $B=0$.
Units for threshold $s_0$ is in GeV$^2$. }
\label{table1}
\end{table}
\end{center}
\end{widetext}

\section*{Acknowledgements}

This work was supported by  by Samsung Science and Technology Foundation under Project Number SSTF-BA1901-04.