Margin Perceptrons for Graphs

This contribution extends linear classifiers to sub-linear classifiers for graphs and analyzes their properties. The results are (i) a geometric interpretation of sub linear classifiers, (ii) a generic learning rule based on the principle of empirical risk minimization, (iii) a convergence theorem for the margin perceptron in the separable case, and (iv) the VC-dimension of sub linear functions. Empirical results on graph data show that the perceptron and margin perceptron algorithm on graphs have similar properties as their vectorial counterparts.