An Online Algorithm for Learning a Labeling of a Graph

This short report analyzes a simple and intuitive online learning algorithm - termed the graphtron - for learning a labeling over a fixed graph, given a sequence of labels. The contribution is twofold