9.3. Summary
137
and stabilizes with fewer labelled nodes than LGC, TACO and LapSVMp. The LGC
and TACO approaches have also a stable performance, but LapSVMp approach has
worse performance on the synthetic dataset and the ISOLET dataset. The results for
two classes are similar to the four-class case, but the LapSVMp approach has similar
performance to ours using the ISOLET data.
Our GBE approach shows a lower error rate when the number of labelled nodes
in each class is the same, but the number of instances of each class is different. Thus
it performs at approximately the same level as the other state-of-the-art algorithms
in the balanced cases, but outperforms them in both imbalanced cases: imbalanced
class sizes, and imbalanced numbers of labelled points.
9.3 Summary
The attraction of graph-based semi-supervised learning algorithms is that they not
only use the class label information, but also exploit the graph structure, in particular the intuition that connected nodes “should”, in general, have the same labels.
Graph-based SSL approaches tend to have better performance than non-graph-based
SSL [92]. We have combined the intuition that graph structure helps class label assignments with our new technique for signed network embedding, The performance
of our technique matches that of the comparable approaches when the class sizes are
balanced, but exceeds them substantially when classes are imbalanced — which is
the typical real-world case. The performance differences illustrate the weakness of
these other two methods — their embedding creates the same well-known problem
as k-means when the classes are of different sizes and shapes because they place the
decision boundary in the “middle” of the class representatives.
Notes
There are two ways of framing the graph-based SSL problem which have led to
different algorithmic strategies. One is based on probability. The Information Regularization approach [21, 41] is an example of the early work of this kind. The adsorption approach [3] is another example based on random-walk probability. Two
modified versions of the adsorption approach [73, 94] were proposed later. There are
also some other similar versions, for example the Quadratic Criteria approach [6]
and Measure Propagation [92].
The other way to frame this problem is based on graph cuts and Laplacian
kernels. An overview of the properties and interpretation of spectral clustering can
be found in [101]. In these approaches, classification is carried out in the embedded
graph by classifying each unlabelled point as belonging to the class of its (Euclidean
distance) nearest labelled neighbor.
Subsequently, many extensions of spectral graph analysis approaches have
been developed, including a signed graph spectral approach based on placing negative pairs on opposite sides of the axis [48], and a signed graph spectral approach
based on pushing negative pairs apart [112].
137
and stabilizes with fewer labelled nodes than LGC, TACO and LapSVMp. The LGC
and TACO approaches have also a stable performance, but LapSVMp approach has
worse performance on the synthetic dataset and the ISOLET dataset. The results for
two classes are similar to the four-class case, but the LapSVMp approach has similar
performance to ours using the ISOLET data.
Our GBE approach shows a lower error rate when the number of labelled nodes
in each class is the same, but the number of instances of each class is different. Thus
it performs at approximately the same level as the other state-of-the-art algorithms
in the balanced cases, but outperforms them in both imbalanced cases: imbalanced
class sizes, and imbalanced numbers of labelled points.
9.3 Summary
The attraction of graph-based semi-supervised learning algorithms is that they not
only use the class label information, but also exploit the graph structure, in particular the intuition that connected nodes “should”, in general, have the same labels.
Graph-based SSL approaches tend to have better performance than non-graph-based
SSL [92]. We have combined the intuition that graph structure helps class label assignments with our new technique for signed network embedding, The performance
of our technique matches that of the comparable approaches when the class sizes are
balanced, but exceeds them substantially when classes are imbalanced — which is
the typical real-world case. The performance differences illustrate the weakness of
these other two methods — their embedding creates the same well-known problem
as k-means when the classes are of different sizes and shapes because they place the
decision boundary in the “middle” of the class representatives.
Notes
There are two ways of framing the graph-based SSL problem which have led to
different algorithmic strategies. One is based on probability. The Information Regularization approach [21, 41] is an example of the early work of this kind. The adsorption approach [3] is another example based on random-walk probability. Two
modified versions of the adsorption approach [73, 94] were proposed later. There are
also some other similar versions, for example the Quadratic Criteria approach [6]
and Measure Propagation [92].
The other way to frame this problem is based on graph cuts and Laplacian
kernels. An overview of the properties and interpretation of spectral clustering can
be found in [101]. In these approaches, classification is carried out in the embedded
graph by classifying each unlabelled point as belonging to the class of its (Euclidean
distance) nearest labelled neighbor.
Subsequently, many extensions of spectral graph analysis approaches have
been developed, including a signed graph spectral approach based on placing negative pairs on opposite sides of the axis [48], and a signed graph spectral approach
based on pushing negative pairs apart [112].