Header logo is

Graph Based Semi-Supervised Learning with Sharper Edges


Conference Paper


In many graph-based semi-supervised learning algorithms, edge weights are assumed to be fixed and determined by the data points‘ (often symmetric)relationships in input space, without considering directionality. However, relationships may be more informative in one direction (e.g. from labelled to unlabelled) than in the reverse direction, and some relationships (e.g. strong weights between oppositely labelled points) are unhelpful in either direction. Undesirable edges may reduce the amount of influence an informative point can propagate to its neighbours -- the point and its outgoing edges have been ``blunted.‘‘ We present an approach to ``sharpening‘‘ in which weights are adjusted to meet an optimization criterion wherever they are directed towards labelled points. This principle can be applied to a wide variety of algorithms. In the current paper, we present one ad hoc solution satisfying the principle, in order to show that it can improve performance on a number of publicly available benchmark data sets.

Author(s): Shin, H. and Hill, NJ. and Rätsch, G.
Book Title: ECML 2006
Journal: Machine Learning: ECML 2006
Pages: 401-412
Year: 2006
Month: September
Day: 0
Editors: F{\"u}rnkranz, J. , T. Scheffer, M. Spiliopoulou
Publisher: Springer

Department(s): Empirical Inference
Bibtex Type: Conference Paper (inproceedings)

DOI: 10.1007/11871842_39
Event Name: 17th European Conference on Machine Learning (ECML)
Event Place: Berlin, Germany

Address: Berlin, Germany
Digital: 0
Language: en
Organization: Max-Planck-Gesellschaft
School: Biologische Kybernetik

Links: PDF


  title = {Graph Based Semi-Supervised Learning with Sharper Edges},
  author = {Shin, H. and Hill, NJ. and R{\"a}tsch, G.},
  journal = {Machine Learning: ECML 2006},
  booktitle = {ECML 2006},
  pages = {401-412},
  editors = {F{\"u}rnkranz, J. , T. Scheffer, M. Spiliopoulou},
  publisher = {Springer},
  organization = {Max-Planck-Gesellschaft},
  school = {Biologische Kybernetik},
  address = {Berlin, Germany},
  month = sep,
  year = {2006},
  month_numeric = {9}