extfieldsofstudy:
Computer Science
Medicine

text:
Additional Neural Matrix Factorization model for computational drug repositioning

Background Computational drug repositioning, which aims to find new applications for existing drugs, is gaining more attention from the pharmaceutical companies due to its low attrition rate, reduced cost, and shorter timelines for novel drug discovery. Nowadays, a growing number of researchers are utilizing the concept of recommendation systems to answer the question of drug repositioning. Nevertheless, there still lie some challenges to be addressed: 1) Learning ability deficiencies; the adopted model cannot learn a higher level of drug-disease associations from the data. 2) Data sparseness limits the generalization ability of the model. 3)Model is easy to overfit if the effect of negative samples is not taken into consideration. Results In this study, we propose a novel method for computational drug repositioning, Additional Neural Matrix Factorization (ANMF). The ANMF model makes use of drug-drug similarities and disease-disease similarities to enhance the representation information of drugs and diseases in order to overcome the matter of data sparsity. By means of a variant version of the autoencoder, we were able to uncover the hidden features of both drugs and diseases. The extracted hidden features will then participate in a collaborative filtering process by incorporating the Generalized Matrix Factorization (GMF) method, which will ultimately give birth to a model with a stronger learning ability. Finally, negative sampling techniques are employed to strengthen the training set in order to minimize the likelihood of model overfitting. The experimental results on the Gottlieb and Cdataset datasets show that the performance of the ANMF model outperforms state-of-the-art methods. Conclusions Through performance on two real-world datasets, we believe that the proposed model will certainly play a role in answering to the major challenge in drug repositioning, which lies in predicting and choosing new therapeutic indications to prospectively test for a drug of interest.

Background
Traditional new drug design and discovery are an expensive, time-consuming and high-risk process. For instance, it takes at least 10-15 years, and an estimated budget of 8-10 billion dollars to develop and bring a new drug to the market [1,2]. Since the 1990s, the annual quota of new drugs approved by the US Food and Drug Administration (FDA) has been declining. Meanwhile, biopharmaceutical companies continue to increase their investments in new drug design and discovery [3], which implies that new drugs are becoming more and more expensive. And drugs designed for specific targets often have unperceivable side *Correspondence: jieyuehe@seu.edu.cn School of Computer Science and Engineering, Key Lab of Computer Network & Information Integration, MOE, Southeast University, 210018 Nanjing, China effects, about 90% of experimental drugs fail to pass the first phase of clinical trials [4]. The process of developing innovative drugs remains expensive, time-consuming and full of uncertainty. In light of these challenges, Computational drug repositioning, which aims to find new uses and applications for existing drugs, has become an alternative for the traditional new drug discovery. The drugs approved for sale, which has undergone several rigorous clinical trials are ensured to be safe as they already passed laborious assessments for any unpleasant side effects [5]. Hence, drugs designed according to the new applications are more likely to pass the screening of regulatory authorities [6].
The core of computational drug repositioning is to mine new uses of existing drugs, and treat diseases that are not within its original design. Drug repositioning begins with an accidental discovery of new applications of the original drug. Taking thalidomide as an example [5], the drug was first used as a sedative in Germany, marketed in the United Kingdom as a treatment to nausea and insomnia, and it is also used to relieve pregnancy reactions among pregnant women. First listed in 1956 and banned in 1962, the reintegration of thalidomide again as a drug is attributed to the accidental discovery that it can be used to treat leprosy nodular erythema. Cases of drugs like thalidomide reflect the fact that a single medication can treat multiple diseases. As an essential technology to discover new applications of old drugs, and an efficient way to improve R&D productivity, computational drug repositioning has been receiving a great deal of attention from the biotech and pharmaceutical industries.
In recent years, researchers have explored a variety of computational drug repositioning approaches, such as graph-based methods, matrix factorization based methods, Collaborative filtering etc. In relevance to our inspiration for the presented work in this paper, we will give a broad research overview for related work in the area of computational drug repositioning. The aim is to further clarify the research standing of the proposed model, and showcase our initial setup motivations.
Graph-based models are considered to be the cornerstone of the search recommendation area, used in many fields, such as social networks and search engines to name a few. Based on the provided information, the graph model first constructs a connection diagram between research objects according to certain rules. This diagram can be a directed or undirected graph. In drug repositioning problem, there are at least two types of nodes, drug nodes and disease nodes. The graph model constructs a drug-disease network according to the therapeutic relationships between drugs and diseases. Selecting the appropriate strategy used to estimate the associations is key to the success of the graph model, such as recent distance, public neighbors and other approaches. Li et al. [7] proposed a method based on the "guilt-byassociation" notion, which uses all known proteins and drugs to construct nodes-and edges-weighted biological relevant interactome network. The novel network topology features are proposed to characterize interaction pairs, and random forest algorithm is employed to identify potential drug-protein interaction. Chen et al. [8] proposed a method, under the hypothesis that similar drugs often target similar target proteins and the framework of random walk, to predict potential drug-target interactions on a large scale. Wang et al. [9] proposed a method named Heterogeneous Graph Based Inference (HGBI). A heterogeneous drug-target graph, which incorporates known drug-target interactions as well as drug-drug and target-target similarities, is first constructed. Based on this graph, a novel drug and target association prediction technique is inferred. Martinez et al. [10] proposed a new methodology for drug-disease and disease-drug prioritization named DrugNet. Based on a previously developed network-based prioritization method called ProphNet, they were able to build a three-layer heterogeneous network that contained diverse types of elements and interactions. Their findings suggest that DrugNet could be very useful for discovering new drug use cases, and the integration of heterogeneous data would be beneficial to improve the performance of classifiers for the drug repositioning task. Luo et al. [11] proposed a computational method to find novel indications for existing drugs. By applying comprehensive similarity measures, they were able to build a heterogeneous network with known drug-disease interactions. Bi-Random Walk algorithm was then implemented to predict innovative drug-disease associations.
Matrix factorization based models assume that several factors can represent each drug and disease. When drugs and diseases characteristics are consistent in the matrix, it is believed that there is a high correlation between the drug and the disease; that is, the drug may be used to treat the disease. This model decomposes the known drugdisease treatment association matrix into two low-rank drugs and disease potential factor matrices. Usually, the rank of the latent factor matrix is much smaller than the number of drugs or diseases. Matrix factorization technique is widely used in data dimensionality reduction, and recommendation application scenarios. Researchers continue to improve the matrix decomposition model for the drug repositioning task to adapt to the application scenario, as the use of a single feature does not entirely imitate the characteristics of drugs and diseases. Zhang et al. [12] proposed a unified computational platform which presents the task of hypothesis generation for drug repositioning as a constrained nonlinear optimization problem. They utilized a three-layer network approach to explore potential new associations among drugs and diseases with no prior links. Dai et al. [13] based on the idea that association between drug and disease has its evidence in the interactome network of genes. The authors proposed a matrix factorization model, which incorporates the biological information of genomic space interactions for the prediction of novel drug-disease associations. According to the drug-disease relationships, Luo et al. [14] proposed the Drug Repositioning Recommendation System (DRRS) to predict novel interactions for known drugs. This method used the drug similarity and disease similarity to construct a heterogeneous network, which was represented by a drug-disease adjacency matrix. Finally, the drug relocation could be realized by completing the matrix with the use of fast Singular Value Thresholding (SVT) algorithm presented in [15].
Collaborative filtering is commonly used to learn and predict the relationship between users and items in a recommendation system scenario. Lately, some researchers turned to collaborative filtering to tackle the challenge of drug repositioning. Following the same belief as Dai et al. [13], Regenbogen et al. [16] via using a collaborative filtering approach, constructed a relationship matrix comprising drugs, diseases, and genetic information. Non-Negative Matrix Factorization (NMF) technique was then introduced to predict the correlation between drugs and diseases. Zhang et al. [17] proposed the model which uses a neighbor-based collaborative filtering technique to incorporate complex data information for drug-disease relationship prediction.
Nevertheless, the above methods based on recommendation systems are limited in three aspects: insufficient learning ability, data sparsity, and disregarding the effect of negative samples. Matrix factorization models the drug-disease relationship as an inner product of drug latent factors and disease potential factors, which is a linear combination. The combination itself does not take into account the weight relationship between factors, and cannot learn the complex associations between drugs and diseases. In addition, the number of diseases which can be treated by a single medication is small. Similarly, the number of drugs that can be applied to cure the same illness is low as well. As a result, merely relying on drug-disease treatment relationship data cannot adequately reflect the relationship between drugs and diseases. Moreover, the previously described models ignore the negative sampling technique, and only uses known drugdisease associations. This exclusion may lead to overfitting, and degrades the performance of the model on the test set. Therefore, to overcome the shortcomings mentioned above, we propose an Additional Neural Matrix Factorization (ANMF) model. The ANMF model combines additional auxiliary information, neural network, and matrix factorization to infer novel treatments for diseases.
So as to overcome data sparsity, the ANMF model makes use of drug-drug and disease-disease similarities to enhance the representation information of drugs and diseases. Uncovering the hidden features of both drugs and diseases is made possible by the use of a deep learning technique, Additional Stacked Denoising Autoencoder (ADAE) [18]. The extracted hidden features will then participate in a collaborative filtering process by utilizing the idea of the product operation of the Generalized Matrix Factorization (GMF) method [19]. The GMF product operation introduces neuronal nodes and a nonlinear activation function. Therefore, the model can uncover further nonlinear relationships between drugs and diseases. This procedure will eventually allow us to obtain a model with a greater learning ability. Lastly, with the aim of minimizing the likelihood of model overfitting, negative sampling techniques are employed to strengthen the training set. Compared with the state-of-the-art models, the ANMF model is shown to be more valid. We can summarize the main contributions of this paper as follows: (1) A novel Additional Neural Matrix Factorization (ANMF) model is proposed for drug repositioning. The model combines deep learning representation with the nonlinear matrix factorization technique, and allows for integration of auxiliary information regarding drugs and diseases during the hidden features extraction process. As follows, a better-hidden relationship between drugs and diseasees can be captured.
(2) The negative sampling technique mentioned in [20] from the field of natural language processing is used to enhance the training set, which reduces the possibility of overfitting. The generalization feature of the model is improved as well. ( 3) The ANMF model tested both on the Gottlieb dataset [21] and the Cdataset [14], is assumed to retain its validity as its AUC (Area Under Curve), AUPR (Area Under Precision-Recall Curve) and HR (Hit Ratio) values are superior to that of the state-of-the-art related model's benchmarks.
The rest of this paper is as constructed as follows: we will introduce the implementation details and principles of the ANMF model in "Methods" section. In "Results" section, the experiments and results of the ANMF model on the Gottlieb dataset and the Cdataset will be discussed. The corresponding discussions are presented in "Discussion" section. The final "Conclusion" section will serve as a summary of our work and a guideline for future ventures.

Methods
The ANMF model proposed for drug repositioning combines neural network with matrix factorization model, and fuses additional auxiliary information to infer novel treatments for diseases. Figure 1 shows the architecture of the ANMF model.
The upper part of Fig. 1 is the process of mining the hidden feature of drug i, where drug i indicates the hidden feature of drug i. The bottom portion is the process of mining the hidden feature of disease j, where disease j indicates the hidden feature of disease j. The procedure of mining the hidden features of diseases and drugs is in reality the reconstruction of drug and disease attribute features. This process will be described in detail in "Hidden feature mining" section. The middle part of Fig. 1 shows the elementwise product operation of the extracted drug i and disease j . Finally, the product result will be inputted into a single layer perceptron to predict the Fig. 1 The architecture of the ANMF model drug-disease relationship. The prediction process will be described thoroughly in "Generate predicted value" section. In "ANMF Learning process" section, we will define the general loss function of the ANMF model, and show how the model can learn the corresponding parameters. Incorporating the negative sampling techniques onto the training set with will be described in the "Defining the number of negative sampling" section.
At present, the field of deep learning is still considered as a "blackbox process", lacking a set of axiomatic mathematical proof. However, we can proceed from the practical significance of matrix factorization model. The hidden features of drugs store the specific preferences of drugs, and the hidden features of diseases store the attributes of diseases. What our model does is to retrieve the implicit characteristics of drugs and diseases based on the historical links of drugs-diseases and also the auxiliary information. By matching the drug hidden feature with the hidden feature of the disease, the probability that the drug can treat the disease can be obtained.
Several relevant definitions are given to facilitate the interpretation of the ANMF model.

Datasets
There are two datasets used in the paper, the Gottlieb dataset [21] contains 593 drugs registered in Drug-Bank [22], 313 diseases listed in the Online Mendelian Inheritance in Man database (OMIM) [23] and 1933 validated drug-disease associations in total. The summary of the Gottlieb dataset is shown in Table 1.
We performed additional experiments on the Cdataset [14]. The Cdataset contains 409 drugs registered in Drug-Bank [22], 663 diseases recorded in the OMIM database [23] and 2532 validated drug-disease associations. See Table 2 for details.
Here, drug similarities are calculated via the Chemical Development Kit (CDK) [24] based on Simplified Molecular Input Line Entry Specification (SMILES) [25]. Pairwise drug similarity and chemical structures are denoted as the Tanimoto score of their 2D chemical patterns. The similarities between diseases are obtained from MimMiner [26], which estimates the degree of pairwise disease similarity via text mining their medical descriptions information in the OMIM database. All of the above information can be obtained from [14].

Hidden feature mining
In recent years, deep learning proved to be efficient in discovering high-level hidden representations from various raw input data. Various algorithms used the auxiliary  andDrugSim i * as the original information and auxiliary information when performing the following described encoding and decoding operation.
First, the encoding procedure described by formula (1) is performed, where drug i is the hidden feature of drug i, g represents an arbitrary activation function, W 1 and V 1 represent the weight parameters, and b drug denotes the bias parameter.
The decoding operation is performed by using formula (2). The objective is to generate the reconstructed valuê Likewise, formula (3) is also a decoding operation on drug i , and the purpose is to generate the reconstructed valueDrugSim i * of DrugSim i * .
As a result, the loss function caused by the above encoding and decoding operations is as shown in the formula (4).
By minimizing Eq.(4), the hidden feature of drug i can ultimately be obtained. Similarly, the lower part of Fig. 1 shows the process of acquiring the hidden feature of disease j, which is theoretically the same procedure as extracting the hidden feature of drug i. The process substitutes the original information and auxiliary information with s disease j and Disease j * , where s disease j = {R 1j , R 2j , . . . R mj } represents the relationship between disease j and all other drugs.

Generate predicted value
Through the above-described steps, we managed to acquire the hidden feature of drug i and the hidden feature of disease j respectively. The traditional matrix factorization model allows us to perform the inner product operation on drug i and disease j to obtain the predicted valuer ij , which represents the probability that drug i can treat disease j. However, the traditional matrix factorization model has the limitation of insufficient learning ability caused by the use of a fixed and straightforward inner product to estimate complex drug-disease interactions. The inner product operation does not take into account the weight relationship between factors, and cannot learn the complex associations between drugs and diseases.
In reference to the GMF model, the ANMF model uses the product operation of GMF instead of the inner product operation of the traditional matrix factorization model. Consequently, the ANMF model can learn the nonlinear relationship between drugs and diseases by introducing neuronal nodes and the nonlinear activation function, which improves the accuracy of the ANMF model. To do this, first calculate the elementwise product of the drug hidden feature and the disease hidden feature, and then input it into the single layer perceptron to obtain the predicted value. By introducing the neural network, the model can learn nonlinear drug-disease relationship and exhibit better learning and prediction ability. The ANMF model predicts the drug-disease relationship as presented formula (5): Where drug i and disease j respectively represent the hidden features of drug i and disease j calculated by the ANMF model, is the elementwise product, h represents the weight parameter, F out represents an arbitrary activation function andr ij denotes the predicted value.

ANMF Learning process
Now, we will define the general loss function of the ANMF model, and introduce how the model can learn the corresponding parameters. In general, the loss function of the ANMF includes two parts: the loss caused by extracting drug hidden features and disease hidden features as well as the loss between the predicted values and the target values.
The loss function of drug i hidden feature extraction is defined as shown in formula (6) : Where, W l , V l denote the weight parameters, λ denotes the regularization parameter and α represents the equilibrium parameter. Similarly, the loss function of disease j hidden feature extraction is defined as shown in formula (7): Where W d , V d denote the model parameters, δ denotes the regularization parameter and β represents the equilibrium parameter. The loss between the predicted value and the target value is defined as shown in formula (8): Where r ij denotes the target value andr ij denotes the predicted value. As a result, the general loss function for the training model is presented in formula (9): where R + denotes a set of positive instances and R − denotes a set of negative instances, which can all be (or sampled from) unobserved drug-disease interactions. Where ϕ and ψ denote for the hyperparameters of the loss function.
As shown formula (6), formula (7) and formula (8), the mathematical formulas for LossOfPrediction, LossOf-Drug, and LossOfDisease share similar fragments, namely drug i and disisease j . In other words, the parameters contained in drug i and disisease j are shared by two steps of mining hidden feature and generating predicted value. It is these shared parameters that serve as a bridge between the two steps. Moreover, parameters are trained simultaneously. Thus, the information contained is orthogonal. This also ensures that there is no overlap in information in formula (9). And enabling our model to simultaneously learn effective hidden features, and capture drug and disease similarity and relationship.
The parameters of the ANMF model can be learned by minimizing formula (9), using the stochastic gradient descent method(SGD).

Results
In this section, we will systematically evaluate the performance of the ANMF model using the Gottlieb dataset [21]. First, the evaluation metrics used in this study will be introduced. Next, the performance of the ANMF model under various parameter settings will be compared to find the optimal parameter settings. And we will survey the ANMF model's performance with several state-ofthe-art algorithms by referring to the evaluation metrics previously described, including new drug scenario. To further validate the robustness of the ANMF model, further experiments on the Cdataset [14] will be presented.

Evaluation metrics
For a systematical evaluation of the ANMF model's performance in comparison to other approaches, we adopted ten-fold cross validation (10-CV). To implement ten-fold cross validation, we randomly split all verified drugdisease associations in the dataset into ten equal-sized subsets, and all non-verified associations are considered as candidate associations. In each fold, we considered one subset as the test set, while the combined remaining nine subsets served as the training set. All candidate associations were then added to the test set. After the ANMF model training is completed, the associations in the test set will get a corresponding score.
In this study, we denoted the verified drug-disease associations as positive samples, while the remaining unverified associations were considered as negative samples. For each specific threshold, we calculate the corresponding true positive (TP), true negative (TN), false positive (FP), and false negative (FN) values. If a test association's corresponding score is greater than the threshold, it was labeled as a positive sample. Else, it was considered as a negative sample. Hence, TP and TN values characterized the number of positive and negative samples correctly identified. FP and FN values denoted the number of positive and negative samples misidentified. By regulating the threshold, we were able to obtain the True Positive Rate (TPR) and False Positive Rate (FPR). Finally, the AUC (Area Under Curve) value was acquired by drawing the Receiver Operating Characteristic (ROC) curve. Moreover, this study also used AUPR (Area Under Precision-Recall Curve) as the second evaluation indicator. Because AUC measure does not capture all aspects of the model's performance, adding the AUPR measure can more fully reflect the true performance of the model. The Hit Ratio (HR) evaluation indicator was also used in this study. Intuitively, HR measures the presence of the positive samples within the top N. And HR@n means Hit Ratio with cut offs at n.

Parameters setting
The main parameters that the ANMF model needs to set are the hidden feature dimension, and the number of negative sampling. This is due to the fact that, the size of the hidden feature vector controls the complexity of the ANMF model, while the number of negative sampling controls the generalization capabilities of the proposed model. Hence, two experiments are conducted for evaluating the performance of the model under both different dimension values of hidden feature vector and different negative sample sizes.
All hyperparameters are set as follows: In order to reduce the amount of calculation, ϕ and ψ in Eq. (9) were set to 0.5, by default. Similar to [16], we use a masking noise with a noise level of 0.3 to get the corrupted inputs from the raw inputs. The rest of hyperparameters are tuned according to the validation set. The validation set is formed by holding out one interaction per drug from the training set. We perform a grid search over α in formula (6)

The dimension of hidden feature
Since it controls the complexity of the model, the dimension of the hidden feature vector is a very important parameter for the ANMF model. If the dimension of hidden feature vector was set to a large value, the model will likely to over-fit. But if the dimension was set to a small value, the model will not be able to learn the highlevel association between drugs and diseases. Thus, the following experiment was preformed to observe the performance of the ANMF model in different settings, and to have a clear understanding in regards to the appropriate dimension value that required to be set for the hidden feature vector. Figure 2 illustrates the performance of the ANMF model on the Gottlieb dataset under different dimension values of the hidden feature vector. We can observe that there is a steady improvement as the dimension of the hidden feature vector increases, where a dimension value of 128 shows a peak in HR@10 performance, followed by a degradation potentially due to overfitting. As the Fig. 2 The performance of ANMF model under different hidden feature dimensions dimension grows, the model's AUC value and Hit Ratio value increases. This scenario shows that the ANMF model can capture more complex associations between drugs and diseases as the dimension increases. However, the AUC value has a downward trend as the dimension of value varies in the range [128,256], this confirms that the model tends to over-fit when the dimension of the hidden feature vector is too large. The larger the dimension value of the hidden features, the more complex the model will be. According to Occam's razor law, among models with the same effect, a model with a lower complexity should be selected. So 128 was chosen as the appropriate dimension parameter value for the ANMF model.

Defining the number of negative sampling
The inclusion of the negative samples is a crucial step to the ANMF model. In this study, we refer to the idea of the negative sampling techniques in natural language processing [20] to enhance the training set. For each validated drug-disease association in the training set, we randomly take in N associations that have not been verified as negative samples into the training set. Since the number of positive samples, in reality, is much smaller than the number of negative samples, the above approach is desirable. However, Negative sampling is risky. The greater the number of negative sampling, the more it will increase the probability of forming a wrong negative sample or forcing the unknown positives to be considered negative. Therefore, we conducted this experiment to observe the performance of the model at different numbers of negative sampling.
The abscissa calculated from of Fig. 3 represents the value of N. Figure 3 illustrates the performance of the ANMF model on the Gottlieb dataset when the negative samples value varies from [1,20]. We can observe a steady improvement as the number of negative samples grows. This scenario clearly demonstrates that using negative sampling techniques to enrich the training set is effective. However, when the value of N ranges from 10 to 20, both the AUC and the Hit Ratio values tend to decrease, which shows that wrong negative samples were forming as the value of N is increasing. According to the above experiment, we set the appropriate value of N to 10.
The experimental results clearly demonstrates that the negative sampling technique has a certain degree of improvement on the prediction effect and generalization performance of the model, which explains the effectiveness of the negative sampling technique to some extent.

Baselines and comparison
With the aim of evaluating the performance of the proposed ANMF model, we will compare it with the current three most advanced models, DRRS [14], GMF [19] and HGBI [9].
DRRS is currently considered to be one of the best algorithms in the field of drug repositioning. This algorithm works by constructing a heterogeneous network via exploiting the drug-disease relationships, drug similarity and disease similarity. It then implements a fast Singular Value Thresholding (SVT) algorithm to complete the drug-disease adjacency matrix with predicted scores for previously unknown drug-disease associations.
GMF is a matrix decomposition model, in which neural networks and matrix decomposition are combined to enable the capturing of the nonlinear relationships between drugs and diseases. In other sense, the GMF model is an ANMF model without an auxiliary information version.
HGBI is introduced based on the guilt-by-association principle, as an intuitive interpretation of information flow on the heterogeneous graph. The parameters setting for the above mentioned methods are all established according to their corresponding literature. The overall performance of all methods is evaluated by applying the ten-fold cross validation technique (10-CV) specified in "Evaluation metrics" section.
The experiment results in terms of AUC, AUPR and Hit Ratio values are illustrated in Table 3. As clearly shown by the experimental results of Table 3, the proposed ANMF model outperforms other competitive methods in terms of AUC value. More specifically, the ANMF has an AUC value of 0.938, while DRRS, GMF, and HGBI yield results of 0.93, 0.88, and 0.829, respectively. Moreover, in terms of AUPR value, the ANMF model achieved the highest value of 0.347, while DRRS, GMF, and HGBI have results of 0.292, 0.281, and 0.16, respectively. Next, we compared the performance of the ANMF model with the other three models in terms of Hit Ratio value. The proposed ANMF model surpasses other models in regards to HR@1, HR@5, and HR@10. Furthermore, in the case of HR@10, our proposed ANMF model has a Hit Ratio value of 74.2%, while DRRS, GMF, and HGBI have 72.7%, 61.9%, and 59.3%, respectively.

Predicting indications for new drugs
The ANMF model can also be used for drugs without previously known disease associations. One hundred seventy-one drugs in the Gottlieb data set only has one known drug-disease association. In this case, we will be taking 171 known association as the test set, the remaining verified associations are considered as the training set. The evaluation metrics are AUC value, AUPR value and Hit Ratio. The experimental results in terms of AUC value, AUPR value and Hit Ratio are presented in Table 4.
As shown in Table 4, the performance of our proposed ANMF model is superior to other competitive methods regarding AUC value. More specifically, the AUC value of the ANMF model is 0.859, while the results of DRRS, GMF, and HGBI are 0.824, 0.813, and 0.746, respectively. Moreover, in terms of AUPR value, the ANMF model achieved the highest value of 0.161, while the results of DRRS, GMF, and HGBI are 0.107, 0.106, and 0.065, respectively. Now we turn to the comparison of the ANMF model performance with the other previously mentioned models in terms of Hit Ratio value. As likewise shown in the experimental results in Table 4, the proposed ANMF

Validation on the Cdataset
To further validate the robustness of the proposed ANMF model, we performed additional experiments on the Cdataset [14]. The evaluation metrics used in this validation phase experiment are the same as the ones mentioned in "Evaluation metrics" section. The hidden features dimension and the number of negative sampling were set to 256, and 10, respectively. Other hyperparameter settings remain the same. In terms of predicting known associations, the results of this experiment portrayed in Table 5 show that the ANMF model measured an AUC value of 0.952, a superior outcome when compared to the AUC values that of DRRS, GMF, and HGBI which were 0.947, 0.915, and 0.858 respectively. Moreover, in terms of AUPR value, the ANMF model achieved the highest value of 0.394. Concerning the Hit Ratio value, the ANMF model similarly performed better than the other models in the case of HR@1, HR@5 and HR@10. For instance, in the case of HR@10, the Hit Ratio value of the ANMF model is 76.3%, while the DRRS, GMF, and HGBI models measured Hit Ratio values of 70.1%, 56.3%, and 55.1% respectively.
According to the results in Table 6, the ANMF model likewise outperformed the previously mentioned models in predicting new drugs with an AUC value of 0.857, as opposed to 0.824 for DRRS, 0.798 for GMF, and 0.732 for HGBI. Moreover, in terms of AUPR value, the ANMF

Discussion
Through experiments performed on two real-world datasets, we managed to demonstrate that the proposed ANMF model outperformed other portrayed methods, and displayed significant performance enhancements. For the Gottlieb dataset, the AUC, AUPR and Hit Ratio measured values were 0.938, 0.347 and 74.2% respectively. And the model's predictive performance on the Cdataset was 0.952 for the AUC value, 0.394 for AUPR value and 76.3% for the Hit Ratio value. The above-declared findings are all superior to their counterparts among other surveyed algorithms. Furthermore, we can deduce that using negative sampling techniques to enrich the training set showed to be effective through the performed experiments in "Defining the number of negative sampling" section. Moreover, integrate assistance information to assist the model in overcoming the challenges of data sparsity. By comparing the performance of the ANMF model and the GMF model, which is an ANMF model with no auxiliary information version, the ANMF model outperforms the GMF model both in terms of AUC, AUPR and Hit Ratio values on two common data sets. And as the sparseness of the data set increases, the gap between the performance of the ANMF and the GMF model also increases. This result demonstrates the correctness of our initial assumption that integrating auxiliary information can overcome the sparseness of the data to a certain extent.

Conclusion
As a vital and lucrative technology to discover new applications of old drugs, computational drug repositioning has been receiving growing attention from both the industry and academia. In this paper, we proposed an Additional Neural Matrix Factorization (ANMF) model for computational drug repositioning. The ANMF model combined deep learning representation with the nonlinear matrix factorization technique, to resolve the problems of data sparsity and insufficient learning ability. Furthermore, the negative sampling technique was employed to overcome the issue of model overfitting.
Exhaustive experiments under multiple configurations demonstrated significant improvements over related competitive benchmarks. However, we believe that improvements can be made to the ANMF model in the future research. This study only makes use of drug similarity and disease similarity, and the attribute information of drugs and diseases is not limited to these two features. Furthermore, the ANMF model only uses a single-layer perceptron, which is the simplest deep learning model. For future work, using a complex deep learning model along with other auxiliary information to learn drug-disease relationship promises to deliver far improved results.


Matching biomedical ontologies through compact differential evolution algorithm

ABSTRACT Although biomedical ontologies have been widely used in the life science domain, the heterogeneous problem among biomedical ontologies hampers their inter-operability. Thus, the establishment of meaningful links between heterogeneous biomedical ontologies, so-called biomedical ontology matching, is critical to the success of biomedical ontology engineering. To determine the biomedical ontology alignment with high quality, in this work, a Hybrid Compact Differential Evolution (HCDE) algorithm-based biomedical ontology matching technique is proposed. In particular, we propose a similarity metric on biomedical concepts, construct an optimal model for the biomedical ontology matching problem, and introduce a binomial crossover into CDE's evolving the process to enhance its performance. The experiments are carried out on the Disease and Phenotype track and Biodiversity and Ecology track from the Ontology Alignment Evaluation Initiative (OAEI 2018). The experimental results show that HCDE can significantly improve the CDE in terms of the alignment's quality, and the alignments obtained by HCDE are also better than OAEI 2018's participants.

Introduction
In recent years, various biomedical ontologies, such as FMA (Detwiler, Mejino, & Brinkley, 2016) and SNOMED-CT (Filice & Kahn, 2019), have been widely used in the life science domain (Faria et al., 2018). However, existing biomedical ontologies that cover overlapping domains are mostly developed independently, and the different ways of defining the same biomedical concept yield heterogeneous problems among biomedical ontologies, which hampers their inter-operability. Thus, the establishment of meaningful links between biomedical concepts, so-called biomedical ontology matching, is critical to the success of biomedical ontology engineering (Oliveira & Pesquita, 2018).
Usually, a biomedical ontology possesses tens of thousands of biomedical concepts which are semantically ambiguous, and these biomedical concepts own complex relationships between each other. Thus, it is a big challenge to match them effectively. Being inspired by the success of Evolutionary Algorithm (Acampora, Loia, & Vitiello, 2013;Ginsca & Iftene, 2010;Martinez-Gil & Montes, 2011;Naya, Romero, & Loureiro, 2010;Wang, Ding, & Jiang, 2006;Xue & Pan, 2018;Xue & Wang, 2015) in ontology matching domain, in this work, we propose CONTACT Junfeng Chen chen-1997@163.com to use Differential Evolutionary algorithm (DE) (Storn & Price, 1997) to determine the biomedical ontology alignment with high quality. Since matching biomedical ontologies is a large-scale problem, we utilize a compact DE (CDE) (Mininno, Neri, Cupertino, & Naso, 2011) to avoid the memory overflow and introduce a local search strategy into CDE's evolving process to improve its converging speed. In particular, our contributions made in this paper are as follows: • a similarity metric on biomedical concept pair is proposed to calculate the similarity value of two biomedical concepts, • an optimal model for biomedical ontology matching is constructed, • a problem-specific Hybrid CDE (HCDE) is presented to effectively solve the biomedical ontology matching problem.
The rest of the paper is organized as follows: Section 2 presents the biomedical ontology matching problem and biomedical concept similarity metric; Section 3 presents in detail the HCDE-based biomedical ontology matching technique; Section 4 shows the experimental results; and finally, Section 5 draws the conclusion.

Biomedical ontology matching
Biomedical ontology matching dedicates to determine an ontology alignment which consists of biomedical concept correspondences. Usually, some external resources, such as the electronic dictionaries and knowledge bases, are required in matching process. Since the quality of biomedical ontology alignment can be measured by the number of correspondences found and the mean similarity value of the biomedical concept correspondences, in this work, we utilize the following equation to measure a biomedical alignment's quality: where |C 1 |, |C 2 | and |A| are, respectively, the cardinalities of two biomedical concepts sets C 1 and C 2 , and an alignment A between them, simValue i is the similarity value of the ith correspondence of A.
Further, an optimal model for the biomedical ontology matching problem is constructed as follows: where |C 1 | and |C 2 |, respectively, represent the cardinalities of two biomedical concepts sets C 1 and C 2 , x i , i = 1, 2, . . . , |C 1 | represents the ith pair of correspondence, and in particular, x i = 0 means the ith source concept is mapped to none. Supposing A is X's corresponding alignment, the objective function F(X) is equal to f (A).

Similarity metric
Biomedical similarity metric is the foundation of the biomedical ontology matching technique (Cross, 2018). In this work, we utilize a profile-based similarity metric to measure to what extent two biomedical concepts are similar to each other. Given the concept hierarchies of two biomedical ontologie, for each biomedical concepts, we construct a profile for it by collecting the name, property name, and method name from itself and all its direct ascendant and descendants. Then, the similarity value of two biomedical concepts c 1 and c 2 is calculated through their profiles p 1 and p 2 : where • |p 1 | and |p 2 | are the cardinalities of p 1 and p 2 , respectively, • p 1 i and p 2 j are, respectively, the ith element of p 1 and jth element of p 2 , • sim () computes the similarity value between p 1 i and p 2 j by SMOA (Stoilos, Stamou, & Kollias, 2005) and UMLS (Bodenreider, 2004), which is defined as follows:

Hybrid compact differential evolution algorithm
To save the memory consumption and improve the converging speed, in this work, we utilize the compact version of DE, i.e. CDE, and combine CDE (global search) with a binomial crossover (local search) to address the biomedical ontology matching problem. In the following, three kernel components of HCDE are presented, i.e. the encoding mechanism, mutation operator and the local search, and the pseudocode of HCDE is presented at last.

Encoding mechanism
In our proposal, a Probability Vector (PV) (Xue & Pan, 2018) is utilized to characterize the entire population, and each element inside stands for the probability that holds true for a biomedical concept correspondence. We utilize the grey encoding mechanism to encode each biomedical concept mapping. When decoding, the number obtained represents the index of a target biomedical concept, and in particular, the value 0 means a source concept is not mapped to any target concept.

Mutation operator
In HCDE, three solutions, namely ind r , ind s , and ind t , are sampled from the PV, and an offspring ind off is generated as follows: where F = 1.5 is a scale factor that determines how far the generated offspring is from ind t . For the biomedical ontology matching problem, which is a discrete problem, we introduce the edit distance to measure two individuals' distance. In the following, we present the equation about the calculation of two individuals ind r and ind s 's edit distance: where |ind r | is the cardinality of ind r , ind r,i and ind s,i are, respectively, the ith element of ind r and ind s . Next, the offspring ind off are generated by partly flipping the elements of ind t , and the number of altered elements is determined by a random number in [0, 1] and editDistance(ind r , ind s ). For the sake of clarity, the pseudocode of the mutation operator is given in Algorithm 1:

Local search
To improve CDE's converging speed, a local search strategy in introduced, which searches for the optimal solution in the neighbourhood of the elite solution. In particular, we execute the local search in each generation which is implemented with the binomial crossover. For the sake of clarity, the pseudocode of the binomial crossover is given in Algorithm 2.

Algorithm 2 Binomial Crossover
The binary crossover randomly copies a sequential fragment of ind off 's genes into the corresponding positions of ind off , to generate ind elite 's neighbour solution. This procedure is similar to the two-point crossover where the first cut point is randomly selected from {1, 2, . . . , n} where n is the length of a solution, and the second point is determined such that L consecutive genes (counted in a circular manner) are taken from ind off . In this work, since ind off and elite are both generated through PV, they are similar in term of chromosome's information, i.e. many gene bit values of them are the same. Therefore, even when crossover probability is large, the ind off generated by the crossover operator only mutates a few gene bit values of elite. In this sense, this variation operator can be considered fairly exploitative.

The pseudocode of hybrid compact differential evolution algorithm
Given the length of a solution (or PV) length, the maximum number of generations maxGen, the binomial crossover probability p c , the step length for updating PV step, the pseudo-code of HCDE is given in Algorithm 3.

Experimental setup
In order to study the effectiveness of HCDE, we exploit the Disease and Phenotype track 1 and Biodiversity and Ecology track 2 from the Ontology Alignment Evaluation Initiative (OAEI 2018). 3 The Disease and Phenotype track is composed of two tasks which, respectively, require matching Human Phenotype Ontology (HP) 4 to Mammalian Phenotype Ontology (MP), 5 and Human Disease Ontology (DOID) 6 to the Orphanet Rare Disease Ontology (ORDO). 7 The Biodiv track requires matching the Environment Ontology (ENVO) 8 and the Semantic Web for Earth and Environment Technology Ontology (SWEET), 9 and the Flora Phenotype Ontology (FLOPO) 10 and the Plant Trait Ontology (PTO). 11 All these biomedical ontologies are particularly useful for biodiversity and ecology research and have been used in various projects, which are semantically rich and contain tens of thousands of classes.
In order to compare with CDE-based biomedical ontology matcher, which is the nonlocal search version of HCDE, and the participants of OAEI 2018, 12 we evaluate the obtained alignments with traditional recall, precision and f -measure (Van Rijsbergen, 1986). HCDE and CDE's results in the tables are the mean values in 30 independent executions, and the symbols P, R and F in the tables stand for precision, recall and f -measure, respectively. HCDE uses the following parameters which represent a trade-off setting obtained in an empirical way to achieve the highest average alignment quality on all exploited dataset.
We run the Disease and Phenotype track with an Intel Core i9-8950HK CPU @ 2.90 GHz × 12 and 25 Gb allocated RAM, the Biodiversity and Ecology track with an Intel Core i5-7500 CPU @ 3.40 GHz and 15.7 Gb allocated RAM, which are the same with the OAEI's hardware configurations.

Experimental results
As can be seen from Tables 1 and 2, HCDE's f -measure is the best in all testing cases. In general, our precision value is high, which show the effectiveness of the proposed concept similarity metric. Comparing with CDE, which is the nonlocal search version of HCDE, the recall and precision are both improved significantly, which further show the effectiveness of the local search algorithm. To conclude, HCDE can effectively match the biomedical ontologies.

Conclusion
To efficiently match the biomedical ontologies, an HCDEbased technique is proposed to efficiently determine the identical biomedical concepts. In particular, HCDE combines CDE (global search) and binominal crossover (local search) to address the biomedical ontology matching problems. In addition, a novel biomedical ontology similarity metric is presented to distinguish the heterogeneous concepts and an optimal model of biomedical ontology matching problem is constructed. The experimental results show that the introduction of a local search strategy can significantly improve the converging speed of CDE, and the performance of HCDE outperforms the state-of-the-art ontology matchers of OAEI 2018.


extfieldsofstudy:
Computer Science
Mathematics

text:
Primal-Dual Block Frank-Wolfe

We propose a variant of the Frank-Wolfe algorithm for solving a class of sparse/low-rank optimization problems. Our formulation includes Elastic Net, regularized SVMs and phase retrieval as special cases. The proposed Primal-Dual Block Frank-Wolfe algorithm reduces the per-iteration cost while maintaining linear convergence rate. The per iteration cost of our method depends on the structural complexity of the solution (i.e. sparsity/low-rank) instead of the ambient dimension. We empirically show that our algorithm outperforms the state-of-the-art methods on (multi-class) classification tasks.

Introduction
We consider optimization problems of the form: directly motivated by regularized and constrained Empirical Risk Minimization (ERM). Particularly, we are interested in problems whose solution has special "simple" structure like low-rank or sparsity. The sparsity constraint applies to large-scale multiclass/multi-label classification, low-degree polynomial data mapping [5], random feature kernel machines [32], and Elastic Net [39]. Motivated by recent applications in low-rank multi-class SVM, phase retrieval, matrix completion, affine rank minimization and other problems (e.g., [9,31,2,3]), we also consider settings where the constraint x ∈ C (e.g., trace norm ball) while convex, may be difficult to project onto. A wish-list for this class of problems would include an algorithm that (1) exploits the function finite-sum form and the simple structure of the solution, (2) achieves linear convergence for smooth and strongly convex problems, (3) does not pay a heavy price for the projection step.
We propose a Frank-Wolfe (FW) type method that attains these three goals. This does not come without challenges: Although it is currently well-appreciated that FW type algorithms avoid the cost of projection [14,1], the benefits are limited to constraints that are hard to project onto, like the trace norm ball. For problems like phase retrieval and ERM for multi-label multi-class classification, the gradient computation requires large matrix multiplications. This dominates the per-iteration cost, and the existing FW type methods do not asymptotically reduce time complexity per iteration, even without paying the expensive projection step. Meanwhile, for simpler constraints like the 1 norm ball or the simplex, it is unclear if FW can offer any benefits compared to other methods. Moreover, as is generally known, FW suffers from sub-linear convergence rate even for well-conditioned problems that enjoy strong convexity and smoothness.
In this paper we tackle the challenges by exploiting the special structure induced by the constraints and FW steps. We propose a variant of FW that we call Primal-Dual Block Frank Wolfe. The main advantage is that the computational complexity depends only on the sparsity of the solution, rather than the ambient dimension, i.e. it is dimension free. This is achieved by conducting partial updates in each iteration, i.e., sparse updates for 1 and low-rank updates for the trace norm ball. While the benefits of partial updates seem unclear for the original problem, they significantly benefit a primal-dual reformulation. This reduces the per iteration cost to roughly a ratio of s d compared to naive Frank-Wolfe, where s is the sparsity (or rank) of the optimal solution, and d is the feature dimension. Meanwhile, the per iteration progress of our proposal is comparable to a full gradient descent step, thus retaining linear convergence rate.
For strongly convex and smooth f and g we show that our algorithm achieves linear convergence with per-iteration cost sn over 1 -norm ball, where s upper bounds the sparsity of the primal optimal. Specifically, for sparse ERM with smooth hinge loss or quadratic loss with 2 regularizer, our algorithm yields an overall O(s(n + κ) log 1 ) time complexity to reach duality gap, where κ is the condition number (smoothness divided by strong convexity). Our theory has minimal requirements on the data matrix A.
Experimentally we observe our method yields significantly better performance compared to prior work, especially when the data dimension is large and the solution is sparse.

Related Work
We review relevant algorithms that improve the overall performance of Frank-Wolfe type methods. Such improvements are roughly obtained for two reasons: the enhancement on convergence speed and the reduction on iteration cost. Very few prior works benefit in both.
Nesterov's acceleration has proven effective as in Stochastic Condition Gradient Sliding (SCGS) [23] and other variants [36,26,10]. Restarting techniques dynamically adapt to the function geometric properties and fills in the gap between sublinear and linear convergence for FW method [18]. Some variance reduced algorithms obtain linear convergence as in [13], however, the number of inner loops grows significantly and hence the method is not computationally efficient.
Linear convergence has been obtained specifically for polytope constraints like [27,20], as well as the work proposed in [21,11] that use the Away-step Frank Wolfe and Pair-wise Frank Wolfe, and their stochastic variants. One recent work [1] focuses on trace norm constraints and proposes a FW-type algorithm that yields similar progress as projected gradient descent per iteration but is almost projection free. However, in many applications where gradient computation dominates the iteration complexity, the reduction on projection step doesn't necessarily produce asymptotically better iteration costs.
The sparse update introduced by FW steps was also appreciated by [22], where they conducted dual updates with a focus on SVM with polytope constraint. Their algorithm yields low iteration costs but still suffer from sub-linear convergence.
On the other hand, the recently popularized primal-dual formulation min x max y {g(x) + y Ax − f (y)} has proven useful for different machine learning tasks like reinforcement learning, ERM, and robust optimization [8]. Especially for the ERM related problems, the primal-dual formulation still inherits the finite-sum structure from the primal form, and could be used to reduce variance [38,35] or reduces communication complexity in the distributed setting [37]. However, there has been a lack of studies for constrained problems for this form. Meanwhile, as we emphasize in this paper, since the most time-consuming part of this formulation comes from the bilinear term y Ax, we are able to exploit simple structure from the optimal solutions.

Notation
We briefly introduce the notation used throughout the paper. We use bold lower case letter to denote vectors, capital letter to represent matrices. · is 2 norm for vectors and Frobenius norm for matrices unless specified otherwise.
· * indicates the trace norm for a matrix.
We say a function f is α strongly . We use f * to denote the convex conjugate of f , i.e., f * (y) def = max x x, y − f (x). Some more parameters are problem-specific and are defined when needed.

A Theoretical Vignette
To elaborate the techniques we use to obtain the linear convergence for our Frank-Wolfe type algorithm, we consider the 1 norm constrained problem as an illustrating example: where f is L-smooth and µ-strongly convex. If we invoke the Frank Wolfe algorithm, we compute Even when the function f is smooth and strongly convex, (2) converges sublinearly. As inspired by [1], if we assume the optimal solution is s-sparse, we can enforce a sparse update while maintaining linear convergence by a mild modification on (2): We also call this new practice block Frank-Wolfe as in [1]. The proof of convergence can be completed within three lines.
(by convexity and µ-strong convexity of f ) Therefore, when η = µ 2L , h t+1 ≤ (1 − µ 4L ) t h 1 and the iteration complexity is O( L µ log(1/ )) to achieve error. Although we achieve linear convergence, the advantage of overall complexity against classical methods (e.g. Projected Gradient Descend (PGD)) is not shown yet. Luckily, with the updatex being sparse, it is possible to improve the iteration complexity, while maintaining the linear convergence rate. In order to differentiate, we name the sparse update nature of (3) as partial update.
Consider quadratic functions as an example:f (x) = 1 2 x Ax, whose gradient is Ax for symmetric A. Asx is sparse, One can maintain the value of the gradient efficiently: Ax (t) ≡ (1 − η)Ax (t−1) + ηA I,:x , where I is the support set ofx. We therefore reduce the complexity of one iteration to O(sd), compared to O(d 2 ) with PGD. Similar benefits hold when we replace x by a matrix X and conduct a low-rank update on X.
The benefit of partial update is not limited to quadratic functions. Next we show that for a class of composite function, we are able to take the full advantage of the partial update, by taking a primal-dual re-formulation.

Primal-Dual Formulation
Note that the problem we are tackling is as follows We first focus on the setting where x ∈ R d is a vector and C is the 1 -norm ball. This form covers general classification or regression tasks with f i being some loss function and g being a regularizer. Extension to matrix optimization over a trace norm ball is introduced in Section 4.4. Even with the constraint, we could reform (5) as a primal-dual convex-concave saddle point problem: or its dual formulation: Notice (7) is not guaranteed to have an explicit form. Therefore some existing FW variants like [22] that optimizes over (7) may not apply. Instead, we directly solve the convex concave problem (6) and could therefore solve more general problems, including complicated constraint like trace norm.
Since the computational cost of the gradient ∇ x L and ∇ y L is dominated by computing A y and Ax respectively, sparse updates could reduce computational costs by a ratio of roughly O(d/s) for updating x and y while achieving good progress.

Primal-Dual Block Frank-Wolfe
With the primal-dual formulation, we are ready to introduce our algorithm. The idea is simple: since the primal variable x is constrained over 1 norm ball, we conduct block Frank-Wolfe algorithm and achieve an s-sparse update. Meanwhile, for the dual variable y we conduct greedy coordinate ascent method to select and update k coordinates (k determined later). We selected coordinates that allow the largest step, which is usually referred as a Gauss-Southwell rule denoted by GS-r [30]. Our algorithm is formally presented in Algorithm 1. The parameters to set in the algorithm request setting assumptions on f and g: Assumption 4.1. We assume the functions satisfy the following properties: • Each loss function f i is convex and β-smooth, and is α strongly convex over some convex set (could be R), and linear otherwise.
Suitable loss functions f i include smooth hinge loss [33] and quadratic loss function. Relevant applications covered are Support Vector Machine (SVM) with smooth hinge loss, elastic net [39], and linear regression problem with quadratic loss.
As L(x, y) is µ-strongly convex and L-smooth with respect to x, we set the primal learning rate η = µ 2L according to Section 3.2. Meanwhile, the dual learning rate δ is set to balance its effect on the dual progress as well as the primal progress. We specify it in the theoretical analysis part.
The computational complexity for each iteration in Algorithm 1 is O(ns). Both primal and dual update could be viewed as roughly three steps: coordinate selection, variable update, and maintaining A T y or Ax. The coordinate selection as Eqn. (8)

Theoretical Analysis
We derive convergence analysis under Assumption 4.1. The derivation consists of the analysis on the primal progress, the balance of the dual progress, and their overall effect. Algorithm 1 Frank-Wolfe Block Primal-Dual Method for 1 Norm Ball 1: Input: Training data A ∈ R n×d , primal and dual step size η, δ > 0. 2: Initialize: Use Block Frank Wolfe to update the primal variable: x ← arg min

5:
Update w to maintain the value of Ax: 6: Consider the potential dual update:ỹ

7:
Choose greedily the dual coordinates to update: let I (t) be the top k coordinates that maximize Update the dual variable accordingly: 8: 9: end for 10: Output: Define the primal gap as ∆ is the primal optimal solution such that the dual D(y (t) ) = L(x (t) , y (t) ), and is sparse enforced by the 1 constraint. The dual gap is ∆ . We analyze the convergence rate of duality gap Primal progress: Firstly, similar to the analysis in Section 3.2, we could derive that primal update introduces a sufficient descent as in Lemma B.2.
Dual progress: With the GS-r rule to carefully select and update the most important k coordinates in the dual variable in (10), we are able to derive the following result on dual progress that diminishes dual gap as well as inducing error. − Refer to Lemma B.5 for details. Primal Dual progress: The overall progress evolves as: primal hindrance In this way, we are able to connect the progress on duality gap with constant fraction of its value, and achieve linear convergence: that satisfies Assumption 4.1. Set s to upper bound the sparsity of the primal optimalx (t) , and learning rates η = µ 2L , δ = 1 k ( L µnβ + 5βR 2αµn 2 (1 + 4 L µ )) −1 . The duality gap Rβ nµ ) log 1 ) iterations to achieve error. The overall complexity is O(ns L µ (1 + β α Rβ nµ ) log 1 ). For our target applications like elastic net, or ERM with smooth hinge loss, we are able to connect the time complexity to the condition number of the primal form.
Corollary 4.1.1. Given a smooth hinge loss or quadratic loss f i that is β-smooth, and 2 regularizer g = µ 2 x 2 . Define the condition number κ = βR µ . Setting s upper bounds the sparsity of the primal optimalx (t) , and learning rates iterations to achieve error. The overall complexity is O(s(n + κ) log 1 ).
Our derivation of overall complexity implicitly requires ns ≥ d by setting k = sd/n ≥ 1. This is true for our considered applications like SVM. Otherwise we choose k = 1 and the complexity becomes O(max{d, ns}(1 + κ n ) log 1 ).
In Table 1, we briefly compare the time complexity of our algorithm with some benchmark algorithms: (1) Accelerated Projected Gradient Descent (PGD) (2) Frank-Wolfe algorithm (FW) (3) Stochastic Variance Reduced Gradient (SVRG) [15] (4) Stochastic Conditional Gradient Sliding (SCGS) [23] and (5) Stochastic Variance-Reduced Conditional Gradient Sliding (STORC) [13]. The comparison is not thorough but intends to select constrained optimization that improves the overall complexity from different perspective. Among them, accelerated PGD improves conditioning of the problem, while SCGS and STORC reduces the dependence on number of samples. In the experimental session we show that our proposal outperforms the listed algorithms under various conditions.

Algorithm
Per

Extension to the Trace Norm Ball
We also extend our algorithm to matrix optimization over trace norm constraints: This formulation covers multi-label multi-class problems, matrix completion, affine rank minimization, and phase retrieval problems (see reference therein [3,1]). Equivalently, we solve the following primal-dual problem: Here y i is the i-th row of the dual matrix Y . For this problem, the partial update we enforced on the primal matrix is to keep the update matrix low rank: X ← arg min X * ≤λ,rank(X)≤s Algorithm 2 Frank-Wolfe Block Primal-Dual Method for Trace Norm Ball 1: Input: Training data A ∈ R n×d , primal and dual step size η, δ > 0. Target accuracy . 2: Initialize: for t = 1, 2, · · · , T do 4: Use Frank Wolfe to Update the primal variable: )-approximation of Eqn. (18).

5:
Update W to maintain the value of AX: 6: Consider the potential dual update:Ỹ 7: Choose greedily the rows of the dual variable to update: let I (t) be the top k coordinates that maximize Update the dual variable accordingly: 8: 9: end for 10: Output: However, an exact solution to (18) requires computing the top s left and right singular vectors of the matrix X (t−1) − 1 ηL (Z + ∇g(X (t−1) ) ∈ R d×c . Therefore we loosely compute an ( 1 2 , /2)-approximation, where is the target accuracy, based on the following definition: F be the objective function in (18), and let l * t = l t (X (t) ). Given parameters γ ≥ 0 and ≥ 0, a feasible solution V to (18) is The time dependence on the data size n, c, d, s is ncs + s 2 (n + c) [1], and is again independent of d. Meanwhile, the procedures to keep track of W (t) ≡ AX (t) requires complexity of nds + ncs, while updating Y (t) requires dck operations. Therefore, by setting k ≤ ns(1/c + 1/d), the iteration complexity's dependence on the data size becomes O(n(d + c)s) operations, instead of O(ndc) for conducting a full projected gradient step. Recall that s upper bounds the rank ofX (t) ≤ min{d, c}.
The trace norm version mostly inherits the convergence guarantees for vector optimization. Refer to the Appendix for details. Assumption 4.2. We assume the following property on the primal form (17): • f i is convex, and β-smooth. Its convex conjugate f * i exists and satisfies 1 α -smooth on some convex set (could be R c ) and infinity otherwise.
• g is µ-strongly convex and L-smooth.
The assumptions also cover smooth hinge loss as well as quadratic loss. With the similar assumptions, the convergence analysis for Algorithm 2 is almost the same as Algorithm 1. The only difference comes from the primal step where approximated update produces some error: Primal progress: With the primal update rule in Algorithm 2, it satisfies L( With no much modification in the proof, we are able to derive similar convergence guarantees for the trace norm ball.
The six datasets used here are summarized in Table 2. All of them can be found in LIBSVM datasets [4]. We augment the features of MNIST, ijcnn, and cob-rna by random binning [32], which is a standard technique for kernel approximation. Data is normalized. We set the 1 constraint to be 300 and the 2 regularize parameter to 10/n to achieve   The results are shown in Fig 1. To focus on the convergence property, we show the decrease of loss function instead of prediction accuracy. From Fig 1, our proposed algorithm consistently outperforms the benchmark algorithms. The winning margin is roughly proportional to the solution sparsity ratio, which is consistent with our theory.

Experiments with trace norm ball on synthetic data
For trace norm constraints, we also implemented our proposal Primal Dual Block Frank Wolfe to compare with some prior work, especially Block FW [1]. Since prior work were mostly implemented in Matlab to tackle trace norm projections, we therefore also use Matlab to show fair comparisons. We choose quadratic loss f (AX) = AX − B 2 F and g to be 2 regularizer with µ = 10/n. The synthetic sensing matrix A ∈ R n×d is dense with n = 1000 and d = 800. Our observation B is of dimension 1000 × 600 and is generated by a ground truth matrix X 0 such that B = AX 0 . Here X 0 ∈ R 800×600 is constructed with low rank structure. We vary its rank s to be 10, 20, and 100. The comparisons with stochastic FW, blockFW [1], STORC [13], SCGS [23], and projected SVRG [15] are presented in Figure 2, which verifies that our proposal PDBFW consistently outperforms the baseline algorithms.

Conclusion
In this paper we consider a class of problems whose solutions enjoy some simple structure induced by the constraints. We propose a FW type algorithm to exploit the simple structure and conduct partial updates, reducing the time cost for each update remarkably while attaining linear convergence. For a class of ERM problems, our running time depends on the sparsity/rank of the optimal solutions rather than the ambient feature dimension. Our empirical studies verify the improved performance compared to various state-of-the-art algorithms.

A Efficient Coordinate Selections
The modified Block Frank-Wolfe step in Eqn. (3) achieves an s-sparse update of the iterates and could be computed efficiently when one knows which s coordinates to update. However, in order to find the s coordinates, one needs to compute the full gradient ∇f (x) with naive implementation. This phenomenon reminds us of greedy coordinate descent.
Even with the known fact that coordinate descent converges faster with greedy selection than with random order [30], there have been hardness to propogate this idea because of expensive greedy selections since the arguments that GCD converges similarly with RCD in [28], except for special cases [25,24,6,17]. This is also probability why the partial updates nature of FW steps is less exploited before.
We investigate some possible tricks to boost GCD method that could be possibly applied to FW methods. A recent paper [17], Karimireddy et al. make connections between the efficient choice of the greedy coordinates with the problem of Maximum Inner Product Search (MIPS) for a composite function P (x) = f (Ax) + g(x), where A ∈ R n×d . We rephrase the connection for the Frank-Wolfe algorithm. Since the computation of gradient is essentially A ∇f |Ax + ∇g(x), to find its largest magnitude is to search maximum inner products among: whereã i ∈ R n is the i-th column of data matrix A, and ∇f |Ax is the gradient of f at Ax. In this way, we are able to select the greedy coordinates by conducting MIPS for a fixed R 2d×(n+1) matrix [A |I| − A | − I] and each newly generated vector [∇f |Ax |∇g i (x)]. Therefore when ∇g i is constant for linear function or ±λ for g(x) = λ x 1 , we could find the largest magnitude of the gradient in sublinear time. Still, the problems it could conquer is very limited. It doesn't even work for 2 regularizer since the different coordinates in ∇ i g(x) creates d new vectors in each iteration and traditional MIPS could resolve it in time sublinear to d. Meanwhile, even with constant ∇ i g(x), it still requires at least O((2d) c log(d)) times of inner products of dimension n + 1 for some constant c [34].
However, we have shown that for general composite form f (Ax) + g(x) with much more relaxed requirements on the regularizer g, we are able to select and update each coordinate with constant times of inner products on average while achieving linear convergence. Therefore the usage of these tricks applied on FW method (MIPS as well as the nearest neighbor search [6]) is completely dominated by our contribution and we omit them in the main text of this paper.

B.1 Derivation of Primal-Dual Formulation
We use Von Neumann-Fan minimax theorem for the whole derivation when swapping each min-max formula [7]. For the last equality, there is a convex constraint in the minimization part. Although the original Von Neumann-Fan doesn't have constraints, it naturally applies to the case when x (assuming function is convex to x) is bounded in a convex set, since we could change f (x, y) to f (x, y) + I C (x), where I C (x) = 0 if x ∈ C and ∞ otherwise. Then the property will be properly inherited.

B.2 Notation and simple facts
Recall primal, dual and Lagrangian forms: Similar to the definitions in [24], we introduce the primal gap defined as ∆ . Recall the assumptions: • f i is convex and β-smooth, and is α strongly convex over some convex set, and linear otherwise.
• g is µ-strongly convex and L-smooth.
To begin with, it is easy to verify that f * i is 1/β-strongly convex and is 1/α-smooth on a convex set and infinity otherwise (See Claim B.6). For simplicity we first assume α ≥ 1 2 β and then generalize the result. Claim B.1.
• Based on our update rule, ∃g ∈ ∂ y 1 n i f * i (y (t) ), such that y (t) And our update rule ensures that I (t) consists of indices i ∈ [n] that maximizes | 1 n a i x (t) − g i |.

B.4 Primal Dual Progress
In order to get a clue on how to analyze the dual progress, we first look at how the primal and dual evolve through iterations. For an index set I and a vector y ∈ R n , denote y I = i∈I y i e i ∈ R k as the subarray of y indexed by I, with |I| = k. Recall Algorithm 1 selects the coordinates to update in the dual variable as I (t) .
Proof. Notice we have claimed that −D(y) is 1 β -strongly convex and for all g ∈ ∂ y 1 n n i f * i (y (t) ), Meanwhile since −L(x, y) is 1 α -smooth over its feasible set, Also, with the update rule of dual variables, we could make use of Eqn. (19) and re-write Eqn. (20) as: Together we get: Therefore we will connect the progress induced by − y (t) − y (t−1) and dual gap ∆ (t) d next.

B.5 Dual progress
Claim B.4. An α-strongly convex function f satisfies: This simply due to Since −D is 1 β -strongly convex, we get whereĪ is a set of size k that maximizes the values of A ix (t) − g i .
With the relation between 1 n A I (t) x (t) − g I (t) and y (t) − y (t−1) we finish the proof.

B.6 Convergence on Duality Gap
Now we are able to merge the primal/dual progress to get the overall progress on the duality gap.
(from Eqn. (21) and (22)) Similarly to the previous setting, we get the whole primal-dual progress is bounded as follows: Therefore, when we set a proper k and δ such that β Rβ nµ ) log 1 ) iterations for the duality gap ∆ (t) to reach error.

B.7 Smooth Hinge Loss and Relevant Properties
Smooth hinge loss is defined as follows: Our loss function over a prediction p associated with a label i ∈ {±1} will be f i (p) = h(p i ). The derivative of smooth hinge loss h is: Its convex conjugate is: Notice since f i (p) = h( i p), f * i (p) = h * (p/ i ) = h * (p i ).
Claim B.6. For a convex and β-smooth scalar function f , if it is α strongly convex over some convex set, and linear otherwise, then its conjugate function f * is 1/β-strongly convex, and it is a 1/α-smooth function plus an indicator function over some interval [a, b].
Proof. To begin with, since f (x) ≤ β, ∀x, meaning f is β-smooth, then with duality we have f * is 1/β strongly convex [16]. Secondly, since f is α strongly convex over a convex set, meaning an interval for R, therefore f could only be linear on (−∞, a] or [b, ∞), and is α-strongly convex over the set [a, b] (Here for simplicity a < b could be ±∞).  y − a), ∀y ≤ a, and similarly

B.8 Convergence of Optimization over Trace Norm Ball
The convergence analysis for trace norm ball is mostly similar to the case of 1 ball. The most difference lies on the primal part, where our approximated update incur linear progress as well as some error.
Proof. Refer to the proof in [1] we have: L(X (t+1) , Y (t) ) − L(X (t) , Y (t) ) ≤ (1 − µ 8L ) L(X (t) , Y (t) )) − L(X (t) , Y (t) ) + µ 16L Now move the first term on the RHS to the left and rearrange we get: Therefore we get: Now back to the convergence guarantees on the trace norm ball. Figure 3: Convergence result comparison of different algorithms on smoothed hinge loss by varying the coefficient of the regularizer. The first row is the results ran on the rcv1.binary dataset, while the second row is the results ran on the news20.binary dataset. The first column is the result when the regularizer coeffcient µ is set to 1/n. The middle column is when µ = 10/n, and the right column is when µ = 100/n.

C More Results on Empirical Studies
C.1 More experiments with 1 norm To investigate more on how our algorithms perform with different choices of parameters, we conducted more empirical studies with different settings of condition numbers. Specifically, we vary the parameter µ that controls the strong convexity of the primal function. Experiments are shown in Figure 3.


SECURE TRANSMISSION OF DATA USING IMAGE STEGANOGRAPHY

Data is one of the most relevant and important term from the ancient Greek age to modern science and business. The amount of data and use of data transformation for organizational work is increasing. So, for the sake of security and to avoid data loss and unauthorized access of data we have designed an image Steganographic algorithm implementing both Cryptography and Steganography. This algorithm imposed a cipher text within a cover image to conceal the existence of the cipher text and the stego-image is transferred from sender to intended receiver by invoking a distributed connection among them to achieve the data authenticity.

INTRODUCTION
As a part of information security "Steganography" is a wellknown concept, literally which signifies the meaning "covered writing" [12]. Steganography imposes the secret information within a cover object termed as stego-medium to escape detection and to retain the original information with minimum distortion. This stego-medium appears like a non-secret file in the network and manages to avoid drawing the attention towards itself as a content of security.
secret-information + cover-medium = stego-medium (1) Steganography had been widely used for secure communication [3]. The schemes used at this age are the physical process of Steganography. In modern digital steganography information is first encrypted. Then using an embedding algorithm in the transport layer encrypted information is embedded with the cover medium and transmitted over the network [10] [11]. Both cryptography and steganography provide data confidentiality and authenticity. In contrast to cryptography which focuses on keeping the message secret while the existence of secret message may tempt the attacker whereas Steganography hides a message as well as the very existence of secret information [5]. Cryptography ensures privacy of message and structure of the message alter whereas steganography ensures the secrecy of message and the structure of message does not alter [7] [3]. Steganography may use in conjunction with cryptography by concealing the existence of the ciphered text so that the information is more secure [4].
Media formats .JPEG, .BMP, .GIF, .MP3, .text etc. are suitable as cover medium because of their high degree of redundancy and availability and popularity over internet [6]. Depending on what type of cover-medium used, steganography is classified as audio steganography uses .WAV, .MP3 media formats, video steganography uses .MPEG, .AVI, image steganography uses .JPEG, .BMP, .GIF media formats. Audio steganography utilize the Psycho acoustical property of human auditory system (i.e. the presence of low-pitched sound is undetected in presence of a louder sound) and inserting data into digitalized audio-signals. LSB coding, phase coding, spread spectrum are some popular method of audio steganography. Video Steganography embedded the message within the video files. Due to its large size video Steganography is eligible to hide large amount of data. Image steganography technique utilize the weakness of human visual system [8] and embedded the information with a minor modification in image pixels. LSB coding, masking and filtering etc. are the image steganography method.

LITERATURE REVIEW
In [13], Guo and Le measured the quality factor of JPEG images by maintaining quantization tables and performed some permutations along with this scheme to transmit a hidden file. Authors in [14] combined cryptography with steganography by first encrypting a message using Vernam cipher and then embedding it with an image using LSB technique with shifting. Seethalakshmi et al. [15] implemented neural networks to identify best locations in the host image to embed the secret data. Patel and Meena superimposed dynamic cryptography with steganalysis [16]. The LSB of the picture element is modified with the MSB of it and pixel selection is done using pseudo random number.
Abood combined image cryptography with steganography [17]. Both encryption and decryption are done using RC4 stream cipher and a hash function along with RGB pixel shuffling are used for steganalysis. The authors in [18] proposed two quantum image hiding strategies. A steganography quantum approach is proposed to hide an image in another image file. Secondly, a quantum watermarking approach is used to hide a water-marked gray image to a carrier image. Qo et al. proposed a quantum steganography approach using matrix coding for quantum color images [19].

CONTRIBUTION
To make a secure and imperceptible transaction of information, we have proposed a technique to hide the encrypted text within an image by combining the cryptography and steganography process. In our proposed method we first encrypt the plain text using public key cryptography algorithm RSA of 50bit. Then choose a JPEG image as cover and read the headerfooter of this image in an array buffer. We generate the Stegoimage by including the cipher text at the end of the footer.

METHODS USED
Among various methods of Cryptography and Steganography we have used RSA algorithm and Image Steganography method.

RSA Algorithm:
Rivest et al. invented RSA [1] algorithm and it is widely used public key cryptography algorithm having two algebraic structures: a public key R = Zn + X and a private group G = Z(∅(n)) * X. In RSA algorithm two prime numbers (p and q) are taken initially and their products are used to generate the public key and private key. Public key consists of a value n and e, called modulus and public exponent respectively. Private key termed as d is called private exponent. The public key and private key generation of RSA algorithm is as follows: Step 1: Choose two large, random prime number p and q, such that p ≠ q.
Step 2: Compute modulus n as n = p×q.
Step 4: Select the public exponent e, where 1 < e < Ø(n) and e is a co-prime of Ø(n).

Image Steganography:
Image Steganography uses digital image as cover object to hide the information as it contains huge amount of redundant bits [9]. Images are divides into a matrix of pixels and each pixel is represented by bit pattern. Generally images are represented by 24bit or 8bit pixel either in the form of a binary file where each pixel represents three colors Red, Green and Blue (RGB) for color image or as a gray scale image [9]. In image steganography information is hidden within an image with a minor modification in the image pixels. In the specific domain of digital image various image formats exist for different applications such as JPEG (Joint Photographic Experts Group), GIF (Graphical Interchange Format), BMP etc. [3].
In this paper, we have used a .jpeg file as a cover medium. The original text is first encrypted using the well-known RSA cryptography algorithm. The generated cipher text is hidden behind the .jpeg image file for secure transmission of the data to the receiver. The encrypted text is appended at the end of the image file and finally the stego file is exposed through an RMI architecture for different Client-Server actions.

RMI Architecture:
Remote Method Invocation [2] allow programmers to develop a distributed object application. RMI creates a Client-Server relationship. The Server application creates an object and makes it accessible remotely. A Client application receives a reference to the object on the server and then invokes the method on it. The interface uses by the Client and Server objects to create a remote connection is provided through stubs and skeleton, remote reference and transport layer protocol. A simple Client/Server application is created by using the following step.
Step 1: Enter and Compile the Source Code: This application uses four source files-first file, which defines the remote interface that is provided by the server, second source file implements the remote interface, third one contains the main program for the server machine and fourth one implements the client side of this distributed application.
Step 2: Generate Stubs and Skeleton: Stubs reside on the client machine to present the same interfaces as the remote server.

Step 3: Install files on Client and Server
Step 4: Start the RMI registry on server machine Step 5: Start the server Step 6: Start the Client

PROPOSED ALGORITHM
This section presents a step-by-step solution to the problem described above. The encryption algorithm at the Sender's end and decryption algorithm at the Receiver's end are detailed below.

Encryption Algorithm (Sender's end):
Step 1: Select the text file where the original message has been written.
Step 2: Encrypt the content of the text file using the RSA algorithm with the public key of the receiver.
Step 4: Read the header and footer of the selected image in an array buffer.
Step 5: Add the encrypted data at the end of image footer.
Step 6: Sender and receiver are connected to the network.
Step 7: Sender provides the receiver's IP address and then send the Stego-image if the IP address is valid.
Step 2: Extract the encrypted message from the end of the stegoimage by reading the image footer.
Step 3: Generate the private key and decrypt the extracted message and then create a text file.
Step 4: Save the text file at the desired location.

Key Used:
The privacy of any cryptography or steganography algorithm depends on the size of the key used. In the proposed algorithm, we have used the RSA algorithm for encrypting the text data. In RSA, two large random prime numbers are generated and are processed to create the private and public keys. These prime numbers need to be kept secret. The length of the RSA key depends on the number of bits used in the modulus function. In this algorithm, we have used keys of size 2048 bits.

Fig.1. Flowchart of proposed algorithm
The flow diagram (shown in Fig.1) of the proposed work has been explained in this section. Initially receiver asks the sender for connection establishment over the internet. Once they are connected, the sender starts the file transfer process. For secure transmission of the text file, sender applies an integrated approach by combining cryptography with image steganography.
The sender first encrypts the text file using RSA cryptography algorithm and then hides the cipher text behind an image for secure propagation. After validation of the receiver's IP address, the image stego file is sent to the receiver. The latter upon reception extracts the encrypted text message from the image file and decrypts it to get the original message.

DATA FLOW DIAGRAM
This section illustrates the proposed technique through data flow diagrams. The Fig.2 and Fig.3 presents the context level and first level of the data flow diagram for the proposed strategy. In the context level, entire method is covered by a single process leveled 0. It performs five major operations-encryption of the original text file, hiding the cipher text behind an image file, transmission and reception of the stego file, extraction of the encrypted text from the image file at the receiver's end and finally decryption of the cipher text to get the original message.

ILLUSTRATION OF PROPOSED METHOD
The proposed method involves the process of encrypt the text file into an image, extraction of original text from stego image and final output.

Process of Encrypting the Text File into an Image:
As we stated to enhance the security level at first we have encrypted the plain text then we apply the Steganography method on this encrypted text. First we take a .txt or .doc file as plain text and read it. Then encrypt this plain text using RSA algorithm of key size 50 bits. We have chosen JPEG image as cover image. Then read the header and footer of this image and stored into an array buffer. We have added the ciphered text at the end of footer of the selected cover image and generated the stego image. The stego image is then sent to the intended receiver through a distributed connection between them, which we have created using the RMI architecture.  Fig.4 presents the sender's interface through which he/she selects the text file to be sent and the image file for embedding the encrypted text file. The sender then selects "Encrypt" button to start the crypto-stego integrated approach.

Extracting Original-Text from Stego-Image:
After receiving the Stego image, receiver first extract the Cover Image and Cipher Text. Then de-cipher cipher text and create a text file which contains the plain text. Then save the text file to its preferable location. The Fig.5 presents the interface for the Receiver where upon selection of the "Extract and Decrypt" button the entire process of cipher text decryption and original message extraction is done.

Final Output:
The Fig.6 shows the original image we have used as cover image to hide the text and Fig.7 shows the same image after imposing the cipher text within it. Interestingly, both original and stego images are indistinguishable. Camouflaging an encrypted pattern to an exactly natural image is intended for fooling eavesdroppers. The quality factors of the original image is managed by embedding each pixel of the stego image to a specific region.

CONCLUSION AND FUTURE SCOPE
At this age of civilization exchanging data for communication through the network is an integral part of every organization and every sector of society. Our proposed algorithm is to secure this communication with a secure communication system by creating a distributed connection. This algorithm imposed an encrypted text which has been encrypted by using the RSA algorithm within a JPEG image and then the image file is send over the network i.e. we combining the concept of Cryptography and Steganography to make an illusion to the hacker that the sender sends an unsuspicious media file to the receiver. As an image file appear in the network as an innocent media file so it does not attract the hacker as a content of security. In this algorithm Cryptography makes the data secure as a cipher text and Steganography makes this cipher text disguise so that no one other than the intended receiver can know the existence of the cipher text within the image file. Here we have embedded the encrypted text at the footer of the chosen JPEG image file. In future our work will be focused on to embed the text within the image pixel and we will work to eradicate the problem of lossy compression related to the JPEG image and extend our work on other image formats like .BMP, .GIF etc..