Sparsification of Reaction-Diffusion Dynamical Systems on Complex Networks

Abstract

Graph sparsification is an area of interest in computer science and applied mathematics. Spar- sification of a graph, in general, aims to reduce the number of edges in the network while preserving specific properties of the graph, like cuts and subgraph counts. Modern deep learn- ing frameworks, which utilize recurrent neural network decoders and convolutional neural networks, are characterized by a significant number of parameters. Pruning redundant edges in such networks and rescaling the weights can be useful. Computing the sparsest cuts of a graph is known to be NP-hard, and sparsification routines exist for generating linear-sized sparsifiers in almost quadratic running time. The complexity of this task varies, closely linked to the desired level of sparsity to achieve. The thesis introduces the concept of sparsification to the realm of reaction-diffusion complex systems. The aim is to address the challenge of reducing the number of edges in the network while preserving the underlying flow dynamics. Sparsification of such complex networks is approached as an inverse problem guided by data representing flows in the network, where a relaxed approach is adopted considering only a subset of trajectories. The network sparsification problem is mapped to a data assimilation problem on a reduced order model (ROM) space with constraints targeted at preserving the eigenmodes of the Laplacian matrix under perturbations. The Laplacian matrix is the difference between the diagonal matrix of degrees and the graph’s adjacency matrix. Approximations are proposed to the eigenvalues and eigenvectors of the Laplacian matrix subject to perturbations for computational feasibility, and a custom function is included based on these approximations as a constraint on the data assimilation framework. Extensive empirical testing covered a range of graphs, while its application to multiple instances led to the creation of sparse graphs. In the latter phase of the thesis, a framework is presented to enhance proper orthogonal de- composition (POD)-based model reduction techniques in reaction-diffusion complex systems. This framework incorporates techniques from stochastic filtering theory and pattern recog- nition (PR). Obtaining optimal state estimates from a noisy model and noisy measurements forms the core of the filtering problem. By integrating the particle filtering technique, the reaction-diffusion state vectors are generated at various time steps, utilizing the ROM states as measurements. To ensure the framework’s effectiveness, intermittent updates to the system variables are made during the particle filtering step, employing the carefully crafted sparse graph. The framework is utilized for experimentation, and results are presented on random graphs, considering the diffusion equation on the graph and the chemical Brusselator model as the reaction-diffusion system embedded in the graph. Limitations of the method are discussed, and the proposed framework is evaluated by comparing its performance against the Neural Ordinary Differential Equation or neural ODE-based approach, which serves as a compelling reference due to its demonstrated robustness in specific applications.