Timezone: »

Label Selection on Graphs
Andrew Guillory · Jeff Bilmes

Tue Dec 08 07:00 PM -- 11:59 PM (PST) @ None #None

We investigate methods for selecting sets of labeled vertices for use in predicting the labels of vertices on a graph. We specifically study methods which choose a single batch of labeled vertices (i.e. offline, non sequential methods). In this setting, we find common graph smoothness assumptions directly motivate simple label selection methods with interesting theoretical guarantees. These methods bound prediction error in terms of the smoothness of the true labels with respect to the graph. Some of these bounds give new motivations for previously proposed algorithms, and some suggest new algorithms which we evaluate. We show improved performance over baseline methods on several real world data sets.

Author Information

Andrew Guillory (University of Washington)
Jeff Bilmes (University of Washington, Seattle)

More from the Same Authors