event
Thursday 11 Oct 2018: Change detection on sequences of graphs
Daniele Zambon, Daniele Grattarola - University of Exeter
Harrison 170 14:30-15:30
Many fields, like physics, neuroscience, chemistry, and sociology, investigate phenomena that can be effectively described as a sequence of multivariate measurements, where the pairwise relations between different elements of a system can be represented as a sequence of attributed graphs that change over time. Here, the identification of a possible change in the behaviour of the data stream - a situation associated with anomalies or events in the observed system- stands out as a major research challenge. Due to the variety of real-world applications, graphs come in different forms, with variable attributes, topology, and ordering, making it difficult to perform a mathematical analysis in the graph space.
In order to tackle this challenge, we propose a two-step methodology based on embedding graphs into a vector space, where conventional multivariate statistical hypothesis testing can be applied. The first contribution associated with the methodology consists in theoretical results showing how the confidence level of an event occurring in the graph domain can be associated with the confidence level of the actual test applied on the embedding space; this enables the identification of events in the graph domain through the embedding space.
The second contribution delves deeper in the selection of the embedding strategy and, motivated by the fact that metric graph distances are not practical even for moderately-large-scale applications, introduces a deep learning technique based on generative adversarial networks, which allows us to embed graphs without having to perform all computations in the graph domain. Finally, we show how to extend both techniques to account for the intrinsic non-Euclidean nature of graphs, by considering constant-curvature Riemannian manifolds as embedding spaces, obtaining significant performance improvements in change detection. We discuss the effectiveness of our results on several problems, including a real-world scenario of epileptic seizure prediction on brain networks.
