NORMA: Norm-Guided Explanation Subgraph Discovery

Discovering explanatory subgraphs is essential for interpreting Graph Neural Networks (GNNs). Many existing and popular explainers optimize by maximizing mutual information (MMI) between selected subgraphs and predicted labels; however, the resulting optimization landscape is often non-smooth and poorly conditioned, leading to suboptimal local optima. To address this issue, we develop a norm-theoretic framework for subgraph analysis. We show that subgraphs containing model-utilized features tend to induce graph embeddings with larger $\ell_2$ norms, as they align more strongly with the supportive subspace shaped by the GNN’s weight matrices, a phenomenon consistently observed across multiple datasets. Based on this insight, we propose NORMA, a parameterized explainer that uses subgraph-embedding $\ell_2$ norms as a stable optimization signal to guide subgraph selection. Experiments on fsix benchmark datasets demonstrate that NORMA effectively alleviates the optimization difficulties of MMI-based methods and achieves superior explanation quality.