Predicting the Labelling of a Graph via Minimum $p$-Seminorm Interpolation

Abstract

We study the problem of predicting the labelling of a graph. The graph is given and a trial sequence of (vertex, label) pairs is then incrementally revealed to the learner. On each trial a vertex is queried and the learner predicts a boolean label. The true label is then returned. The learner's goal is to minimise mistaken predictions. We propose minimum p-seminorm interpolation to solve this problem. To this end we give a p-seminorm on the space of graph labellings. Thus on every trial we predict using the labelling which minimises the p-seminorm and is also consistent with the revealed (vertex, label) pairs. When p = 2 this is the harmonic energy minimisation procedure of [22], also called (Laplacian) interpolated regularisation in [1]. In the limit as $p \to 1$ this is equivalent to predicting with a label-consistent mincut. We give mistake bounds relative to a label-consistent mincut and a resistive cover of the graph. We say an edge is cut with respect to a labelling if the connected vertices have disagreeing labels. We find that minimising the p-seminorm with p = 1 + $\varepsilon$ where $\varepsilon$ →0 as the graph diameter D →$\infty$gives a bound of $O(\Phi^2 \log D)$ versus a bound of $O(\Phi D)$ when p = 2 where $\Phi$ is the number of cut edges.