Bidirectional Semi-Supervised Learningwith Graphs
Tomoharu Iwata1 and Kevin Duh2
1

NTT Communication Science Laboratories
iwata.tomoharu@lab.ntt.co.jp
2
Nara Institute of Science and Technology
kevinduh@is.naist.jp

Abstract. We present a machine learning task, which we call bidirectional semi-supervised learning, where label-only samples are given as
well as labeled and unlabeled samples. A label-only sample contains thelabel information of the sample but not the feature information. Then, we
propose a simple and eﬀective graph-based method for bidirectional semisupervised learning in multi-label classiﬁcation. The proposed method
assumes that correlated classes are likely to have the same labels among
the similar samples. First, we construct a graph that represents similarities between samples using labeled and unlabeled samples in thesame way with graph-based semi-supervised methods. Second, we construct another graph using labeled and label-only samples by connectingclasses that are likely to co-occur, which represents correlations between
classes. Then, we estimate labels of unlabeled samples by propagating labels over these two graphs. We can ﬁnd a closed-form global solution forthe label propagation by using matrix algebra. We demonstrate the effectiveness of the proposed method over supervised and semi-supervised
learning methods with experiments using synthetic and multi-label text
data sets.
Keywords: semi-supervised learning, label propagation, multi-label classiﬁcation

1

Introduction

The performance of a classiﬁer can be improved as the number of labeled samples
is increased. However, we might not have enough labeled samples to achieve areasonable performance because their generation incurs cost and requires time.
To overcome the shortage of labeled samples, there has been great interest inmethods that eﬀectively increase training samples. For example, semi-supervised
learning [1] augments training samples by using unlabeled samples. The otherexamples include domain adaptation [2] and class adaptation [3], where theformer utilizes samples from diﬀerent domains and the latter utilizes samples
from diﬀerent taxonomies.
In this paper, we consider a new way to improve multi-label classiﬁcation
performance, where we have label-only samples as well as labeled and unlabeled

Table 1. Notation.
Symbol Description{(x, y)} labeled samples{x} unlabeled samples{y} label-only samples
N
number of labeled samples
U
number of unlabeled samples
O
number of label-only samples
K
number of classes
M
number of features
Table 2. Given data in supervised, semi-supervised and bidirectional semi-supervised
learning.
Problem
Given data
supervised{(x, y)}(one-directional) semi-supervised {(x, y)}, {x}bidirectional semi-supervised {(x, y)}, {x}, {y}samples. The labeled samples are a set of pairs of feature and label vectors
N +U{(xi , yi )}N
i=1 , and the unlabeled samples are a set of feature vectors {xi }i=N +1
without label information. The label-only samples are a set of label vectors+U +O{yi }Ni=N +U +1 , where corresponding feature information is unavailable. We callthis setting bidirectional semi-supervised learning. Semi-supervised learning isdeﬁned as a task with abundant inputs (unlabeled samples) but few input-output
pairs (labeled samples); so we deﬁne bidirectional semi-supervised learning as atask with abundant inputs and abundant outputs (label-only samples), but few
input-output pairs. Table 1 summaries our notation, and Table 2 summaries
the given data in supervised, semi-supervised and bidirectional semi-supervised
learning.
This setting can be found in many real applications. For example, let us
consider recommendation problems in two diﬀerent domains, where the feature
vector is a user’s preference for items in a given domain, and the label vector is
the user’s binary preference for items in another domain [4, 5]. Here, we supposethat we want to estimate the preferences in the second domain. Users who havepreferences in the both domains can be used for labeled samples, those who havepreferences only in the ﬁrst domain can be used for the unlabeled samples, andthose who have preferences only in the second domain can be used for the labelonly samples. Cross-lingual information retrieval [6–8] is another application,
where the feature vector is a query and the label vector consists of relevant
documents in a diﬀerent language. Here, we might have a lot of documents in adiﬀerent language for label-only samples. Other applications include automatic
image annotation problems [9–11], where the feature vector is image features
and the label vector is the annotations. The label-only samples can be obtainedusing text corpus under the assumption that correlation between annotations isrelated to correlation between word in the text corpus. Similarly, in multi-label
text classiﬁcation problems, label correlation might be available from outsidelabel-only sources. In general, bidirectional semi-supervised problems may arise
when we have disjoint datasets of features and labels.
Unlabeled samples contain information about the distribution of samples in
the feature space. Semi-supervised learning methods uses this information forimproving performance. Similarly, label-only samples contain information about
the distribution in the label space, or information about correlations between
classes. Therefore, we can expect that the multi-label classiﬁer performance canbe improved by using label-only samples.
We propose a simple and eﬀective graph-based method for bidirectional semisupervised learning. A number of graph-based semi-supervised learning methods,
or label propagation, have been proposed [12–15] because of its simplicity andeasy implementation. They have used for a wide variety of applications, suchas text classiﬁcation [16], image recognition [17] and protein function prediction [18]. With the graph-based semi-supervised method, a graph is constructedusing labeled and unlabeled samples by connecting samples that have similarfeature vectors, where each node corresponds to a sample. Then, labels are estimated by propagating labels over the constructed graph with the assumptionthat connected samples tend to have the same label. An advantage of graph-basemethods is that we can obtain a global closed-form solution.
The proposed method is an extension of the graph-based semi-supervised
methods. First, we construct a graph using labeled and unlabeled samples in thesimilar way with graph-based semi-supervised learning. Second, we constructanother graph using labeled and label-only samples by connecting classes thatare likely to co-occur, where each node corresponds to a class. Then, we estimate
labels by using these two graphs with the assumption that labels of correlatedclasses in similar samples tend to be the same. We can obtain a global closed-form
solution for the proposed method. We can use similar techniques that have been
extensively studied for graph-based semi-supervised methods for the proposed
method, such as techniques for constructing eﬀective graphs and algorithms foreﬃcient estimation.
The remainder of this paper is organized as follows. In Section 2, we formulate the proposed method, and describe a closed-form solution and an iterative
estimation method. In Section 3, we brieﬂy review related work. In Section 4, we
demonstrate the eﬀectiveness of the proposed method with experiments usingsynthetic and multi-label text data sets. Finally, we present concluding remarks
and a discussion of future work in Section 5.

2

Proposed method

We suppose that there are N labeled samples {(xi , yi )}N
i=1 , U unlabeled samples+U
N +U +O{xi }N,andOlabel-onlysamples{y}.
Afeature vector is reprei
i=N +1i=N +U +1
sented by xi = (xim )M
,
where
x
is
the
mth
elementof the ith sample’s
imm=1
feature vector, and M is the number of features. A label vector is represented

+(a) sample graph(b) class graph(c) sample-class graphFig. 1. Sample, class and sample-class graphs. Square and circle nodes represent sample
and class, respectively.

by yi = (yik )K
k=1 , where yik = 1 if the ith sample is categorized into class k,yik = −1 otherwise, yik ∈ {−1, 1}, and K is the number of classes. Each sample
can be assigned to multiple classes. Classes that do not appear in labeled samples can appear in label-only samples. Our task is to assign labels to unlabeled
samples.
First, we construct a sample graph, where nodes are the labeled and unlabeled
samples. An edge between two nodes represents the similarity of feature vectorsof the two samples. The edge weight can be calculated by using Gaussian kernel
as follows,( α)
wij = exp − k xi − xj k2 ,(1)2
where α is the precision parameter. We can also build the sample graph with knearest neighbors, where nodes are connected if they are k nearest neighbors in
Euclidean distance, and wij = 0 otherwise. Figure 1 (a) shows an example of asample graph, where a square node represents a sample.
Second, we construct a class graph, where nodes are the classes that appear
in the labeled and label-only samples. An edge between two nodes represents
the similarity of the two classes, or how likely the two classes co-occur. The edge
weight can be calculated by using Gaussian kernel in the similar way to thesample graph,()β
vkl = exp − k y (k) − y (l) k2 ,(2)2where β is the precision parameter, and y (k) = (y1k , · · · , yN k , yN +U +1,k , · · · , yN +U +O,k )is an N + O dimensional vector that consists of the kth elements of label vectors
in the labeled and label-only samples. y (k) can be used with L2 normalization
so that the weights correlate to their cosine similarities. Figure 1 (b) shows anexample of a class graph, where a circle node represents a class. Note that there
are N + U nodes in the sample graph, and K nodes in the class graph.
Then, we estimate labels for unlabeled samples using the sample and classgraphs. We suppose that fik is a real valued relaxation of yik , which is to be
estimated. We assume that labels of correlated classes (which are connected in
the class graph) in similar samples (which are connected in the sample graph) arelikely to be similar. This can be achieved by minimizing the following function,1 ∑ ∑wij vkl (fik − fjl )2 ,2 i,j=1
N +U

E=

K

(3)

k,l=1

with the constraint of fik = yik on the labeled data i = 1, · · · , N . When wij ishigh (feature vectors of i and j are similar) and vkl is high (classes k and l arecorrelated), the estimated value for class k of the ith sample needs to be similar
to that for class l of the jth sample so as to minimize the objective function E.
Therefore, by minimizing the objective function, we can ﬁnd estimated labels,
where correlated classes in similar samples have similar labels.
The proposed method can be seen as label propagation on a sample-classgraph that is build by combining sample and class graphs as shown in Figure 1(c), where the correlated classes in the similar samples are connected. In thesample-class graph, each node corresponds to a class of each sample, and thenumber of nodes is (N + U )K.
With graph-based semi-supervised learning methods, the following objectivefunction is minimized,
∑
1 ∑
wij
(fik − fjk )2 ,2 i,j=1
N +U

E=

K

(4)

k=1

where they assume that similar samples have similar labels. However, they do
not consider the correlation between classes. The graph-based semi-supervised
learning methods can be seen as label propagation on a sample graph withoutclass graphs. The proposed method with vkl = 1 if k = l and vkl = 0 otherwise
coincides with the graph-based semi-supervised method.
2.1

Closed-form solution

We can ﬁnd a closed-form global solution for the minimization of the objectivefunction E by using matrix algebra. The proposed method propagates labels on
the sample-class graph as shown in Figure 1. Therefore, we can use the samealgorithm for ﬁnding the solution with label propagation for semi-supervised
learning [15]. Let A be an (N +U )K ×(N +U )K matrix, whose (iK +k, jK +l)th
element is AiK+k,jK+l = wij vkl as follows,
w11 v11 w11 v12 · · ·w11 v1K..
 w11 v21 w11 v22 · · ·

.

,
A=
(5)

..
.
..
.
.
.


.
.
.
.
wN +U,1 vK1 · · · · · · wN +U,N +U vKK
which represents the sample-class graph. Let D be a diagonal matrix, whose ith
diagonal element is(N +U )K
∑
Dii =
Aij .
(6)
j=1

The graph Laplacian matrix L is deﬁned as,
L = D − A.

(7)

Let f = (f11 , f12 , · · · , f1K , f21 , · · · , fN +U,K )> be the vector of f values on all of
the labeled and unlabeled samples. The objective function E can be written as,
E = f > Lf .

(8)

Then, we can obtain the following closed-form solution by solving the constrained
optimization problem using Lagrange multipliers,
fl = y l ,(9)fu = −L−1
uu Lul yl .

(10)Here, f = (fl , fu ) and(L=

Lll Llu
Lul Luu),(11)

which are partitioned with respect to values of labeled and unlabeled samples.
2.2

Iterative algorithm

We can also obtain a solution by using an iterative algorithm [19, 20]. Whenthe graphs are sparse, the iterative algorithm is eﬃcient and reduces required
memory. Sparse graphs can be obtained by using k nearest neighbor graph construction for sample and class graphs. With the closed-form solution, we need
the inverse of a U K × U K matrix Luu , whose inverse is not sparse even if Luu issparse. The numbers of unlabeled samples U and classes K might be large, andit might require a huge memory space for storing the U K × U K dense matrix.
On the other hand, the iterative algorithm does not need to calculate any dense
matrices. First, we initialize estimates as follows,(0)fl← yl ,

fu(0) ← (0, 0, · · · , 0).

(12)
(13)

Then, we iterate the following updates until convergence,f (t+1) ← D −1 Af (t) ,
(t+1)

fl

← yl ,(14)(15)

where f (t) is the estimates of the tth iteration. We can ﬁnd the unique ﬁxed
point by the iterative algorithm.

2.3

Induction

The method described before is transductive, which means that the method
estimates labels of the given unlabeled samples. When we newly obtain unlabeled
samples to be estimated, we can estimate their labels by combining previously
given samples and the newly obtained samples. However, it is ineﬃcient. We caneﬃciently estimate labels for out of samples using the estimation result for thepreviously given samples as follows,∑N +U ∑K
j=1

l=1 wij vkl fjl

fik = ∑N +U ∑K
j=1

l=1 wij vkl

,

(16)

where fjl is the estimated labels of the previously given samples.

3

Related work

Bidirectional semi-supervised learning is a new type of machine learning task,
and the proposed method is a simple method based on graphs. A lot of graphbased semi-supervised learning methods have been proposed. However, most ofthem are for single-label classiﬁcation. Those methods can be applied to multilabel classiﬁcation by estimating each label independently. However, by considering the class interdependence for multi-label classiﬁcation, the performancecan be improved and some those types of graph-based semi-supervised learning
methods have been proposed [21–23, 4]. For example, [22] proposed a methodthat estimates labels so that multiple labels for each sample satisfy the given
correlations between classes. Other multi-label classiﬁers also uses class correlation [24]. However, they utilize only classes that appeared in the labeled samples.
On the other hand, the proposed method can utilize classes that do not appear
in the labeled samples by representing class correlation by a graph, and propagate labels over the graph. With the proposed method, even if two classes do notdirectly co-occur, label information can propagate through edges. In [21], correlation between labels for each sample is considered. In contrast, the proposed
method considers correlation between labels not only in one sample but also in
multiple similar samples.

4

Experiments

4.1

Data

We demonstrate the eﬀectiveness of the proposed method using the following
two data sets: Swissroll and Patent.
The Swissroll data [25, 26] are synthetic, where samples of three dimensionalfeature vectors are lying on a two dimensional nonlinear manifold as shown in
Figure 2. We augmented the swissroll data set with multiple labels. We generated
label vectors so that they became similar if their feature vectors were located

10
9,10
4
4,5

3,4

9

3
2,3
2
1 1,2

5
5,6
6
6,7

8,9
8

7,8
7

Fig. 2. Swissroll data. Each point represents a feature vector and its color represents
the labels. The numbers show that nearby samples are assigned to those classes.

closely in the two dimensional nonlinear manifold, where we set the number ofclasses at K = 10. We generated samples, where the number of labeled, unlabeled
and label-only samples were N = 10, U = 1, 000 and O = 1, 000 respectively.
The Patent data consist of patents published in Japan from January to Marchin 2004, to which International Patent Classiﬁcation (IPC) codes were attachedby experts according to their content. We used bag-of-words of a patent for thefeature vector, where the number of words was M = 104, 621, and we normalizedeach feature vector by L2 norm. We used the most frequently occurred 500 IPC
codes in the corpus for the classes, K = 500. We sampled 10 labeled samples,
1, 000 unlabeled samples, and 5, 000 label-only samples from the corpus.
Figure 3 shows a class graph of the Patent data set. Here, each node represents a class, and it is visualized by [27] so that connected nodes are locatedclosely. Some classes form clusters, and we can see the structure of classes fromthe visualization result. In the Patent data set, there are correlated classes, suchas ‘transmitter’ and ‘receiver’, ‘distinct material semiconductor’ and ’distinctalignment semiconductor’, and ‘system to generate signals for adjusting focus’and ‘automatic focus adjusting system’.

4.2

Measurements

For the evaluation measurements, we used mean reciprocal rank (MRR) andnormalized discounted cumulative gain (NDCG) [28], which were widely used in
evaluating ranking problems. We used ranking measurements because they givehigher scores when true classes are ranked higher than false classes even if theestimated classes did not exactly match with the true classes. They were also
used for multi-label classiﬁcation [29–31].

Fig. 3. A class graph of the Patent data set, where each node represents a class or IPC
code.

The MRR is the average of the reciprocal ranks, and the MRR of the ith
sample is given as follows,
M RRi =

1 ∑
1
,
|yi |
rankik(17)

k:yik =1

where rankik is the rank of class k of the ith sample in the estimated result, and|yi | represents the number of classes that satisfy yik = 1.
The DCG is calculated as follows,
DCGi = gi1 +

K
∑
gik
,
log2 k(18)

k=2where gik = 1 if the kth ranked estimated class is the true class for the ith
sample, and gik = 0 otherwise. NDCG can be obtained by normalizing DCG by
the maximum possible DCG, and NDCG lies on the interval 0.0 to 1.0. With theproposed method, classes were ranked according to values fik for each unlabeled
sample. Higher MRR and NDCG represent better classiﬁcation performance.
4.3

Compared methods

We compared the proposed method, which uses all of the labeled, unlabeled andlabel-only samples, with a supervised method, which uses only labeled samples,and a semi-supervised method, which uses labeled and unlabeled samples.
For the supervised method (SL), we used a maximum entropy model, which
is a discriminative classiﬁer, and it has achieved high performance for text classiﬁcation [32]. The maximum entropy model estimates the probability distribution

Table 3. Average MRR and NDCG in the Swissroll data set and their standard deviation.
MRR
NDCG
SL
0.520 ± 0.049 0.738 ± 0.047
SSL
0.602 ± 0.048 0.814 ± 0.053
Proposed 0.675 ± 0.047 0.900 ± 0.039
Table 4. Average MRR and NDCG in the Patent data set and their standard deviation.
MRR
NDCG
SL
0.029 ± 0.021 0.157 ± 0.021
SSL
0.025 ± 0.018 0.153 ± 0.019
Proposed 0.034 ± 0.023 0.166 ± 0.026

that maximizes entropy under the constraints imposed by the given data. The
probability that the ith sample is classiﬁed into class k is calculated as follows,exp(θk> xi ),P (k|i) = ∑K>
l=1 exp(θl xi )(19)

where θk is a parameter vector for class k. The labels were ranked according thisestimated probability. The parameters can be obtained using maximum a posteriori (MAP) estimation with Gaussian priors. We chose the hyper-parameters
for the Gaussian priors from {10−2 , 10−1 , 1} that achieved the best performance.
For the semi-supervised method (SSL), we used a graph-based semi-supervised
method, or label propagation [12]. The graph-based semi-supervised method coincides with the proposed method when the class graph is constructed with
vkl = 1 if k = l, and vkl = 0 otherwise as described before. We set the precisionparameter for Gaussian kernel at α = 1, and the number of neighbors at 10
when we construct the graph.
With the proposed method, we set the precision parameters for Gaussian
kernel at α = 1 and β = 1, and the number of neighbors at 10 when we constructboth of the sample and class graphs. With the semi-supervised and proposed
method, we estimated labels using iterative algorithms.
4.4

Results

Tables 3 and 4 show the averages of MRR and NDCG and their standard deviations over 100 experiments with Swissroll and Patent data sets, respectively. The
proposed method achieved the best performance in both data sets. This result
indicates that the proposed method can appropriately assign labels through its
use of label-only samples as well as unlabeled samples.
Figure 4 shows NDCGs achieved by the proposed method with diﬀerent numbers of label-only samples in Swissroll and Patent data sets. As the number oflabel-only samples increases, the NDCG increases. The MRR showed the same

0.92
0.9

NDGC

0.88
0.86
0.84
0.82
0.8
0

100

200

300

400

500

3000

4000

5000

O

(a) Swissroll
0.168
0.166
0.164
NDGC

0.162
0.16
0.158
0.156
0.154
0.152
0

1000

2000
O

(b) PatentFig. 4. NDCG with diﬀerent numbers of label-only samples.

tendency of the NDCG. This result implies that the proposed method can obtain
relationships between classes more precisely by using more label-only samples.

5

Conclusion

We presented bidirectional semi-supervised learning, which is a novel machinelearning task to improve performance by using label-only samples as well aslabeled and unlabeled samples. We then proposed a simple and eﬀective graphbased method for bidirectional semi-supervised learning. The proposed method
assumes that correlated classes are likely to have the same labels among the similar samples. The correlated classes can be found by using labeled and label-onlysamples, and the similar samples can be found by using labeled and unlabeled
samples. In experiments with synthetic and text data sets, we conﬁrmed thatthe proposed method can improve the performance of multi-label classiﬁcation.

Although our results have been encouraging as a ﬁrst step towards bidirectional semi-supervised learning, we must extend our approach in a number of directions. First, we can extend the proposed method by using more advanced techniques for graph-based semi-supervised learning because the proposed method
uses the same framework with the graph-based semi-supervised learning methods. Examples include methods for learning weight matrices [12], and eﬃcientalgorithms for label estimation [33, 34].
Second, we need to investigate methods for bidirectional semi-supervised
learning other than the proposed graph-based method. In the semi-supervised
learning, a wide variety of methods have been proposed such as transductive
SVMs [35, 36], methods using generative models [1, 37] as well as graph-based
methods. These methods might be helpful for considering new bidirectional semisupervised learning methods.
Finally, we would like to evaluate the proposed method in other real applications. Application examples include collaborative ﬁltering [4, 5], cross-lingual
information retrieval [6–8], and image annotation [10, 11].

References
1. Nigam, K., McCallum, A.K., Thrun, S., Mitchell, T.M.: Text classiﬁcation fromlabeled and unlabeled documents using EM. Machine Learning 39(2/3) (2000)
103–134
2. Daume III, H., Marcu, D.: Domain adaptation for statistical classiﬁers. Journal of
Artiﬁcial Intelligence Research 26 (2006) 101–126
3. Iwata, T., Tanaka, T., Yamada, T., Ueda, N.: Improving classiﬁer performanceusing data with diﬀerent taxonomies. IEEE Transactions on Knowledge and Data
Engineering 23(11) (2011) 1668–1677
4. Li, T., Yan, S., Kweon, T.M.I.S.: Local-driven semi-supervised learning with multilabel. In: IEEE International Conference on Multimedia and Expo. ICME ’09(2009) 1508–1511
5. Nakatsuji, M., Fujiwara, Y., Tanaka, A., Uchiyama, T., Ishida, T.: Recommendations over domain speciﬁc user graphs. In: Proceeding of the 2010 conference on
ECAI 2010: 19th European Conference on Artiﬁcial Intelligence. (2010) 607–612
6. Dumais, S.T., Landauer, T.K., Littman, M.L.: Automatic cross-linguistic information retrieval using latent semantic indexing. In: Proceedings of Workshop on
Cross-Linguistic Information Retrieval in SIGIR’ 96. (1996) 16–23
7. Xu, J., Weischedel, R., Nguyen, C.: Evaluating a probabilistic model for crosslingual information retrieval. In: Proceedings of the 24th Annual International
ACM SIGIR Conference on Research and Development in Information Retrieval.
SIGIR ’01 (2001) 105–110
8. Platt, J.C., Toutanova, K., Yih, W.: Translingual document representations fromdiscriminative projections. In: Proceedings of the 2010 Conference on Empirical
Methods in Natural Language Processing. EMNLP ’10 (2010) 251–261
9. Blei, D.M., Jordan, M.I.: Modeling annotated data. In: SIGIR ’03: Proceedings ofthe 26th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. (2003) 127–134
10. Socher, R., Fei-Fei, L.: Connecting modalities: Semi-supervised segmentation andannotation of images using unaligned text corpora. In: Proceedings of the IEEE
Conference on Computer Vision and Pattern Recognition. CVPR (2010) 966–973

11. Kimura, A., Kameoka, H., Sugiyama, M., Nakano, T., Maeda, E., Sakano, H.,
Ishiguro, K.: Semicca: Eﬃcient semi-supervised learning of canonical correlations.
In: Proceedings of IAPR International Conference on Pattern Recognition. ICPR
’10 (2010) 2933–2936
12. Zhu, X., Ghahramani, Z., Laﬀerty, J.: Semi-supervised learning using Gaussianﬁelds and harmonic functions. In: Proceedings of the 20th International Conference
on Machine Learning. ICML ’03 (2003) 912–919
13. Zhou, D., Bousquet, O., Lal, T.N., Weston, J., Scholkopf, B.: Learning with local
and global consistency. In: Advances in Neural Information Processing Systems
16, MIT Press (2004) 321–328
14. Belkin, M., Matveeva, I., Niyogi, P.: Regularization and semi-supervised learningon large graphs. In: Proceedings of the Annual Conference on Learning Theory.
COLT, Springer (2004) 624–638
15. Zhu, X., Goldberg, A.B.: Introduction to Semi-Supervised Learning. Synthesis Lectures on Artiﬁcial Intelligence and Machine Learning. Morgan & Claypool(2009)
16. Subramanya, A., Bilmes, J.: Soft-supervised learning for text classiﬁcation. In: Proceedings of the Conference on Empirical Methods in Natural Language Processing.
EMNLP ’08, Stroudsburg, PA, USA, Association for Computational Linguistics(2008) 1090–1099
17. Cao, L., Luo, J., Huang, T.S.: Annotating photo collections by label propagationaccording to multiple similarity cues. In: Proceedings of the 16th ACM international conference on Multimedia. MM ’08, New York, NY, USA, ACM (2008)
121–130
18. Kato, T., Kashima, H., Sugiyama, M.: Robust label propagation on multiple networks. IEEE Transactions on Neural Networks 20(1) (2009) 35–44
19. Zhu, X., Ghahramani, Z.: Learning from labeled and unlabeled data with label
propagation. Technical report, Carnegie Mellon University (2002)
20. Bengio, Y., Delalleau, O., Roux, N.L.: Label propagation and quadratic criterion.
In et al., O.C., ed.: Semi-supervised learning. MIT Press, Cambridge, MA, USA(2006)
21. Wang, J., Zhao, Y., Wu, X., Hua, X.S.: Transductive multi-label learning for video
concept detection. In: Proceedings of the 1st ACM international conference on
Multimedia information retrieval. MIR ’08, New York, NY, USA, ACM (2008)
298–304
22. Zha, Z.J., Mei, T., Wang, J., Wang, Z., Hua, X.S.: Graph-based semi-supervised
learning with multiple labels. J. Vis. Comun. Image Represent. 20 (February 2009)97–10323. Liu, W., Chang, S.F.: Robust multi-class transductive learning with graphs. In:
IEEE Conference on Computer Vision and Pattern Recognition. CVPR ’09 (2009)381–388
24. Liu, Y., Jin, R., Yang, L.: Semi-supervised multi-label learning by constrained
non-negative matrix factorization. In: Proceedings of the 21st national conferenceon Artiﬁcial intelligence. AAAI’06, AAAI Press (2006) 421–426
25. Tenenbaum, J.B., de Silva, V., Langford, J.C.: A global geometric framework for
nonlinear dimensionality reduction. Science 290(5500) (December 2000) 2319–2323
26. Roweis, S., Saul, L.: Nonlinear dimensionality reduction by locally linear embedding. Science 290(5500) (December 2000) 2323–2326
27. Matsubayashi, T., Yamada, T.: The hierarchical individual timestep method forlarge-scale graph drawing. In: Proc. of the 15th International Symposium on Graph
Drawing. GD ’07 (2007)28. Järvelin, K., Kekäläinen, J.: Cumulated gain-based evaluation of IR techniques.
ACM Trans. Inf. Syst. 20 (October 2002) 422–446
29. Lin, X., Chen, X.w.: Mr.KNN: soft relevance for multi-label classiﬁcation. In: Proceedings of the 19th ACM International Conference on Information and Knowledge
Management. CIKM ’10, New York, NY, USA, ACM (2010) 349–358
30. Angelova, R., Kasneci, G., Weikum, G.: Graﬃti: graph-based classiﬁcation inheterogeneous networks. World Wide Web (2011)31. Yang, Y., Gopal, S.: Multilabel classiﬁcation with meta-level features in a learningto-rank framework. Machine Learning (2011)
32. Nigam, K., Laﬀerty, J., McCallum, A.: Using maximum entropy for text classiﬁcation. In: Proceedings of IJCAI-99 Workshop on Machine Learning for Informat
ion Filtering. (1999) 61–67
33. Garcke, J., Griebel, M.: Semi-supervised learning with sparse grids. In: Proc. ofthe 22nd ICML Workshop on Learning with Partially Classiﬁed Training Data.
(2005)
34. Mahdaviani, M., Freitas, O.D., Fraser, B., Hamze, F.: Fast computational methods
for visually guided robots. In: Proc. of the International Conference on Robotics
and Automation. ICRA ’05 (2005)
35. Bennett, K.P., Demiriz, A.: Semi-supervised support vector machines. In: Advancesin Neural Information Processing Systems, MIT Press (1999) 368–374
36. Fung, G., Mangasarian, O.L.: Semi-supervised support vector machines for unlabeled data classiﬁcation. Optimization Methods and Software 15 (2001) 29–44
37. Fujino, A., Ueda, N., Saito, K.: Semisupervised learning for a hybrid generative/discriminative classiﬁer based on the maximum entropy principle. IEEE
Transactions on Pattern Analysis and Machine Intelligence 30(3) (2008) 424–437