Exploratory data analysis of graph embeddings: exploiting manifold structure

点击翻译按钮获取中文摘要

My research consists of statistical inference based on graphs, similarity matrices, or other relational information. This work has important societal, humanitarian and scientific implications, for example: uncovering malicious activity on the dark web, performing intrusion detection on a corporate enterprise network, or stopping DDOS/BGP hijacks at global internet scales, which all require sophisticated network analysis of internet traffic data. Finally, similarity matrices constructed by morphological comparison of cells in active/inactive states, in healthy/diseased conditions, or before/after treatment may yield insights into drug development. For graphs that follow a latent position model, it was only recently observed that the high-dimensional embedding obtained by matrix factorisation concentrate about a low dimensional set, in the Hausdorff sense. The objective of this research project is to uncover the connections between the geometric features of spectral embeddings of graphs and the spectral properties of the underlying kernel in order to derive inference procedures, such as kernel parameter estimation and tests of common network hypotheses. These tools will be released as code, supported by theory and demonstrated on applications such as those mentioned above. So far, our contribution is to describe the topology and geometry of the low dimensional set, proving it is a topological manifold and establishing the link between in-manifold geodesic distance and geodesic distance in latent space. A key feature of our problem setup is that the kernel used to produce the graph is unknown, in which case the manifold is not available in closed form and typically lives in infinite-dimensional space. The aim is to further this work for different classes kernels in a unified framework, or, more broadly, formulate a statistically well-principled approach to interpreting the geometric structure of spectral embeddings as part of exploratory data analysis and visualisation. Beyond this, there are a number of related avenues for investigation: * other types of graphs, including directed, multi-partite, and weighted* sparsity* time dynamics * other statistical inference procedures associated with graphs such as regression, classification, model selection.