UMD Theses and Dissertations

Permanent URI for this collectionhttp://hdl.handle.net/1903/3

New submissions to the thesis/dissertation collections are added automatically as they are received from the Graduate School. Currently, the Graduate School deposits all theses and dissertations from a given semester after the official graduation date. This means that there may be up to a 4 month delay in the appearance of a given thesis/dissertation in DRUM.

More information is available at Theses and Dissertations at University of Maryland Libraries.

Browse

Subject: search.filters.subject.graph

Search Results

Now showing 1 - 4 of 4
  • Thumbnail Image
    Item
    Representation Learning For Large-scale Graphs
    (2023) Jin, Yu; JaJa, Joseph; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
    Graphs are widely used to model object relationships in real world applications such as biology, neuroscience, and communication networks. Traditional graph analysis tools focus on extracting key graph patterns to characterize graphs which are further used in the downstream tasks such as prediction. Common graph characteristics include global and local graph measurements such as clustering coefficient, global efficiency, characteristic path length, diameter and so on. Many applications often involve high dimensional and large-scale graphs for which existing methods, which rely on small numbers of graph characteristics, cannot be used to efficiently perform graph tasks. A major research challenge is to learn graph representations that can be used to efficiently perform graph tasks as required by a wide range of applications. In this thesis, we have developed a number of novel methods to tackle the challenges associated with processing or representing large-scale graphs. In the first part, we propose a general graph coarsening framework that maps large graphs into smaller ones while preserving important structural graph properties. Based on spectral graph theory, we define a novel distance function that measures the differences between graph spectra of the original and coarse graphs. We show that the proposed spectral distance sheds light on the structural differences in the graph coarsening process. In addition, we propose graph coarsening algorithms that aim to minimize the spectral distance, with provably strong bounds. Experiments show that the proposed algorithms outperform previous graph coarsening methods in applications such as graph classification and stochastic block recovery tasks. In the second part, we propose a new graph neural network paradigm that improves the expressiveness of the best known graph representations. Graph neural network (GNN) models have recently been introduced to solve challenging graph-related problems. Most GNN models follow the message-passing paradigm where node information is propagated through edges, and graph representations are formed by the aggregation of node representations. Despite their successes, message-passing GNN models are limited in terms of their expressive power, which fail to capture basic characteristic properties of graphs. In our work, we represent graphs as the composition of sequence representations. Through the design of sequence sampling and modeling techniques, the proposed graph representations achieve provably powerful expressiveness while maintaining permutation invariance. Empirical results show that the proposed model achieves superior results in real-world graph classification tasks. In the third part, we develop a fast implementation of spectral clustering methods on CPU-GPU platforms. Spectral clustering is one of the most popular graph clustering algorithms which achieved state-of-the art performance in a wide range of applications. However, existing implementations in commonly used software platforms such as Matlab and Python do not scale well for many of the emerging Big Data applications. We present a fast implementation of the spectral clustering algorithm on a CPU-GPU heterogeneous platform. Our implementation takes advantage of the computational power of the multi-core CPU and the massive multithreading capabilities of GPUs. We show that the new implementation achieved significantly accelerated computation speeds compared with previous implementations on a wide range of tasks. In the fourth part, we study structural brain networks derived from Diffusion Tensor Imaging (DTI) data. The processing of DTI data coupled with the use of modern tractographic methods reveal white matter fiber connectivity at a relatively high resolution; this allows us to model the brain as a structural network which encodes pairwise connectivity strengths between brain voxels. We have developed an iterative method to delineate the brain cortex into fine-grained connectivity-based brain parcellations. This allows to map the initial large-scale brain network into a relatively small weighted graph that preserves the essential structural connectivity information. We show that graph representations based on the brain networks from new brain parcellations are more powerful in discriminating between different populations groups, compared with existing brain parcellations.
  • Thumbnail Image
    Item
    GREMLIN++ & BITGRAPH: IMPLEMENTING THE GREMLIN TRAVERSAL LANGUAGE AND A GPU-ACCELERATED GRAPH COMPUTING FRAMEWORK IN C++
    (2019) Barghi, Alexander; Franklin, Manoj; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
    This thesis consists of two major components, Gremlin++ and BitGraph. Gremlin++ is a C++ implementation of the Gremlin graph traversal language designed for interfacing with C++ graph processing backends. BitGraph is a graph backend written in C++ designed to outperform Java-based competitors, such as JanusGraph and Neo4j . It also offers GPU acceleration through OpenCL . Designing the two components of this thesis was a major undertaking that involved implementing the semantics of Gremlin in C++, and then writing the computing framework to execute Gremlin’s traversal steps in BitGraph, along with runtime optimizations and backend-specific steps. There were many important and novel design decisions made along the way, including some which yielded both advantages and disadvantages over Java-Gremlin. BitGraph was also compared to several major backends, including TinkerGraph, JanusGraph, and Neo4j. In this comparison, BitGraph offered the fastest overall runtime, primarily due to data ingest speedup.
  • Thumbnail Image
    Item
    HISTORICAL GRAPH DATA MANAGEMENT
    (2015) Khurana, Udayan; Deshpande, Amol; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
    Over the last decade, we have witnessed an increasing interest in temporal analysis of information networks such as social networks or citation networks. Finding temporal interaction patterns, visualizing the evolution of graph properties, or even simply comparing them across time, has proven to add significant value in reasoning over networks. However, because of the lack of underlying data management support, much of the work on large-scale graph analytics to date has largely focused on the study of static properties of graph snapshots. Unfortunately, a static view of interactions between entities is often an oversimplification of several complex phenomena like the spread of epidemics, information diffusion, formation of online communities, and so on. In the absence of appropriate support, an analyst today has to manually navigate the added temporal complexity of large evolving graphs, making the process cumbersome and ineffective. In this dissertation, I address the key challenges in storing, retrieving, and analyzing large historical graphs. In the first part, I present DeltaGraph, a novel, extensible, highly tunable, and distributed hierarchical index structure that enables compact recording of the historical information, and that supports efficient retrieval of historical graph snapshots. I present analytical models for estimating required storage space and snapshot retrieval times which aid in choosing the right parameters for a specific scenario. I also present optimizations such as partial materialization and columnar storage to speed up snapshot retrieval. In the second part, I present Temporal Graph Index that builds upon DeltaGraph to support version-centric retrieval such as a node’s 1-hop neighborhood history, along with snapshot reconstruction. It provides high scalability, employing careful partitioning, distribution, and replication strategies that effectively deal with temporal and topological skew, typical of temporal graph datasets. In the last part of the dissertation, I present Temporal Graph Analysis Framework that enables analysts to effectively express a variety of complex historical graph analysis tasks using a set of novel temporal graph operators and to execute them in an efficient and scalable manner on a cloud. My proposed solutions are engineered in the form of a framework called the Historical Graph Store, designed to facilitate a wide variety of large-scale historical graph analysis.
  • Thumbnail Image
    Item
    A Study of Resting State FMRI Dynamic Functional Network Analysis of MTBI
    (2015) Hou, Wenshuai; JaJa, Joseph; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
    Mild Traumatic Brain Injury (MTBI) is one of the most common neurological disorders. A subset of patients develop persistent cognitive deficits. A number of the brain studies have been conducted to discover the abnormalities and disruptions in the brain functional networks using similar methods to those employed in more severe brain disorders such as Alzheimer's or Schizophrenia. Static functional network analysis using resting state brain fMRI images has shown some promising results in identifying characteristics of MTBI. However, recent development in the dynamics of functional networks have been able to reveal insightful information about anomalies in brain activities that have not been observed when using traditional static analysis. Our work focuses on both static and dynamic functional analysis of the brain. Our overall analysis pipeline is data-driven using a dataset of 47 MTBI subjects and a demographically matching healthy control group size of 30. The data-driven approach proactively removes noise, focuses on the entire brain functional networks and performs advanced independent component analysis, followed by statistical tests to characterize the functional networks of MTBI patients. A key distinction of our research is the finer labeling of MTBI subject according to their long term 6 months recovery status. Our results suggest that those MTBI subject who suffer prolonged recovery exhibit disturbed functional networks, and slowed dynamism in functional connectivity than those of the healthy control or those MTBI participants who recovered quickly. A number of useful network measurements have been found to capture the states and changes of the brain functional networks for healthy and different types of MTBI subjects in their resting state. We believe that our findings can shed more light into the impact of MTBI on the effectiveness of several functional networks and can contribute to helping clinicians make more informed decisions to aid in the recovery of MTBI patients.