Abstract
Recently the world is witnessing an explosion of data, demanding scientific and application-specific models for data analysis. Unarguably, data is the new oil. It is well-known that a graph is the most abstract and discrete representation of data that originated from real world problems. These problems range from the seven bridges of Konigsberg in 1736 to monolithic integrated circuits to biology, food web, internet, transportation, computer systems, social networks and countless others.
Depending on the problem at hand, such complex data can be broadly classified into two groups. The first group accounts for problems where the data inherit distinct and invariant graph structures due to several factors that include the nature of data acquisition, data sampling, and intrinsically discrete structures of the data sources. A noteworthy example is 3D reconstructed neuron cells, where each neuron emulates a tree-structure branching topology. The second group of problems involves datasets that are deficient of fixed graph structures. Unlike the first category, the graph in this case should either be estimated based on optimization criteria or be initialized using some ad hoc constraints. Image or video based data is one example of this category, where the graph could be drawn from the pixels, the patches, or the frames depending on the nature of the problem.
The primary objective of this thesis is to investigate the above two categories of graph structured data with varying degrees of structural complexity in specific problems. We perform novel image analysis, build graph models, develop graph theoretic tools and scalable algorithms for two major purposes - informatics and categorization. In the first group, we consider activity recognition and neuromorphology. In the second group, we consider geomorphological event detection and event monitoring from videos.
In activity recognition, we use 3D reconstructed skeleton models of subjects performing a predefined set of activities. In such a model, the number of vertices and edges are fixed, connoting low structural complexity. We leverage such simple structures and propose Unified Graph Signal Processing (UGraSP) to integrate activity recognition and person identification using the same graph features. With additional graph structures, UGraSP is improved to make Unified Graph based Activity Detection (UGrAD) to encode the activity dynamics in terms of graph features. The central aspect of this thesis is the graph theoretic modeling of neuronal arbors. Feature-based representation and categorization of neurons, a topic that correlates with neuronal functionality, is still an open problem in neuromorphology. We use 3D reconstructed neurons (fixed graph) from stained images, where the number of vertices is not fixed for every neuron but the edges between the vertices are structurally fixed. We propose NeuroPath2Path that utilizes path-based modeling of neuron anatomy and provides a visualization tool for the continuous deformation between a pair of neurons. NeuroPath2Path offers several advantages. Decomposition of a neuron into paths can be viewed as an assembly of individual circuits from the terminals to the soma, integrating semi-local features that act as path descriptors. Next, instead of subgraph matching, NeuroPath2Path provides a full-graph matching algorithm. The matching algorithm presents several biological factors, including fractality and decaying importance of features along the path. NeuroPath2Path also precisely investigates the feasibility of algorithmic constraints on the structural repertoire of neuronal arbors, thereby enforcing criteria, such as hierarchy mismatch. NeuroPath2Path can be extended to two major domains - morphological analysis and structural transformation of microglia cells, and in progressive degradation of neuronal paths in neurodegenerative diseases. In addition, the knowledge of neuronal functions, such as potentiation and co-adaptive spiking can be translated to neural networks in order to achieve better performance and emulate neurons by way of neural networks.
In geomorphological event detection, we are interested in three major application areas, which are road health estimation, sinkhole detection and monitoring, and rock-slope fault detection, from InSAR (Interferometric Synthetic Aperture Radar) data. The structural complexity of the data is elevated compared to the previous two problems. It is because there is no predefined connectivity among the vertices. We first model the data with a graph using K-nearest neighborhood approach. Then, we develop Laplacian Weighted Covariance (LaWeCo) for spatial localization of geomorphological events. Later, using a temporal bipartite graph model and iterative prior estimation, we propose DDT to detect as well as monitor such events.
Simultaneous detection and tracking of events from videos is another challenging problem with more complexity of graph structures. Here, there are multiple options for the selection of vertices and edges. By blending the recursive estimation of a spatial graph and temporal graphs of patches over time into a dictionary learning framework, we propose Graph based Dictionary learning for Event Detection (GraDED) to accomplish both the tasks. Lastly, we consider the problem of accelerating the convergence of LMS filters. The problem apparently does not require graph modeling of data and combinatorial feature extraction. However, the imposition of a graph structure to the data is shown to improve the convergence of LMS.
