Deformed Graph Laplacian for Semisupervised Learning

By Chen Gong, Tongliang Liu, Dacheng Tao, Keren Fu, Enmei Tu, Jie Yang. 2015

124 citations recorded by the source corpus.

Graph Laplacian has been widely exploited in traditional graph-based semisupervised learning (SSL) algorithms to regulate the labels of examples that vary smoothly on the graph. Although it achieves a promising performance in both transductive and inductive learning, it is not effective for handling ambiguous examples (shown in Fig. 1). This paper introduces deformed graph Laplacian (DGL) and presents label prediction via DGL (LPDGL) for SSL. The local smoothness term used in LPDGL, which regularizes examples and their neighbors locally, is able to improve classification accuracy by properly dealing with ambiguous examples. Theoretical studies reveal that LPDGL obtains the globally optimal decision function, and the free parameters are easy to tune. The generalization bound is derived based on the robustness analysis. Experiments on a variety of real-world data sets demonstrate that LPDGL achieves top-level performance on both transductive and inductive settings by comparing it with popular SSL algorithms, such as harmonic functions, AnchorGraph regularization, linear neighborhood propagation, Laplacian regularized least square, and Laplacian support vector machine.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Jun Zhu
2. Liyuan Wang
3. Chongxuan Li
4. Lanqing Hong
5. Zhenguo Li
6. Kuo Yang
7. Chen Gong
8. Xiaojun Chang

In Computer Vision and Pattern Recognition

1. Jun Zhu
2. Liyuan Wang
3. Zhenguo Li
4. Chongxuan Li
5. Lanqing Hong
6. Yucen Luo
7. Kuo Yang
8. Jian Yang

Citations in the corpus

• ORDisCo: Effective and Efficient Usage of Incremental Unlabeled Data for Semi-supervised Continual Learning (2021, background): “Graph Laplacian regularization [6] penalizes the variation of labels on the graph of manifold structure.”
• Smooth Neighbors on Teacher Graphs for Semi-Supervised Learning (2017, background): “Many of them often optimize a supervised loss over labeled data with a graph Laplacian regularizer [4, 18].”
• Two-Stage Label Embedding via Neural Factorization Machine for Multi-Label Classification (2019, background): “Single-label classification (Gong et al. 2015; 2016; Deng et al. 2018b) is one of the most well-known machine learning problems, where each instance x is associated with a single label.”
• Revealing Event Saliency in Unconstrained Video Collection (2017, unknown): “Different from the traditional graph Laplacian, the DGL additionally regularizes the data which corresponds to a low degree in the established graph.”
• Teaching Semi-Supervised Classifier via Generalized Distillation (2018, methodology): “…algorithms: Reliable Label Inference via Smoothness Hypothesis (ReLISH) [Gong et al. , 2014], Label Prediction via Deformed Graph Laplacian (LPDGL) [Gong et al. , 2015a], and Laplacian Regular-ized Least Squares (LapRLS) [Belkin et al. , 2006], among which LapRLS is the basic learner in our GDSSL…”