Search

The field of graph processing has grown significantly due to the flexibility and wide applicability of the graph data structure. In the meantime, so has interest from the community in developing new approaches to graph processing applications. In 2010, Google introduced the vertex-centric programming model through their framework Pregel. This consists of expressing computation from the perspective of a vertex, whilst inter-vertex communications are achieved via data exchanges along incoming and outgoing edges, using the message-passing abstraction provided. Pregel 's high-level programming interface, designed around a set of simple functions, provides ease of programmability to the user. The aim is to enable the development of graph processing applications without requiring expertise in optimisation or parallel programming. Such challenges are instead abstracted from the user and offloaded to the underlying framework. However, fine-grained synchronisation, unpredictable memory access patterns and multiple sources of load imbalance make it difficult to implement the vertex centric model efficiently on high performance computing platforms without sacrificing programmability. This research focuses on combining vertex-centric and High-Performance Comput- ing (HPC), resulting in the development of a shared-memory framework, iPregel, which demonstrates that a performance and memory efficiency similar to that of non-vertex- centric approaches can be achieved while preserving the programmability benefits of vertex-centric. Non-volatile memory is then explored to extend single-node capabilities, during which multiple versions of iPregel are implemented to experiment with the various data movement strategies. Then, distributed memory parallelism is investigated to overcome the resource limitations of single node processing. A second framework named DiP, which ports applicable iPregel 's optimisations to distributed memory, prioritises performance to high scalability. This research has resulted in a set of techniques and optimisations illustrated through a shared-memory framework iPregel and a distributed-memory framework DiP. The former closes a gap of several orders of magnitude in both performance and memory efficiency, even able to process a graph of 750 billion edges using non-volatile memory. The latter has proved that this competitiveness can also be scaled beyond a single node, enabling the processing of the largest graph generated in this research, comprising 1.6 trillion edges. Most importantly, both frameworks achieved these performance and capability gains whilst also preserving programmability, which is the cornerstone of the vertex-centric programming model. This research therefore demonstrates that by combining vertex-centricity and High-Performance Computing (HPC), it is possible to maintain performance, memory efficiency and programmability.

Graph algorithms find several usages in industry, science, humanities, and technology. The fast-growing size of graph datasets in the context of the processing model of the current hardware has resulted in different bottlenecks such as memory locality, work-efficiency, and load-balance that degrade the performance. To tackle these limitations, high-performance computing considers different aspects of the execution in order to design optimized algorithms through efficient usage of hardware resources. The main idea in this thesis is to analyze the structure of graphs to exploit special features that are key to introduce new graph algorithms with optimized performance. First, we study the structure of real-world graph datasets with skewed degree distribution and the applicability of graph relabeling algorithms as the main restructuring tools to improve performance and memory locality. To that end, we introduce novel locality metrics including 'Cache Miss Rate Degree Distribution', 'Effective Cache Size', 'Push Locality and Pull Locality', and 'Degree Range Decomposition'. Based on this structural analysis, we introduce the Uniform Memory Demands strategy that (i) recognizes diverse memory demands and behaviours as a source of performance inefficiency, (ii) separates contrasting memory demands into groups with uniform behaviours across each group, and (iii) designs bespoke data structures and algorithms for each group in order to satisfy memory demands with the lowest overhead. We apply the Uniform Memory Demands strategy to design three graph algorithms with optimized performance: (i) the SAPCo Sort algorithm as a parallel counting sort algorithm that is faster than comparison-based sorting algorithms in degree-ordering of power-law graphs, (ii) the iHTL algorithm that optimizes locality in Sparse Matrix-Vector (SpMV) Multiplication graph algorithms by extracting dense subgraphs containing incoming edges to in-hubs and processing them in the push direction, and (iii) the LOTUS algorithm that optimizes locality in Triangle Counting by separating different caching demands and deploying specific data structure and algorithm for each of them.

There is increasing understanding that many complex systems of interest - everything from the global economy, to social group dynamics, to biochemical processes in the brain - require holistic modelling, rather than the consideration of units of the population in isolation. Network science techniques, which commence by viewing the system as a set of vertices or nodes (the units of the population, e.g. individual people) and edges (the relationships between them, e.g. friendship), are one popular approach to do so. Naturally, such complex systems express a wide array of important properties that we ought to account for when modelling them, beyond simply the presence or absence of a particular relationship. Most pertinently for this work, they evolve over time - i.e. they are 'dynamic' - and the units of the population may have distinct properties, or attributes, which further differentiate them from each other. We define any such extra information we might possess outside of the simple node/edge paradigm to be 'metadata'. Despite the potential utility of such metadata, it is only quite recently that methods have begun to jointly model both network and metadata together. In this thesis, we provide a new class of models that do so - specifically, with the purpose of finding groups in networks that change over time. We describe distinct versions of this class of models that allow the networks to be weighted and directed, as well as avoid the potential issue of placing nodes with similar degrees in the same group. In addition to elaborating such models, we derive novel requirements for the efficient detectability of groups given the presence of metadata - and in the process explain why a recent paper which claims to do the same for a similar static model is flawed. The inference method we leverage to investigate detectability is also highly scalable, and we further accelerate the process by proposing both a 'greedy' scheme, and a recursive procedure that effectively provides a top-down hierarchy of the network groups. We conclude by using our models as one component of a larger method, that provides an entirely novel means of estimating the influence of an author. We use a causal framing of the problem that to our knowledge has not previously been explored in this context, and depends upon recent ideas from the causal inference literature.

This doctoral thesis will present the results of my work into querying graphs on large-scale data, from both the data perspective and query perspective. We first propose a scheme to reduce large graphs into small ones. It contracts obsolete parts, stars, cliques and paths into supernodes. We then build a hierarchical scheme to further reduce the graph, under limited resources. For both the contraction scheme and the hierarchy, we show that it is generic and lossless. We show that the same contracted graph is able to support multiple query classes at the same time, no matter whether their queries are label-based or not, local or non-local. Moreover, existing algorithms for these queries can be readily adapted to compute exact answers by using the synopses when possible, and decontracting the supernodes only when necessary. Using real-life graphs, we experimentally verify the efficiency and effectiveness of our contraction schemes. Meanwhile, we propose an extension of graph patterns, referred to as conditional graph patterns (CGPs). The CGPs allows one to express several conventional queries in a conditioned one, and annotate similar patterns to compute answers for all patterns in a single enumeration. In a CGP, one can specify a simple condition on each edge such that the edge exists if and only if the condition is satisfied. We show that CGPs allow us to catch missing links, increase the expressivity of graph functional dependencies, and provide a succinct representation of graph patterns. We studies their consistency, matching, incremental matching and containment problems and settles down their complexity bounds. We develop algorithms for matching, incremental matching and parallel matching of CGPs, and for (incremental, parallel) multi-CGP matching and optimization. We empiricallyverify the efficiency and effectiveness of our algorithms on real-life and synthetic graphs.

Modern applications generate a massive amount of data that is challenging to process or analyse. Graph algorithms have emerged as a solution for the analysis of this data because they can represent the entities participating in the generation of large scale datasets in terms of vertices and their relationships in terms of edges. Graph analysis algorithms are used for finding patterns within these relationships, aiming to extract information to be further analysed. The breadth-first search (BFS) is one of the main graph search algorithms used for graph analysis and its optimisation has been widely researched using different parallel computers. However, the BFS parallelisation has been shown to be chal- lenging because of its inherent characteristics, including irregular memory access patterns, data dependencies and workload imbalance, that limit its scalability. This thesis investigates the optimisation of the BFS on the Xeon Phi, which is a modern parallel architecture provided with an advanced vector processor using a self-created development framework integrated with the Graph 500 benchmark. As a result, optimised parallel versions of two high-level algorithms for BFS were created using vectorisation, starting with the conventional top-down BFS algorithm and, building on this, leading to the hybrid BFS algorithm. The best implementations resulted in speedups of 1.37x and 1.33x, for a one million vertices graph, compared to the state-of-the-art, respectively. The hybrid BFS algorithm can be further used by other graph analysis algorithms and the lessons learned from vectorisation can be applied to other algorithms targeting the existing and future models of the Xeon Phi and other advanced vector architectures.

Emerging applications such as video transcoding and graph algorithms have seen fast development and broad adoption recently. It is crucial to improve the performance of these emerging applications for cost-efficiency and scalability. This thesis focuses on video transcoding and graph algorithms and uses software-hardware co-design to optimize their execution. Video transcoding is rapidly growing as the demand for online streaming services continues to strive, and understanding the hardware bottleneck in performing video transcoding is the stepping stone to develop dedicated hardware for it. Graph data structure is widely used in modeling complicated relationships between entities. Algorithms and applications that utilize the expressiveness of graphs are rapidly evolving and employed in various domains like social networks, chemistry, biology, and physics. With the expanding family of graph algorithms and the exploding size of real-world graphs, it is hard for hardware to keep up with the ever-growing demand for processing power for graph algorithms. To make the issue worse, the irregular memory access pattern in graph algorithms makes it hard to fully utilize traditional hardware like CPUs and GPUs. In this thesis, I propose software and hardware co-design to improve the performance of emerging applications. At a high level, I first present hardware characterization that reveals the hardware bottlenecks with the change in software parameters. Then I benchmark the performance of the most popular graph sparsification algorithms on their performance in preserving graph properties. Finally, I propose a power-efficient accelerator supporting multiple dataflows for Graph Convolutional Networks. Specifically, first, I perform CPU characterization on video transcoding, revealing the hardware bottlenecks (textit{e.g}. frontend, backend, branch misprediction, stalls) and how they shift with software parameters. Second, I use graph sparsification to tackle the exploding size of real-world graphs. I conduct a comprehensive benchmark on 12 graph sparsification algorithms, exploring their performance in preserving 16 essential graph properties on 14 real-world graphs, and give insights into how to choose the appropriate sparsification method for different down-stream tasks. Last, I present THISWORK, a power-efficient Graph Convolutional Network (GCN) accelerator designed to support multiple dataflows, achieving both high execution efficiency and flexibility.

A graph is a mathematical construct that models pairwise relations between objects through nodes (or vertices) and edges (also known as links) that connect these nodes. Due to the capacity of graphs to encapsulate a wide range of combinatorial structures, there has been a vibrant pursuit of developing fast and efficient graph algorithms to address a broad spectrum of graph-related problems, including covering and packing problems, clustering problems, distance computation, and symmetry breaking.This thesis explores approximation algorithms for graph problems. The first part is dedicated to distance computation problems, where we present several new hardness of approximation results across different models of computation, including the centralized, distributed, and dynamic models.The second part focuses on symmetry-breaking problems in Distributed Computing. Here, we devise efficient approximation algorithms for Maximum Independent Set and Maximum Matching in regular graphs, and introduce new hardness of approximation results for Maximum Independent Set.

In this dissertation, we investigate a multitude of novel algorithms aimed at efficiently constructing geometric spanners across various computational scenarios. In addition to devising new algorithms, we also develop several methodologies and frameworks for analyzing geometric spanners and their attributes, such as sparsity, weight, and separation properties, offering valuable tools for readers engaged in related research areas.We present our results in three main chapters. We begin by investigating the construction of the greedy $t$-spanner for a set of points in the plane. This spanner is an undirected graph constructed by considering pairs of points in order by distance, and connecting a pair by an edge when there does not already exist a path connecting that pair with length at most $t$ times the Euclidean distance. Our analysis reveals that for any $t>1$, these graphs exhibit a linear number of crossings and possess bounded degeneracy in their intersection graphs. These properties lead to the development of a separator theorem for greedy spanners, which demonstrates our capability to form a recursive separator hierarchy from the planarizations of these spanners in linear time, or in near-linear time if the planarization is unknown. Expanding on these fundamental concepts, we address an unresolved question concerning the existence of lightweight bounded-degree spanners for unit ball graphs in metrics with bounded doubling dimension. We present a distributed algorithm operating within $\mathcal{O}(\log^*n)$ rounds in the LOCAL model of computation, achieving significant improvements over prior methodologies. We extend the applicability of this algorithm to the CONGEST model while maintaining its round complexity. Our investigations extend to the two-dimensional Euclidean plane, where we devise constructions with a constant average number of edge intersections per node. Experimental evaluations validate the efficiency of our distributed algorithm compared to centralized counterparts. Finally, we focus on the dynamic maintenance of lightweight bounded-degree $(1+\varepsilon)$-spanners in $d$-dimensional Euclidean spaces. In a fully-dynamic setting, where points can be inserted or deleted, we aim to minimize the recourse while preserving essential spanner properties. We introduce a novel fully-dynamic algorithm with amortized constant recourse for point insertion and $\mathcal{O}(\log\Delta)$ recourse for point deletion, representing the first advancement on lightweight dynamic spanners. Throughout this dissertation, our aim is to also offer insightful discussions on the open problems inherent in each addressed scenario, providing many opportunities for readers seeking to engage with and explore further challenges in this field.

There are a wide variety of platforms to choose from when deciding to write a parallel algorithm. The chosen platform has a great impact on how developers write and run their code. Incompatibility between platforms is a major problem: in order for a developer to change systems or devices they often must rewrite their program from scratch. PyKokkos is an alternative option to committing to a specific platform. It sits on top of the Kokkos framework that bridges the gap between various XPU devices. While Kokkos allows users to program parallel functions that can run expeditiously on both GPU and CPU in C++, PyKokkos also allows users to program in Python. Code written in PyKokkos has all the benefits of Python, while being both performant and portable. Presented here are two examples of graph algorithms implemented for the first time in PyKokkos (or in Python): a parallel Maximal Independent Set algorithm and a parallel Shortest Path algorithm using Lattice-Linear Predicate. These implementations showcase the versatility of PyKokkos, where it makes writing parallel operations simple and easy, while not sacrificing performance.

This dissertation presents a comprehensive approach to advancing proteomics and under-studied proteins in network biology, emphasizing the development of reliable algorithms, fair evaluation practices, and accessible computational tools. A key contribution of this work is the introduction of RoKAI, a novel algorithm that integrates multiple sources of functional information to infer kinase activity. By capturing coordinated changes in signaling pathways, RoKAI significantly improves kinase activity inference, facilitating the identification of dysregulated kinases in diseases. This enables deeper insights into cellular signaling networks, supporting targeted therapy development and expanding our understanding of disease mechanisms. To ensure fairness in algorithm evaluation, this research carefully examines potential biases arising from the under-representation of under-studied proteins and proposes strategies to mitigate these biases, promoting a more comprehensive evaluation and encouraging the discovery of novel findings. Additionally, this dissertation focuses on enhancing accessibility by developing user-friendly computational tools. The RoKAI web application provides a convenient and intuitive interface to perform RoKAI analysis. Moreover, RokaiXplorer web tool simplifies proteomic and phospho-proteomic data analysis for researchers without specialized expertise. It enables tasks such as normalization, statistical testing, pathway enrichment, provides interactive visualizations, while also offering researchers the ability to deploy their own data browsers, promoting the sharing of findings and fostering collaborations. Overall, this interdisciplinary research contributes to proteomics and network biology by providing robust algorithms, fair evaluation practices, and accessible tools. It lays the foundation for further advancements in the field, bringing us closer to uncovering new biomarkers and potential therapeutic targets in diseases like cancer, Alzheimer's, and Parkinson's.

While modern complex computer systems provide enormous benefits to our daily lives, the increasing complexity of these large-scale systems also makes them more susceptible to unexpected software malfunctions and malicious attacks. This is especially true for Health Information Technology (HIT), which has revolutionized healthcare delivery by making it more efficient, effective, and accessible. Nevertheless, the widespread adoption of HIT has introduced new challenges related to ensuring system reliability and security. As a result, the development of novel algorithms and frameworks to detect anomalies in such systems has become increasingly important for enhancing patient safety and improving the efficiency and effectiveness of healthcare services. This dissertation presents innovative approaches for anomaly detection in HIT systems using Electronic Health Records (EHR), addressing the complexity of HIT and the need for patient data privacy and security. The first approach is an event sequence and subsequence anomaly detection algorithm that utilizes network-based representations, considers higher-order dependencies, and incorporates salient information of sequences for discrimination. By monitoring changes in the graph structure after removing test sequences, the algorithm effectively identifies anomalies and suggests plausible transitions for detected anomalous subsequences. Leveraging the cutting-edge natural language processing model Bidirectional Encoder Representations from Transformers (BERT), the second approach, named EHR-BERT, learns and identifies patterns in sequences bidirectionally, demonstrating improved accuracy and reduced false negatives through extensive evaluations. The third approach presents a comprehensive framework for detecting system-level abnormal events using high-dimensional system volume data. This framework employs machine learning models to identify outliers through a voting machine strategy, constructs weighted graphs representing the correlation of co-occurring outliers, and utilizes spectral graph theory and the paraclique algorithm to capture clusters with high correlations of co-occurring anomalies. Collectively, the proposed approaches advance state-of-the-art in anomaly detection in HIT systems and contribute to the development of advanced algorithms that can be applied in various clinical domains, ultimately improving patient outcomes and enhancing the reliability and efficiency of healthcare services. Additionally, the proposed approaches have the potential to be applied to other complex computer systems beyond HIT, where anomaly detection is critical for maintaining system reliability and security.

Over the last few decades, the design of algorithms for combinatorial problems has benefited greatly from a continous optimization perspective. In this dissertation, we will focus on some specific ideas from continous optimization, particularly so-called interior point methods (IPMs), for the design of efficient algorithms for some combinatorial problems in theoretical computer science. We will present algorithms for three different applications using these ideas:1) We first present an improved interior point method algorithm for exact $s$-$t$ maximum flow on directed graphs that runs in time $O(m^{4/3+o(1)}U^{1/3})$ where $U$ is the ratio of the maximum to minimum capacities on the edges.2) We then design a faster interior point method for the class of semi-definite programs (SDPs), a class of convex programs that have led to polynomial time algorithms for a variety of problems in combinatorial optimization, statistics and machine learning. Our algorithm runs in $O(\sqrt{n} (mn^2 + m^\omega + n^\omega)\log(1/\varepsilon))$ time for an SDP with $m$ constraints and $n$ sized variable matrix, which improves over the previous results in a wide variety of regimes. 3) We present a constructive proof of the Spencer problem by designing a Stieltjes transform based barrier function and running a random walk analyzed using this barrier function which gives a signing with discrepancy of $O(\sqrt{n})$ with high probability. We then show that unlike previous such approaches, our approach may generalize to resolve matrix discrepancy problems.

Given the vertices, V, of an unknown graph G = (V, E), exact learning refers to the process of reconstructing the edges, E, to learn its structure using an all-knowing black box oracle. This is motivated by a broad range of applications from network discovery, where the goal is to infer the topology of a communication network from queries, to computational biology and digital phylogeny, where we wish to learn how a set of objects have been evolved through a set of experiments. In this dissertation, we study various instances of exact learning of graphs using different query settings. For instance, we present an optimal algorithm to learn digital phylogenetic trees (directed rooted trees) using path queries, where a path query given two vertex, u and v, it returns true if and only if there is a directed path from u to v. We also provide efficient algorithms to learn other directed graphs such as multitrees, butterfly networks, and almost-trees from path queries. In addition, we study efficient learning algorithms for network mapping using kth-hop queries, where a kth-hop query given vertex u and v and integer k, it returns the k-th vertex on a shortest path from u to v.

A fundamental question in graph theory is the Single-Source Shortest Path (SSSP) problem. This is well-studied in classical algorithm literature, but is only more recently studied in the parallel setting. A relatively simple way to solve SSSP in parallel is with a Parallel Bellman-Ford(BF). BF shows strong performance on dense graphs, when m >> n. But due to its frontier-based approached, BF is bounded by the diameter of the graph. This thesis proposes 2 different preprocessing strategies to alleviate this. The first strategy is to generate shortcuts such that each vertex attempts to have at most degree k. The secondapproach is graph contraction, which removes specific vertices and replaces them with a single shortcut. We show that both preprocessing strategies reduce the overall rounds required to complete all testing algorithms. Additionally, we evaluate both preprocessing strategies with our own implementation of BF and state of the art parallel SSSP algorithms. In general, δ-stepping and ρ-stepping show improved times after contraction.

With the ever-increasing size of data available to researchers, traditional methods of analysis often cannot scale to match problems being studied. Often only a subset of variables may be utilized or studied further, motivating the need of techniques that can prioritize variable selection. This dissertation describes the development and application of graph theoretic techniques, particularly the notion of domination, for this purpose. In the first part of this dissertation, algorithms for vertex prioritization in the field of network controllability are studied. Here, the number of solutions to which a vertex belongs is used to classify said vertex and determine its suitability in controlling a network. Novel efficient scalable algorithms are developed and analyzed. Empirical tests demonstrate the improvement of these algorithms over those already established in the literature. The second part of this dissertation concerns the prioritization of genes for loss-of-function allele studies in mice. The International Mouse Phenotyping Consortium leads the initiative to develop a loss-of-function allele for each protein coding gene in the mouse genome. Only a small proportion of untested genes can be selected for further study. To address the need to prioritize genes, a generalizable data science strategy is developed. This strategy models genes as a gene-similarity graph, and from it selects subset that will be further characterized. Empirical tests demonstrate the method’s utility over that of pseudorandom selection and less computationally demanding methods. Finally, part three addresses the important task of preprocessing in the context of noisy public health data. Many public health databases have been developed to collect, curate, and store a variety of environmental measurements. Idiosyncrasies in these measurements, however, introduce noise to data found in these databases in several ways including missing, incorrect, outlying, and incompatible data. Beyond noisy data, multiple measurements of similar variables can introduce problems of multicollinearity. Domination is again employed in a novel graph method to handle autocorrelation. Empirical results using the Public Health Exposome dataset are reported. Together these three parts demonstrate the utility of subset selection via domination when applied to a multitude of data sources from a variety of disciplines in the life sciences.

Graphs are important and useful mathematical representations that can be used to model different objects in various research disciplines. For example, graphs are used for representing structures of chemical compounds in mathematical chemistry, representing phylogenetic trees in evolutionary biology, the small world concepts in social networks, and topology of a computer network. There are several properties on a graph for us to study, such as connectivity, reachability and distances. In this thesis, we study three fun algorithmic challenges and apply graph algorithms and data structures to improve them. The first challenge is to design a data structure that solves the fully dynamic graph connectivity problem. For any sequence of edge insertions and deletions to a graph, our data structure performs updates in amortized randomized O(logn(loglogn)²) time, improving Thorup’s result by a O(loglogn) factor for the first time since 2000. Our result leaves a small O((loglogn)²) gap to the Ω(logn) lower bound given by Pătrașcu and Demaine in 2006. The second topic we study includes various structures on graphs concerning distances and reachability, such as spanners, emulators, hopsets and shortcutting sets. A (β,ϵ)-hopset is a set of weighted edges added to an undirected weighted graph so that distances between any pair of vertices can then be (1+ϵ)-approximated using a path with at most β edges (hops). We applied Thorup and Zwick’s sublinear additive emulator construction to build a hopset. The construction, parameterized by k > 0, has an optimal tradeoff between the hopset size $O(n^{1+frac{1}{2^{k+1}-1}})$, the hop bound β = O(k/ϵ)^(k), and the approximation ratio (1+ϵ). This optimal tradeoff is established by the work of Abboud, Bodwin, and Pettie. A shortcutting set is a reachability-preserving set of directed edges whose addition to a directed unweighted graph reduces the diameter. We show that there is a Ω(n^(1/6)) diameter lower bound on any shortcutting set of O(n) size. The lower bound techniques can also be applied to undirected weighted graphs. In particular, we provide a  + Ω(n^(1/11)) additive distortion lower bound for O(n)-size spanners and a  + Ω(n^(1/18)) additive distortion lower bound for O(n)-size emulators. The third problem we solve is the asynchronous Byzantine agreement problem. In distributed computing, reaching consensus among all n processes is a challenging task, especially when a subset of processes are secretly corrupted and malicious behavior may occur. We provide a protocol that solves Byzantine agreement in an asynchronous distributed network model under perhaps the most challenging assumptions. Although we assume a fully-connected authenticated network ensuring that once a message is sent it will be delivered, the protocol has to work against a full-information (no cryptography for hiding information) and adaptive (corrupting processes over time) adversary. Most Byzantine agreement protocols are developed under weaker adversary models. We propose the first polynomial time protocol that allows up to ⌊(n−1)/4⌋ faulty processes, improving King and Saia’s 2013 result from (1.14×10⁻⁹)n faulty processes. Unlike the first two topics in this thesis, the asynchronous Byzantine agreement problem is not obviously related to graphs. But interestingly, one building block in our protocol is a fractional matching algorithm with a continuous Lipschitz guarantee.

The problem of efficiently computing subgraphs has received much attention from the database research community. In this thesis, we study important problem of efficient graph analysis at a large scale. Three subgraph computation problems are studied. These problems are (1) Triangle Listing, (2) Batch-dynamic Triangle Listing, and (3) Historical K-cores. The first problem, triangle listing, has a fundamental and theoretical significance in graph analytics. Efficient solutions often leverage the orientation framework: the mapping of an undirected graph into a directed acyclic graph for a specified global vertex ordering. We put forward improvement to this framework and present an adaptive orientation technique that satisfies the orientation technique but refines it by selectively traversing incident edges based on the out-degree of the vertices in the oriented graph as the computation of triangles is conducted. The second problem, batch-dynamic triangle listing, studies triangle listing in the context of batch-dynamic graphs. The setting differs from the former by an additional parameter of a batch-update of edges, where only updated triangle solutions are the relevant output for our problem setting. In this thesis, we notice that this problem has yet to be studied systematically and propose an efficient algorithm which (1) only outputs updated triangles and (2) ensures that each triangle solution is identified without the presence of any duplicate solutions. The final problem, historical K-cores, studies the k-cores in temporal graphs where each edge is associated with a timestamp representing its occurrence. We propose and study the efficient querying historical k-cores in temporal graphs. Given an integer k and a time window, we study the problem of computing all k-cores in the graph snapshot over the time window.

GPUs are now in widespread use for many non-graphics applications, like machine learning, scientific computations, and computer vision, but many challenges remain for achieving their full potential in many areas. Some algorithms and data structure operations, originally developed with sequential CPU architectures in mind, appear to be inherently serial in nature, and require new methods to adapt them to take advantage of the many-core GPU architecture. This dissertation describes methods for utilizing this massive parallelism to solve problems on large datasets while also grappling with the limitations on GPU memory size.First, we present an approach to maximum clique enumeration (finding all maximum cliques in a graph) on the GPU via an iterative breadth-first traversal of the search tree. In order to achieve high performance on the GPU, our implementation aims to maximize available parallelism and minimize divergence between threads. The biggest challenge for a breadth-first implementation is the memory required to store all of the intermediate clique candidates. To mitigate this issue, we employ a variety of strategies to prune away non-maximum candidates and present a thorough examination of the performance and memory benefits of each of these options. We also explore a windowing strategy as a middle-ground between breadth-first and depth-first approaches, and investigate the resulting trade-off between parallel efficiency and memory usage. Our results demonstrate that when we are able to manage the memory requirements, our approach achieves high throughput for large graphs indicating this approach is a good choice for GPU performance. We demonstrate an average speedup of 1.9x over previous parallel work, and obtain our best performance on graphs with low average degree.Finally, we present our GPU implementation of the quotient filter, a compact data structure designed to implement approximate membership queries. The quotient filter is similar to the more well-known Bloom filter; however, in addition to set insertion and membership queries, the quotient filter also supports deletions and merging filters without requiring rehashing of the data set. Furthermore, the quotient filter can be extended to include counters without increasing the memory footprint. We implement two types of quotient filters on the GPU: the standard quotient filter and the rank-and-select-based quotient filter. We describe the parallelization of all filter operations, including a comparison of the four different methods we devised for parallelizing quotient filter construction. In solving this problem, we found that we needed an operation similar to a parallel scan, but for non-associative operators. One outcome of this work is a variety of methods for computing parallel scan-type operations on a non-associative operator.For membership queries, we achieve a throughput of up to 1.13 billion items/second for the rank-and-select-based quotient filter: a speedup of 3x over the BloomGPU filter. Our fastest filter build method achieves a speedup of 2.1--3.1x over BloomGPU, with a peak throughput of 621 million items/second, and a rate of 516 million items/second for a 70% full filter. However, we find that our filters do not perform incremental updates as fast as the BloomGPU filter. For a batch of 2 million items, we perform incremental inserts at a rate of 81 million items/second -- a 2.5x slowdown compared to BloomGPU's throughput of 201 million items/second. The quotient filter's memory footprint is comparable to that of a Bloom filter.

Using Natural Language Processing (NLP) and graph algorithms on 100 years of state and federal legal decisions, the names of lawyers and their relationships are extracted using transformer-based language models and then analyzed with Social Network Analysis (SNA) to build social networks and then study how these social networks change over time. Data was grouped by jurisdiction and decade, and various metrics were calculated for each group. Changes in these metrics over time are substantial and show that SNA must take into account the passage of time when looking at data sets spanning large intervals of time. More generally, because individual metrics can be sensitive to scale and other factors, it was found that looking at the changes in metrics over time was often more informative and consistent across different jurisdictions. This may have implications for analysis in other domains as well.

Causal maps use directed network structures to represent causality between concepts in a system, and are vital for conceptual modeling- a core activity in the field of Modeling & Simulation (M&S). Simulation models are generated from collections of maps, introducing scalability challenges as modelers are unable to effectively process large collections manually, or when maps contain many concepts. Despite this, there is a paucity of research on reducing human interventions across the various steps in causal mapping. In this thesis, we develop Network Science tools to overcome these challenges and present a framework for processing maps automatically. First, we demonstrate how the accepted practice of manually transforming evidence into maps introduces significant bias and that indirect elicitation must be fully documented. To further reduce the risk of bias from modelers, we present and evaluate a method to combine maps using semantic and causal information. We then develop a systematic, data-driven approach to extract a useful model from combined maps, in part by characterizing whether recently proposed metrics on identifying central concepts are feasible in large maps. Our approach is validated through studies on suicide modeling and can subsequently be used to process causal maps in many other research areas.

For applications involving graph-structured data, a natural problem is to identify subgraphs that match a given template. In this thesis, we present several approaches for solving this subgraph matching problem, including approaches for both exact and inexact subgraph matching. Additionally, we define several problems related to subgraph matching in order to obtain a better understanding of the entire solution space for the subgraph matching problem. We analyze a variety of synthetic and real-world multiplex datasets, including Sudoku, transportation networks, Twitter, the DBPedia knowledge graph, and several datasets from the DARPA-MAA program for modeling adversarial activity. We then show how our exact subgraph matching approach can be extended to handle errors in network alignment, the process of merging multiple networks together to form a single multiplex network. Finally, we address the closely related problem of matching variable length path-based graph templates, and apply our method to identify potential activation pathways within a biological knowledge graph extracted from scientific publications on COVID-19.

Graph processing frameworks are typically designed to optimize the evaluation of a single graph query. However, in practice, we often need to respond to multiple graph queries, either from different users or from a single user performing a complex analytics task. This thesis is aimed at simultaneously evaluating batches of graph queries of two types: point-to-all and point-to-point. By fully utilizing system resources, batched evaluation amortizes runtime overheads incurred due to fetching vertices and edge lists, synchronizing threads, and maintaining computation frontiers. In addition, new runtime optimizations are developed that enable faster evaluation of batches of queries than their independent and one-by-one evaluation.In the context of point-to-all queries, we develop the sharing optimization that dynamically identifies shared queries that substantially represent subcomputations in the evaluation of different queries in a batch, evaluates the shared queries, and then uses their results to accelerate the evaluation of all queries in the batch. The resulting SimGQ system delivers substantial speedups over a conventional framework that evaluates and responds to queries one by one. We have also adapted the batching principles used by SimGQ to the streaming graph scenario in which we continuously maintain the results of a small batch of shared queries and use them for low-cost evaluation of arbitrary user queries.For point-to-point queries we have identified unique characteristics of such queries and based upon them developed two new optimizations. The first optimization, online pruning, eliminates propagation from vertices that are determined to not contribute to a query’s final solution and thus enables early termination. The second optimization, dynamic direction prediction, dynamically selects the direction in which to evaluate the query – either forward (from source) or backward (from destination) – as their costs can differ greatly. The resulting system, PnP, delivers substantial performance benefits over the state-of-the-art. To solve a batch of point-to-point queries, we extended this system by incorporating the batching principles in SimGQ along with a new query aggregation technique that eliminates the redundant computation across point-to-point queries that share the same source or destination vertex.

Some of the most challenging problems in ecology, hydrology, and geomorphology arise from processes which play out over large spatial scales and long time intervals. High-resolution global digital elevation models are becoming available. They will allow problems of broad spatial extent to be addressed, but only if we can handle the enormous volume of data. Similarly, performance gains in computers now make it feasible to test more complex theory using computational models, but only if efficient techniques are used. In this dissertation I develop and demonstrate techniques for handling large geospatial raster datasets and rapidly modeling ecological and hydrological processes, producing results that are orders of magnitude more efficient than previous work. Notably, these techniques work on both high-performance machines and laptops. Finally, I apply the techniques to a challenging problem at the interface of ecology, evolution, climate, and geology.

Computation of shortest paths is one of the classical problems in theoretical computer science. Given a pair of nodes s and t in a graph G, the goal is to find a path of minimum weight from s to t. Most graphs that commonly occur in practice are sparse graphs. In this work, we deal with several computational problems related to shortest paths in sparse graphs and we present algorithms that provide significant improvements in performance in both sequential and distributed settings. We also present fine-grained reductions that establish fine-grained hardness for several problems related to shortest paths. In the sequential context, we consider the fine-grained complexity of sparse graph problems whose time complexities have stayed at Õ(mn) over the past several decades, where m is the number of edges and n is the number of vertices in the input graph. All of these problems are known to be subcubic equivalent and this shows that achieving sub-mn running time is hard, but only for dense graphs where $m = [Theta] (n²). We introduce the notion of a sparse reduction which preserves the sparsity of graphs, and we present near linear-time sparse reductions between various pairs of graph problems in the Õ(mn) class. We also introduce the MWC-hardness conjecture, which states that Minimum Weight Cycle problem cannot be solved in sub-mn time. We establish that several important graph problems in the Õ(mn) class such as APSP, second simple shortest path (2-SiSP), Radius, and Betweenness Centrality are MWC-Hard, establishing sub-mn fine-grained hardness for these problems. A well-known generalization of the shortest path problem is the k-simple shortest paths (k-SiSP) problem, where we want to find k simple paths from s to t in a non-decreasing order of their weight. In this thesis we present a new approach for computing all pairs k simple shortest paths (k-APSiSP), which is based on forming suitable path extensions to find simple shortest paths; this method is different from the 'detour finding' technique used in all prior work on computing multiple simple shortest paths, replacement paths, and distance sensitivity oracles. The Õ(mn) time bound of our 2-APSiSP algorithm matches the fine-grained time complexity for the simpler 2-SiSP problem, which is the single source-sink version of this problem. Computing APSP is one of the most fundamental problems in distributed computing. We present a simple Õ(n [superscript 3/2]) rounds deterministic algorithm for computing APSP in the well-known CONGEST model which is the first Õ(n²) round deterministic algorithm for this problem. We then improve this further by reducing the round complexity to Õ(n [superscript 4/3]). We also present a faster algorithm for graphs with moderate integer edge weights. We develop several derandomization techniques for our deterministic APSP algorithms. These include efficient deterministic distributed algorithms for computing a small blocker set, which is a set that intersects a desired collection of shortest paths, and several deterministic pipelined approaches for computing the shortest path distance values as well as for propagating the messages in the network. Aside from our deterministic results, all non-trivial distributed algorithms currently known for computing APSP are randomized.

Graphs are a powerful tool for the study of dynamic processes, where a set of interconnected entities change their states according to the time-varying behavior of an underlying complex system. For instance, in a social network, an individual's opinions are influenced by their contacts; while, in a traffic network, traffic conditions are spatially localized due to the fact that vehicles are often constrained to move along roads. Understanding the interplay between structure and dynamics in networked systems enables new models, algorithms, and data structures for managing and learning from large amounts of data arising from these processes.This dissertation is focused on recent work on the analysis of dynamic graph processes. More specifically, we will show how sampling and spectral graph theory can be applied to effectively represent data from such processes. We also present efficient algorithms for learning Interleaved Markov Models (IHMMs). These are powerful latent variable models that enable the clustering of discrete sequences without training data and lead to interesting challenges in terms of inference. Furthermore, we also discuss how graphs can be modified in order to control a process of interest via network design and introduce three ongoing projects on the subject of this dissertation. The statement of the thesis is that mining and modeling processes on graphs leads often to problems that are not not only hard computationally but also in terms of inference. They can be solved using spectral, probabilistic, and combinatorial optimization algorithms, and must take into account the graph structure and also large amounts of data traces from these processes.

Networks (or graphs) are a powerful tool to model complex systems such as social networks, transportation networks, and the Web. Network design problems, including planning, implementing and augmenting networks for desirable properties, arise naturally in many applications: How to improve commute time in traffic network? How to contain fake news in social networks? How to preserve a species by conserving important properties of an ecosystem? How to promote healthier behaviour among individuals via their social interactions? However, characterizing the combinatorial effect of these network modifications leads to challenging optimization problems. From a theoretical standpoint, different from their search counterparts (e.g. computing shortest path), the design problems (e.g. optimizing shortest paths) are computationally hard. My thesis focuses on the development of algorithms for solving large-scale real-world problems using network design. In this thesis, I will discuss a few network design problems and their solutions. In the first part, I will describe design problems to optimize structural properties of a network. More specifically, I will focus on shortest path distance optimization and improvement of node centrality. In the second part, I will show how network design can be used in security related applications via leader hiding problem. Lastly, network modification will be used to improve or control network processes. In particular I will describe influence minimization and resilience maximization in networks via making optimal changes. I will present fast algorithms for these problems using continuous optimization, randomized algorithms and game theoretic techniques.

Graph partitioning has played an important role in theoretical computer science, particularlyin the design of approximation algorithms and metric embeddings. In some of these applica-tions, fundamental tradeoffs in graph partitioning prevented further progress. To overcomethese barriers, we consider partitions of certain derived graphs of an undirected graph G ob-tained by applying Gaussian elimination to the Laplacian matrix of G to eliminate verticesfrom G. We use this technique and others to obtain new results on the following fronts:Cheeger’s Inequality: Cheeger’s inequality shows that any undirected graph G with min-imum√ nonzero normalized Laplacian eigenvalue λ G has a cut with conductance at mostO( λ G ). Qualitatively, Cheeger’s inequality says that if the relaxation time of a graph ishigh, there is a cut that certifies this. However, there is a gap in this relationship, as cutscan have conductance as low as Θ(λ G ).To better approximate the relaxation time of a graph, we consider a more general object.Specifically, instead of bounding the mixing time with cuts, we bound it with cuts in graphsobtained via Gaussian elimination from G. Combinatorially, random walks in these graphsare equivalent in distribution to random walks in G restricted to a subset of its vertices. Asa result, all Schur complement cuts have conductance at least Ω(λ G ). We show that unlikewith cuts, this inequality is tight up to a constant factor. Specifically, there is a derivedgraph containing a cut with conductance at most O(λ G ).Oblivious Routing: We show that in any graph, the average length of a flow path in anelectrical flow between the endpoints of a random edge is O(log 2 n). This is a consequence ofa more general result which shows that the spectral norm of the entrywise absolute value ofthe transfer impedance matrix of a graph is O(log 2 n). This result implies a simple obliviousrouting scheme based on electrical flows in the case of transitive graphs.Random Spanning Tree Sampling: We give an m 1+o(1) β o(1) -time algorithm for generat-ing uniformly random spanning trees in weighted graphs with max-to-min weight ratio β. In2the process, we illustrate how fundamental tradeoffs in graph partitioning can be overcomeby eliminating vertices from a graph using Schur complements of the associated Laplacianmatrix.Our starting point is the Aldous-Broder algorithm, which samples a random spanning treeusing a random walk. As in prior work, we use fast Laplacian linear system solvers to shortcutthe random walk from a vertex v to the boundary of a set of vertices assigned to v called a“shortcutter.” We depart from prior work by introducing a new way of employing Laplaciansolvers to shortcut the walk. To bound the amount of shortcutting work, we show that mostrandom walk steps occur far away from an unvisited vertex. We apply this observation bycharging uses of a shortcutter S to random walk steps in the Schur complement obtained byeliminating all vertices in S that are not assigned to it.Spectral Sparsification: We introduce a new approach to spectral sparsification thatapproximates the quadratic form of the pseudoinverse of a graph Laplacian restricted to asubspace. We show that sparsifiers with a near-linear number of edges in the dimensionof the subspace exist. Our setting generalizes that of Schur complement sparsifiers. Ourapproach produces sparsifiers by sampling a uniformly random spanning tree of the inputgraph and using that tree to guide an edge elimination procedure that contracts, deletes,and reweights edges. In the context of Schur complement sparsifiers, our approach has twobenefits over prior work. First, it produces a sparsifier in almost-linear time with no runtimedependence on the desired error. We directly exploit this to compute approximate effectiveresistances for a small set of vertex pairs in faster time than prior work [33]. Secondly,it yields sparsifiers that are reweighted minors of the input graph. As a result, we give anear-optimal answer to a variant of the Steiner point removal problem.A key ingredient of our algorithm is a subroutine of independent interest: a near-lineartime algorithm that, given a chosen set of vertices, builds a data structure from which wecan query a multiplicative approximation to the decrease in the effective resistance betweentwo vertices after identifying all vertices in the chosen set to a single vertex with inversepolynomial additional additive error in near-constant time.

In this dissertation, we introduce different models for understanding and controlling the spreading dynamics of a network with a consumable resource. In particular, we consider a spreading process where a resource necessary for transit is partially consumed along the way while being refilled at special nodes on the network. Examples include fuel consumption of vehicles together with refueling stations, information loss during dissemination with error correcting nodes, consumption of ammunition of military troops while moving, and migration of wild animals in a network with a limited number of water-holes. We undertake this study from two different perspectives. First, we consider a network science perspective where we are interested in identifying the influential nodes and estimating a nodes’ relative spreading influence in the network. For this reason, we propose generalizations of the well-known centrality measures to model such a spreading process with consumable resources. Next, from an optimization perspective, we focus on the application of an Electric Vehicle road network equipped with wireless charging lanes as a resource allocation problem. The objective is this case is to identify a set of nodes for optimal placement of the wireless charging lanes. For this reason, we propose an integer programming model formulation and use it as a building block for different realistic scenarios. We conclude this dissertation by giving an approach to improve route selection for the optimization model proposed by using feedback data while giving comparisons to different realistic scenarios.

In this dissertation we examine two topics relevant to modern machine learning research: 1) Subgraph counting and 2) High-dimensional subset selection. The former can be used to construct features for performing graph analytics. The latter has applications in sparse modeling such as feature selection, sparse regression, and interpretable machine learning. Since these problems become intractable for large datasets, we design efficient approximation algorithms for both tasks with data-dependent performance guarantees. In the first part of the dissertation, we study the problem of approximating all three and four node induced subgraphs in a large graph. These counts are called the 3 and 4-profile, respectively, and describe a graph's connectivity properties. This problem generalizes graphlet counting and has found applications ranging from bioinformatics to spam detection. Our algorithms use the novel concept of graph profile sparsifiers: sparse graphs that can be used to approximate the full profile counts for a given large graph. We obtain novel concentration results showing that graphs can be substantially sparsified and still retain good approximation quality for the global graph profile. We also study the problem of counting local and ego profiles centered at each vertex of the graph. These quantities embed every vertex into a low-dimensional space that characterizes the local geometry of its neighborhood. We introduce the concept of edge pivots and show that all local 3 and 4-profiles can be computed as vertex programs using compressed two-hop information. Our algorithms are local, distributed message-passing schemes and compute all graph profiles in parallel. We empirically evaluate these algorithms with a distributed GraphLab implementation, and show improvements over previous state-of-the-art in experiments scaling up to 640 cores on Amazon EC2. In the second part we shift to the problem of subset selection: for example, selecting a few features from a large feature set. Motivated by the need for interpretable, nonlinear regression models for high-dimensional data, we draw a novel connection between this and submodular maximization. We extend an earlier concept of weak submodularity from the setting of sparse linear regression to a broad class of objective functions, including generalized linear model likelihoods. We then show that three greedy algorithms (Oblivous, Forward Stepwise, and Orthogonal Matching Pursuit) perform within a constant factor from the best possible subset. Our methods do not require any statistical modeling assumptions and allow direct control over the number of obtained features. This contrasts with other work that uses regularization parameters to control sparsity only implicitly. Our proof technique connecting convex analysis and submodular set function theory may be of independent interest for other statistical learning applications that have combinatorial structure. In the third part, we consider the problem of explaining the predictions of a given black-box classifier. For example, why does a deep neural network assign an image to a particular class? We cast interpretability of black-box classifiers as a subset selection problem and propose to solve it with an efficient streaming algorithm. We provide a constant factor approximation guarantee for this algorithm in the case of a random stream order and a weakly submodular objective function. This is the first such theoretical guarantee for this general class of functions, and we also show that no such algorithm exists for a worst case stream order. Our algorithm obtains similar explanations of Inception V3 predictions 10 times faster than the state-of-the-art LIME framework.

Networks are a mathematical abstraction of the interactions between a set of entities, with extensive applications in social science, epidemiology, bioinformatics, and cybersecurity, among others. There are many fundamental problems when analyzing network data, such as anomaly detection, dense subgraph mining, motif finding, information diffusion, and epidemic spread. A common underlying task in all these problems is finding an "interesting subgraph"; that is, finding a part of the graph---usually small relative to the whole---that optimizes a score function and has some property of interest, such as connectivity or a minimum density. Finding subgraphs that satisfy common constraints of interest, such as the ones above, is computationally hard in general, and state-of-the-art algorithms for many problems in network analysis are heuristic in nature. These methods are fast and usually easy to implement. However, they come with no theoretical guarantees on the quality of the solution, which makes it difficult to assess how the discovered subgraphs compare to an optimal solution, which in turn affects the data mining task at hand. For instance, in anomaly detection, solutions with low anomaly score lead to sub-optimal detection power. On the other end of the spectrum, there have been significant advances on approximation algorithms for these challenging graph problems in the theoretical computer science community. However, these algorithms tend to be slow, difficult to implement, and they do not scale to the large datasets that are common nowadays. The goal of this dissertation is developing scalable algorithms with theoretical guarantees for various network analysis problems, where the underlying task is to find subgraphs with constraints. We find interesting subgraphs with guarantees by adapting techniques from parameterized complexity, convex optimization, and submodularity optimization. These techniques are well-known in the algorithm design literature, but they lead to slow and impractical algorithms. One unifying theme in the problems that we study is that our methods are scalable without sacrificing the theoretical guarantees of these algorithm design techniques. We accomplish this combination of scalability and rigorous bounds by exploiting properties of the problems we are trying to optimize, decomposing or compressing the input graph to a manageable size, and parallelization. We consider problems on network analysis for both static and dynamic network models. And we illustrate the power of our methods in applications, such as public health, sensor data analysis, and event detection using social media data.

The importance of irregular applications such as graph analytics is rapidly growing with the rise of Big Data. However, parallel graph workloads tend to perform poorly on general-purpose chip multiprocessors (CMPs) due to poor cache locality, low compute intensity, frequent synchronization, uneven task sizes, and dynamic task generation. At high thread counts, execution time is dominated by worklist synchronization overhead and cache misses. Researchers have proposed hardware worklist accelerators to address scheduling costs, but these proposals often harden a specific scheduling policy and do not address high cache miss rates. This thesis presents Minnow, a technique that addresses these bottlenecks by augmenting each core in a CMP with a memory throughput-optimized lightweight engine connected through an accelerator interface. These engines offload worklist operations from worker threads, reducing synchronization costs and improving scalability. The engines also perform worklist-directed prefetching, a software prefetching technique that exploits knowledge of upcoming tasks to perform nearly perfectly accurate and timely prefetch operations. In this thesis, we first characterize several graph applications within a popular graph analytics framework to determine their performance and bottlenecks. Next, Minnow and worklist-directed prefetching are discussed in detail, including the Minnow accelerator interface, microarchitecture, and prefetch flow control mechanism. Finally, the benefits of Minnow and worklist-directed prefetching are evaluated within a cycle-accurate microarchitectural simulator.

In this thesis two questions are addressed. First is the question of the time complexity of an algorithm gathering information on a tree with unknown topology. The tree is known to have maximum depth $D$ and maximum degree $\Delta$. This has been an open problem since being asked by Chlamtac and Kutten in 1985. This thesis resolves the question with upper and lower bounds that are essentially tight. The second question this dissertation addresses is what proportion of graphs have a fixed type of spectrum. We show that at most a $2^{-c n^{3/2}}$ proportion of graphs on $n$ vertices have integral spectrum. This improves on previous results of Ahmadi, Alon, Blake, and Shparlinski, who in 2009 showed that the proportion of such graphs was exponentially small.

Graph processing is experiencing a surge of renewed interest as applications in social networks and their analysis have grown in importance. Additionally, graph algorithms have found new applications in speech recognition and the sciences. In order to deliver the full potential of these emerging applications, graph processing must become substantially more efficient, as graph processing's communication-intensive nature often results in low arithmetic intensity that underutilizes available hardware platforms.To improve graph algorithm performance, this dissertation characterizes graph processing workloads on shared memory multiprocessors in order to understand graph algorithm performance. By querying performance counters to measure utilizations on real hardware, we find that contrary to prevailing wisdom, caches provide great benefit for graph processing and the systems are rarely memory bandwidth bound. Leveraging the insights of our workload characterization, we introduce the Graph Algorithm Iron Law (GAIL), a simple performance model that allows for reasoning about tradeoffs across layers by considering algorithmic efficiency, cache locality, and memory bandwidth utilization. We also provide the Graph Algorithm Platform (GAP) Benchmark Suite to help the community improve graph processing evaluations through standardization.In addition to understanding graph algorithm performance, we make contributions to improve graph algorithm performance. We present our direction-optimizing breadth-first search algorithm that is advantageous for low-diameter graphs, which are becoming increasingly relevant as social network analysis becomes more prevalent. Finally, we introduce propagation blocking, a technique to reduce memory communication on cache-based systems by blocking graph computations in order to improve spatial locality.

The explosive growth in the rate of data generation in recent years threatens to outpace the growth in computer power, motivating the need for new, scalable algorithms and big data analytic techniques. No field may be more emblematic of this data deluge than the life sciences, where technologies such as high-throughput mRNA arrays and next generation genome sequencing are routinely used to generate datasets of extreme scale. Data from experiments in genomics, transcriptomics, metabolomics and proteomics are continuously being added to existing repositories. A goal of exploratory analysis of such omics data is to illuminate the functions and relationships of biomolecules within an organism. This dissertation describes the design, implementation and application of graph algorithms, with the goal of seeking dense structure in data derived from omics experiments in order to detect latent associations between often heterogeneous entities, such as genes, diseases and phenotypes. Exact combinatorial solutions are developed and implemented, rather than relying on approximations or heuristics, even when problems are exceedingly large and/or difficult. Datasets on which the algorithms are applied include time series transcriptomic data from an experiment on the developing mouse cerebellum, gene expression data measuring acute ethanol response in the prefrontal cortex, and the analysis of a predicted protein-protein interaction network. A bipartite graph model is used to integrate heterogeneous data types, such as genes with phenotypes and microbes with mouse strains. The techniques are then extended to a multipartite algorithm to enumerate dense substructure in multipartite graphs, constructed using data from three or more heterogeneous sources, with applications to functional genomics. Several new theoretical results are given regarding multipartite graphs and the multipartite enumeration algorithm. In all cases, practical implementations are demonstrated to expand the frontier of computational feasibility.

Symmetry has long been recognized as a major obstacle in integer programming. Unless properly recognized and exploited, the branch-and-bound tree generated when solving highly symmetric integer programs (IPs) can contain many identical subproblems, resulting in a waste of computational effort. Effective methods have been developed to exploit known symmetry. This thesis focuses on improving methods that compute the symmetry group of an IP. In the literature, computing the symmetry group of an IP is performed by generating a graph with a similar structure as the IP, and then computing the automorphism group of the graph. Unfortunately, these graphs may be much larger than the IP problem, resulting in a possible waste of computational resources. The approach of this thesis is to detect the group of an edge-colored graph generated by the IP. This avoids the need for additional nodes to track coefficients, reducing the search space. Actually finding the group will be done by adapting and expanding a symmetry detection algorithm to work with these edge-colored graphs.

In this thesis we investigate two topics in data mining on graphs; in the first part we investigate the notion of centrality in graphs, in the second part we look at reconstructing graphs from aggregate information. In many graph related problems the goal is to rank nodes based on an importance score. This score is in general referred to as node centrality. In Part I. we start by giving a novel and more efficient algorithm for computing betweenness centrality. In many applications not an individual node but rather a set of nodes is chosen to perform some task. We generalize the notion of centrality to groups of nodes. While group centrality was first formally defined by Everett and Borgatti (1999), we are the first to pose it as a combinatorial optimization problem; find a group of k nodes with largest centrality. We give an algorithm for solving this optimization problem for a general notion of centrality that subsumes various instantiations of centrality that find paths in the graph. We prove that this problem is NP-hard for specific centrality definitions and we provide a universal algorithm for this problem that can be modified to optimize the specific measures. We also investigate the problem of increasing node centrality by adding or deleting edges in the graph. We conclude this part by solving the optimization problem for two specific applications; one for minimizing redundancy in information propagation networks and one for optimizing the expected number of interceptions of a group in a random navigational network. In the second part of the thesis we investigate what we can infer about a bipartite graph if only some aggregate information -- the number of common neighbors among each pair of nodes -- is given. First, we observe that the given data is equivalent to the dot-product of the adjacency vectors of each node. Based on this knowledge we develop an algorithm that is based on SVD-decomposition, that is capable of almost perfectly reconstructing graphs from such neighborhood data. We investigate two versions of this problem, in the versions the dot-product of nodes with themselves, e.g. the node degrees, are either known or hidden.

As three-dimensional virtual environments become both more prevalent and more fragmented, studying how users are connected via their avatars and how they benefit from the virtual world community has become a significant area of research. An in-depth analysis of virtual world Social networks is needed to evaluate how users interact in virtual worlds, to better understand the impact of avatar Social networks on the virtual worlds, and to improve future online Social networks. Our current efforts are focused on building and exploring the Social network aspects of virtual worlds. In this thesis, we build a Social network of avatars based on their interaction in the Second Life virtual world and compare it to other Social networking sites found on the web. Experimental results with data crawled from Second Life virtual worlds demonstrate that our approach was able to build a representative network of avatars in a virtual world from the sample data. The analysis comparison between virtual world Social networks and others in the flat web allows us to gauge measures that better explore the relationship between locations linked by multiple users and their avatars. Using this comparison, we can also determine if techniques of personalized search and content recommendation are feasible for virtual world environments.

In this thesis, we present an efficient graph-based image-segmentation algorithm that improves upon the drawbacks of the minimum spanning tree based segmentation algorithm, namely leaks that occur due to the criterion used to merge regions, and the sensitivity of the output to the parameter k. To address these problems, we propose the use of bidirectional Mahalanobis distance, along with a Gaussian model for each region, and an intuitive normalized parameter τ that replaces k and works for all images without having to be changed. Furthermore, we propose an approximation to the algorithm that enables it to run efficiently in O(NlogN) time (N represents the number of pixels in the image), without compromising on the performance. Experiments on a wide variety of images demonstrates the ability of the algorithm to achieve accurate results in an efficient manner.

In this dissertation, we developed and tested a sketching, visualization, and simulation tool called Sketchmate for demonstrating graph algorithms commonly taught in undergraduate computer science courses. For this research, we chose to focus on shortest path and network flow algorithms. Two versions of this tool have been implemented: 1) an instructor tool that supports computer-aided manual simulations of algorithms that augment traditional whiteboard presentations, allowing lectures to be more dynamic and interactive, and 2) a student tool that supports computer-aided manual practice of algorithms that enables students to work through homework problems more quickly while providing detailed incremental feedback about their performance and about how to solve a problem when they get stuck. Previous algorithm simulation systems have essentially forced instructors to narrate an algorithm as though they were describing an automated set of slides. In contrast, our tool allows instructors to manually manipulate attributes of a graph as they demonstrate an algorithm. A set of experiments was conducted using the tools. The results for the student tool showed that there was no statistically significant difference in test score improvement between Sketchmate and paper and pencil students, although they did show that Sketchmate students scored roughly one letter grade higher than paper and pencil students. Based on survey data, the students preferred using the tool to using paper and pencil. The results of the experiment involving the instructor tool showed that although there was no statistically significant difference in learning between Sketchmate and the whiteboard, both the instructor and the students preferred a Sketchmate lecture to a whiteboard lecture.

This dissertation addresses a series of graph problems inspired by the computational issues with face with the Internet, a massive distributed network of autonomous agents. There are several levels to this problem. From a systems perspective, what can we do to facilitate computation over massive graphs? From a modeling perspective, what do natural graphs look like and what features are useful? From a game theoretic perspective, the graphs often represent individuals or systems with their own goals and agendas. Can we understand how these systems compete and when these competitions are fair or can be manipulated?These questions are addressed. For the first, we consider the problem of streaming graph partitioning and show it is feasible. For the second, we study the joint degree distribution of a graph and show it is combinatorially easy to work with. Finally, we address questions about tournament design and manipulation.

This work addresses two novel problems in the field of computational genomics. The first is whole genome alignment and the second is inferring horizontal gene transfer using posets. We define these two problems and present algorithmic approaches for solving them. For the whole genome alignment, we define alignment graphs for representing different evolutionary events, and define a scoring function for those graphs. The problem defined is proven to be NP-complete. Two heuristics are presented to solve the problem, one is a dynamic programming approach that is optimal for a class of sequences that we define in this work as breakable arrangements. And, the other is a greedy approach that is not necessarily optimal, however, unlike the dynamic programming approach, it allows for reversals. For inferring horizontal gene transfer, we define partial order sets among species, with respect to different genes, and infer genes involved in horizontal gene transfer by comparing posets for different genes. The posets are used to construct a tree for each gene. Those trees are then compared and tested for contradiction, where contradictory trees correspond to genes that are candidates of horizontal gene transfer.

The biochemical community has been using graphical (topological, chemical) indices in the study of Quantitative Structure-Activity Relationships (QSAR) and Quantitative Structure-Property Relationships (QSPR), as they have been shown to have strong correlations with the chemical properties of certain chemical compounds (i.e. boiling point, surface area, etc.). We examine some of these chemical indices and closely related pure graph theoretical indices: the Randić index, the Wiener index, the degree distance, and the number of subtrees. We find which structure will maximize the Randić index of a class of graphs known as cacti, and we find a functional relationship between the Wiener index and the degree distance for several types of graphs. We also develop an algorithm to find the structure that maximizes the number of subtrees of trees, a characterization of the second maximal tree may also follow as an immediate result of this algorithm.