# Permutation-Invariant Subgraph Discovery

arXiv: https://arxiv.org/abs/2104.01063 · HTML: https://mlsanity.com/paper/2104.01063/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 42 references that are in the map.
- First posted on arXiv 2 Apr 2021.

## Builds on (most cited first, 8 of 8)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Alternating Direction Graph Matching](https://mlsanity.com/paper/1611.07583/) (2016)
- [Robust Multimodal Graph Matching: Sparse Coding Meets Graph Matching](https://mlsanity.com/paper/1311.6425/) (2013)
- [Stock Market Prediction from WSJ: Text Mining via Sparse Matrix Factorization](https://mlsanity.com/paper/1406.7330/) (2014)
- [ROML: A Robust Feature Correspondence Approach for Matching Objects in A Set of Images](https://mlsanity.com/paper/1403.7877/) (2014)

## Abstract (arXiv)

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.