Topological Fingerprints in Complex Networks: From Pathway Scoring to Heuristics for Longest Simple Paths

Abstract

Extracting clear, quantifiable information from networks is an important but challengingtask across many distinct fields that use networks to model complex phenomena. There are many centrality measures to help quantify the importance of individual nodes, as well as network-level measures to summarize global information, but these measures are usually devoid of any actual context regarding the phenomena being modeled. Additionally, for larger networks, many of these metrics become computationally intractable rather quickly. This dissertation addresses specific instances of these challenges through two distinct but related contributions. First, we introduce xGATE, a network-based pipeline designed to measure the activity of biological pathways. Second, we introduce the Eccentric Random Walker (ERW), a novel heuristic for the longest simple path (LSP) problem. The first part focuses on constructing gene coexpression networks from single-cell RNA sequencing data, and then treating biological pathways as induced subgraphs within a larger coexpression network. From here, we want vectorized representations of these subgraphs that capture the relevant structural information, so we propose our novel graph embedding scheme, GraphOdyssey. We proceed with the assumption that pathways that correspond to biologically relevant processes (with respect to the cell cohort used to construct the gene co- expression network) should have topological structures that somehow deviate significantly from the structures formed by induced subgraphs of the same size but with randomly se- lected genes. Therefore, the problem is reframed as anomaly detection where we have a pathway embedding against embeddings from randomly induced subgraphs, and we use a Variational AutoEncoder (VAE) to assign anomaly scores. We test this framework against other pathway scoring pipelines such as ORA, AUCell, and scGSEA and find that xGATE outperforms competing methods using benchmarking pathways on both a liver and pancreas dataset. In particular, in the pancreas dataset, xGATE is able to confirm impaired autophagy and high apoptosis pathway activity in Type 1 Diabetes (T1D) among the beta cells, as well as detect the early pathways that are dysregulated in beta cells correspond- ing to AAB+ (autoantibody-positive) individuals. In a colorectal cancer dataset, xGATE iv was able to reveal distinct immune-hot vs. immune-cold regions that matched the tissue histology. The second part shifts gears and introduces the LSP problem formally, as well as our novel heuristic, ERW. Given a graph G = (V, E), ERW relies on the novel concept of dynamic eccentricity, which recomputes the eccentricity of potential next nodes in the graph G[V\V_P], where V_P is the set of nodes that have already been visited. ERW then selects the next node in the walk according to these dynamic eccentricities. When benchmarked on 45 Newman-Watts-Strogatz graphs that have Hamiltonian paths, the paths found by ERW were consistently between 93.8%–99.5% of the lengths of the corresponding Hamiltonian paths. When tested against Genetic Algorithms (GAs) and other competing methods on 14 real-world complex networks, ERW found significantly longer paths than all competing methods on all of the networks. Our results also demonstrate that ERW is an effective tool for measuring how vulnerable a network is to path-based attacks.