Geometric Aspects of Complex Networks and Graph Mining: Distances, Embeddings, and Perturbations

Understanding the geometric aspects of complex networks holds the key to solving numerous practical problems, including link prediction, anomaly detection, and graph comparison. In this work, I draw upon both topological and geometric aspects of graph theory to develop new graph mining algorithms that yield valuable scientific insight. I consider the geometric structure of networks at many levels, specifically examining graph embeddings, the theory of the length spectrum, and graph distance under perturbations. First, I use the geometry of graph embeddings to develop two algorithms that solve tasks such as link prediction and anomaly detection in an efficient and interpretable way. Second, I study the intrinsic metric structure of a graph using the theory of the length spectrum.  Third, I propose to extend these studies by focusing on the metric structure of large collections of graphs through methods such as metric learning in order to define principled methods for computing distances between graphs. Finally, I propose to test the assumption that underlies the consideration of distances  between graphs: that graphs that are structurally similar exhibit similar behaviors. I will test this hypothesis by studying how certain dynamical properties of graphs change under small perturbations of their structure. In particular I will focus on the largest eigenvalue of the non-backtracking matrix, which is known to determine the epidemic threshold of certain dynamics. Understand the effects of such perturbations will provide insight into feasible interventions as well as the ability of an adversary to effectively manipulate network structure and affect its dynamics. Exploring different geometric aspects of complex networks and exploiting them to design and develop new data mining algorithms presents a way forward in the development of the theoretical foundations of network and data science.