MoN18: Eighteenth Mathematics of Networks meeting
James Robinson (UCL) Predicting switching graph labelings with cluster specialists
We address the problem of predicting the labeling of a graph in an online setting when the labeling is changing over time. Our primary algorithm is based on a specialist approach; we develop the machinery of cluster specialists which probabilistically exploits the cluster structure in the graph. The algorithm makes use of a given set of these cluster specialists, and we explore two distinct sets in this paper. We show that one such variant of this algorithm surprisingly only requires O(log n) time on any trial t on an n-vertex graph. Our secondary algorithm is a quasi-Bayesian classifier which requires O(t log n) time to predict at trial t. We prove switching mistake-bound guarantees for both algorithms. For our primary algorithm, the switching guarantee smoothly varies with the magnitude of the change between successive labelings. In preliminary experiments we compare the performance of these algorithms against an existing algorithm (a kernelized Perceptron) and show that our algorithms perform better on synthetic data.
Contact:
Keith Briggs
(
)
or
Richard G. Clegg (richard@richardclegg.org)