A Novel Graph-Based Fisher Kernel Method for Semi-supervised Learning

Graph-based semi-supervised learning methods play a key role in machine learning applications, particularly when no parametric information or other prior knowledge is available. Given a graph whose nodes represent the points and the weighted edges the relations between them, the goal is to predict the values of all unlabeled nodes exploiting the information provided by both label and unlabeled nodes. In this paper, we propose a novel graph-based approach for semi-supervised binary classification. The algorithm extends the Fisher Subspace estimation approaches by adopting a kernel graph covariance measure. This similarity measure defines a relation between nodes generalizing both the shortest path and the commute time distance. This quantity is called the sum-over-paths covariance. Experiments on synthetic and real-world datasets highlight that the proposed algorithm achieves better results with respect to those obtained by state-of-the-art competitors.