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.