Browsing by Subject "Graphs"

Now showing 1 - 6 of 6
  • Thumbnail Image
    Item
    Big Temporally-Detailed Graph Data Analytics
    (2015-06) Gunturi, Venkata Maruti Viswanath
    Increasingly, temporally-detailed graphs are of a size, variety, and update rate that exceed the capability of current computing technologies. Such datasets can be called Big Temporally-Detailed Graph (Big-TDG) Data. Examples include temporally-detailed (TD) roadmaps which provide typical travel speeds experienced on every road segment for thousands of departure-times in a typical week. Likewise, we have temporally-detailed (TD) social networks which contain a temporal trace of social interactions among the individuals in the network over a time window. Big-TDG data has transformative potential. For instance, a 2011 McKinsey Global Institute report estimates that location-aware data could save consumers hundreds of billions of dollars annually by 2020 by helping vehicles avoid traffic congestion via next-generation routing services such as eco-routing. However, Big-TDG data presents big challenges for the current computer science state of the art. First, Big-TDG data violates the cost function decomposability assumption of current conceptual models for representing and querying temporally-detailed graphs. Second, the voluminous nature of Big-TDG data can violate the stationary ranking-of-candidate-solutions assumption of dynamic programming based techniques such Dijsktra's shortest path algorithm. This thesis proposes novel approaches to address these challenges. To address the first challenge, this thesis proposes a novel conceptual model called, "Lagrangian Xgraphs," which models non-decomposability through a series of overlapping (in space and time) relations, each representing a single atomic unit which retains the required semantics. An initial study shows that Lagrangian Xgraphs are more convenient for representing diverse temporally-detailed graph datasets and comparing candidate travel itineraries. For the second challenge, this thesis proposes a novel divide-and-conquer technique called "critical-time-point (CTP) based approach," which efficiently divides the given time-interval (over which over non-stationary ranking is observed) into disjoint sub-intervals over which dynamic programming based techniques can be applied. Theoretical and experimental analysis show that CTP based approaches outperform the current state of the art.
  • Thumbnail Image
    Item
    Gamma-Supermagic Labeling The Products of Two Cycles
    (2020-08) Sorensen, Lincoln
    A $\Gamma$-supermagic group edge labeling of a graph $G(V,E)$ with $|E|=g$ is an injection from $E$ to an Abelian group of order $g$ such that the sum of labels of all incident edges of every vertex $v \in V$ is equal to the same element $\gamma \in \Gamma$. We develop methods for labeling the products of two cycles $C_m \square C_n$ using a variety of external direct products of Abelian groups.
  • Thumbnail Image
    Item
    List colorings with distinct list sizes, the case of complete bipartite graphs
    (University of Minnesota. Institute for Mathematics and Its Applications, 2011-10) Füredi, Zoltán; Kantor, Ida
  • Thumbnail Image
    Item
    Robust Deep Learning on Graphs
    (2020-08) Ioannidis, Vasileios
    The era of "data deluge'' has sparked the interest in graph-based learning methods and their application in a number of disciplines ranging from sociology and biology to transportation or communications. Realizing the potential of graph-based learning has never been closer, even though formidable challenges are yet there to overcome. Contemporary graphs have massive scale up to billions of nodes, and generate unceasingly "big data''. Graph edges or node attributes may be only partially available due to application specific constraints, which calls for learning approaches to impute the missing information. Graph deep learning methods model complex nonlinear functions and achieve remarkable results in various tasks but the theoretical analysis of such methods is lacking. Last but not least, approaches to learning over graph data must be also robust to adversarial behavior. These challenges have been confronted only partly and separately under different formulations and application domains. The proposed research is centered on analytical and algorithmic foundations that aspire to address the aforementioned challenges facing robust deep learning tasks over large-scale dynamic graphs. The overarching vision is to leverage and adapt state-of-the-art deep learning, optimization and networking tools for inference tasks based on limited graph data. Target applications include identifying node and edge anomalies, predicting node attributes, as well as providing graph-driven recommendations. The ultimate goal is to both analytically and numerically demonstrate how valuable insights from {modeling graph data} can lead to markedly improved learning tools. To this end, the present thesis investigates three main research thrusts: i) unveiling anomalies on graphs; ii) robust deep learning on graphs; and iii) explaining deep learning on graphs via scattering transforms.The aforementioned research thrusts introduce novel methods that aim to tackle the challenges of robust deep learning on graphs. The potential of the proposed approaches is showcased by rigorous theoretical results and extensive experiments.
  • Thumbnail Image
    Item
    Towards Learning Powerful Deep Graph Neural Networks and Embeddings
    (2020-06) Verma, Saurabh
    Learning powerful data embeddings has recently become the core of machine learning algorithms especially in natural language processing and computer vision domains. In the graph domain, the applications of learning graph embeddings are vast and have distinguished use-cases across multi-cross domains such as bioinformatics, chemoinformatics, social networks and recommendation systems. To date, graph remains the most fundamental data structure that can represent many forms of real-world datasets. However, due to its rich but complex data structure, graph presents a significant challenge in forging powerful graph embeddings. Even standard deep learning techniques such as Recurrent Neural Networks (RNNs) or Convolutional Neural Networks (CNNs) are not capable enough to operate on the data lying beyond 1D sequence of say words or 2D pixel-grid of images and therefore, cannot generalize to arbitrary graph structure. Recently, Graph Neural Networks (GNNs) have been proposed to alleviate such limitations but the current state is far from being mature in both theory and applications. To that end, this thesis aims at developing powerful graph embedding models for solving wide-variety of real-world problems on the graph. We study some of the major approaches for devising graph embedding namely Graph Kernel Or Spectrum and GNN. We expose and tackle some of their fundamental weakness and contribute several novel state-of-the-art graph embedding models. These models can achieve superior performance in solving many real-world problems on graphs such as node classification, graph classification or link prediction over existing methods and that too comes with desirable theoretical guarantees. We first study the capabilities of Graph Kernel or Spectrum approaches toward yielding powerful graph embeddings in terms of uniqueness, stability, sparsity and computationally efficiency. Second, we propose Graph Capsule Neural Network that can yield powerful graph embeddings by capturing much more information encoded in the graph structure in comparison with existing GNNs. Third, we devise a first ever universal and transferable GNN and thus, makes transfer learning possible in graph domain. Specifically with this particular GNN, graph embeddings can be shared and transfered across different models and domains, reaping the huge benefits of transfer learning. Lastly, there is a dearth of theoretical explorations of GNN models such as their generalization properties. We take the first step towards developing a deeper theoretical understanding of GNN models by analyzing their stability and deriving their generalization guarantees. To the best of our knowledge, we are the first to study stability bounds on graph learning in a semi-supervised setting and derive related generalization bounds for GNN models. In summary, this thesis contributes several state-of-the-art graph embeddings and novel graph theory, specifically (i) Powerful Graph Embedding called Family of Graph Spectral Distances (Fgsd) (ii) Highly Informative GNN Called Graph Capsule Neural Network (GCAPS) (iii) Universal and Transferable GNN called Deep Universal and Transferable Graph Neural Network (DUGNN) (iv) Stability Theory and Generalization Guarantees of GNN.
  • Thumbnail Image
    Item
    Two Problems Involving Random Walks on Graphs: Random surfers, PageRank, and short-time asymptotics for the heat kernel
    (2021-12) Yuan, Amber
    Semi-supervised and unsupervised machine learning methods often rely on graphs to model data, prompting research on how theoretical properties of operators on graphs are leveraged in learning problems. In the first part of the thesis, we propose a framework for rigorously studying continuum limits of learning algorithms on directed graphs. We use the new framework to study the PageRank and show how it can be interpreted as a numerical scheme on a directed graph involving a type of normalized graph Laplacian. We show that the corresponding continuum limit problem, which is taken as the number of webpages grows to infinity, is a second-order, elliptic equation that contains reaction, diffusion, and advection terms. In the second part of the thesis, we work in the undirected graph setting and study the short-term behavior of a graph-based random walk defined via the heat kernel. We prove how to estimate the random walk via a Gaussian and propose a method for homogenizing the graph Laplacian to obtain better length-scale restrictions for parameters in the graph model.