Research on Interpretability of High-Order Graph Neural Networks: Structural Consistency Explanation and Expressive Power Analysis

This study focuses on the differences between high-order graph neural networks (e.g., 1-2-3-GNN) and standard message-passing architectures in terms of structural consistency of model-level explanations, and explores whether high-order GNNs with stronger expressive power can generate more consistent structured explanations. Core issues include the expressive power of graph neural networks (related to the WL test), the two levels of interpretability (instance-level and model-level), and the advantages and mechanisms of high-order GNNs in capturing complex structural patterns.

Graph Neural Networks (GNNs) have been successfully applied in fields such as molecular property prediction and social network analysis, but face two core issues: expressive power and interpretability. In terms of expressive power, standard message-passing GNNs (e.g., GCN, GAT) are equivalent to the 1-WL test and cannot distinguish certain structures (e.g., regular graphs); high-order GNNs (k-GNNs) improve expressive power to the k-WL level through k-tuple node neighborhoods, and 1-2-3-GNN is a feasible implementation that hierarchically integrates 1/2/3-tuples. Interpretability is divided into instance-level (explanations for specific predictions) and model-level (patterns learned overall), and structural consistency refers to the rationality and consistency of explanations in graph structures (e.g., connected subgraphs, stable patterns).

This study evaluates the structural consistency of explanations between 1-2-3-GNN and standard GNNs (GCN, GIN) through comparative experiments. Experimental elements include:

1. Benchmark datasets: Select datasets with clear structural semantics such as molecules and social networks;
2. Explanation extraction: Adopt model-level explanation methods such as neural subgraph mining, concept activation vectors, and prototype learning;
3. Consistency evaluation: Quantify structural consistency through indicators such as connectivity of explanation subgraphs, pattern stability, and alignment with domain knowledge. GIN is used as a benchmark model, whose expressive power reaches the upper bound of 1-WL, facilitating the comparison of the advantages of high-order GNNs.

The study found that high-order GNNs (1-2-3-GNN) can generate model-level explanations with more structural consistency compared to standard GNNs:

1. Explanation subgraphs are more connected, with important nodes forming connected structures rather than isolated nodes;
2. Key patterns are more stable, remaining consistent across training runs or data subsets;
3. Better alignment with domain knowledge (e.g., chemical functional groups in molecular data). Mechanisms include: high-order GNNs can directly encode k-tuple local structures (e.g., triangles), stronger discriminative ability (distinguishing structures that standard GNNs cannot recognize), and better matching with task inductive biases.

High-order GNNs have the following limitations:

1. Computational overhead is significantly higher than standard GNNs, posing challenges for large-scale graph applications;
2. Prone to overfitting on small datasets;
3. Explanations involve complex k-tuple structures, which may increase the difficulty of human understanding. It is necessary to balance expressive power, computational cost, and explanation usability according to application scenarios.

In terms of applications, the structurally consistent explanations of high-order GNNs can facilitate scientific discoveries (e.g., molecular design) and provide a basis for model selection (prioritize in scenarios with high interpretability requirements). Future research directions include:

1. Adaptive order selection: automatically select the optimal k value;
2. Efficient high-order GNNs: reduce computational complexity;
3. Human-computer interaction explanations: intuitively present complex structural explanations;
4. Causal interpretability: explore causal relationships in graph structures.