StableGX: Stable Global Explanations for GNNs on Large Heterogeneous and Heterophilic Graphs

Graph Neural Networks (GNNs) are increasingly deployed on large real-world graphs, where global explanations should remain consistent across the different graph samples required for scalable analysis. Existing global GNN explainers can produce different explanations from different samples of data for the same black-box GNN model and face additional challenges on heterogeneous and heterophilic graphs with large, irregular neighborhoods and rich node features. We introduce StableGX, a global explainer for node-classification GNNs that targets both fidelity and stability across explanation samples. StableGX maps each node and its multi-hop neighborhood to a fixed-dimensional, interpretable representation of node features and neighborhood statistics, and identifies representative exemplar populations in the GNN embedding space. It then learns logical signatures for these populations using boundary-aware sampling, which identifies candidate points near the population boundary and applies max–min selection to improve boundary coverage. We theoretically relate boundary approximation error to fidelity and stability, and establish a bound on the approximation error induced by the proposed sampling procedure. Experiments across homogeneous and heterogeneous, homophilic and heterophilic graphs show that StableGX produces faithful and stable global explanations. In particular, it improves over GNNXemplar on large heterogeneous and heterophilic graphs, while GNNXemplar remains stronger on simpler homogeneous graph benchmarks.