Active and online learning of convex sets on graphs
Data: Giovedì 16 giugno
Luogo: Aula 5016 (Lab LM)
Speaker: Maximilian Thiessen (TU Wien)
Persona di riferimento: Marco Bressan
Abstract: Node classification is a well-known problem in graph-based machine learning, where the goal is to predict the binary node labels of a given graph. Many theoretical results exist, including bounds on the number of mistakes in the online learning model and query complexity bounds in the active learning model. In this talk, we present a new perspective on active and online node classification using convexity theory. Geodesic (i.e., shortest-path based) convexity is a natural generalisation of Euclidean convexity and allows the definition of convex sets and halfspaces on graphs. We discuss that in many applications, clusters and communities in networks tend to form geodesically convex subgraphs. In the first half of the talk, we focus on the problem of learning geodesically convex halfspaces on graphs and study its query complexity. We prove general upper bounds on the query complexity and show tight lower bounds corresponding to well-established separation axioms. While previous bounds typically depend on the cut size of the labelling, all parameters in our bounds can be computed from the unlabelled graph. In the second half of the talk, we discuss online learning of general convex sets on graphs. We discuss simple mistake bounds based on the halving algorithm and introduce an efficient alternative achieving almost the same bound in the special case of halfspaces.
Bio: Max is a PhD student supervised by Prof. Thomas Gärtner in the machine learning research unit at TU Wien, Austria. Before that, he studied computer science at the University of Bonn, Germany, under the supervision of Dr. Tamás Horváth. His main research interest is active and semi-supervised learning. He focuses on novel sample and query complexity bounds for learning tasks on graphs using, among other things, convexity theory.