Help Privacy Policy Disclaimer
  Advanced SearchBrowse




Journal Article

Graph sharpening


Hill,  NJ
Department Empirical Inference, Max Planck Institute for Biological Cybernetics, Max Planck Society;
Max Planck Institute for Biological Cybernetics, Max Planck Society;

Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available

Shin, H., Hill, N., Lisewski, H., & Park, J.-S. (2010). Graph sharpening. Expert Systems with Applications, 37(12), 7870-7879. doi:10.1016/j.eswa.2010.04.050.

Cite as: https://hdl.handle.net/21.11116/0000-0002-689F-7
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 this paper, we present one solution satisfying the principle, in order to show that it can improve performance on a number of publicly available bench-mark data sets. When tested on a real-world problem, protein function classification with four vastly different molecular similarity graphs, sharpening improved ROC scores by 16% on average, at negligible computational cost.