On Combining Feature Selection and Over-Sampling Techniques for Breast Cancer Prediction

: Breast cancer prediction datasets are usually class imbalanced, where the number of data samples in the malignant and benign patient classes are signiﬁcantly different. Over-sampling techniques can be used to re-balance the datasets to construct more effective prediction models. Moreover, some related studies have considered feature selection to remove irrelevant features from the datasets for further performance improvement. However, since the order of combining feature selection and over-sampling can result in different training sets to construct the prediction model, it is unknown which order performs better. In this paper, the information gain (IG) and genetic algorithm (GA) feature selection methods and the synthetic minority over-sampling technique (SMOTE) are used for different combinations. The experimental results based on two breast cancer datasets show that the combination of feature selection and over-sampling outperform the single usage of either feature selection and over-sampling for the highly class imbalanced datasets. In particular, performing IG ﬁrst and SMOTE second is the better choice. For other datasets with a small class imbalance ratio and a smaller number of features, performing SMOTE is enough to construct an effective prediction model.

Introduction
Breast cancer, which is cancer that develops from breast tissue, is one of the important problems in the medical domain. It is the second most severe cancer among all of the cancers that have already been discovered. Some factors have been found to cause breast cancer, such as obesity, a lack of physical exercise, alcoholism, hormone replacement therapy during menopause, ionizing radiation, a family history of breast cancer, etc. [1]. In practice, many medial institutes have paid much attention to the early detection of breast cancer.
In related literatures, many data mining and machine learning techniques have been used to develop various kinds of breast cancer prediction models. Among them, some focus on the improvement of learning models and some focus on data pre-processing steps. For example, convolutional neural networks (CNN), as one representative of a deep learning technique, were modified to improve their prediction performance [2,3]. On the other hand, some studies focus on feature selection for filtering out irrelevant features from a given dataset for the construction of more effective classifiers [4,5] and data sampling Appl. Sci. 2021, 11, 6574 2 of 9 for re-balancing class imbalanced datasets in order to decrease the effect of skewed class distribution in the learning process [6,7].
For related works of feature selection, Sasikala et al. [8] propose a novel feature selection method based on the genetic algorithm to select a gene subset from high dimensional gene data, which causes different classifiers perform better than the ones without feature selection. In [9], a genetic algorithm is used for feature selection, where the selected subset is used to construct different classifiers for performance comparisons. On the other hand, Jiang and Jin [10] use a gradient boosting decision tree with Bayesian optimization to remove the irrelevant and redundant features from gene expression data. Raj et al. [11] compare several feature selection methods to determine the best one to combine with the random forest classifier.
For related works on class imbalance learning, Zhang et al. [12] propose a clusteringbased under-sampling method to select informative samples from the clusters identified in the majority and minority classes, and the decision tree based on this boosting technique is employed for the prediction model. In [13], eighteen different under-and over-sampling methods are used to balance related class imbalanced cancer datasets, in which the oversampling methods perform better than the under-sampling ones. Cai et al. [14] apply the synthetic minority over-sampling technique (SMOTE) to balance the training dataset and employ the stacking ensemble method to combine multiple classifiers, which achieved better performance than conventional methods. Rani et al. [15] investigated the effect of performing SMOTE on five different classifiers to determine the best one for breast cancer prediction.
According to Fernandez et al. [16], SMOTE over-sampling can benefit from the use of feature selection, where feature selection is performed over the class imbalanced dataset to select a subset feature of it, and then the reduced dataset is over-sampled to make it contain the same size of the data samples as in the majority and minority classes. Recently, Solanki et al. [17] propose the contrary procedure that SMOTE be performed first to rebalance the breast cancer dataset, and then wrapper-based feature selection methods can be applied to reduce the feature dimensions.
However, to the best of our knowledge there is not any study examining the performances of both procedures to combine feature selection and over-sampling for breast cancer prediction. Therefore, the research objective of this paper is to compare these two combination orders with two baselines by employing feature selection and oversampling individually. Particularly, filter and wrapper-based feature selection methods are combined with SMOTE for performance comparison. In addition, one small-and one large-scale breast cancer datasets are used in order to understand the performance of different approaches.
The contribution of this paper is two-fold. First, the procedures of combining the feature selection and over-sampling steps are compared in terms of breast cancer prediction, which has never been done before. Second, the best combination procedure and combined algorithms that will be identified in this paper can be used as one the representative baseline methods for future research.
The rest of this paper is organized as follows. Section 2 overviews related literature on feature selection and over-sampling. Section 3 describes the two different combination procedures and the experimental setup. Section 4 presents the experimental results, and Section 5 concludes the paper.

Feature Selection
Feature selection is an important data pre-processing step in data mining and knowledge discovery from databases. It focuses on selecting representative features from a given training set, which have higher discriminative power to make classifiers better able to distinguish between different classes. Moreover, another advantage of feature selection is to reduce feature dimensionality, which lowers the computational complexity during the classifier training stage [5,18].
In general, feature selection algorithms are composed of four basic steps, which are a generation procedure to generate the candidate feature subset, an evaluation function to evaluate the effectiveness of the feature subset, a stopping criterion to determine when to stop the previous steps, and a validation procedure to examine whether the feature subset is valid [19].
Existing feature selection algorithms can be divided into filter, wrapper, and embedded methods depending on how they combine the feature selection search with the construction of the classifiers. In filter methods, the relevance of features such as distance, consistency, dependency, information, and correlation are assessed,. That is, the feature relevance score is calculated, in which low-scoring features are removed. Some representative methods include relief, the Fisher score, and information gain.
In wrapper methods, a specific classification algorithm is used to determine the quality of different subsets of features. Since the space of feature subsets can grow exponentially with the number of features, heuristic search methods are used to guide the search for an optimal subset. Therefore, wrapper methods are very computationally intensive, especially when the construction of the chosen classifier requires a high computational cost. One representative wrapper method is the genetic algorithm.
In embedded methods, feature selection is incorporated as part of the classifier training process. That is, the feature selection method is embedded in the modeling algorithm, where the classifier is used to evaluate the quality of the selected subset of features. Embedded methods have the advantage of including interaction with the classification model, while at the same time being far less computationally intensive than wrapper methods. One representative wrapper method is the decision tree classifier.

Over-Sampling
In practice, the class imbalanced dataset problem usually occurs since the number of data samples in one class are significantly different from those of the other one; say the imbalance ratio is 1:100. For the example of breast cancer datasets, they do not usually contain both the malignant and benign patient classes, denoted as the minority and majority classes, respectively. Without dealing with the class imbalance problem, most machine learning models aim at maximizing the accuracy of its classification rule by ignoring the minority class examples, with the classification of all testing examples being organized into the majority class [6].
In general, there are three types of solutions to the class imbalance problem, which are algorithm level, data level, and cost-sensitivity methods. Among them, the data level methods based on data sampling techniques are usually considered first since they are used independently of the classifier [6]. Data sampling techniques focus on re-balancing the given training set. Particularly, under-and over-sampling techniques have been used, in which the former is for reducing the size of the majority class, whereas the latter is used for enlarging the size of the minority class. Among them, the synthetic minority over-sampling technique (SMOTE) is one representative method, which has been used as the baseline in many related studies [16].
The aim of SMOTE is to produce new synthetic examples for the minority class. For example, a minority class instance i is selected as the basis to create new synthetic data. According to a specific distance metric, usually the Euclidean distance, the number of the neighbors nearest to i are chosen from the training set, e.g., i 1 , i 2 , and i 3 . Next, a randomized interpolation is conducted to obtain new synthetic data, i.e., s 1 , s 2 , and s 3 .

Two Combination Orders for Feature Selection and Over-Sampling
In this paper, two orders of combining the feature selection and over-sampling steps are compared by being given a training set, denoted as TR, which is composed of M and N Appl. Sci. 2021, 11, 6574 4 of 9 majority and minority class data samples, respectively, and each data sample is represented by k dimensional features. For the first order, i.e., performing feature selection first and over-sampling second, a chosen feature selection algorithm is employed to select some representative features from the TR. As a result, a reduced feature subset of TR is produced, denoted as TR reduced , where each data sample is represented by o dimensional features (k > o). Next, the over-sampling algorithm is used to generate M-N synthetic data samples for the minority class, leading to a balanced training set, denoted as TR reduced_balanced , which is composed of 2M data samples. That is, the number of data samples in the majority and minority classes are the same.
On the other hand, for the second combination order, the over-sampling algorithm is used first to re-balance the training set, i.e., TR, which results in a balanced training set, denoted as TR balanced . TR balanced is composed of 2M data samples, and each data sample is represented by k dimensional features. Next, the chosen feature selection algorithm is performed over TR balanced , leading to a reduced feature subset of TR balanced , denoted as TR balanced_reduced . In TR balanced_reduced , each data sample is represented by p dimensional features (k > p). Note that the number of features in TR reduced_balanced by the first combination order and TR balanced_reduced by the second combination order are not necessarily the same, i.e., o = p.
Therefore, the performances of the classifiers trained by TR reduced_balanced and TR balanced_reduced can be compared individually based on the same testing set. Moreover, other classifiers trained by TR reduced through performing feature selection alone and TR balanced through performing over-sampling alone are regarded as the baseline approaches for further performance comparison.

Datasets
In order to examine the performances of both orders of combining feature selection and over-sampling, two related breast cancer datasets are considered. The first one is based on the KDD Cup 2008 breast cancer dataset (https://www.kdd.org/kdd-cup/view/ kdd-cup-2008 (accessed on 15 February 2021)), which contains 102294 data samples, and each data sample is represented by 117 different image features, which are extracted from 4 X-ray images per patient. Particularly, the class imbalance ratio is 163.2.
The second dataset is based on the Breast Cancer Wisconsin Dataset downloaded from the UCI Machine Learning Repository (https://archive.ics.uci.edu/ml/datasets/ breast+cancer+wisconsin+%28original%29 (accessed on 15 February 2021)). It is composed of 699 data samples, in which each data sample is represented by 10 features including clump thickness, uniformity of cell size, uniformity of cell shape, marginal adhesion, single epithelial cell size, bare nuclei, bland chromatin, normal nucleoli, and mitoses. In addition, the class imbalance ratio is 1.86.
To train and test the classifier, the 5-fold cross validation method is used to divide each dataset into 80% and 20% training and testing sets. This means that every subset will be trained and tested five times, and the average prediction accuracy can obtained consequently be. In other words, each patient data will be used as the training and testing data example. In addition, the class imbalance ratio of the training set in each fold is controlled to be the same as the original dataset.

The Feature Selection and Over-Sampling Methods
In this paper, the information gain (IG) as the filter method and the genetic algorithm (GA) as the wrapper method are used for feature selection. Particularly, these two methods have been used in many research problems, including text classification [20], gene expression microarray analysis [21], intrusion detection [22], financial distress prediction [23], software defect prediction [24], etc.
IG evaluates the gain of each variable in the context of the target variable, which is based on calculating the reduction in entropy. That is, the feature ranking stage focuses on Appl. Sci. 2021, 11, 6574 5 of 9 ranking the subsets of features by high information gain entropy in decreasing order. In GA, an initial set of candidate solutions (i.e., individuals) are created and their corresponding fitness values are calculated for the later cross-over and mutation steps. Specifically, the individuals are subsets of predictors, and the fitness values are measures of the model performance.
Analyses were performed using the WEKA data mining software package. Most related parameters are based on its default values, except for the genetic algorithm, where the population size, crossover rate, and mutation rate were set as 50, 0.8, and 0.01, respectively [25].
On the other hand, the over-sampling method is based on SMOTE. It has been widely used as a baseline over-sampling method for breast cancer datasets [14][15][16][17]. The percentage of synthetic instances was set to make the two datasets become balanced datasets where the malignant and benign classes contain the same numbers of data samples. Other related parameters were based on the default values of WEKA.

The Classifier Design
After the original training set TR was pre-processed by different approaches, i.e., TR reduced_balanced , TR balanced_reduced , TR balanced , and TR reduced , they were used to train the support vector machine (SVM) classifier for performance comparisons. In related literature, SVM has been widely used as the baseline classifier for breast cancer prediction [26][27][28][29].
The implementation of SVM was based on the RBF kernel function, and its related parameters were based on the default values of WEKA. Figure 1 shows the AUC (area under the ROC curve) rates of different approaches. In addition, Figure 2 shows the type I errors of the different approaches, which represent the error of miss-classifying the malignant cases into the benign class. Note that IG+SMOTE and GA+SMOTE mean the combination order of performing feature selection first and over-sampling second, whereas SMOTE+IG and SMOTE+GA represent the opposite combination order. In addition, the baseline represents using the original training set without performing any feature selection or over-sampling steps to train the SVM classifier.   As we can see, the combinations of feature selection and over-sampling can allow the SVM to provide higher AUC rates and related lower type I errors than the ones with feature selection and over-sampling alone at the baseline. More specifically, the combination order of performing feature selection first and over-sampling second outperforms the opposite combination order. In particular, IG+SMOTE is the best combined approach, which causes the SVM to provide an AUC rate of 0.788 and a type I error rate of 0.003, which significantly outperforms the others (p<0.05). On the other hand, for the feature reduction result, using IG and GA produce the selection of 94 and 14, respectively. Figures 3 and 4 show the AUC rates and the type I errors of different approaches, respectively. Different from the previous results, the approach that performed the best for the AUC was SMOTE (i.e., 0.962), whereas the second one was the baseline (i.e., 0.960). On the other hand, the approach that performed the best for the type I error is SMOTE+IG (i.e., 0.032), whereas the second-best ones are the baseline and SMOTE (i.e., 0.037). The As we can see, the combinations of feature selection and over-sampling can allow the SVM to provide higher AUC rates and related lower type I errors than the ones with feature selection and over-sampling alone at the baseline. More specifically, the combination order of performing feature selection first and over-sampling second outperforms the opposite combination order. In particular, IG+SMOTE is the best combined approach, which causes the SVM to provide an AUC rate of 0.788 and a type I error rate of 0.003, which significantly outperforms the others (p < 0.05). On the other hand, for the feature reduction result, using IG and GA produce the selection of 94 and 14, respectively. Figures 3 and 4 show the AUC rates and the type I errors of different approaches, respectively. Different from the previous results, the approach that performed the best for the AUC was SMOTE (i.e., 0.962), whereas the second one was the baseline (i.e., 0.960). On the other hand, the approach that performed the best for the type I error is SMOTE+IG (i.e., 0.032), whereas the second-best ones are the baseline and SMOTE (i.e., 0.037). The other approaches producing similar AUC results were IG (i.e., 0.959), IG+SMOTE (i.e., 0.957) and SMOTE+IG (i.e., 0.955), whereas IG+SMOTE and IG produced similar type I errors, which were0.038 and 0.044. These approaches do not have a significant level of performance difference. In particular, for the feature reduction result, using IG and GA produce 8 and 1 selected features, respectively.

The Breast Cancer Wisconsin Dataset
The experimental results based on two different breast cancer datasets indicate that when the collected dataset is highly class imbalanced and contains a certain number of features, it is better to consider the combination of feature selection and over-sampling. Particularly, performing feature selection first and over-sampling second is likely to cause the classifier to provide higher accuracy than performing over-sampling first and feature selection second.
On the other hand, if the imbalance ratio of the collected dataset is not very high and it does not contain a large number of features, there is no need to consider the combination of feature selection and over-sampling. On the contrary, performing over-sampling to rebalance the dataset is enough to allow the classifier to provide relatively good performance. other approaches producing similar AUC results were IG (i.e., 0.959), IG+SMOTE (i.e., 0.957) and SMOTE+IG (i.e., 0.955), whereas IG+SMOTE and IG produced similar type I errors, which were0.038 and 0.044. These approaches do not have a significant level of performance difference. In particular, for the feature reduction result, using IG and GA produce 8 and 1 selected features, respectively.  The experimental results based on two different breast cancer datasets indicate that when the collected dataset is highly class imbalanced and contains a certain number of features, it is better to consider the combination of feature selection and over-sampling. Particularly, performing feature selection first and over-sampling second is likely to cause the classifier to provide higher accuracy than performing over-sampling first and feature selection second.
On the other hand, if the imbalance ratio of the collected dataset is not very high and it does not contain a large number of features, there is no need to consider the combination of feature selection and over-sampling. On the contrary, performing over-sampling to re-  other approaches producing similar AUC results were IG (i.e., 0.959), IG+SMOTE (i.e., 0.957) and SMOTE+IG (i.e., 0.955), whereas IG+SMOTE and IG produced similar type I errors, which were0.038 and 0.044. These approaches do not have a significant level of performance difference. In particular, for the feature reduction result, using IG and GA produce 8 and 1 selected features, respectively.  The experimental results based on two different breast cancer datasets indicate that when the collected dataset is highly class imbalanced and contains a certain number of features, it is better to consider the combination of feature selection and over-sampling. Particularly, performing feature selection first and over-sampling second is likely to cause the classifier to provide higher accuracy than performing over-sampling first and feature selection second.
On the other hand, if the imbalance ratio of the collected dataset is not very high and it does not contain a large number of features, there is no need to consider the combination of feature selection and over-sampling. On the contrary, performing over-sampling to re-

Conclusions
Feature selection aims at selecting representative features from a given training set, whereas over-sampling is for re-balancing the class imbalanced training set. In this paper, the order of combining feature selection and over-sampling for breast cancer prediction are compared in terms of classification accuracy. In order to assess the performances of different combination approaches, the information gain (IG) and the genetic algorithm (GA) as the filter and wrapper-based feature selection methods and the synthetic minority oversampling technique (SMOTE) were employed for creation of the combinations. Moreover, two breast cancer datasets with significantly different class imbalance ratios and number of features were used for the experiments.
Regarding the experimental results, for the highly imbalanced dataset containing a large number of features, performing both feature selection and over-sampling can cause the SVM classifier provide higher AUC rates than performing feature selection and oversampling alone as well as at the baseline. In particular, it is recommended to execute feature selection first and over-sampling second. On the contrary, for the dataset with the low imbalance ratio and small number of features, performing over-sampling alone is the better choice.


extfieldsofstudy:
Computer Science
Mathematics

text:
RWNE: A Scalable Random-Walk based Network Embedding Framework with Personalized Higher-order Proximity Preserved

Higher-order proximity preserved network embedding has attracted increasing attention recently. In particular, due to the superior scalability, random-walk based network embedding has also been well developed, which could efficiently explore higher-order neighborhood via multi-hop random walks. However, despite the success of current random-walk based methods, most of them are usually not expressive enough to preserve the personalized higher-order proximity and lack a straightforward objective to theoretically articulate what and how network proximity is preserved. In this paper, to address the above issues, we present a general scalable random-walk based network embedding framework, in which random walk is explicitly incorporated into a sound objective designed theoretically to preserve arbitrary higher-order proximity. Further, we introduce the random walk with restart process into the framework to naturally and effectively achieve personalized-weighted preservation of proximities of different orders. We conduct extensive experiments on several real-world networks and demonstrate that our proposed method consistently and substantially outperforms the state-of-the-art network embedding methods.

Introduction
Network embedding, which has recently attracted increasing attention in both academia and industry, is a general and fundamental technique for representing nodes of a network as vectors in a low-dimensional space Goyal and Ferrara 2018;Cai, Zheng, and Chang 2018). Such embedding vectors can then be used for a variety of network mining tasks, such as node profiling (classification and clustering) (Sen et al. 2008;, link prediction (Shi et al. 2015;Wei et al. 2017), similarity search (Sun et al. 2011;Sun et al. 2012;Zhou et al. 2017), etc.
One basic requirement of network embedding is that the learned vectors of nodes should preserve the network structures. Along with this direction, many network embedding methods are proposed to preserve the first-order proximity which expresses the local pairwise structure indicated by the observed edges between nodes (e.g., (Roweis and Saul 2000;Belkin and Niyogi 2002;Tang and Liu 2011;Ahmed et al. 2013)), or further to preserve the second-order proximity between a pair of nodes which implies the similarity be-tween their neighborhood structures (e.g., (Tang et al. 2015;. Despite their success, in recent years, more and more works (Cao, Lu, and Xu 2015;Ou et al. 2016;) have demonstrated that, besides the first-and second-order proximity directly indicated by pairwise edges, the higher-order proximity is also of tremendous importance in capturing the underlying structures of the network. First, differentorder proximities describe the network structures from different levels of scope, which give us much valuable information with different granularities. Thus, embeddings with the lower-order proximity alone do not necessarily perform best on all networks and target applications (Perozzi et al. 2017;. For example, in classification tasks with coarser-grained classes, the higher-order proximity is likely to be more helpful than lower-order proximity. Second, real-world networks are usually very sparse, with only a small number of edges observed. That is, the observed first-order proximity and even second-order proximity may not be sufficient to reflect the underlying relations between nodes (Tang et al. 2015). Therefore, to address the network sparsity issue, it is also very important to incorporate higherorder proximity to capture more available information.
Although many works have been recently proposed to preserve the higher-order proximity in network embedding, most of them are developed to explicitly exploit the higherorder proximity matrix by the technique of matrix factorization (e.g., (Cao, Lu, and Xu 2015;Ou et al. 2016;) or deep learning (e.g., Cao, Lu, and Xu 2016)), which are known to have scalability issues when dealing with large-scale networks . In order to be more efficient, inspired by the Skipgram algorithm (Mikolov et al. 2013), random walk based network embedding algorithms have also been well developed (Perozzi, Al-Rfou, and Skiena 2014;Tang et al. 2015;Grover and Leskovec 2016;Perozzi et al. 2017). In general, these algorithms use a two-step approach to generate nodes embeddings. First, they perform random walks on a network to generate nodes sequences. Then they run the Skipgram algorithm over these sequences to generate nodes embeddings. Although these random walk based algorithms are known for having superior scalability for large-scale net-works and having ability for exploring higher-order neighborhood via multi-hop random walks, there are still some issues. First, they either treat different-order neighborhood equivalently (Perozzi, Al-Rfou, and Skiena 2014) which may not be expressive enough to incorporate a personalized combination of proximities of different orders, or use a complex second-order biased random walk (Grover and Leskovec 2016) which can be costly when pre-computing its third-order transition probability hypermatrix . Second, in essence, these algorithms convert the network embedding problem as the word embedding problem by treating a node as a word and pre-generating the node "corpus" via random walks. As a consequence, they have no specific objective to articulate what and how network proximity is preserved and have no sound theory to estimate the essential role of random walk playing in network embedding, which also limits their superiority.
In this paper, to address the above issues, we present a general scalable Random Walk based Network Embedding framework (called RWNE), in which arbitrary higher-order proximity of the network can be explicitly preserved with a sound objective carefully designed to simultaneously capture both the local pairwise similarity and the global listwise equivalence between nodes. More than that, to make the framework efficient and practical for large-scale networks, we theoretically show that the above objective can be equivalently optimized by sampling the nodes via the random walk process with the probability proportional to the proximity, which clarifies why and how we can use random walks to preserve arbitrary user-specified network proximity and reversely explains what and how network proximity is preserved for an arbitrary user-specified random walk. Further, we introduce the random walk with restart process to naturally and effectively achieve personalized-weighted preservation of different-order proximities with an elegant attenuation function controlled by a personalized teleport probability. Finally, we conduct extensive experiments on six realworld networks over three classical network mining tasks: multi-label node classification, node clustering, and link reconstruction. The experimental results demonstrate that our proposed method consistently and substantially outperforms the state-of-the-art network embedding methods. To summarize, the main contributions of our work are as follows: 1. We systematically present a general scalable randomwalk based network embedding framework in which random walk is efficiently and explicitly incorporated into a sound objective designed theoretically to preserve arbitrary higher-order proximity.
2. We further introduce the random walk with restart process to practically preserve the personalized higher-order proximity which naturally weights different-order proximities with an elegant attenuation function controlled by a personalized teleport probability.
3. We conduct extensive experiments on several real-world networks and demonstrate that our proposed model consistently and considerably outperforms the state-of-the-art network embedding methods.

Related Work
Network embedding has aroused lots of research interest. The earlier network embedding algorithms, also called graph embedding, are studied as a dimension reduction problem, such as LLE (Roweis and Saul 2000), Laplacian eigenmaps (Belkin and Niyogi 2003), etc. These methods focus on the first-order proximity which models the local structure of the network. Recently, to sufficiently explore the network structure from different levels of scope, a bunch of methods have been proposed to preserve the higher-order proximity in network embedding. Most of these methods are proposed to explicitly factorize a higher-order proximity matrix, such as GraRep (Cao, Lu, and Xu 2015), HOPE (Ou et al. 2016), M-NMF , NetMF (Qiu et al. 2018), AROPE , etc. However, in principle, as the computation and storage of higher-order proximity matrices are generally at least O(|V| 2 ) complexity, these matrix-factorization methods often have efficiency issues when dealing with large-scale networks. Besides, deep learning is also studied in preserving higher-order proximity. For example, SDNE  first applies a deep auto-encoder to preserve both 1stand 2ndorder proximity. DNGR (Cao, Lu, and Xu 2016) further uses a stacked denoising auto-encoder to preserve higherorder proximity. Unfortunately, same as matrix-factorization methods, these methods also confront efficiency issues. Specially, deep convolution networks are popularly applied on graphs in very recent years (e.g. GCN (Kipf and Welling 2017) and GAT (Velickovic et al. 2018)), which are studied as supervised/semi-supervised feature learning models with node attributes/features incorporated. We also compare with these methods, but it is noteworthy that in this paper we focus on the most fundamental case that only the network structure information is available.
On the other hand, due to the superior scalability, randomwalk based network embedding algorithms have also been well developed. In general, these algorithms use a twostep framework to generate node embeddings: first perform random walks on a network to generate nodes sequences and then run the Skipgram algorithm (Mikolov et al. 2013) over these sequences to generate nodes embeddings. For example, DeepWalk (Perozzi, Al-Rfou, and Skiena 2014) uses uniform random walks to generate node sequences and then runs the Skip-gram algorithm. Node2vec (Grover and Leskovec 2016) further generalizes a second-order biased random walk to seek a trade-off between breadth-first and depth-first graph searches. Despite their success, as introduced in Section 1, there are still some issues. In this paper, instead of the above two-step framework, we focus on a straightforward framework by explicitly incorporating random walk into a sound objective designed theoretically to preserve personalized higher-order proximity.

Problem Formulation
We formulate the normalized adjacency matrix (denoted as A) as the first-order proximity matrix, which captures the direct neighbor relations between nodes (Tang et al. 2015;. Specially, such first-order proximity can be alternatively viewed as the transition probability of a single step of random walk over the network. Then, in the probabilistic setting based on random walk, we can easily generalize it to kth-order proximity A k (Cao, Lu, and Xu 2015): the transition probability of a random walk with exactly k steps, which represents the k-hop relations between nodes. As proximities of different orders explore the relations from different levels of scope, which all can provide valuable information to guide the embedding, a desirable embedding model for real-world networks must be capable of preserving a delicate integrated higher-order proximity which combining the proximities of different orders as follows: where β k is the weight to control the prestige of kth-order proximity A k , and the sum of all weights In the rest of this section, we will systematically present a general scalable random-walk based network embedding framework, called RWNE, which is able to effectively and efficiently preserve the above integrated higher-order proximity. Without loss of generality, we first describe the RWNE model to directly preserve a general form of higher-order proximity D with arbitrary weights. Then, we show a superior optimization with random-walk simulation, which makes the model computationally efficient and scalable for large-scale networks. We further introduce the random walk with restart process to naturally adjust the prestiges of different-order proximities by a personalized teleport probability. Finally, we briefly analyze the time complexity of RWNE.

Preserving Higher-order Proximity
Local Pairwise Similarity. Given a higher-order proximity matrix D integrating all orders from the 1-st to the k-th (as defined in Eq. (1)), it is straightforward that each entry D ij implies the local pairwise similarity between each pair of nodes (v i , v j ) in view of the integrated relation from different levels of scope (from 1-hop to k-hop). If D ij > 0, there is a similarity between v i and v j , and the larger D ij is, the more similar v i and v j are; If D ij = 0, they have no similarity. Therefore, we can directly use each entry D ij to constrain the similarity of the embedding vectors of each pair of nodes (v i , v j ). Before that, we first define a normalized cosine distance as follows, which is used to measure the similarity of the embedding vectors: where v i is the embedding vector of node v i . Then, instead of a naive treatment which rigidly sets D ij as the target similarity and minimizes the error loss between D ij and sim(i, j), we propose a new loss to measure the similarity cost of each pair of nodes (v i , v j ) in the embedding space: There are two subtleties in our careful design of Eq. (3). First, though under normalization, one proximity may have different weight from one similarity score, which means rather than treating proximity as the exact target similarity, it can only be concluded that the larger proximity is, the more similarity is. And that is why we abandon the aforementioned naive treatment. In our design, we impose a penalty to push v i and v j embedded similarly and set D ij as the penalty coefficient to guarantee that larger proximity will incur more penalty and thus generate a stronger push to be similar. Second, there is an exception that zero proximity expresses the dissimilarity, which is essentially different from positive proximity. Thus we separate out the zero proximity and set an opposite penalty for it, i.e., impose a penalty to push v i and v j embedded dissimilarly.
Then, by using the loss of Eq.
(3) for all pairs of nodes, the objective function to preserve the local similarity is defined as follows: Minimizing Eq. (4) pushes the similarity of the embedding vectors of v i and v j towards 1 if proximity D ij is large (The larger the proximity, the stronger the push) and pushes it towards 0 if D ij = 0. As a result, we preserve the local pairwise similarity between nodes.
Global Listwise Equivalence. In addition to the local similarity, we can extract more information by considering the relative equivalence. For instance, for three nodes v i , v j , v k with D ij = D ik = D jk = 0.1, the local similarity between v i and v j may be very weak in view of the strength of D ij . However, in a relative view, we can conclude that v i and v j is equivalent in v k 's viewpoint, because they distribute the equal proximity with v k . Further, if for the listwise proximity distribution D i =(D i,1 , D i,2 , · · ·, D i,|V| ) and D j =(D j,1 , D j,2 , · · ·, D j,|V| ), v i and v j always have the above equivalence (i.e., D ik ≡D jk for ∀k=1, · · ·, |V|), we can conclude that v i and v j play an equivalent global structure role in the whole network. We refer to the above information as the global listwise equivalence. Note that some works (Tang et al. 2015) extract the similar information from first-order proximity. We differentiate them in the aspects where we provide a more definite meaning and generalize it as a basic attribute of arbitrary higher-order proximity.
To preserve the global listwise equivalence, we propose a self-supervised component: the proximity predictor Φ(·), which is a deep architecture composed of multiple nonlinear functions to predict the proximity distribution of an input node. As shown in Figure 1, for each node v i , the predictor Φ(·) uses the embedding vector v i as the input and output a |V|-dimentional distribution Φ(i) ∈ R 1×|V| , which is the predicted approximation of proximity distribution D i . Then, supervised by D i , the predictor Φ(·) is trained to make the output Φ(i) be close to D i , which means that if we pick two nodes v i and v j with similar proximity distributions (i.e. D i = D j ), the predictor Φ(·) will be trained to learn similar outputs (i.e. Φ(i) = Φ(j)) and thus to push the input embedding vector v i and v j to be similar. Therefore, by modeling the proximity in this way, we can learn similar embeddings for nodes with similar proximity distributions. That is, we capture the global listwise equivalence between nodes.  To train the predictor Φ(·), we follow the inspiration of the design in Eq. (3) which sets the target proximity as a penalty coefficient and separates zero proximity from positive proximity, and design the loss to measure the prediction cost for each node v i as follows: Note that in principle, Φ(·) can be an arbitrarily deep neural network, but as we focus on the effort of random walk in this paper, we only use a simple single-layer architecture and leave a superior trying as future work. In this setting, the proximity predictor Φ(·) is defined as: where W∈R |V|×d , V is the nodes set, d is the embedding dimensionality; σ(·) is the logistic function.
Finally, by using the loss of Eq. (5) for all nodes, the objective function to preserve the global equivalence is defined as follows: The Joint Objective. To simultaneously preserve both the local pairwise similarity and the global listwise equivalence provided by the higher-order proximity D, we jointly minimize the following objective function, which combines Eq. (4) and Eq. (7): where (i, j) =−(γ log sim(i, j) +λ log Φ(i) j ) is the loss for positive proximity, ζ(i, j)=−(γ log(1−sim(i, j))+λ log(1− Φ(i) j ) is the loss for zero proximity; γ and λ are hyperparameters to reflect user's emphasis.

Optimization with Random Walk Simulation
In practice, an accurate computation of Eq. (1) to get the higher-order proximity matrix D with k ≥ 2 is both time and space consuming. Thus it is undesirable to directly solving the objective of Eq. (8) due to the efficiency issue, especially for large-scale networks.
To address the above issue, we highlight that D is essentially an integrated probability matrix combining the transition probabilities of a random walk in 1-st, 2-nd, · · · , k-th step with corresponding weights β 1 , β 2 , · · · , β k , where each entry D ij = β 1 A ij + β 2 A 2 ij + · · · + β k A k ij represents the weighted average hitting probability from v i to v j within a k-steps random walk. Then, Without calculating Eq. (1), we can invent a k-steps "drop-out" random walk to simulate the probability matrix D: in l-th step (for ∀l = 1, 2, · · ·, k), the walker first randomly moves from the current node to an adjacent node as a normal random walk, and then randomly drops out the current-step hitting node with the dropping probability 1−β l . By this means, the expected hitting probability from v i to v j in k steps is exactly D ij . That is to say, for each node v i , the above k-steps "drop-out" random walker starting from v i hits/samples a paired node v j with the probability D ij .
In our carefully designed objective of Eq. (8), the probability D ij is delicately and theoretically arranged as a weight coefficient. Then, in the probabilistic setting, we can equivalently treat the probabilistic real weight as a binary weight by node-sampling treatment, with the sampling probability proportional to the original real weight. That is, we can eliminate the D ij in the first term of Eq. (8) by sampling nodes with the probability D ij , which can be simulated by the aforementioned k-steps "drop-out" random walks starting from v i . Furthermore, for the second term j∈{Dij=0} ζ(i, j) in Eq. (8), as the matrix D is usually very sparse with many zero entries, we also leverage an uniform-sampling treatment to optimize it. Overall, with the node-sampling treatment, the objective function of Eq. (8) is optimized as: where T is the sampling-frequency/walk-times which can be set as the iteration epochs when solving the objective by an iterative algorithm (e.g. SGD); p 1→k i is the hitting nodes set in a k-steps "drop-out" random walk starting from v i ; E j ∼I/{p 1→k i } means an uniform-sampling with nodes {p 1→k i } excluded. Note that in each walk, as the random walker samples |p 1→k i | nodes, we also operate uniform-sampling for the equal times to ensure the fairness.
The optimized objective of Eq. (10) replaces the expensive computation of higher-order proximity with random walk simulation, and thus has superior efficiency and scalability, and can be easily mini-batch-minimized by applying an iterative algorithm. So far, we have theoretically described a general scalable random walk based embedding framework. For arbitrary user-specified weights {β 1 , β 2 , · · · , β k , · · · }, the framework is able to effectively and efficiently preserve the weighted combination of different-order proximities by deploying the aforementioned "drop-out" random walk. Reversely, for arbitrary user-specified random walk, the framework can also be used by directly minimizing the Eq. (10), However, superior to other random-walk models, the framework explicitly clarifies what and how network proximity is preserved in random-walk structure, that is the average hitting/sampling probability in k steps of the user-specified random walk is just the integrated higher-order proximity which is theoretically preserved by the objective of Eq. (8).
Random Walk with Restart. Although we have theoretically described the RWNE framework, it is still limited because there is no principled way to determine desirable weights {β 1 , β 2 , · · · , β k , · · · } or random walks. In general, it is intuitive that the relation/influence over a very long distance can be very weak, i.e., the prestige of different-order proximity is likely to decay with the distance. Therefore, instead of a normal random walk widely used in the existing models, we introduce the random walk with restart (referred to as RWR) process: in each step of a random walk, the walker can return back to the root with a personalized teleport probability α. The transition probability of RWR is recurrently formalized as: where P k is the k-th step transition probability matrix of RWR, and P 0 = I is an identity matrix; A is the single-step transition probability matrix of normal random walk, i.e., the first-order proximity matrix. Equivalently, we have: Thus, by deploying the RWR process, the integrated higherorder proximity matrix to be preserved (i.e. the average hitting/sampling probability matrix) in k steps is derived as: in which the proximities of different-orders are weighted with a function β(t)= (1+α(k−t))(1−α) t k . As Figure 2 shows, β(t) is approximately an exponentially decreasing function, and the decay rate can be freely adjusted by the personalized teleport probability α.
Finally, by deploying the RWR process, RWNE is able to effectively and efficiently preserve a personalized higherorder proximity (as shown in Eq. (13)) in which the proximities of different orders are naturally weighted with an elegant attenuation function controlled by a personalized teleport probability. The final objective of RWNE by applying the RWR process is as follows: (14) where rwr 1→k i is the hitting nodes set in a k-steps random walk with restart process starting from v i .

Complexity Analysis
In this section, we discuss the time complexity of RWNE. We use iterative algorithms (e.g. mini-batch SGD) to minimize the objective function (as shown in Eq. (14)). In each iteration, we only consider a single root node and deploy a k-steps random walk (with restart) starting from it to sample  Figure 2: The decline curves of β(t) = (1+α(k−t))(1−α) t k in different α. The k is set as 100 and each curve is normalized by β(1). k paired nodes. As random walk takes only constant time in each step (even in a weighted network, we can use Alias sampling (Walker 1977) to perform a random walk in O(1) time) and the computation of the loss for each pair of nodes also takes constant time, we can see that the complexity of each iteration (i.e., the complexity of the inner-body in Eq. (14)) is O(k). Then, given the network size |V| and the iteration epochs T , we can extract that the overall time complexity of RWNE is O(kT |V|), which is linear to the number of nodes in the network. Therefore, the proposed RWNE model is computationally efficient and scalable for large-scale networks.

Experiments
In this section, we report the experimental results. Code and data will be released in the camera-ready version.

DataSets
Here we use the following six publicly available networks.
• Cora (McCallum et al. 2000): This is a citation network with 2,708 papers, 5,429 citation links, and 7 categories.
• PubMed (Kipf and Welling 2017): This is also a citation network with 19,717 nodes, 44,338 links, and 3 categories.
• Blogcatalog (Tang and Liu 2009a): This is a social network with 10,312 nodes, 333,983 links, and 39 categories.
• Flickr (Tang and Liu 2009a): This is a social network with 80,513 nodes, 5,899,882 links, and 195 categories.
• Youtube (Tang and Liu 2009b): This is a very large network with 1,138,499 nodes, 2,990,443 links and 47 labels.

Baseline Methods and Experimental Settings
We compare our RWNE model with the following random walk based (DeepWalk, LINE, Node2vec), matrix factorization based (GraRep, HOPE), and deep learning based (SDNE, GCN, GAT) network embedding methods.
• LINE (Tang et al. 2015) defines loss functions to preserve 1st-and 2nd-order proximity separately. After optimizing the loss functions, it concatenates these embeddings.
• Node2vec (Grover and Leskovec 2016) is generalized from Deepwalk by introducing a biased random walk.
• GCN (Kipf and Welling 2017) is a semi-supervised feature learning model which defines a convolution operator to directly operate graph-structured data.
• GAT (Velickovic et al. 2018) is a novel neural network architecture that operates graph-structured data by leveraging masked self-attentional layers.
We evaluate the quality of the embedding vectors learned by different methods on three classical network mining tasks: multi-label node classification, node clustering, and link reconstruction. To ensure the significance of the results, we repeat each experiment ten times and report their mean value and standard deviation value. For the common hyperparameters, we set learning-rate lr = 0.025, embeddingdimension d = 128, negative-samples m = 5, and iterationepochs T = 20000 for all methods. Specially, for Deep-Walk and Node2vec, we set walk-times wt=10, walk-length wl = 80, window-size k = 10, and set the bias parameters of Node2vec as p = q = 0.25, as recommended in their papers. For SDNE, we tune its parameters of α, β, ν by using a grid-search strategy, and get α = 10 3 , β = 10, ν = 10 −4 . For GCN and GAT, we consistently use the structural features (i.e. adjacent matrix) as the input features. For other parameters and other baselines, we use the default settings as shown in their original papers. For our RWNE model, we set the loss-weight γ = 10 and λ = 1 (see in Eq. (8)), the personalized-teleport-probability α = 0.3 (see in Eq. (11)), the walk-steps (walk-length) k =10 (see in Eq. (14)). Note that the walk-steps k in our model actually delimits an upper bound of the order to be preserved which shares the similar meaning with the window-size in DeepWalk and Node2vec.

Multi-label Node Classification
For the node classification task, we first learn the node embedding vectors from the full nodes on each dataset, and then use the embedding vectors as input features for a one-vs-rest logistic regression classifier, and use both Macro-F1 score and Micro-F1 score as the metrics for evaluation. We repeat each classification experiment ten times and randomly split 50% of the nodes for training and the other 50% for testing, and report both the mean value and the standard deviation value. Due to the lack of space, we report the mean Macro/Micro-F1 scores in Table 1 and Table 2, and report the standard deviations in the supplementary material. Note that we exclude the results of some models on the Youtube dataset because they either fail to terminate in one week (SDNE) or run out of memory (GraRep, HOPE, GCN, GAT). We can observe that our proposed RWNE model consistently and significantly outperforms all the state-of-theart baselines in both metrics on all datasets. For example, on the Cora dataset, RWNE outperforms all baseline models by 0.03-0.22 (relatively 4%-35%) in terms of Macro-F1 score and by 0.03-0.08 (relatively 4%-11%) in terms of Micro-F1 score; On the BlogCatalog dataset with larger size, RWNE also achieves the gains of 0.03-0.16 (relatively 12%-109%) in Macro-F1 score and 0.02-0.19 (relatively 7%-78%) in Micro-F1 score. Specially, by only taking random-walk based methods (DeepWalk, LINE, Node2vec) into account, we can find that RWNE also consistently improves the classification performance by around 0.02-0.08 in both metric scores on all datasets.
More generally, we can find that, by deploying sufficient long-distance random walks, random walk based algorithms (DeepWalk, Node2vec, and our RWNE) can achieve considerable improvements than matrix factorization based and  deep learning based algorithms, especially on the large-scale datasets. Besides, it is worth mentioning that by using the adjacent matrix as the input features, the semi-supervised feature learning models (GCN, GAT) show worse performance than expected, which implies that these models may not be suitable to exploit a graph with poor attribute features.

Node Clustering
For the node clustering task, we use the embedding vectors as the input to a k-means cluster and evaluate the performance in terms of NMI (Normalized Mutual Information) score. And also, all the experiments are conducted ten times, and the mean NMI scores are shown in Table 3, and the standard deviations are shown in the supplementary material.
Overall, the results of node clustering are consistent with the results of node classification, and we can reach a similar conclusion as analyzed in Section 4.3. We can see that the proposed RWNE model consistently and clearly outperforms all the comparative baselines on all datasets. For example, on the Cora dataset, RWNE improves the NMI score by 0.02-0.12 (relatively 5%-33%) over random walk based models, and by 0.05-0.17 (relatively 12%-57%) over other baseline models. On the BlogCatalog dataset, RWNE improves the NMI score by around 0.02-0.03 (relatively 9%-17%) over random walk based models, and by around 0.03-0.08 (relatively 15%-72%) over other baseline models.

Link Reconstruction
For the link reconstruction task , we rank pairs of nodes according to their similarities, i.e. the inner product of two embedding vectors, and then reconstruct/predict the links for the highest ranking pairs of nodes. We use the MAP (Mean Average Precision) metric (Goyal and Ferrara 2018) to estimate the reconstruct precision. Also, all the experiments are conducted ten times, and the mean MAP scores are shown in Table 4, and the standard deviations are shown in the supplementary material.
We can observe that the results of link reconstruction are also consistent with the results of node classification and node clustering, and we can draw similar conclusions. Overall, in terms of the MAP scores on all the six datasets, the proposed RWNE consistently and substantially achieves around 0.02-0.07 improvements over DeepWalk and Node2vec, and around 0.05-0.27 gains over other baselines.

Parameter Sensitivity
In our model, there exist four important parameters: walksteps k, personalized teleport probability α, and loss weight γ and λ. In this section, we illustrate these parameters sensitivity by the Macro-F1 scores of node classification experiments on the Blogcatalog dataset. For each experiment, we vary one parameter and fix the others as the default values (as shown in Section 4.2). The results are shown in Figure 3. From Figure 3(a), we can see that the performance is soaring when k<10 while it shows a slight decline trend when k>10, which reveals that it is beneficial to capture the proximity within an appropriate level of scope. From Figure 3(b), we can observe that the model achieves the best performance when α reaches around 0.3, which clearly proves the necessity and effectiveness of random walk with restart process. In addition, Figure 3(c) and Figure 3(d) show the effects of varying the weight γ and λ. We can observe that it is worthwhile to jointly preserve the local similarity and global equivalence with suitable weights (e.g., γ = 10 and λ = 1).

Case Study: Scalability
As analyzed in Section 3.4, the proposed RWNE model has superior scalability with a linear complexity. In this section, we further experimentally verify the scalability of RWNE. We first generate a series of random graphs with different sizes of [1k; 10k; 100k; 1000k; 10000k], and then apply our method to these synthetic networks to learn node embeddings. The time consumption is shown in Figure 4. We can see that the running time grows linearly with the number of nodes, which demonstrates that our method is efficient and scalable for large-scale networks.
In this paper, we present a general scalable random walk based network embedding framework. Distinguishing from existing random-walk based methods, we systematically design a sound objective to explicitly preserve arbitrary higherorder proximity and then equivalently optimize it by random walk simulation. As a result, the random walk is theoretically incorporated into the objective function, which explicitly clarifies the essential role of random walk playing in higher-order proximity preserved network embedding. Further, we also introduce the random walk with restart process to naturally and effectively weight the proximities of different orders by a personalized teleport probability. We conduct extensive experiments on several datasets and the results demonstrate the superiority of our model.


OMAD: Object Model with Articulated Deformations for Pose Estimation and Retrieval

Articulated objects are pervasive in daily life. However, due to the intrinsic high-DoF structure, the joint states of the articulated objects are hard to be estimated. To model articulated objects, two kinds of shape deformations namely the geometric and the pose deformation should be considered. In this work, we present a novel category-specific parametric representation called Object Model with Articulated Deformations (OMAD) to explicitly model the articulated objects. In OMAD, a category is associated with a linear shape function with shared shape basis and a non-linear joint function. Both functions can be learned from a large-scale object model dataset and fixed as category-specific priors. Then we propose an OMADNet to predict the shape parameters and the joint states from an object's single observation. With the full representation of the object shape and joint states, we can address several tasks including category-level object pose estimation and the articulated object retrieval. To evaluate these tasks, we create a synthetic dataset based on PartNet-Mobility. Extensive experiments show that our simple OMADNet can serve as a strong baseline for both tasks.

: Our OMAD representation for modeling articulated objects. In OMAD, we use shape parameters β β β to capture shape geometric deformations and use joint states Θ Θ Θ to capture pose deformations. We use to represent the variables in canonical space (e.g.P P P ), which distinguishes from variables in camera space (e.g. P P P).
propose an explicit parametric representation to depict shape and pose of articulated objects in the same category. There are two sources of articulated deformations, namely shape geometric deformation on parts and pose deformations on joints. To handle both deformations, we propose a novel Object Model with Articulated Deformations (OMAD) (Fig. 1). To describe the shape geometric deformations, given an articulated object, we consider its rest structure (i.e. shape geometry, joint parameters) in the axis-aligned, zero-centered canonical space. Then for its shape, which is represented by ordered sparse keypoints, can be derived from the proposed shape function P P P = S(β β β ; B B B), where β β β is a pose-invariant shape parameters in canonical space, and B B B is the category-specific linear shape basis. For the joint parameters Φ Φ Φ , we devise a non-linear joint function Φ Φ Φ = J(β β β ; Γ Γ Γ) with parameters Γ Γ Γ. The parameters {B B B, Γ Γ Γ} of shape function and joint function can be regarded as categoryspecific priors, and can be learned from existing object dataset like PartNet-Mobility [28] with proposed OMAD-PriorNet. In this way, the shape geometric deformation can be fully described by (P P P , Φ Φ Φ ). On the other hand, the pose deformation on joints can simply defined by its joint state Θ Θ Θ in camera space.
To combine both deformations, we devise a deformation function W (P P P , Φ Φ Φ , Θ Θ Θ). It can transform the rest structure in canonical space to camera space. In this sense, we can depict arbitrary articulated object of a known category simply with β β β and Θ Θ Θ. To predict β β β and Θ Θ Θ, we propose a novel OMADNet, which is mainly constituted by a neural prediction stage for coarse estimation of β β β and Θ Θ Θ and an optimization stage to refine the prediction results. To show the applicability of the proposed OMADNet, we apply it into two different tasks, namely articulated object pose estimation and articulated object retrieval. The predicted shape parameters β β β can be used for pose-oblivious object retrieval [8]. Besides, the predicted joint state Θ Θ Θ and joint parameters Φ Φ Φ can directly address the object pose estimation task. To evaluate our method, we select articulated object models of 5 categories from PartNet-Mobility [28] to create a dataset named ArtImage. For the articulated object pose estimation task, we achieve better results on joint state error and joint distance error compared to existing method. For the object retrieval task, we achieve 82.3 average mAP on 5 categories.
Our contribution can be summarized as follows: • A novel category-specific articulated modeling approach named OMAD, which ex-plicitly models both shape deformation and pose deformation at category-level.
• With the proposed OMAD, we provide a simple OMADNet to estimate the shape parameters and joint states required to describe the articulated object from its single observation. The output of OMADNet can be used to address the category-level object pose estimation task and the articulated object retrieval task.

Related Work
Articulated Object Shape Signature and Retrieval. The shape parameters in our proposed OMAD which capture the geometric features of articulated objects and summarize them into a vector are mostly like the shape signature adopted in [2,8,12,13,18,19]. However, these shape signatures cannot be directly applied to our case for at least two reasons: (1) Their methods are largely relied on the mesh representation, such as spectral-based [12], graphbased [2], geodesic-based [8], SDF-based [18], while our shape is in point cloud format. (2) None of the previous methods are interested in the joint parameters of the articulated objects, while our representation takes both joint states and joint parameters into account. For articulated object retrieval task, the standard benchmarks are the the McGill shape benchmark (MSB) [22] and ISDB dataset [8]. However, the object models for a certain category are very few for both datasets, which cannot support the training of our proposed OMAD-PriorNet and OMADNet. Low-rank Shape Prior. Our proposed OMAD adopts a low-rank shape prior based approach to model the sparse shape. Such choice has been proved effective in many tasks, such as instance segmentation [23], NRSfM [3,4,14,25], object structure learning [7], human body modeling [17,21]. To the best of our knowledge, we are the first to apply it to the generic articulated object modeling. It is worth noting that our method differs from SMPL [17] and its variants [21] from at least two aspects: (1) SMPL [17] relies on handcrafted mesh templates with fixed topology and vertex number, while our OMAD only requires flexible point cloud input.
(2) SMPL [17] performs PCA on standard meshes to obtain shape basis, while our proposed OMAD-PriorNet can learn shape basis in an unsupervised manner directly from raw point cloud.
Category-level Articulated Object Pose Estimation. Cateogry-level object pose estimation task aims at predicting poses of unseen objects in the same category, which is firstly introduced by NOCS [27]. A-NCSH [15] extends this task to articulated objects. Later, several works on this task are conducted on videos [11,16]. Our proposed OMADNet can address the category-level articulated object pose estimation task given a single depth image as input. Overall, our work is closely related to [15] with significant different on methodology. Firstly, [15] takes a part-centered perspective, the joint states are estimated from the predicted part segmentations and poses. Our method takes a joint-centered perspective, the joint states are directly predicted by OMADNet. Secondly, [15] uses dense NOCS coordinates to represent articulated objects, while our method use ordered keypoints to obtain sparse correspondence, which largely reduces optimization complexity. Thirdly, Li et al. [15] models the shape deformation implicitly with segmentation and NOCS coordinates, which cannot explicitly reflects the complete shape deformation by parameterization as our proposed OMAD representation. Thus it cannot support other important tasks like object retrieval.

Object Model with Articulated Deformations, OMAD
In this section, we will give a definition about the articulated objects which the OMAD can support (Sec. 3.1). As the representation of pose deformation on the joints are self-evident, we will mainly discuss how to model shape geometric deformations in canonical space(Sec. 3.2) with shape function (Sec. 3.2.1) and joint function (Sec. 3.2.2). A general articulated object in camera space is formed by transforming the keypoints and joint parameters in canonical space via a deformation function (Sec. 3.3).

Object Articulation
We take a joint-centered perspective to study articulated objects. Kinematic tree is one kind of abstraction of articulated objects (See Fig. 2). We denote the joint that connects one node and its parent node in the kinematic tree as the reference joint of this node. For example, if joint k connects node a and its parent node b, then joint k is the reference joint of node a.
Here we consider three types of joints: free joint, revolute joint and prismatic joint (See Fig. 2). (1) Free joint is the joint that connects the world node with the base part (root node) in the kinematic tree. The joint state of free joint can be defined as θ θ θ ( f ree) = (R ( f ) , t ( f ) ), which can be seen as the 6D pose of base part in the world coordinate space. (2) For revolute joint, joint parameters can be defined as φ φ φ (r) = (u u u (r) , q q q (r) ), where u u u (r) represents the direction of joint axis and q q q (r) represents the pivot point of joint axis. The joint state is denoted by θ θ θ (r) , which is the relative rotation angle compared to a pre-defined rest state in canonical space. (3) For prismatic joint, joint parameters can be defined as φ φ φ p , where u u u (p) represents the direction of joint axis. The joint state is denoted by θ θ θ (p) , which is the relative distance along the joint axis compared to a pre-defined rest state in canonical space.
With the introduction of reference joint and free joint, the part number and the joint number can be equal. Given an articulated object with K joints, the overall joint state is denoted as Θ Θ Θ = {θ θ θ 1 , . . . , θ θ θ K }.

Geometric Deformation in Canonical Space
As pose deformation can be independently considered by Θ Θ Θ, we model the shape geometric deformation in the canonical space (See Fig. 3). Objects of the same category in the canonical space have the following properties: (1) The directions in the joint parameters are aligned. (2) The whole object is zero-centered. (3). The joint states are the same and predefined. To note, our canonical space does not normalize the object scale, because object scale is a crucial part of the shape geometry and can be explicitly modeled by the OMAD representation. We use to represent the variables in canonical space (e.g.P P P ), which distinguishes from variables in camera space (e.g. P P P). As the articulation is associated with shape and joint, thus we model the geometric deformation with a shape function and joint function.

Shape Function
As detailed geometric deformation is hard to be modeled, we adopt the sparse shape representation, which seeks sparse keypoint correspondences among objects from the same category. Inspired by [7], we predict the sparse shape with the low-rank shape prior. Given a complete object point cloud in canonical space, the sparse shape P P P with M keypoints can be generated by shape parameters β β β using shape function S(·): be the matrix of all such shape basis, which will be shared in the same category.

Joint Function
Given the rest-state object in canonical space, we can define joint parameters φ φ φ = (u u u , q q q ), u u u ∈ R 3 , q q q ∈ R 3 for each joint. As the corresponding joint direction u u u is aligned in the canonical space, and the pivot point q q q for each joint are strongly correlated to the shape geometry, we propose to predict joint parameters in canonical space from shape parameters β β β . All the joint parameters Φ Φ Φ = {φ φ φ 1 , . . . , φ φ φ K } of the K joints can be generated by joint function J(·): where Γ Γ Γ is the parameters of the joint function J(·). Since the relationship between shape parameters and joint parameters in canonical space are highly non-linear, we design a twolayer MLP with ReLU activation as J(·).

Deformation function
To combine both shape geometric deformation and pose deformation, we introduce a deformation function P P P = W (P P P , Φ Φ Φ , Θ Θ Θ), which can transform the sparse shape P P P in zero-centered canonical space with joint parameters Φ Φ Φ according to joint states Θ Θ Θ to the observed sparse shape in the camera space P P P. Each keypoint p p p i in P P P that belongs to part k is transformed into p p p i in P P P according to Eq. 3 and Eq. 4:

Learning the OMAD Prior
The parameters of shape function S(β β β ; B B B) and joint function J(β β β ; Γ Γ Γ) are category-specific, and we call these parameters {B B B, Γ Γ Γ} as OMAD prior. We design a network called OMAD-PriorNet to learn OMAD prior for each cateogry in an unsupervised manner. The parameters {B B B, Γ Γ Γ} of shape function S(β β β ; B B B) and joint function J(β β β ; Γ) will be treated as shared network parameters of OMAD-PriorNet for each category, and they will be updated during training process. After the training, these parameters will be fixed as category-specific OMAD prior, then we will predict shape parameters β β β and keypoints P P P for each instance in the training set with the pre-trained OMAD-PriorNet which will be used as ground truth in the training of OMADNet described in Sec. 4.1. Please refer to the supplementary materials for all the loss functions and network structure of OMAD-PriorNet.
Learning of Shape Function. To learn the shape basis B B B for shape function S(·), we adopt a similar design in [7]. We make some modifications on the loss functions to adapt to the articulated objects. The tweaks on loss functions are listed in the following: (1) We add an additional L 2 regularization loss on β β β which can improve the generalization ability. (2) The original chamfer loss, coverage loss and surface loss is changed to part-level. (3) We add a separation loss to ensure the keypoints not collapsed into a cluster.
Learning of Joint Function. The parameters Γ Γ Γ of joint function J(·) is optimized during training according to the proposed joint loss defined in Eq. 5.
where L µ µ µ is a cosine-similarity loss that supervises joint direction and L q q q is the L 2 loss between the predicted joint pivot point and the ground-truth joint pivot point.

OMADNet
With the OMAD representation and the pre-learned OMAD priors, given a point cloud X X X = x x x i ∈ R 3 | i = 1, . . . , N reprojected from a depth image, we propose a OMADNet to predict the shape parameter β β β and joint states Θ Θ Θ. The overall pipeline is shown in Fig. 4.

Coarse Prediction of Shape Parameters and Joint States
Feature Extractor. We adopt PointNet++ [20] to extract d-dimensional dense point-wise feature F dense ∈ R N×d from X X X. Then we can generate global feature F global ∈ R d using a max pooling layer with the extracted dense feature. The Shape Branch. The shape branch learns to predict pose-invariant shape parameters β β β in canonical space. It uses a two layer MLP with global feature F global as input to regress a vector as shape parameters β β β . We supervise β β β by Eq. 6: where β β β * is obtained by the pre-trained OMAD-PriorNet described in Sec. 3.4, and L joint is defined in Eq. 5. L β β β indirectly supervises β β β by generating keypoints P P P = S(β β β ; B B B) and joint parameters Φ Φ Φ = J(β β β ; Γ Γ Γ) in canonical space.The parameters {B B B, Γ Γ Γ} are obtained from pre-trained OMAD-PriorNet and are fixed during training. The Joint State Branch. This branch predicts joint states using a two layer MLP with global feature F global as input to regress joint states Θ Θ Θ. As there are three joint types in consideration, we treat them separately. For the free joint, θ θ θ base = {R R R base ,t t t base }, we directly supervise R R R base , which is represented by a quaternion vector, via a cosine-similarity loss L base(R) while the loss L base(t) for t t t base is a Root Mean Square (RMS) loss. For the 1D revolute (L r ) or prismatic (L p ) joint, we use L 2 loss on θ θ θ (r) or θ θ θ (p) . The overall loss for joint state is: where 1 (·) j indicates whether it is the joint type for the joint j. The Keypoint Branch. The keypoint branch will directly predict ordered keypoint targetŝ P P P ∈ R M×3 in camera space using dense feature F dense . These keypoints are for the optimization process described later in Sec. 4.2. Similar to PVN3D [10], we predictP P P with an offset-voting mechanism, that is every point will regress all the M keypoint offsets with respect to its own location. These offsets are denoted by O ∈ R N×M . However, it is hard to directly regress keypoint offsets in camera space for articulated objects due to large joint deformations and self-occlusion. So we additionally predict an attention map S of input point cloud X X X to focus areas around keypoints. Specifically, the j-th keypointp p p j ∈P P P is generated by Eq. 8:p where s i, j ∈ [0, 1] is the attention score of i-th point for j-th keypoint, o o o i,k ∈ O is the 3D offset of j-th keypoint repective to the i-th point, x x x i ∈ X X X is the 3D coordinates of i-th input point. The prediction ofP P P is supervised by: where Θ Θ Θ * is the ground truth of the joint state, the rest of deformation function W (·) is obtained from pre-trained OMAD-PriorNet in Sec. 3.4.

Optimization-based Estimator
Since the regression of neural network is known to be noisy, empirically the estimated highlevel properties like shape parameters β β β and joint states Θ Θ Θ are less accurate than the predicted ordered keypoint targetsP P P in camera space. Thus, to push the limits of the prediction results in inference, we propose to refine β β β and Θ Θ Θ with an energy function E defined in Eq. 10: where P P P is the camera-space keypoints generated by deformation function W (·). The energy function E is differentiable, so we can try to find optimal shape parameters β β β and joint states Θ Θ Θ to fit the predicted keypoint targetsP P P during the optimization process. The initial values of β β β and Θ Θ Θ are obtained from OMADNet prediction, which vastly reduces the optimization time. Please refer to the supplementary files for further details.

Dataset
To the best of our knowledge, there is no public image dataset for articulated object tasks in category level. So we create a synthetic dataset named ArtImage to evaluate OMADNet. We select 5 categories of object models from PartNet-Mobility dataset [28] and render depth images under random joint states, object positions and viewpoints for each category with Unity [1]. We will make our dataset public in the future. Please refer to the supplementary materials for further details of ArtImage.

Experiments on Category-level Pose Estimation
Metrics. We use the following metrics to evaluate the performance of our algorithm on category-level pose estimation. (1) joint state. All the joint states error are evaluated in camera space, including mean angle error for revolute joints (max error 90 • for missing ones) and mean distance error for prismatic joints (max error 1 for missing ones). (2) joint parameters. All the joint parameters are evaluated in camera space. we use mean angle error to evaluate the orientation of joint axis, and use mean distance error to evaluate the distance between two joint axes.
Main Results. Table 1 shows the performance of different methods on category-level pose estimation. We can see that OMAD(refine) surpasses OMAD(initial) by a large margin, which proves the effectiveness of our optimization-based estimator. Compared to state-ofthe-art method A-NCSH [15], our OMAD(refine) achieves better results on joint state error and joint distance error on most categories. It is worth noting that the prediction of A-NCSH [15] heavily relies on part segmentation, which could result in missing parts or joints when segmentation fails. While our method could utilize kinematic prior information to Table 1: Performance comparison on category-level pose estimation task on ArtImage. OMAD(initial) represents the initial joint state and joint parameters predicted by OMAD-Net, and OMAD(refine) represents the refined results with our optimizer. prevent missing joints. Besides, our method is much faster than A-NCSH because we adopt sparse keypoints for optimization. We show some qualitative results of our OMAD(refine) in Fig. 5. We can see that the predicted keypoints after optimization can achieve semantic consistency in category, and maintain object structure under heavy self-occlusion.
Ablation Study. Table 2 shows some ablation experiment results. We use optimizationbased estimator as default setting in all the ablation experiments. We can see from Table 2 that the use of attention score vastly boosts the performance on all metrics when predicting keypoint targets. We also analyze the upper bound of our method in Table 2. The overall performance improves a lot when we replace keypoint targetsP P P predicted by keypoint branch with ground-truth keypoints during optimization process. This indicates that our OMAD representation has great potential and the bottleneck of our method is the quality of predicted keypoint locations in camera space. Please see supplementary files for ablation study on keypoint number, shape parameters β β β and experiment results on real images.

Experiments on Articulated Object Retrieval
Metrics. The pose-invariant shape parameters predicted by OMADNet can be used as shape signatures for articulated object retrieval task. We use the Euclidean distance of shape parameters to estimate the similarity between object instances. We randomly choose 100 depth images as test query set for each category. We report the mAP (mean Average Precision) of top-10 instances on five categories in the test dataset.  Results. To the best of our knowledge, there is no available retrieval method specially designed for our setting. Inspired from [5], we design a simple but effective Siamese Network as baseline which uses PointNet++ [20] backbone and contrastive loss [9] for training. Please see supplementary files for further details of the Siamese Network. Table 3 shows some quantitative results. Although our method are not specially designed for retrieval task, we still achieve better performance compared to the baseline on most categories. We find that the Siamese Network can not distinguish some similar instances in drawer category, which vastly harms the performance, while our method can distinguish them very well. Fig. 6 shows t-SNE [26] visualization of shape parameters predicted by OMADNet. We can see that the predicted shape parameters can distinguish different instances well and maintain pose-invariant.

Conclusion
In this work, we propose a novel category-level representation, OMAD, for articulated object by modeling the two kinds of deformations namely the shape geometric deformation and pose deformation. The OMAD can describe articulated objects with shape parameters and joint states. Then for a naturally observed object, we propose to predict such OMAD information via OMADNet. The predicted OMAD information can be used for multiple tasks, such as category-level object pose estimation and articulated object retrieval.