138
Chapter 9. Signed graph-based semi-supervised learning
Blum et al. [7, 8] was the first to use graph cut ideas for classification by simple counting the edges between classes. Joachims [42] embeds the graph first, and
then learns from the embeddings. Zhu et al. [123] proposed the first approach using a Laplacian kernel in the optimal function and called it the Gaussian Random
Fields SSL approach. Zhou et al. [118] proposed a more relaxed version: the Local
and Global Consistency (LGC) approach, which counts the distances from the labelled nodes to the corresponding labelled node as penalties in the objective function.
Belkin et al. [4, 5] proposed two similar versions based on SVM (LapSVM) and Regularized Least Squares. Melacci and Belkin [59] later refine the LapSVM approach
and reduced the computational complexity for training from O(n 3 ) to O(kn 2 ).
Subramanya et al. [93] compared various approaches using several common
datasets. Based on their experiments, there is no single approach which performs the
best for all datasets.
The problem of imbalance has been considered by Li et al. [52] in the context
of sentiment prediction. They compare undersampling and oversampling approaches
(which assume that labelled examples are relatively plentiful) to dynamic subspaces
using attribute selection and show that this latter technique improves prediction performance by 2 to 4 percentage points. However, subspace sampling approaches can
only be applied to attributed data, and not to data that is already graphical, for example social networks.
The approach in this chapter was first described in Zheng and Skillicorn [113].
Chapter 9. Signed graph-based semi-supervised learning
Blum et al. [7, 8] was the first to use graph cut ideas for classification by simple counting the edges between classes. Joachims [42] embeds the graph first, and
then learns from the embeddings. Zhu et al. [123] proposed the first approach using a Laplacian kernel in the optimal function and called it the Gaussian Random
Fields SSL approach. Zhou et al. [118] proposed a more relaxed version: the Local
and Global Consistency (LGC) approach, which counts the distances from the labelled nodes to the corresponding labelled node as penalties in the objective function.
Belkin et al. [4, 5] proposed two similar versions based on SVM (LapSVM) and Regularized Least Squares. Melacci and Belkin [59] later refine the LapSVM approach
and reduced the computational complexity for training from O(n 3 ) to O(kn 2 ).
Subramanya et al. [93] compared various approaches using several common
datasets. Based on their experiments, there is no single approach which performs the
best for all datasets.
The problem of imbalance has been considered by Li et al. [52] in the context
of sentiment prediction. They compare undersampling and oversampling approaches
(which assume that labelled examples are relatively plentiful) to dynamic subspaces
using attribute selection and show that this latter technique improves prediction performance by 2 to 4 percentage points. However, subspace sampling approaches can
only be applied to attributed data, and not to data that is already graphical, for example social networks.
The approach in this chapter was first described in Zheng and Skillicorn [113].