Exploratory data analysis of graph embeddings: exploiting manifold structure

我的研究包括基于图表、相似矩阵或其他关系信息的统计推断。这项工作具有重要的社会、人道主义和科学意义，例如：发现黑暗网络上的恶意活动，在企业企业网络上执行入侵检测，或者在全球互联网规模上阻止DDOS/BGP劫持，这些都需要对互联网流量数据进行复杂的网络分析。最后，通过对处于活动/非活动状态、健康/疾病状态或治疗前/后的细胞进行形态比较而构建的相似性矩阵可能会对药物开发产生洞察力。对于遵循潜在位置模型的图，最近才观察到通过矩阵因式分解得到的高维嵌入集中在Hausdorff意义下的低维集合。这个研究项目的目的是揭示图的谱嵌入的几何特征和底层核的谱性质之间的联系，以便推导出推理过程，如核参数估计和常见网络假设的测试。这些工具将以代码的形式发布，并得到理论支持，并在上述应用程序中进行演示。到目前为止，我们的贡献是描述了低维集合的拓扑和几何，证明了它是一个拓扑流形，并在潜在空间中建立了流形内测地距离和测地距离之间的联系。我们的问题设置的一个关键特征是用于生成图形的核是未知的，在这种情况下，流形不能以封闭形式提供，并且通常存在于无限维空间中。其目的是在一个统一的框架内为不同类别的核推进这项工作，或者更广泛地说，制定一种统计上有良好原则的方法来解释光谱嵌入的几何结构，作为探索性数据分析和可视化的一部分。除此之外，还有许多相关的研究途径：*其他类型的图，包括有向图、多部分图和加权“稀疏性”时间动力学图*与图相关的其他统计推断过程，如回归、分类、模型选择。

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.