  Graph Neural Networks (GNNs) have achieved promising performance in a variety
of graph-focused tasks. Despite their success, however, existing GNNs suffer
from two significant limitations: a lack of interpretability in results due to
their black-box nature, and an inability to learn representations of varying
orders. To tackle these issues, we propose a novel
\textbf{M}odel-\textbf{a}gnostic \textbf{G}raph Neural \textbf{Net}work
(MaGNet) framework, which is able to effectively integrate information of
various orders, extract knowledge from high-order neighbors, and provide
meaningful and interpretable results by identifying influential compact graph
structures. In particular, MaGNet consists of two components: an estimation
model for the latent representation of complex relationships under graph
topology, and an interpretation model that identifies influential nodes, edges,
and node features. Theoretically, we establish the generalization error bound
for MaGNet via empirical Rademacher complexity, and demonstrate its power to
represent layer-wise neighborhood mixing. We conduct comprehensive numerical
studies using simulated data to demonstrate the superior performance of MaGNet
in comparison to several state-of-the-art alternatives. Furthermore, we apply
MaGNet to a real-world case study aimed at extracting task-critical information
from brain activity data, thereby highlighting its effectiveness in advancing
scientific research.
