  We introduce Permutation and Structured Perturbation Inference (PSPI), a new
problem formulation that abstracts many graph matching tasks that arise in
systems biology. PSPI can be viewed as a robust formulation of the permutation
inference or graph matching, where the objective is to find a permutation
between two graphs under the assumption that a set of edges may have undergone
a perturbation due to an underlying cause. For example, suppose there are two
gene regulatory networks X and Y from a diseased and normal tissue
respectively. Then, the PSPI problem can be used to detect if there has been a
structural change between the two networks which can serve as a signature of
the disease. Besides the new problem formulation, we propose an ADMM algorithm
(STEPD) to solve a relaxed version of the PSPI problem. An extensive case study
on comparative gene regulatory networks (GRNs) is used to demonstrate that
STEPD is able to accurately infer structured perturbations and thus provides a
tool for computational biologists to identify novel prognostic signatures. A
spectral analysis confirms that STEPD can recover small clique-like
perturbations making it a useful tool for detecting permutation-invariant
changes in graphs.
