Adaptive edge weighting for graph-based learning algorithms

Masayuki Karasuyama*, Hiroshi Mamitsuka

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

16 Citations (Scopus)
440 Downloads (Pure)


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.

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


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


Dive into the research topics of 'Adaptive edge weighting for graph-based learning algorithms'. Together they form a unique fingerprint.

Cite this