1
Towards Faithful Graph Explanations with Synergistic Edge Effects via Granular Balls
arXiv:2607.21381v1 [cs.AI] 23 Jul 2026
Jiancu Chen, Shuyin Xia* , Senior Member, IEEE, Guan Wang, Degang Chen, Fan Chen
Abstract—Instance-level explanations aim to reveal the rationale behind a model’s decisions for a specific graph. Previous methods explain graph neural networks (GNNs) by selecting important edges to induce subgraphs, where edge importance is assessed by perturbing each edge and observing changes in the model predictions. However, they often neglect the synergistic effects among edges, which are crucial for accurately characterizing edge importance. To address this issue, we propose SeeExplainer, a parameter-free explainer to interpret GNNs. Specifically, we first introduce a granular-ball graph refinement mechanism that decomposes a graph into several disjoint granular-balls with no fixed size, and utilize them as nodes to construct a structural graph. This process can better capture the synergistic effects among edges. Then, we perturb nodes and edges in the structural graph to generate explanatory subgraphs based on their respective contributions. Experiments on several graph classification datasets of different networks show that SeeExplainer outperforms state-of-the-art baselines. Index Terms—Graph Neural Networks, synergistic effects, granular-ball, explainability, interpretability
security [8]. Therefore, explaining GNNs has become a key research area in explainable machine learning [9], [10].
Fig. 1. The synergistic effects among edges. A substructure s1 exhibits a significantly higher contribution than the sum of its individual edges e1 and e2 .
I. I NTRODUCTION
I
N recent years, Graph Neural Networks (GNNs) have attracted significant attention for their outstanding performance in graph classification tasks [1]–[3]. Since graph data is widely found in real-world domains, such as social networks [4], chemistry [5], and biology [6], [7], the practical value of GNNs has become increasingly prominent. However, like many deep learning models, the “black-box” nature of GNNs makes their internal mechanisms difficult to understand. Without interpretation of the model’s underlying mechanisms, it is hard to establish trust, which directly affects its application in critical areas such as fairness, privacy protection, and Manuscript received April xx, xxxx; revised August xx, xxxx. This research was partially supported by the National Natural Science Foundation of China under Grant Nos. 62222601, 62176033, 62221005, and 61936001; the Chongqing Municipal Education Commission Youth Project No. KJQN202301231; the Key Cooperation Project of the Chongqing Municipal Education Commission under Grant No. HZ2021008; the Scientific and Technological Research Program of the Chongqing Municipal Education Commission under Grant No. KJZD-M202400603; and the Project of the Key Laboratory of Tourism Multisource Data Perception and DecisionMaking, Ministry of Culture and Tourism, under Grant No. H2023009. (*Corresponding author: Shuyin Xia). Jiancu Chen, Shuyin Xia, Guan Wang, Degang Chen, and Fan Chen are with the Chongqing Key Laboratory of Computational Intelligence, Key Laboratory of Big Data Intelligent Computing, Key Laboratory of Cyberspace Big Data Intelligent Security, Ministry of Education, School of Computer Science and Technology, Chongqing University of Posts and Telecommunications, Chongqing, China. Jiancu Chen is also with the School of Computer Science and Engineering, Chongqing Three Gorges University, Chongqing, China. (email: [email protected], [email protected], [email protected], [email protected], [email protected]).
To interpret graph neural networks, researchers have proposed various explanation techniques. Model-level explanations [11]–[15] aim to reveal the global structural patterns and decision strategies captured by the model. Instance-level explanations aim to reveal the reasons behind a model’s decisions on specific graph instances. Unlike model-level explanations, instance-level explanations offer more fine-grained and localized insights, aligning more closely with human reasoning and scientific research. Early methods primarily focused on node contributions, that is, revealing which entities contribute to the model’s predictions. These methods typically highlight the most representative regions of the graph by learning node masks or scoring functions. GNNExplainer [10] jointly optimizes node masks with the prediction target. Perturbationbased strategies assess node contributions by removing or perturbing nodes. GraphLime [16] observes changes in model predictions through local node perturbations to identify key nodes that affect classification decisions. These methods rely on node information but overlook the fact that selecting an edge naturally entails selecting the corresponding endpoints [17], making it difficult to effectively explore subgraph-level explanations. To address this issue, recent methods have begun to focus on edge contributions. GraphMask [18] maintains the minimal set of edges that preserve the prediction results through sparsity constraints. SubgraphX [19] evaluates edge contributions to provide more comprehensive explanations. PGExplainer [20] models edges by learning a parameterized edge mask generator. Eig-Search [17] generates
2
induced subgraphs by selecting important edges, and uses them to generate subgraph-level explanations. Nevertheless, the aforementioned methods emphasize the importance by perturbing an individual edge, but overlook the synergistic effect among edges, which hampers the accurate identification of edge importance. For example, in graph coloring problems [21], edges sharing vertices cannot have the same color; in network flow problems [22], edges that share vertices may be subject to shared traffic constraints. As shown in Fig. 1(a), multiple edges collectively form a special nitro functional group (e1 and e2 ), if we split the nitro group and calculate its contribution separately, it loses its specific meaning. As shown in Fig. 1(b), if we calculate the importance of nitro groups as a whole, their contribution is not simply the sum of their independent edge contributions, but rather exhibits nonlinear growth. To address this issue, we propose SeeExplainer, a graph neural network explainer that captures the synergistic effect among edges and directly generates subgraphs to explain GNN predictions. Inspired by granular-ball computing theory [23], [24] and the human cognitive concept of “global precedence”, we cover the entire graph using a coarse-grained granular-ball, then obtain a structural graph through non-isomorphic factorization, and perturb nodes and edges in the structural graph to generate an explanatory subgraph. Specifically, we first use a coarse splitting strategy to efficiently explore a coarse-grained representation of the original graph, then use a fine splitting strategy to progressively refine the granular-balls into different sizes and optimal granularities, and construct a structural graph based on these granular-balls. During the construction of the structural graph, the original nodes and edges are not removed; rather, the internal structure of a granular-ball is represented as a whole within the structural graph. This preserves the original graph structure while capturing the synergistic effect among edges, resulting in better explanations. In summary, our contributions are as follows: • General Aspects: We propose a structural graph generation strategy that captures the synergistic effect among edges, offering a new perspective compared with traditional methods that only consider the contribution of individual edges. • Novel Methodologies: We introduce SeeExplainer, a parameter-free explainer to interpret graph neural networks, which directly generates multi-granularity explanatory subgraphs based on the structural graph. Compared with traditional methods that generate induced subgraphs based on important edges, our method is simple and effective. • Multifaceted Experiments: Extensive experiments on public real-world graph classification datasets of different networks demonstrate the efficacy of SeeExplainer, greatly enhancing the explainability of GNNs. II. R ELATED W ORK A. Graph Neural Network Graph data is widely used in many real-world domains [5], [7], [25]. Unlike image and text data, a graph is represented by
a feature matrix and an adjacency matrix. Specifically, consider a graph G = (V, X, A), where V = {v1 , v2 , ..., vn } is the set of nodes, X ∈ Rn×d is the matrix consisting of the dn×n dimensional feature vectors of all nodes, and A ∈ {0, 1} is the adjacency matrix of G. Graph neural networks learn node representations based on these matrices. Although there are various types of graph neural networks, such as Graph Convolutional Networks (GCNs) [26], and Graph Isomorphism Networks (GINs) [27], they all follow an information aggregation scheme, in which a node’s representation is obtained by aggregating and combining the features of its neighboring nodes. Here, we use GCNs as an example to illustrate the information aggregation scheme. For Graph G, the aggregation operation in GCNs can be mathematically 1 1 written as Xi+1 = σ(D− 2 ÂD− 2 Xi Wi ), where Xi denotes the output feature matrix of the i-th GCN layer and X0 is set to X. The node features are transformed from Xi ∈ Rn×ci+1 . Note that  = A + I is employed to add self-loops, and D is a diagonal node degree matrix to perform normalization on Â. In addition, Wi ∈ Rci ×ci+1 is a learnable weight matrix to perform linear transformations on features, and σ(·) is the non-linear activation function. B. Instance-level explanations Instance-level explanation methods aim to identify the subset of input features that most strongly influence the prediction, providing input-dependent explanations for each graph [9]. Based on how feature-contribution scores are obtained, instance-level explanation methods can be categorized into gradient- or feature-based methods [28], [29], decompositionbased methods [30], surrogate-based methods [16], [31]–[33], and perturbation-based methods [10], [19], [20], [34]–[36]. Perturbation-based methods are widely used to explain deep graph models. Their core motivation is to study how the output changes under different input perturbations. When important features are preserved (i.e., not perturbed), the prediction should remain similar to the original prediction. In practice, these methods employ various mask-generation algorithms to produce different types of masks. Combining a mask with the input graph produces a new graph that retains important input information. This new graph is then fed into the trained GNN to evaluate the mask and update the mask-generation algorithm. C. Granular-ball Computing In 1982, Chen [37] points out that the brain gives priority to recognizing a “wide range” of contour information in image recognition, and that human cognition exhibits the characteristic of “global precedence”. The human brain’s global precedence cognition is efficient and robust, which is beneficial for improving the performance of existing artificial intelligence algorithms. Wang [38] first introduces the large-scale cognitive rule into granular computing and proposes multi-granular cognitive computing. Xia and Wang [23], [24] further use granular-balls of different sizes to represent “grains” and propose granular-ball computing, in which a large granular-ball represents a coarse-grained representation, while
3
Fig. 2. Overview of SeeExplainer. (a) Synergistic Edge Effects Modeling Module: it constructs a structural graph by leveraging information from the original graph and granular-ball computing, aiming to capture the synergistic effects among edges. (b) Structural Perturbation-Based Explanation Module: it employs graph neural networks to quantify the contributions of nodes (i.e., substructures in the original graph) and edges within the structural graph, and subsequently generates explanatory subgraphs.
a small granular-ball represents a fine-grained representation. Granular-ball computing is initially used to deal with classification problems successfully, and it is also applied to many other learning methods to improve their generalizability or efficiency, such as machine learning [39], clustering [40]– [44], rough sets [45], [46], outlier detection [47], and graph coarsening [48].
graph corresponds to a structural unit in the original graph, while edges (vi′ , vj′ ) ∈ E ′ encode relationships between these structural units. Based on this abstraction, we formulate the explanation task as identifying a subgraph G̃ = (Ṽ , Ẽ) of the structural graph G′ , where Ṽ ⊆ V ′ and Ẽ ⊆ E ′ . The resulting explanatory subgraphs G̃ should ensure that when the original graph substructure corresponding to G′ is used as input, the GNN’s prediction remains faithful to the original output.
III. P RELIMINARIES A. Problem Formulation Let G = (V, E) be a graph, where V = {v1 , v2 , ..., vn } denotes the set of nodes and E ⊆ V × V denotes the set of edges. The adjacency matrix of G is denoted by A ∈ {0, 1}n×n , where Aij = 1 if there exists an edge between nodes vi and vj . Given a pre-trained graph neural network ϕ(·) that denotes the logits predicted by the model for the true label Y , our work aims to identify the explanatory subgraphs within G that are most influential for the model’s prediction. Directly interpreting GNN predictions on the original graph, however, often fails to capture potential synergistic effects among edges. Therefore, we construct a structural graph G′ = (V ′ , E ′ ) by abstracting the local patterns with synergistic effects in G as structural units. Each node v ′ ∈ V ′ in the structural
IV. M ETHOD In this section, we propose SeeExplainer, a graph neural network explainer that considers the synergistic effects among edges and generates subgraphs to explain GNN predictions. As shown in Fig. 2, SeeExplainer includes a synergistic edge effects modeling module (in section IV-A) and a structural perturbation-based explanation module (in section IV-B). A. Synergistic Edge Effects Modeling Module ′
In this module, we aim to generate a structural graph G that captures the synergistic effects among edges in an original graph G. Firstly, at the beginning of the graph structuring process, we use a granular-ball GB to cover G and perform global computation on the graph, thereby simulating the human
4
cognitive characteristic of “global precedence”. Secondly, we perform non-isomorphic factorization on the graph, dividing it into several disjoint subgraphs with no fixed size. This process can better generates substructures with synergistic effects and utilize them as nodes in the structural graph. Specifically, we perform a coarse-splitting strategy on GB, followed by a finesplitting strategy on each child-ball in GB until the algorithm converges. 1) Graph representation and global computation: Given a graph G = (V, E) with n nodes and m edges, the adjacency matrix of G is denoted by A ∈ Rn×n , where ( 1, if (i, j) ∈ E, (1) Aij = 0, otherwise . First, we consider the entire graph as a whole and use an initial granular-ball GB to cover and represent graph G. Mathematically, GB = (V, E), (2) where GB represents the coarsest granularity of G. Then, we compute the degree of each node in G. This step is regarded as a global computation and helps accelerate the subsequent granular-ball splitting process. The degree of node vi is n X deg(vi ) = Aij , (3) j=1
where vi ∈ V . 2) Coarse-splitting strategy: In graph theory, the correlation among edges is generated by sharing vertices [49]. This correlation can be formalized by treating each edge as an entity and the shared vertices as interaction channels. Therefore, we select nodes with the highest degrees in GB as center points of the sub-balls. Mathematically, X C = {c1 , c2 , · · · , cs } = argmax deg(vi ), (4) vi ∈V
√
√
where s = n. The selection of n is empirical, based on previous works [48], [50], [51]. It enables fast processing of large-scale graphs, improving computational efficiency while maintaining a balance between size and quality. Then, we use breadth-first search (BFS) [52] to assign the remaining nodes v ∈ V \ C to obtain child-balls, GB = {GB1 , GB2 , · · · , GBs } ,
(5) √
where GB1 ∩ GB2 ∩ . . . ∩ GBs = ∅, and s = n. 3) Fine-splitting strategy: Next, we perform a fine-splitting strategy on each child-ball GBi ∈ GB, i ∈ (1, s) respectively. Specifically, treat GBi as a new parent-ball, and select two nodes with the highest degree in GBi as the center points. The center points can be represented as, X (ci1 , ci2 ) = argmax deg(v). (6) v∈GBi
And we use BFS to assign the remaining nodes v ∈ GBi \ (ci1 , ci2 ) to obtain two clusters clus i1 and clus i2 .
Then, we calculate the quality of GBi , clus i1 , and clus i2 respectively. The formula for calculating quality is Q(GB) =
|EGB | , |VGB |
(7)
where |EGB | indicates the number of edges in GB, and |VGB | denotes the number of nodes in GB. Next, we will provide the splitting conditions of a granularball. ( Q(clus i1 ) + Q(clus i2 ) > Q(GBi ) , split; (8) otherwise , not split. If the splitting conditions are met, the granular-ball GBi is split into GBi1 and GBi2 , where GBi1 corresponds to clus i1 and GBi2 corresponds to clus i2 . After obtaining GBi1 and GBi2 , they are iteratively treated as new parentballs, and the fine-splitting strategy is applied to them until the algorithm converges. The splitting strategy ensures that all factors in the decomposition process of the graph satisfy a global balance condition. Due to the adaptive number of factors, the overall structure obtained after decomposition also satisfies an inherent balance. Finally, we consider generated granular-balls as new nodes ′ ′ ′ to generate a structural graph G = (V , E ) with p nodes ′ and q edges, where V = {GB1 , GB2 , · · · , GBp } and ′ ′ E = {e1 , e2 , · · · , eq }. The structural graphSG satisfies Sp q GB1 ∩ GB2 ∩ . . . GBp = ∅, and i=1 GBi ⊕ j=1 ej = G. The process of a structural graph generation is provided in Algorithm 1. Algorithm 1 Generation of a structural graph Input: An original graph G = (V, X, A). ′ Output: A structural graph G . 1: Initialize a granular-ball GB covering G, and compute node degrees in G ( Eq. 3 ); √ 2: Select n nodes with the highest degrees as centers, √ assign remaining nodes by BFS, and split GB into n granular-balls {GB1 , · · · , GBs } (Eq. 4-5); 3: Compute the quality Q(GBi ) for each GBi (i = 1, · · · , s) (Eq. 7); 4: for each parent-ball GBi do 5: Select two highest-degree nodes in GBi as centers (Eq. 6); 6: Split GBi into two clusters clus i1 and clus i2 using BFS; 7: Compute Q(clus i1 ) and Q(clus i2 ); 8: if Q(clus i1 ) + Q(clus i2 ) > Q(GBi ) then 9: Split GBi into two child-balls GBi1 = clus i1 and GBi2 = clus i2 and add them to GB list; 10: Treat GBi1 and GBi2 as new parent-balls and repeat step 4; 11: end if 12: end for 13: return GB list
5
B. Structural Perturbation-Based Explanation Module ′
After generating a structural graph G from G, we evaluate it to derive the final explanatory subgraphs. First, we compute ′ the individual contributions of nodes and edges in G , where ′ the contribution of each node in G corresponds to that of the associated substructure in G. Second, we generate explanatory subgraphs based on a simple threshold judgment. 1) Contribution assessment: Given a graph G = (V, E) with n nodes and m edges, its corresponding graph n ′ structural o ′ ′ ′ ′ ′ ′ is denoted as G = (V , E ), where V = v1 , v2 , · · · , vp = ′
{GB1 , GB2 , · · · , GBp }, and E = {e1 , e2 , · · · , eq }. For a graph neural network ϕ(·), we adopt the average prediction confidence as a measure of contribution. Thus, the contribution of G is defined as Pm (ϕ(G) − ϕ(G \ ei )) . (9) I(G) = i=1 m ′
′
The contribution of node vi in G is defined as ′
′
I(vi ) = ϕ(G) − ϕ(G \ vi )), ′
(10)
′
Algorithm 2 Generation of explanatory subgraphs Input: A graph neural network ϕ(·), a graph G = (V, E) ′ ′ ′ ′ and its structural n o graph G = (V , E ) where V ′ = ′ ′ ′ v1 , v2 , · · · , vp = {GB1 , GB2 , · · · , GBp } and E = {e1 , e2 , . . . , eq } Output: Subgraph G̃. 1: initialize G̃ list as an empty list; 2: Put G into ϕ(·) to get its contribution I(G) (Equation 9); ′ ′ 3: Put vi into ϕ(·) to get its contribution I(vi ), where ′ ′ vi ∈ (GB1 , GB2 , · · · GBp ); and put ej into ϕ(·) to get its ′ ′ contribution I(ej ), where ej ∈ (e1 , e2 , . . . , eq ) (Equation 10, 11); ′ ′ 4: Compare I(G) with I(vi ) and I(ej ): ′ 5: if I(vi ) > I(G) then ′ 6: add vi to G̃ list. 7: end if ′ 8: if I(ej ) > I(G) then ′ 9: add ej to G̃ list. 10: end if 11: return G̃ list.
where vi ∈ V , and i ∈ (1, p). ′ ′ The contribution of edge ej in G is defined as ′
′
I(ej ) = ϕ(G) − ϕ(G \ ej )), ′
(11)
′
where ej ∈ E , and j ∈ (1, q). 2) Explanatory subgraphs generation: When we obtain the ′ contribution of each node and edge in G , we generate an explanatory subgraphs for the original graph G. Specifically, ′ ′ we use I(G) as the threshold. If I(vi ) > I(G), then vi is ′ an important substructure in graph G. If I(ej ) > I(G), then ′ ′ ′ ej is an important edge in graph G. We aggregate vi and ej that meet the above conditions, which together form the final explanatory subgraphs. The explanatory subgraphs are obtained by comparing a threshold with the contribution of local structures or edges. The reason is that the threshold is computed as the average contribution of the entire graph. When the contribution of a local structure or edge exceeds the threshold, it indicates that the local structure has obtained positive synergistic effects among edges during the construction of the structural graph. The process of explanatory subgraphs generation is provided in Algorithm 2. C. Time Complexity Analysis Let n and m denote the number of nodes and edges in the original graph, respectively. The number of nodes and edges in the corresponding structural graph is p and q, respectively, and both are much smaller than n and m. The time complexity of SeeExplainer is O((m + n)logn). Specifically, we perform a global computation on the graph to calculate the degree of each node in the graph, with a time complexity of O(m + n). Then, we perform √ a coarsen granularsplitting strategy to the original graph to generate √ balls. In this step, n nodes with the highest degrees are selected as center nodes, and the remaining nodes are assigned using a breadth-first search (BFS) algorithm, resulting in a
time complexity of O(m + n). Next, we treat each granularball as a parent-ball and recursively split until the algorithm converges, with a time complexity of O((m + n)logn). The time complexity for computing the quality of a granular-ball is O(p + q). V. E XPERIMENTS To comprehensively evaluate SeeExplainer, we formulate four research questions: • RQ1 (Fidelity): Can SeeExplainer achieve high fidelity in interpretability? • RQ2 (Stability): Can the explanatory subgraphs be stably generated? Specifically, at different sparsity levels, the overall fidelity is expected to remain similar. • RQ3 (Ablation Studies): How do the key components of SeeExplainer affect its performance? • RQ4 (Case Study): How does SeeExplainer perform in visualization? A. Experimental Setup Datasets: We evaluate our method on several standard graph classification datasets, including MUTAG [53], Mutagenicity [54], NCI1 [55], IMDB-BINARY [4], ENZYMES [6], PROTEINS [56], NCI109 [57], DHFR [7], BZR [25], and DD [5]. Table II lists the basic information of datasets. Experimental Settings: In our evaluation, we consider two variants of GNNs, namely Graph Isomorphism Networks (GIN) [27] and Graph Convolutional Networks (GCN) [26]. For the training of these GNNs, we use grid search to adjust the hyperparameters and find the best combination. We set the epochs to 100, the batch size to 128, the learning rate to 0.01, the learning rate decay factor to 0.5, and the learning rate decay step size to 50. The network hierarchy range is [1, 2, 3, 4, 5], and the hidden layer range is [16, 32, 64, 128].
6
TABLE I T HE FIDELITY COMPARISON BETWEEN S EE E XPLAINER AND BASELINES ON BENCHMARK DATASETS WITH GIN AND GCN (%). H IGHER VALUES INDICATE BETTER FIDELITY. F OR CLARITY, THE BEST RESULT IS HIGHLIGHTED IN BOLD AND THE SECOND - BEST RESULT IS REPRESENTED BY UNDERLINE . GNNs
GIN
GCN
Method
MUTAG Mutagenicity NCI1 IMDB-BINARY ENZYMES PROTEINS NCI109 DHFR
PGExplainer DeepLIFT GNNExpaliner GraphLime GradCAM Eig-Search SeeExplainer PGExplainer DeepLIFT GNNExpaliner GraphLime GradCAM Eig-Search SeeExplainer
18.284 30.168 1.076 41.270 12.251 13.409 64.193 20.262 1.922 1.958 38.920 2.926 6.746 63.305
7.802 19.742 5.549 11.882 16.283 55.563 78.639 1.331 12.625 12.720 2.638 18.683 57.726 87.700
-0.817 12.179 4.358 -5.028 3.512 41.870 69.842 3.958 3.767 3.618 2.868 9.068 57.582 82.457
14.082 4.008 14.870 -4.118 -4.038 11.861 53.566 10.465 11.048 11.130 -10.792 3.765 24.091 48.297
5.064 9.869 10.244 39.576 0.023 26.591 69.190 1.176 6.267 6.028 15.704 -0.910 18.469 39.052
13.350 12.790 15.742 30.368 -5.163 17.124 58.437 11.819 13.723 13.700 25.400 3.562 28.485 62.700
6.788 10.416 1.931 7.380 5.253 52.972 68.281 -0.289 2.946 3.006 -6.772 5.165 36.753 54.132
BZR
DD
0.820 0.374 25.019 8.042 1.576 -52.911 2.770 8.243 29.511 -1.658 -2.060 47.270 7.816 15.741 69.570 62.048 42.258 72.127 76.214 54.947 95.681 -4.426 8.045 13.639 4.224 -0.683 20.700 4.240 -0.206 20.054 -9.316 -3.514 33.710 20.479 22.289 66.919 54.393 66.141 88.519 55.280 75.923 96.111
[58], GNNExplainer [10], GraphLime [16], GradCAM [59], and Eig-Search [17].
TABLE II DATASET I NFORMATION . Datasets
Graphs
Avg. Nodes
Avg. Edges
MUTAG Mutagenicity NCI1 PROTEINS IMDB-BINARY NCI109 DHFR BZR DD ENZYMES
188 4337 4110 1113 1000 4127 756 405 1178 600
17.93 30.32 29.87 39.06 19.77 29.68 42.43 35.75 284.32 32.63
19.79 30.77 32.30 72.82 96.53 32.13 44.54 38.36 715.66 62.14
Metrics. In this paper, we employ standard metrics of fidelity as evaluation criteria, where higher values indicate superior performance. F idelity + measures the change in model prediction when the explanatory subgraphs G̃ is removed, while F idelity − measures the change when only G̃ is retained. F idelity is used to quantify the overall change in model prediction. By evaluating F idelity + and F idelity − , we can obtain a comprehensive understanding of explanation accuracy at different sparsity levels sk , thereby capturing the contribution of different input features. Specifically,
TABLE III B ENCHMARK MODEL INFORMATION . BL, BH, AND ACC INDICATE THE BEST NUMBER OF LAYERS , THE BEST HIDDEN UNITS , AND THE BEST ACCURACY, RESPECTIVELY. GIN
GCN
Datasets
BL
BH
ACC
BL
BH
ACC
MUTAG Mutagenicity NCI1 IMDB-BINARY ENZYMES PROTEINS NCI109 DHFR BZR DD
4 3 3 4 2 4 4 4 4 1
64 64 64 128 128 128 64 64 32 128
0.867 ± 0.083 0.813 ± 0.021 0.784 ± 0.015 0.750 ± 0.034 0.400 ± 0.057 0.732 ± 0.044 0.766 ± 0.024 0.803 ± 0.059 0.840 ± 0.023 0.727 ± 0.032
3 3 3 2 3 3 3 3 5 3
128 64 64 64 128 128 32 128 128 128
0.792 ± 0.124 0.807 ± 0.019 0.743 ± 0.042 0.748 ± 0.046 0.335 ± 0.100 0.734 ± 0.037 0.727 ± 0.030 0.734 ± 0.074 0.852 ± 0.021 0.735 ± 0.029
F idelity + (G, sk ) = ϕ(G, sk ) − ϕ(G \ G̃, sk ),
(12)
F idelity − (G, sk ) = ϕ(G, sk ) − ϕ(G̃, sk ),
(13)
F idelity(G, sk ) = F idelity + (G, sk ) − F idelity − (G, sk ). (14) Note that the fidelity reported in our experimental results is the average of F idelity(G, sk ) across different sparsity levels sk . Stability is defined as the difference between the average fidelity across all sparsity levels and the fidelity at a specific sparsity level. A smaller difference indicates stronger stability. Formally, u
S(sk ) =
1X F idelity(G, sk ) − F idelity(G, sk ) , (15) u k=1
Each dataset is split into 80% training, 10% testing, and 10% validation sets. Each model is run 20 times, and the model with the highest test accuracy is our benchmark model. All experiments are conducted on a Xeon(R) Gold 5218 CPU @ 2.30GHz with four Tesla V100 GPUs. The key software environment includes CUDA 11.3, Python 3.9.18, Pytorch 1.11.0, and NetworkX 3.2.1. The detailed information of the model is shown in Table III. Baselines. We extensively compared our method with the most widely used and the state-of-the-art explain algorithms. The comparison methods including PGExplainer [20], DeepLIFT
where u is the number of sparsity levels. B. Fidelity (RQ1) A good explainer should be able to generate accurate explanations. To verify the effectiveness of SeeExplainer, we conduct experiments on ten real-world datasets. Table I shows the average fidelity results on the datasets (MUTAG, Mutagenicity, NCI1, IMDB-BINARY, ENZYMES, PROTEINS, NCI109, DHFR, BZR, and DD) with different graph neural networks (GIN and GCN) at different sparsity levels (0.5, 0.6,
7
TABLE IV T HE STABILITY COMPARISON BETWEEN S EE E XPLAINER AND BASELINES ON THE BENCHMARK DATASETS USING GIN AND GCN. L OWER VALUES INDICATE BETTER STABILITY. F OR CLARITY, THE BEST RESULT IS HIGHLIGHTED IN BOLD AND THE SECOND - BEST RESULT IS REPRESENTED BY UNDERLINE . GNNs
GIN
GCN
Method PGExplainer DeepLIFT GNNExpaliner GraphLime GradCAM Eig-Search SeeExplainer PGExplainer DeepLIFT GNNExpaliner GraphLime GradCAM Eig-Search SeeExplainer
MUTAG Mutagenicity
NCI1
1.6E-01 1.0E-01 6.1E-02 3.0E-02 1.3E-01 1.5E-01 1.9E-10 1.1E-01 3.4E-02 3.5E-02 1.2E-02 4.7E-02 5.7E-02 6.8E-10
3.9E-02 4.0E-02 3.4E-02 3.0E-02 4.7E-02 1.2E-01 1.2E-10 2.9E-02 3.4E-02 3.5E-02 1.9E-02 5.7E-02 1.3E-01 9.0E-11
7.4E-02 5.8E-02 4.8E-02 7.5E-02 9.6E-02 1.3E-01 8.0E-11 5.4E-02 8.4E-02 8.6E-02 4.6E-03 1.2E-01 1.7E-01 8.6E-11
IMDB-BINARY ENZYMES PROTEINS NCI109 DHFR 8.5E-02 9.1E-02 8.6E-02 5.6E-02 1.1E-01 1.3E-01 2.4E-10 6.9E-02 6.2E-02 6.4E-02 5.9E-02 7.0E-02 9.8E-02 2.7E-10
0.7, 0.8, and 0.9). It is evident from Table I that SeeExplainer achieves the best results compared with baselines across all datasets, regardless of GIN or GCN. These results indicate that SeeExplainer effectively captures the synergistic effects among edges during the structuring stage of the graph, thereby improving fidelity.
8.7E-02 7.3E-02 8.6E-02 1.4E-02 8.6E-02 1.1E-01 6.1E-10 4.5E-02 3.5E-02 3.9E-02 5.1E-03 4.8E-02 6.7E-02 1.3E-09
6.3E-02 6.8E-02 9.4E-02 3.9E-03 8.6E-02 1.2E-01 2.4E-10 6.2E-02 7.5E-02 7.8E-02 7.2E-04 7.4E-02 1.4E-01 1.9E-10
BZR
DD
6.5E-03 4.6E-02 1.2E-02 1.6E-01 7.4E-02 3.1E-02 1.5E-02 5.9E-02 2.3E-02 3.1E-02 1.2E-01 1.7E-01 1.1E-02 3.2E-02 4.3E-03 4.6E-03 2.4E-02 9.6E-02 7.0E-02 9.7E-02 1.0E-01 1.4E-01 7.2E-02 1.6E-02 1.9E-10 3.2E-10 4.3E-10 1.0E-09 2.4E-02 3.4E-02 1.0E-01 1.0E-01 2.9E-02 3.5E-02 1.1E-0 1.4E-01 2.9E-02 4.0E-02 1.4E-02 1.4E-01 3.0E-03 5.6E-02 1.4E-02 1.5E-02 5.6E-02 3.8E-02 1.8E-01 9.7E-02 1.0E-01 4.4E-02 7.1E-02 1.7E-02 1.0E-10 2.8E-10 5.0E-10 1.2E-08
high-value components while removing low-value ones. It should be noted that the graphs in the DD dataset are very large, and their labels are determined by the overall topological structure. This indicates that SeeExplainer has a significant advantage in capturing and characterizing graph structures. C. Stability (RQ2)
Fig. 3. Heatmaps of fidelity− and fidelity+ for GIN and GCN.
Since fidelity is jointly determined by fidelity+ and fidelity− , we present heatmaps of the fidelity+ and fidelity− values across all datasets under different graph neural networks to better illustrate the effectiveness of SeeExplainer. As shown in Fig. 3, the first row depicts the fidelity− values for all datasets using GIN or GCN, where a lower fidelity− indicates better performance. The experimental results show that SeeExplainer achieves the lowest values in most cases. The second row presents the fidelity+ values under GIN or GCN, where a higher fidelity+ indicates better performance. As illustrated in the figure, SeeExplainer consistently attains the highest fidelity+ values in most cases. Consequently, SeeExplainer achieves the best overall performance. Although some baselines have achieve relatively high fidelity+ , their correspondingly high fidelity− values result in suboptimal overall performance. These results indicate that SeeExplainer more effectively captures truly explanatory subgraphs by retaining
In this section, we conduct experiments to evaluate the stability of baselines and SeeExplainer. Stability quantifies the robustness of explanations under different sparsity levels. The average difference in fidelity reflects the degree of fluctuation in the explanations. Accordingly, we evaluate fidelity at different sparsity levels and compute the average difference between the fidelity at each sparsity level and the overall average fidelity across all sparsity levels. Smaller variations indicate that the explainer produces more consistent and stable explanations. The experimental results are reported in Table IV, which shows that SeeExplainer also achieves the best stability performance across all datasets, with values close to 0. The reason is that SeeExplainer generates explanatory subgraphs directly from the structural graph and is therefore unaffected by parameter settings. In contrast, our baseline method Eig-Search produces explanations that depend on the input parameter k, which leads to substantial variation in its output. D. Ablation Studies (RQ3) In this section, to better evaluate the role of each module in SeeExplainer, we conducted ablation experiments to assess the performance of the variants, including the different initialization strategies for structural graph generation and the composition information in the explanatory subgraphs. 1) Initialization methods for structural graph generation: We analyze the influence of different initialization methods in the first division round of structural graph generation, including two and radical n initial granular-balls. The fidelity comparison results are reported in Table V, and the comparison of the average time consumption per graph across different
8
TABLE V A BLATION RESULTS OF DIFFERENT INITIALIZATION METHODS FOR STRUCTURAL GRAPH GENERATION . GNNs GIN GCN
Variants
MUTAG Mutagenicity NCI1 IMDB-BINARY ENZYMES PROTEINS NCI109 DHFR
Two Radical n Two Radical n
62.284 64.193 63.458 63.305
79.479 78.639 87.207 87.700
70.952 69.842 81.348 82.457
52.558 53.566 47.885 48.297
68.487 69.190 38.632 39.052
60.289 58.437 62.656 62.700
67.487 68.281 53.500 54.132
BZR
DD
76.041 55.165 95.205 76.214 54.947 95.681 56.760 75.521 95.396 55.280 75.923 96.111
TABLE VI A BLATION RESULTS OF COMPOSITION INFORMATION IN THE EXPLANATORY SUBGRAPH . GNNs GIN
GCN
Variants
MUTAG Mutagenicity NCI1 IMDB-BINARY ENZYMES PROTEINS NCI109 DHFR
SeeExplainer -w/o inter-structure edges -w/o structures SeeExplainer -w/o inter-structure edges -w/o structures
64.193 16.084 11.514 63.305 9.131 2.198
78.639 50.612 47.116 87.700 54.239 53.452
69.842 28.974 37.386 82.457 42.785 52.735
(a)
(b) Fig. 4. Comparison of time consumption between two and radical n splitting in the first round.
datasets is shown in Fig. 4. Based on the experimental results, we can obtain the following observations. The experimental results in Table V indicate that in the first division round of the granular-ball, the radical n division method achieves overall superior performance. • As shown in Fig. 4, except for the IMDB-BINARY and PROTEINS datasets, the radical n method is clearly faster in terms of time consumption than the two-initial granular-ball method. • Based on the above observations, we can conclude that adopting the radical n method in the first split is more advantageous. It achieves higher fidelity than the twoinitial granular-ball method while also providing faster computation. This phenomenon occurs is because initializing radical n granular-balls enables a more •
53.566 28.737 -9.296 48.297 19.425 3.736
69.190 37.220 21.216 39.052 20.283 14.060
58.437 27.007 15.727 62.700 34.871 21.768
68.281 38.420 50.560 54.132 31.519 33.334
BZR
DD
76.214 54.947 95.681 41.986 25.423 46.067 64.865 11.207 40.381 55.280 75.923 96.111 48.250 22.115 78.373 44.669 54.350 59.311
comprehensive capture of important graph features and leads to faster convergence. 2) Composition information in the explanatory subgraph: We analyze the influence of the construction information of explanatory subgraphs, including SeeExplainer-w/o interstructure edges and SeeExplainer-w/o structures. The results are shown in Table VI. • Removing the inter-structure edges in the structural graph significantly reduces the performance of the model, highlighting its contribution. This mechanism is crucial for capturing coarse-grained features of the graph. Without this mechanism, it is difficult for the model to effectively utilize the features of the graph, which emphasizes its necessity in interpretability tasks. • Removing structures from the explanatory subgraph also significantly reduces the performance of the model. This mechanism can effectively capture fine-grained features in the graph, that is, structural information containing the synergistic effects among edges. It emphasizes the key to understanding the composition of explanatory subgraphs. • It is worth noting that on the MUTAG, NCI1, IMDBBINARY, ENZYMES, PROTEINS, BZR, and DD with GIN, as well as the MUTAG, IMDB-BINARY, ENZYMES, and PROTEINS with GCN, the fidelity of SeeExplainer is higher than the sum of SeeExplainer-w/o inter-structure edges and SeeExplainer-w/o structures, indicating that SeeExplainer effectively captures the synergistic effects among structural components. • The experimental results for subgraphs that contain both the structures in the structural graph and the edges connecting the structures are much greater than those for individual subgraphs. The reason is that the explanatory subgraph effectively captures the compensation effect between coarse-grained structures and fine-grained edges, greatly improving fidelity. E. Case Study (RQ4) We visualize the explainability results of Eig-Search and SeeExplainer on several datasets. When dealing with the
9
Fig. 5. Comparison of cases. The first and third rows indicate Eig-Search, and the second and fourth rows represent SeeExplainer. The bold black areas are explanatory subgraphs.
MUTAG and Mutagenicity datasets, our goal is to identify chemical groups that are highly correlated with mutagenicity. The NCI1 and NCI109 datasets are used to predict effectiveness against cancer cells, where the objective is to discover chemical substructures associated with anticancer activity. The IMDB-BINARY dataset is used for binary movie genre classification, aiming to identify actor communities and highly connected star clusters. The ENZYMES dataset focuses on enzyme function classification, with the goal of identifying local structures that distinguish different enzymatic functions. The PROTEINS dataset is used to determine whether a protein is an enzyme, aiming to uncover substructures indicative of enzymatic activity. The DHFR dataset is employed to predict whether a compound inhibits DHFR, with the objective of explaining which atomic subgraphs contribute to DHFR inhibition. The BZR dataset is used to predict binding to the benzodiazepine receptor, aiming to identify substructures that determine a molecule’s receptor-binding capability. Finally, the DD dataset is used to distinguish protein structure types. Since DD graphs are extremely large and their labels are determined by global topology, the explanation goal is to identify which macroscopic structures govern protein folding types. The comparison result is shown in Fig. 5, which indicates that SeeExplainer retains important structure-level information, enabling classifiers to interpret the results of graph classification. VI. C ONCLUSIONS AND F UTURE W ORK In this work, we proposed SeeExplainer, which investigates how to capture the synergistic effects among graph edges in order to generate more faithful explanations for graph neural networks. Firstly, we explain the existence of
synergistic effects among edges. Then, inspired by granularball computing and graph non-isomorphic decomposition, we represent the original graph as a structural graph to capture edge-level synergy. Finally, explanatory subgraphs are directly generated from the structural graph through simple threshold judgment. Extensive experiments conducted on multiple realworld graph classification datasets verify the effectiveness of SeeExplainer. In future work, we will study SeeExplainer in real application scenarios (such as the medical domain) to evaluate its effectiveness and interpretability in real-world settings. R EFERENCES [1] Y. Xie, S. Lv, Y. Qian, C. Wen, and J. Liang, “Active and semi-supervised graph neural networks for graph classification,” IEEE Transactions on Big Data, vol. 8, no. 4, pp. 920–932, 2022. [2] Y. Xie, Y. Liang, M. Gong, A. K. Qin, Y.-S. Ong, and T. He, “Semisupervised graph neural networks for graph classification,” IEEE Transactions on Cybernetics, vol. 53, no. 10, pp. 6222–6235, 2022. [3] X. Cheng, Y. Wang, Y. Liu, Y. Zhao, C. C. Aggarwal, and T. Derr, “Edge classification on graphs: New directions in topological imbalance,” in Proceedings of the Eighteenth ACM International Conference on Web Search and Data Mining, 2025, pp. 392–400. [4] C. Cai and Y. Wang, “A simple yet effective baseline for non-attributed graph classification,” arXiv preprint arXiv:1811.03508, 2018. [5] C. Morris, N. M. Kriege, F. Bause, K. Kersting, P. Mutzel, and M. Neumann, “Tudataset: A collection of benchmark datasets for learning with graphs,” arXiv preprint arXiv:2007.08663, 2020. [6] K. M. Borgwardt, C. S. Ong, S. Schonauer, S. Vishwanathan, A. J. Smola, and H.-P. Kriegel, “Protein function prediction via graph kernels,” Bioinformatics, vol. 21, no. suppl 1, pp. i47–i56, 2005. [7] J. J. Sutherland, L. A. O’brien, and D. F. Weaver, “Spline-fitting with a genetic algorithm: A method for developing classification structure activity relationships,” Journal of Chemical Information and Computer Sciences, vol. 43, no. 6, pp. 1906–1915, 2003. [8] F. Doshi-Velez and B. Kim, “Towards a rigorous science of interpretable machine learning,” arXiv preprint arXiv:1702.08608, 2017.
10
[9] H. Yuan, H. Yu, S. Gui, and S. Ji, “Explainability in graph neural networks: A taxonomic survey,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 45, no. 5, pp. 5782–5799, 2022. [10] Z. Ying, D. Bourgeois, J. You, M. Zitnik, and J. Leskovec, “Gnnexplainer: Generating explanations for graph neural networks,” Advances in Neural Information Processing Systems, vol. 32, 2019. [11] H. Yuan, J. Tang, X. Hu, and S. Ji, “Xgnn: Towards model-level explanations of graph neural networks,” in Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2020, pp. 430–438. [12] X. Wang and H.-W. Shen, “Gnninterpreter: A probabilistic generative model-level explanation for graph neural networks,” arXiv preprint arXiv:2209.07924, 2022. [13] J. Chen, S. Wu, A. Gupta, and R. Ying, “D4explainer: In-distribution explanations of graph neural network via discrete denoising diffusion,” Advances in Neural Information Processing Systems, vol. 36, pp. 78 964–78 986, 2023. [14] X. Wang and H. W. Shen, “Gnnboundary: Towards explaining graph neural networks through the lens of decision boundaries,” in The Twelfth International Conference on Learning Representations, 2024. [15] S. Saha and S. Bandyopadhyay, “Graphon-explainer: Generating modellevel explanations for graph neural networks using graphons,” Transactions on Machine Learning Research, 2024. [16] Q. Huang, M. Yamada, Y. Tian, D. Singh, and Y. Chang, “Graphlime: Local interpretable model explanations for graph neural networks,” IEEE Transactions on Knowledge and Data Engineering, vol. 35, no. 7, pp. 6968–6972, 2022. [17] S. Lu, B. Liu, K. G. Mills, J. He, and D. Niu, “Eig-search: Generating edge-induced subgraphs for gnn explanation in linear time,” in Forty-first International Conference on Machine Learning, 2024. [18] M. S. Schlichtkrull, N. De Cao, and I. Titov, “Interpreting graph neural networks for nlp with differentiable edge masking,” arXiv preprint arXiv:2010.00577, 2020. [19] H. Yuan, H. Yu, J. Wang, K. Li, and S. Ji, “On explainability of graph neural networks via subgraph explorations,” in International Conference on Machine Learning. PMLR, 2021, pp. 12 241–12 252. [20] D. Luo, W. Cheng, D. Xu, W. Yu, B. Zong, H. Chen, and X. Zhang, “Parameterized explainer for graph neural network,” Advances in Neural Information Processing Systems, vol. 33, pp. 19 620–19 631, 2020. [21] P. Zhang and G. Chartrand, Introduction to graph theory. Tata McGrawHill New York, 2006, vol. 2, no. 2.1. [22] G. R. Waissi, “Network flows: Theory, algorithms, and applications,” 1994. [23] S. Xia, D. Peng, D. Meng, C. Zhang, G. Wang, E. Giem, W. Wei, and Z. Chen, “A fast adaptive k-means with no bounds,” IEEE Transactions on Pattern Analysis and Machine Intelligence, 2020. [24] S. Xia, X. Dai, G. Wang, X. Gao, and E. Giem, “An efficient and adaptive granular-ball generation method in classification problem,” IEEE Transactions on Neural Networks and Learning Systems, vol. 35, no. 4, pp. 5319–5331, 2024. [25] C. Vincent-Cuaz, T. Vayer, R. Flamary, M. Corneli, and N. Courty, “Online graph dictionary learning”, International Conference on Machine Learning. PMLR, 2021, pp. 10 564–10 574. [26] T. N. Kipf and M. Welling, “Semi-supervised classification with graph convolutional networks,” CoRR, vol. abs/1609.02907, 2016. [Online]. Available: http://arxiv.org/abs/1609.02907 [27] K. Xu, W. Hu, J. Leskovec, and S. Jegelka, “How powerful are graph neural networks?” 2019. [Online]. Available: https://arxiv.org/abs/1810.00826 [28] P. E. Pope, S. Kolouri, M. Rostami, C. E. Martin, and H. Hoffmann, “Explainability methods for graph convolutional neural networks,” in Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2019. [29] F. Baldassarre and H. Azizpour, “Explainability techniques for graph convolutional networks,” arXiv preprint arXiv:1905.13686, 2019. [30] Q. Feng, N. Liu, F. Yang, R. Tang, M. Du, and X. Hu, “Degree: Decomposition based explanation for graph neural networks,” arXiv preprint arXiv:2305.12895, 2023. [31] A. Duval and F. D. Malliaros, “Graphsvx: Shapley value explanations for graph neural networks,” in Joint European Conference on Machine Learning and Knowledge Discovery in Databases. Springer, 2021, pp.302–318. [32] T. Pereira, E. Nascimento, L. E. Resck, D. Mesquita, and A. Souza, “Distill n’explain: explaining graph neural networks using simple surrogates,” in International Conference on Artificial Intelligence and Statistics. PMLR, 2023, pp. 6199–6214.
[33] Y. Zhang, D. Defazio, and A. Ramesh, “Relex: A model-agnostic relational model explainer,” in Proceedings of the 2021 AAAI/ACM Conference on AI, Ethics, and Society, 2021, pp. 1042–1049. [34] X. Wang, Y. Wu, A. Zhang, X. He, and T.-S. Chua, “Towards multigrained explainability for graph neural networks,” Advances in Neural Information Processing Systems, vol. 34, pp. 18 446–18 458, 2021. [35] T. Funke, M. Khosla, M. Rathee, and A. Anand, “Zorro: Valid, sparse, and stable explanations in graph neural networks,” IEEE Transactions on Knowledge and Data Engineering, vol. 35, no. 8, pp. 8687–8698, 2022. [36] S. Zhang, Y. Liu, N. Shah, and Y. Sun, “Gstarx: Explaining graph neural networks with structure-aware cooperative games,” Advances in Neural Information Processing Systems, vol. 35, pp. 19 810–19 823, 2022. [37] L. Chen, “Topological structure in visual perception,” Science, vol. 218, no. 4573, pp. 699–700, 1982. [38] G. Wang, “Dgcc: data-driven granular cognitive computing,” Granular Computing, vol. 2, no. 4, pp. 343–355, 2017. [39] M. Sajid, A. Quadir, M. Tanveer, A. D. N. Initiative et al., “Gb-rvfl: Fusion of randomized neural network and granular ball computing,” Pattern Recognition, vol. 159, p. 111142, 2025. [40] S. Xia, D. Peng, D. Meng, C. Zhang, G. Wang, E. Giem, W. Wei, and Z. Chen, “Ball kk-means: Fast adaptive clustering with no bounds,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 44, no. 1, pp. 87–99, 2022. [41] S. Xia, B. Shi, Y. Wang, J. Xie, G. Wang, and X. Gao, “Gbct: efficient and adaptive clustering via granular-ball computing for complex data,” IEEE Transactions on Neural Networks and Learning Systems, 2025. [42] Z. Jia, Z. Zhang, and W. Pedrycz, “Generation of granular-balls for clustering based on the principle of justifiable granularity,” IEEE Transactions on Cybernetics, 2025. [43] W. Li, L. Wei, W. Pedrycz, W. Ding, C. Zhang, T. Zhan, and S. Xia, “Granular-ball regeneration clustering with principle of justifiable granularity,” IEEE Transactions on Neural Networks and Learning Systems, 2025. [44] J. Xie, Y. Cheng, S. Xia, C. Hua, G. Wang, and X. Gao, “Aw-gbgae: an adaptive weighted graph autoencoder based on granular-balls for general data clustering,” IEEE Transactions on Pattern Analysis and Machine Intelligence, 2025. [45] S. Xia, C. Wang, G. Wang, X. Gao, W. Ding, J. Yu, Y. Zhai, and Z. Chen, “Gbrs: A unified granular-ball learning model of pawlak rough set and neighborhood rough set,” IEEE Transactions on Neural Networks and Learning Systems, vol. 36, no. 1, pp. 1719–1733, 2025. [46] J. Yang, Z. Liu, G. Wang, Q. Zhang, S. Xia, D. Wu, and Y. Liu, “Constructing three-way decision with fuzzy granular-ball rough sets based on uncertainty invariance,” IEEE Transactions on Fuzzy Systems, 2025. [47] C. Gao, X. Tan, J. Zhou, W. Ding, and W. Pedrycz, “Fuzzy granule density-based outlier detection with multi-scale granular balls,” IEEE Transactions on Knowledge and Data Engineering, 2025. [48] S. Xia, X. Ma, Z. Liu, C. Liu, S. Zhao, and G. Wang, “Graph coarsening via supervised granular-ball for scalable graph neural network training,” in Proceedings of the AAAI Conference on Artificial Intelligence, 2025, pp. 12 872–12 880. [49] D. B. West et al., Introduction to graph theory. Prentice hall Upper Saddle River, 2001, vol. 2. [50] J. Xie, Z.-Y. Xiong, Q.-Z. Dai, X.-X. Wang, and Y.-F. Zhang, “A new internal index based on density core for clustering validation,” Information Sciences, vol. 506, pp. 346–365, 2020. [51] J. Yu and Q. Cheng, “The upper bound of the optimal number of clusters in fuzzy clustering,” Science in China Series: Information Sciences, vol. 44, no. 2, pp. 119–125, 2001. [52] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to algorithms. MIT press, 2022. [53] A. K. Debnath, R. L. Lopez de Compadre, G. Debnath, A. J. Shusterman, and C. Hansch, “Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds. correlation with molecular orbital energies and hydrophobicity,” Journal of Medicinal Chemistry, vol. 34, no. 2, pp. 786–797, 1991. [Online]. Available: https://doi.org/10.1021/jm00106a046 [54] J. Kazius, R. McGuire, and R. Bursi, “Derivation and validation of toxicophores for mutagenicity prediction,” Journal of Medicinal Chemistry, vol. 48, no. 1, pp. 312–320, 2005, pMID: 15634026. [Online]. Available: https://doi.org/10.1021/jm040835a [55] N. Wale, I. A. Watson, and G. Karypis, “Comparison of descriptor spaces for chemical compound retrieval and classification,” Knowledge and Information Systems, vol. 14, no. 3, pp. 347–375, 2008.
11
[56] V. D. Blondel, J.-L. Guillaume, R. Lambiotte, and E. Lefebvre, “Fast unfolding of communities in large networks,” Journal of Statistical Mechanics: Theory and Experiment, vol. 2008, no. 10, p. P10008, 2008. [57] C. Morris, G. Rattan, and P. Mutzel, “Weisfeiler and leman go sparse: Towards scalable higher-order graph embeddings,” Advances in Neural Information Processing Systems, vol. 33, pp. 21 824–21 840, 2020. [58] M. Ancona, E. Ceolini, A. C. Oztireli, and M. H. Gross, “A unified view of gradient-based attribution methods for deep neural networks,” CoRR, vol. abs/1711.06104, 2017. [Online]. Available:http://arxiv.org/abs/1711.06104 [59] P. E. Pope, S. Kolouri, M. Rostami, C. E. Martin, and H. Hoffmann, “Explainability methods for graph convolutional neural networks,” in Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2019, pp. 10 772–10 781.