Graph Quality Judgement: A Large Margin Expedition

1 Introduction

As a convenient way to describe data relationship, graph is a kind of important structure in machine learning and has played a significant role in many learning tasks [Ng et al., 2001; Zhu, 2007] such as graph-based semi-supervised learning (GSSL) [Blum and Chawla, 2001; Zhu et al., 2003; Zhou et al., 2004]. With the help of graph, GSSL obtains many advantages such as closed-form solution, promising learning performance, and thus GSSL attracts significant attention since it was proposed and has been widely applied in a large amount of applications [Liu et al., 2012].

However, it is widely known that the graph quality, rather than the learning/optimization algorithm, seriously affects the performance of GSSL methods [Zhu, 2007; Belkin and Niyogi, 2008; Wang and Zhang, 2008; Jebara et al., 2009]. Moreover, it has been found in many empirical results [Zhou et al., 2004; Belkin and Niyogi, 2004; Wang and Zhang, 2008; Karlen et al., 2008] that an inappropriate graph may cause GSSL to deteriorate the performance. That is, GSSL with the use of unlabeled data not only does not improve performance, but sometimes it may even be outperformed by direct supervised learning with only a small amount of labeled data. Such a deficiency hinders GSSL to play an important role in more applications. To this end, studying the quality of the graph and developing performance-safe GSSL method are desired. Specifically, it is desirable to judge the quality of graph such that GSSL could often improve performance, while in the worst case it will not be outperformed by direct supervised learning with only labeled data. This task, to our best knowledge, has not been studied in literature.

⇤This research was supported by NSFC (61333014, 61403186), JiangsuSF (BK20140613), 863 Program (2015AA015406).

In this paper, we present a large margin approach named LEAD (LargE margin grAph quality juDgement) inspired by the success of large margin criterion [Vapnik, 1998]. Our basic idea is simple and intuitive. That is, when a certain graph owns a high quality, its predictive results on the unlabeled data may have a large margin separation. Table 1 illustrates the idea through four representative data sets. It can be seen that when one graph owns a better accuracy on the unlabeled data, it may also suffer a smaller hinge loss (a loss w.r.t. large margin separation) [Vapnik, 1998]. In other words, large margin separation may help judge the quality of graph. Based on this recognition, we should exploit the large margin graphs while keeping the small margin graphs (which might be risky) to be rarely exploited. This motivates our proposed LEAD method. LEAD views the predictive results of multiple graphs as features, and then constructs a large margin classifier based on these features. These procedures consequently formulate safe GSSL as Semi-Supervised SVM (S3VM) [Vapnik, 1998; Joachims, 1999] optimization and an efficient algorithm is presented. Extensive experimental results demonstrate that LEAD can effectively improve the safeness of GSSL, in addition achieve highly competitive accuracy with many state-ofthe-art GSSL methods.

The paper is organized as follows. Section 2 briefly reviews related work. Section 3 presents the proposed method. Empirical results are reported in Section 4. Finally, Section 5 gives a conclusive remark of this paper.

2 RelatedWork

GSSL attracts significant attention since it was proposed. A large number of works have been presented on optimizing a label assignment of the unlabeled data, e.g. [Blum and Chawla, 2001; Zhu et al., 2003; Joachims, 2003; Zhou et al., 2004; Belkin et al., 2006; Jebara et al., 2009] and constructing the graph, e.g. [Carreira-Perpi˜n´an and Zemel, 2005; Jebara et al., 2009; Wang and Zhang, 2008]. For optimizing the label assignment, just name a few, Zhu et al. [2003] proposed to use the belief propagation technique and derived a closed-form solution; Zhou et al.[2004] formulated GSSL as a convex regularization problem with a simple iterative algorithm. For the graph construction, many kinds of graphs have been considered. For example, k-nearest neighbor graph, ✏-neighborhood graph, minimal spanning tree [CarreiraPerpi˜n´an and Zemel, 2005], b-matching graph [Jebara et al., 2009], locally linear reconstruction graph [Wang and Zhang, 2008], etc. It is also reported that rather than the type of the graph, the selection of distance metric used in the graph will also significantly affect the final GSSL performance [Zhu, 2007]. There are also approaches, e.g., [Zhu et al., 2005; Argyriou et al., 2005] proposed to optimize the graph construction as well as the label assignment simultaneously.

It is now widely accepted that, with the deepening of research, the quality of the graph construction plays a key role to the learning performance of GSSL method [Zhu, 2007; Belkin and Niyogi, 2008; Wang and Zhang, 2008; Jebara et al., 2009]. What is more serious, as stated in many empirical studies [Zhou et al., 2004; Belkin and Niyogi, 2004; Wang and Zhang, 2008; Karlen et al., 2008], an inappropriate graph can even cause a degenerated performance. How to identify the quality of graph so as to avoid the hurt of using unlabeled data in GSSL has not been deeply studied yet.

There are some discussions in literatures, e.g., [Cozman et al., 2002; Ben-David et al., 2008; Balcan and Blum, 2010] on the reasons about the decreased performance of general semisupervised learning. For example, Cozman et al. [2002] conjectured that the performance degradation on semi-supervised learning is caused by incorrect model assumptions. However, without large amount of domain knowledge, it is difficult to make correct model assumptions. Ben-David et al. [2008], from a theoretical perspective, pointed out that semisupervised learning is not necessarily able to achieve better generalization performance when there is not sufficient domain knowledge. Yet they did not give a feasible solution. Balcan and Blum [2010] showed that when unlabeled data is able to provide a good regularizer, a purely inductive supervised SVM on labeled data using such a regularizer guarantees a good generalization. However, deriving such a good regularizer is quite difficult.

Recently there are some efforts devoted to develop safe semi-supervised learning approaches, e.g., [Li and Zhou, 2005; 2015; Li et al., 2016]. However, developing safe GSSL approaches remains challenging. To our best knowledge, this paper is the first proposal on this aspect.

3 The LEAD Method

To judge the quality of graph so as to alleviate the performance degradation of GSSL methods, we present the LEAD method with the use of large margin principle. As mentioned, when a certain graph owns a high quality, its predictive results on the unlabeled data may derive a large margin separation. In other words, if one predictive result derived by a graph has a small margin, then it may cause a higher risk of performance degradation when using the graph. Therefore, given multiple graphs with unknown quality, one should encourage to use the graphs with large margin, rather than the graphs with small margin, and consequently reduce the chances of performance degradation. Based on the above assumption, by treating the predictive results of multiple graphs as new input training features, the proposed method constructs a large margin classifier for both the labeled and unlabeled data to derive a relatively safe predictive result for GSSL.

Specifically, in GSSL, given a few labeled instances ¶xi↪ yi♦li=1 and a large amount of unlabeled instances ¶xj ♦l+u j=l+1 (l ⌧ u) where y 2 ¶+1↪-1♦ is the output label for input instance x. Let ¶Gt = (V↪ Et↪Wt)♦Tt=1 denote multiple graphs where T refers to the number of graphs. Here V is a set of l+u nodes each corresponds to one instance. E is a set of undirected edges between node pairs. W 2 R(l+u)⇥(l+u) is a nonnegative and symmetric adjacency weighted matrix associating with E in G, i.e., the weight wij on the edge eij 2 E reflects the similarity between xi and xj.

For each graph, GSSL aims to infer an optimal label assignment z = [z1↪ ▷ ▷ ▷ ↪ zl+u] such that the label inconsistency with respect to the graph as well as the existing labeled instances is minimized. This procedure is formulated as,

Eq.(1) is a convex quadratic optimization and could be solved via many efficient GSSL algorithms, for example, the Harmonic method by [Zhu et al., 2003]. Let z(t) = [z(t) 1 ↪ ▷ ▷ ▷ ↪ z(t) l+u ] denote the optimal solution of Eq.(1) with respect to the graph Gt, t = 1↪ ▷ ▷ ▷ ↪ T. Without sufficient domain knowledge, it is difficult to distinguish the quality of these solutions. If one chooses an inappropriate solution, GSSL may cause a performance degradation. To this end, we propose to use large margin principle to help distinguish the quality of the solutions.

Specifically, let ui denote a vector where each entry corresponds to the predictive result of each graph on instance xi, i.e., ui = [z(1) i ↪ ▷ ▷ ▷ ↪ z(T) i ]. We regenerate a new semisupervised training set where ¶ui↪ yi♦li=1 denotes the new labeled examples and ¶uj♦l+u j=l+1 the new unlabeled instances. A large margin linear classifier is then build to separate both the new labeled and unlabeled data. Intuitively, the large margin classifier is lateral to the use of large margin graphs, and avoids the direct utilization of small margin graph, and therefore the chance of performance degradation can be reduced.

Formally, we seek to find a linear classifier f(u) = w0u + b and a label assignment of unlabeled data ˆy = [ˆ yl+1↪ ▷ ▷ ▷ ↪ ˆ yl+u] that minimize the following optimization,

where `(v) = max¶0↪ 1 - v♦ is the hinge loss in large margin separation and the last constraint is balanced constraint [Joachims, 1999] that enforces the class ratio on unlabeled data to be closely related to that of labeled data (β is a small constant). C1 and C2 are parameters trading off the losses on the labeled and unlabeled data, respectively.

Eq.(2) is no more than the classical semi-supervised SVM (S3VM) [Vapnik, 1998; Joachims, 1999]. That is, safe GSSL is posed as S3VM optimization. To our best knowledge this is the first time to connect safe GSSL to S3VM.

To solve the optimization in Eq.(2), one direct solution is the use of traditional S3VM algorithms [Joachims, 1999; Chapelle et al., 2008; Li et al., 2013]. However, these algorithms do not fully exploit the structure in our setting, and may be not efficient. For example, here linear kernel is used while traditional S3VMs often consider the use of non-linear kernels. To this end, we present an efficient alternating optimization algorithm for the solving of Eq.(2).

It alternatively optimizes w (or ˆy) by fixing the ˆy (or w) as constants. Specifically, when ˆy is fixed, Eq.(2) is a standard

Algorithm 1 The LEAD Method

Input: labeled instances ¶(xi↪ yi)♦li=1 , unlabeled instances ¶xj ♦l+u j=l+1 , regularization coefficients C1 and C2, a set of candidate graphs ¶Gt = (V↪ Et↪Wt)♦Tt=1 , the label assignment ˆy0 = [ˆ y0 l+1 ↪ ▷ ▷ ▷ ↪ ˆ y0 l+u ] of a direct supervised learning method using only labeled instances ¶(xi↪ yi)♦li=1

Output: a label assignment on the unlabeled instances ˆy = [ˆ yl+1↪ ▷ ▷ ▷ ↪ ˆ yl+u]

• 1: Perform a GSSL algorithm (in this paper the methods in [Zhu et al., 2003] and [Zhou et al., 2004] are both implemented for comparison) on a set of graphs ¶Gt♦Tt=1 ; record z(t) = [z(t) 1 ↪ ▷ ▷ ▷ ↪ z(t) l+u ] as the optimal solution with respect to the graph Gt, t = 1↪ ▷ ▷ ▷ ↪ T
• 2: Regenerate a new training data set. ¶ui↪ yi♦li=1 denotes the new labeled instances and ¶uj♦l+u j=l+1 the unlabeled instances, where ui = [z(1) i ↪ ▷ ▷ ▷ ↪ z(T) i ], i = 1↪ ▷ ▷ ▷ ↪ l +u
• 3: Initialize ˆy = sign( 1
• 4: repeat
• 5: repeat
• T PTt=1 z(t) ) and ˆ C2 = 10-6C1
• 6: Fix ˆy and update the solution of w via a linear SVM solver like LIBLINEAR [Fan et al., 2008]
• 7: Fix w and update the solution of ˆy via Eq.(3)
• 8: until the objective of Eq.(2) does not decrease
• 9: ˆ C2 = 2 ˆ C2
• 11: If ˆ yl+j(w0ul+j +b)  1, then ˆ yl+j = ˆ y0 l+j , j = 1↪ ▷ ▷ ▷ ↪ u
• 10: until ˆ C2 ≥ C2
• 12: return ˆy = [ˆ yl+1↪ ▷ ▷ ▷ ↪ ˆ yl+u]

linear SVM form and w can be solved by a linear SVM package like LIBLINEAR [Fan et al., 2008] efficiently. When w is fixed, it has been proved that the rank of the elements of the optimal ˆy will be consistent with that of the prediction w0u + b on unlabeled data [Zhang et al., 2007]. Therefore, the optimal ˆy can be derived by the following closed-form solution.

where ¶r1↪ ▷ ▷ ▷ ↪ ru♦ are the ranks of the predictions on the unlabeled data ¶ul+1↪ ▷ ▷ ▷ ↪ ul+u♦ (sorted in a descending order). The larger prediction, the smaller rank. To further improve the quality of the solution, inspired by [Joachims, 1999], we first assign a small importance for the unlabeled data (i.e., C2 is initialized as a very small constant), and then gradually increase the importance of the unlabeled data (i.e., the value of C2) until it reaches an upper bound. Finally, the unlabeled instances lying within the margin remain risky to use and thus their labels are assigned with the direct supervised learning method. The pseudocode of the proposed LEAD method is given in Algorithm 1.

4 Experiment

4.1 Setting

To evaluate the effectiveness of our proposal, we conduct experimental comparison on a number of binary data sets 1 that cover a wide range of properties (Table 2). The sample size ranges from 294 to more than 1,5000. The feature dimensionality ranges from 5 to more than 10,000. The proportion of classes (i.e., ratio of the number of positive samples to that of negative samples) ranges from less than 0▷2 to more than 1▷5. LEAD is compared with the following methods.

• ÷ 1NN: The baseline supervised learning method. Each unlabeled instance is assigned with the label of its nearest labeled instance.
• ÷ Harmonic 2 : The classical harmonic function method proposed in [Zhu et al., 2003]. Without sufficient domain knowledge of graph construction, k-nearest neighbor graph is recognized as a good candidate graph [Zhu, 2007]. Therefore, three types of nearest neighbor graphs (namely 3, 5 and 7 nearest neighbor graphs) are considered for the Harmonic method.
• ÷ LLGC: The classical LLGC (local and global consistency) method proposed in [Zhou et al., 2004]. Similar to the Harmonic method, 3, 5 and 7 nearest neighbor graphs are employed.
• ÷ CGL 3 : This is a GSSL method [Argyriou et al., 2005] that learns a graph from multiple candidate graphs through worst-case.
• ÷ Majority Voting: We also compare with the majority voting method which is known as a popular approach in dealing with multiple predictive results and has been found useful in many situations [Zhou, 2012].
• ÷ GSSL-CV: We further compare with the crossvalidation method which is widely accepted as a popular method to perform model selection. Here the crossvalidation method is performed to select a graph from a set of candidate graphs via the cross-validation result.

The distance metric used to determine nearest neighbors about the above compared methods is set as the Euclidean distance. For the Harmonic and CGL method, the parameters are set to the recommended ones in the package. For the LLGC method, since the authors do not share the code, it is implemented by ourselves and the parameter ↵ is set to 0▷99 recommended in the paper. For the Majority Voting method, the discrete label assignments from a set of candidate graphs are integrated and the label ratio of unlabeled data is enforced to be similar to that of labeled data. For the GSSLCV method, 5-fold cross-validation is conducted (we have conducted other types of cross-validation method, like 2-fold and 10-fold cross-validation, and 5-fold cross-validation performs the best). For the LEAD method, the parameters C1, C2 and β are set to 1, 0.01 and 0.02 for all the experimental settings in this paper. 9 candidate graphs from 3, 5 and 7 nearest neighbor graphs based on 3 distance metrics (i.e., Euclidean, Manhattan and Cosine distance) [Zhu, 2007] are exploited, and correspondingly the GSSL predictive results of LEAD are from the output of classical GSSL methods (i.e., the Harmonic and LLGC methods) on the above graphs. For each data set, 10 instances are labeled and the rest are unlabeled. The class ratio is maintained on both sets. Each experiment is repeated 20 times, and the average accuracy (mean ◦ std) on the unlabeled data is reported.

1 Downloaded from http://olivier.chapelle.cc/ssl-book/ benchmarks.html and http://archive.ics.uci.edu/ml/datasets.html

2 http://pages.cs.wisc.edu/⇠jerryzhu/pub/harmonic function.m 3 http://cvn.ecp.fr/personnel/andreas/code/graph/index.html

4.2 Performance Results

Table 3 shows the comparison result. The proposed LEAD method obtains highly competitive accuracy with compared GSSL methods in the ability of performance improvement. Firstly, in terms of the average accuracy, the proposed LEAD method obtains competitive performance when exploiting both the Harmonic and the LLGC method. Secondly, in terms of the frequency of the performance improvement, LEAD obtains quite good performance (It achieves significant improvement in 9 and 12 cases, which are the most among all the compared methods using the Harmonic and the LLGC method, respectively).

More importantly, unlike the compared GSSL methods that will significantly cause a decreased performance in many cases (regardless of the use of the Harmonic method or the LLGC method), the proposed LEAD method does not decrease the performance significantly. Such a advantage, will help GSSL to play a role in more applications, especially those which require a high reliability for the exploitation of unlabeled data.

Both the Majority Voting method and the GSSL-CV method are to some extent capable of reducing the chance of the performance degradation and improving the accuracy, however they still decrease the performance in some cases, especially when the accuracies of 3, 5 and 7 nearest neighbor graphs are worse than that of the baseline 1NN method.

Table 4 further gives the results of the compared methods and our proposed method on 30 labeled instances. As can be seen, similar to the situations in Table 3, our proposal method effectively improves the safeness of GSSL methods, in addition achieves a highly competitive accuracy in comparison to the state-of-the-art GSSL methods.

Previous discussions are all based on the use of Euclidean distance.To further study the influence of the distance metric, Figure 1 shows the accuracy improvement results of the compared methods against baseline 1NN method with the use of the Manhattan and Cosine distance, respectively. Similarly, unlike the compared methods that may seriously decrease the accuracy in many cases, our LEAD method can often robustly improve the accuracy (the paired t-tests at 95% significance level shows that LEAD will not significantly decrease the accuracy in all the cases).

4.3 Ability in Judging the Graph Quality

We study the ability of our proposed method in judging the quality of the graphs. Specifically, let wl1 ↪wl2 ↪wl3 and ws 1 ↪ ws 2 ↪ ws 3 denote the largest 3 and the smallest 3 coefficients of the learned w in our proposed method. Suppose accl , accs and accave are the average accuracies of the graphs corresponding to ¶wl1 ↪wl2 ↪wl3 ♦, ¶ws 1 ↪ ws 2 ↪ ws 3 ♦ and all the coefficients in w, respectively. Figure 2 shows the average result of accl -accave and accs -accave on 20 random splits for all

1. Based on Cosine distance metric

the experimental data sets. From the figure, it can be observed that in most cases the performance of the largest 3 coefficients is much better than that of the smallest ones. This result indicates that large margin principle can indeed be helpful to judge the quality of the graphs.

5 Conclusion

In this paper we study to judge the graph quality in GSSL, a key factor for GSSL performance, and develop a safe GSSL method LEAD that does not deteriorate the performance when using unlabeled data. Our main contribution is to propose a large margin assumption for the graph quality. Specifically, when a graph owns a high quality, its prediction on unlabeled data may have a large margin separation. Intuitively, one should exploit the large margin graphs and rarely use the small margin graphs (which might be risky), and therefore reduce the chance of performance degeneration when using unlabeled data. We consequently formulate safe GSSL

b) Using the LLGC method

as the classical Semi-Supervised SVM (S3VM) optimization. Extensive experimental results demonstrate that large margin principle is helpful in judging the graph quality and improving the safeness of GSSL.