A0226
Title: Barycentric subspace analysis of a set of graphs
Authors: Elodie Maignant - Zuse Institute Berlin (Germany) [presenting]
Xavier Pennec - Université Côte d'Azur and INRIA (France)
Anna Calissano - Imperial College London (Italy)
Abstract: In the context of statistical analysis of populations of graphs, unlabeled graphs are usually modeled as equivalence classes under the action of permutations on nodes or, equivalently, under the action by conjugation of permutation matrices on adjacency matrices. Such a model relies, however, on the combinatorial problem of graph matching and is therefore computationally limited. As a relaxation of the previous action, we introduce a new framework where graphs are modeled in the quotient space resulting from the action of rotations on the set of adjacency matrices. Now, beyond the idea of relaxation, our approach takes on a natural interpretation from the point of view of spectral graph theory, that is, the study of graphs through their spectrum, a descriptor that has been proven to encode numerous structural properties. Indeed, the action of rotations by conjugation preserves the eigenvalues of a graph (represented by its adjacency matrix), and each resulting equivalence class is exactly the set of all the graphs with a given spectrum, also called cospectral graphs. We unveil the very particular and surprisingly simple geometry of these quotient spaces. Then, within such model, we investigate Barycentric Subspace Analysis (BSA), a non-Euclidean dimensionality reduction method. Through several examples, we illustrate that BSA is a powerful dimensionality reduction tool with great interpretability, particularly when it is used to analyze a set of graphs.
