Adaptive edge weighting for graph-based learning algorithms

Research output: Contribution to journalArticleScientificpeer-review

Researchers

Research units

  • Nagoya Institute of Technology
  • Bioinformatics Center
  • Kyoto University

Abstract

Graph-based learning algorithms including label propagation and spectral clustering are known as the effective state-of-the-art algorithms for a variety of tasks in machine learning applications. Given input data, i.e. feature vectors, graph-based methods typically proceed with the following three steps: (1) generating graph edges, (2) estimating edge weights and (3) running a graph based algorithm. The first and second steps are difficult, especially when there are only a few (or no) labeled instances, while they are important because the performance of graph-based methods heavily depends on the quality of the input graph. For the second step of the three-step procedure, we propose a new method, which optimizes edge weights through a local linear reconstruction error minimization under a constraint that edges are parameterized by a similarity function of node pairs. As a result our generated graph can capture the manifold structure of the input data, where each edge represents similarity of each node pair. To further justify this approach, we also provide analytical considerations for our formulation such as an interpretation as a cross-validation of a propagation model in the feature space, and an error analysis based on a low dimensional manifold model. Experimental results demonstrated the effectiveness of our adaptive edge weighting strategy both in synthetic and real datasets.

Details

Original languageEnglish
Pages (from-to)307-335
JournalMachine Learning
Volume106
Issue number2
Publication statusPublished - 2017
MoE publication typeA1 Journal article-refereed

    Research areas

  • Clustering, Edge weighting, Graph-based learning, Manifold assumption, Semi-supervised learning

Download statistics

No data available

ID: 9529942