Permutation-Invariant Subgraph Discovery
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.
Code (1)
Tasks
Graph MatchingMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Permutationally Invariant Networks for Enhanced Sampling (PINES): Discovery of Multi-Molecular and Solvent-Inclusive Collective Variables
The typically rugged nature of molecular free energy landscapes can frustrate efficient sampling of the thermodynamically relevant phase space due to the presence of high free energy barriers. Enhanced sampling technique…
TranslationQuantifying Distributional Invariance in Causal Subgraph for IRM-Free Graph Generalization
Out-of-distribution generalization under distributional shifts remains a critical challenge for graph neural networks. Existing methods generally adopt the Invariant Risk Minimization (IRM) framework, requiring costly en…
Invariant-Based Weight Sharing for Message Passing
Message-passing neural networks (MPNNs) are a powerful framework for learning representations of graph-structured domains. However, weights in MPNNs act on features only, limiting their ability to capture structural patt…
GraphEBM: Towards Permutation Invariant and Multi-Objective Molecular Graph Generation
Although significant progress has been made in molecular graph generation recently, permutation invariance and multi-objective generation remain to be important but challenging goals to achieve. In this work, we propose …
Drug DiscoveryGraph GenerationMolecular Graph GenerationFine-grained Graph Rationalization
Rationale discovery is defined as finding a subset of the input data that maximally supports the prediction of downstream tasks. In the context of graph machine learning, graph rationale is defined to locate the critical…
Prediction