In this dissertation, I will cover two distinct topics. In the first part, I will discuss the subgraph isomorphism problem which has a broad range of applications from pattern recognition and bioinformatics to compilers circuit design. In combinatorial problems such as these, symmetry, if unaccounted for, can confound standard solvers leading to significant amounts ofredundant work being done. I will introduce multiple approaches for dynamically exploiting this symmetry to accelerate solvers as well as to compactly characterize the set of solutions. I rigorously establish conditions under which from one subgraph isomorphism, potentially exponentially many more may be generated. I also demonstrate through empirical assessment that incorporating symmetry into subgraph search can provide significant reductions in search time and produce many more solutions. In the presence of these huge solution spaces, there still remains the work of determining the actual subgraph isomorphism of interest. In an approach inspired by active learning, I will introduce the problem of querying template vertices for more information to uniquely identify solutions. Multiple different strategies for querying vertices which also incorporate symmetry are established and assessed by rigorous analysis and comprehensive experiments. In the second part, I will discuss methods for formulating neural network constrained optimization problems. With the advent of machine learning, neural networks have been used as a surrogate for complicated physical models, and the incorporation of these networks into optimization problems is a challenge. I will present a direct embedding approach, a mixed integer program, and a nonlinear program with complementarity constraints as methods for formulating these problems to be used with standard optimization solvers. I establish key properties of each methods, and through experiments, I assess the advantages and disadvantages for each approach.

The spatial features within a region influence many processes in human activity. Mountains, lakes, oceans, rivers, freeways, population densities, housing densities, and road networks are examples of geographical factors that impact spatial behaviors. Separated into two parts, the work presented here incorporates this information into both density estimation methods and models of street gang rivalries and territories.

Part I discusses methods for producing a probability density estimate given a set of discrete event data. Common methods of density estimation, such as Kernel Density Estimation, do not incorporate geographical information. Using these methods could result in non-negligible portions of the support of the density in unrealistic geographic locations. For example, crime density estimation models that do not take geographic information into account may predict events in unlikely places such as oceans, mountains, etc. To obtain more geographically accurate density estimates, a set of Maximum Penalized Likelihood Estimation methods based on Total Variation norm and H1 Sobolev semi-norm regularizers in conjunction with a priori high resolution spatial data is proposed. These methods are applied to a residential burglary data set of the San Fernando Valley using geographic features obtained from satellite images of the region and housing density information.

Part II addresses the behaviors and rivalries of street gangs and how the spatial characteristics of the region affect the dynamics of the system. Gangs typically claim a specific territory as their own, and they tend to have a set space, a location they use as a center for their activities within the territory. The spatial distribution of gangs influences the rivalries that develop within the area. One stochastic model and one deterministic model are proposed, providing different types of outputs. Both models incorporate important geographical features from the region that would inhibit movement, such as rivers and large highways. In the stochastic method, an agent-based model simulates the creation of street gang rivalries. The movement dynamics of agents are coupled to an evolving network of gang rivalries, which is determined by previous interactions among agents in the system. Basic gang data, geographic information, and behavioral dynamics suggested by the criminology literature are integrated into the model. The deterministic method, derived from a stochastic approach, modifies a system of partial differential equations from a model for coyotes. Territorial animals and street gangs often exhibit similar behavioral characteristics. Both groups have a home base and mark their territories to distinguish claimed regions. To analyze the two methods, the Hollenbeck policing division of the Los Angeles Police Department is used as a case study.

We present various results and methods for measuring uncertainty and applying active learning to graph-based semi-supervised learning, as well as a graph-dependent result for generalization of decentralized federated learning. The first piece of work presents an analysis of graph-based semi-supervised learning in the framework of Bayesian inverse problems; we prove posterior consistency of the corresponding Bayesian posterior distribution under a clustering model that accounts for overlap between clusters. The second and third pieces of work introduce and apply a graph-based method for selecting informative points for use in active learning. We present a computationally efficient framework for this active learning method and present empirical results on both hyperspectral and synthetic aperture radar datasets. The final piece of work provides an analysis of graph structure dependent generalization guarantees for decentralized federated learning. Through both theoretical analysis and empirical results, we demonstrate that expander graphs are in a sense optimally efficient for balancing communication cost as well as mixing properties of the associated graph.

Graph-based machine learning is a powerful framework for analyzing and understanding complex data structures in various domains. This thesis introduces novel graph-based methods in multiple image analysis tasks, including classification, segmentation, and unmixing, as well as their application in enhancing large language models. The key contributions include: (1) the development of new core-set selection and batch active learning methods that significantly improve the efficiency of graph-based active learning while maintaining its effectiveness; (2) the integration of graph learning, active learning, and advanced feature embedding methods to construct pipelines for SAR image classification and multi- or hyperspectral image segmentation, outperforming neural network-based classifiers or segmenters in semi-supervised learning tasks with limited training data; (3) the incorporation of graph-based regularization into the optimization problem of hyperspectral unmixing, enabling the utilization of a small amount of labeled pixels to greatly improve the performance compared to blind unmixing; and (4) the extension of graph Laplacian-based methods to automatically construct knowledge graphs in combination with large language models, enhancing their information retrieval and response generation capabilities.

The proposed methods showcase the effectiveness and versatility of graph-based approaches in addressing challenges such as limited labeled data, computational efficiency, and knowledge representation. The thesis demonstrates the potential of graph-based methods in pushing the boundaries of image and document analysis and their applicability in a wide range of machine learning problems.

In 1992 Merriman, Bence and Osher proposed a computationally inexpensive threshold

dynamics algorithm for the approximation of the motion by mean curvature. Since its

introduction, numerous generalizations of the algorithm have been made, and the algorithm

has been successfully used in a wide variety of computer vision applications, such as image

segmentation, image inpainting, surface reconstruction etc.. The main focus of this work

are the extensions of the original algorithm as well as multiple new applications such as

probability density estimation and graph segmentation.

Part I discusses a threshold dynamics segmentation algorithm for estimating a probabil-

ity density based on discrete point data. Since point data may represent certain activities,

such as crime, this method can be successfully used for detecting regions of high activity, as

well as locating the region where activities generally occur. To achieve the goal of accurately

locating such regions, a binary segmentation version of the well-known Maximum Penal-

ized Likelihood Estimation (MPLE) model is designed. The method is applied to different

computational examples, including one with actual residential burglary data from the San

Fernando Valley.

In Part II we present an adaptation of the classic Merriman-Bence-Osher (MBO) scheme

utilizing a fully or semi nonlocal graph Laplacian for solving a wide range of learning problems

in data clustering and image processing. Combining ideas from L1 compressive sensing, image

processing and graph methods, the diffuse interface model based on the Ginzburg-Landau

functional was recently introduced to the graph community for solving problems in data

classification. Here, we propose an algorithm for graph-based methods and also make use of

fast numerical solvers for finding eigenvalues and eigenvectors of the graph Laplacian. To

demonstrate the performance of our model, various computational examples are presented,

which proves that the method is successful on images with texture and repetitive structure

due to its nonlocal nature. A wide range of applications is discussed, including data labeling,

image segmentation and image inpainting, which demonstrates the versatility of the proposed

algorithm. The success of this algorithm also raises an important theoretical question: is

it possible to define an analog of the motion by mean curvature of surfaces on graphs, and

what properties would such notion possess.

In this dissertation, a blob method of measuring spatial coverage by a swarm of agents is presented, and two models are introduced: a macroscopic model, consisting of a system of Advection-Diffusion-Reaction equations that govern the spatial distribution of the swarm at the population level; and a microscopic model, represented by a stochastic differential equation, describing the individual behavior of each agent in the swarm. Depending on different tasks, multiple control frameworks are proposed to drive the swarm to a target distribution, and are proved to be both valid in theory and robust in real world case.

First, we briefly review the history of Advection-Diffusion-Reaction (ADR) system in the literature. The ADR system models the agents' motion as drifted brownian motion, and the agents' reaction as probabilistic transition between different states. The key idea of the ADR model lies in the fact that the green's function of Advection-Diffusion Equation is the conditional probability density function of the corresponding drifted brownian motion. The proposed point mass approach verifies that the error between the macroscopic and the microscopic model converges with respect to the inverse of the square root of the swarm size.

Next, we explores a stochastic approach for controlling swarms of independent robots toward a target distribution in a bounded domain. The robots are resource-constraint: they lack both

communication and localization capabilities, and can only gather local information by measuring a scalar field (e.g. concentration of a chemical) from the environment. A simple control law is introduced to govern the diffusion of each robot, so that the distribution of the swarm converges to a pre-defined target distribution over time. The key point behind the control framework is that the solution of heat equation converges to the first-order eigenvector of the Laplacian operator. We further confirm the robustness of the control law in real world case by conducting simulations in computer and test bed experiments in multiple cases of target distributions, where the swarm achieves the theorized convergence to the target distribution despite deviations from assumptions underpinning the theory.

Finally, we presents a novel procedure for computing parameters of a robotic swarm that guarantee coverage performance by the swarm within a specified error from a target spatial distribution. The main contribution is the analysis of the dependence of this error on two key parameters: the number of robots in the swarm and the robot sensing radius, in which we view each robot as a blob instead of a point mass. We model the population dynamics of the swarm as an advection-diffusion-reaction partial differential equation (PDE) with time-dependent advection and reaction terms. We derive rigorous bounds on the discrepancies between the target distribution and the coverage achieved by individual-based and PDE models of the swarm. We use these bounds to select the swarm size that will achieve coverage performance within a given error and the corresponding robot sensing radius that will minimize this error. We also apply the optimal control approach to compute the robots' velocity field and task-switching rates. We validate our procedure through simulations of a scenario in which a robotic swarm must achieve a specified density of pollination activity over a crop field.