Title: The geometry of graph space: Towards graph-valued statistics
Authors: Aasa Feragen - Technical University of Denmark (Denmark) [presenting]
Anna Calissano - Politecnico di Milano (Italy)
Simone Vantini - Politecnico di Milano (Italy)
Abstract: Graph-structured data are abundant in both nature and science, including blood- or lymphatic networks in the body; molecules in chemoinformatics; social networks in communication, or transportation networks in urban planning. While state-of-the-art machine learning such as neural networks are efficient for solving simple problems such as classification of graphs, which predicts a simple, discrete output (a class), they have a harder time solving problems whose answer is a graph, such as graph interpolation, decomposition of variance (PCA), or graph-valued regression. We discuss a space of attributed graphs with variable number of nodes, formed as a quotient of a space of adjacency graphs with respect to a node permutation group. The limitations and possibilities that derive from the geometric properties of the resulting graph-space will be explained. Moreover, problems with existing heuristics for statistics in this and related spaces will be discussed, and a novel strategy for computing statistics in quotient spaces will be presented. This novel strategy will be applied to the particular case of graph-space, defining principal component analysis as well as regression taking values in graph-space, along with heuristics that make them computationally practical.