Explainable Graph Representation Learning via Graph Pattern Analysis

1 Introduction

The research field of explainable artificial intelligence (XAI) [Adadi and Berrada, 2018; Angelov et al., 2021; Hassija et al., 2024] is gaining significant attention in both AI and science communities. Interpretability is crucial for creating robust and trustworthy AI models, especially in critical domains like transportation, healthcare, law, and finance. Graph learning [Sun et al., 2023; Sun and Fan, 2024; Wang and Fan, 2024] is an important area of AI that particularly focuses on graph-structured data that widely exists in social science, biology, chemistry, etc. Explainable graph learning (XGL) [Kosan et al., 2023] can be generally classified into two categories: model-level methods and instancelevel methods.

∗Corresponding author.

Model-level methods of XGL provide transparency by analyzing the model behavior. Examples include XGNN [Yuan et al., 2020], GLG-Explainer [Azzolin et al., 2022], and GCFExplainer [Huang et al., 2023]. Instance-level methods of XGL offer explanations tailored to specific predictions, focusing on why particular instances are classified in a certain manner. For instance, GNNExplainer [Ying et al., 2019] identifies a compact subgraph structure crucial for a GNN's prediction. PGExplainer [Luo et al., 2020] trains a graph generator to incorporate global information and parameterize the explanation generation process. AutoGR [Wang et al., 2021] introduces an explainable AutoML approach for graph representation learning.

However, these works mainly focus on enhancing the transparency of GNN models or identifying the most important substructures that contribute to predictions. The exploration of representation-level explainable graph learning (XGL) is limited. We propose explainable graph representation learning and ask a fundamental question: What specific information about a graph is captured in graph representations? Formally, if we represent a graph G as a d-dimensional vector g, our goal is to understand what specific information about the graph G is embedded in the representation g. This problem is important and has practical applications. Some graph patterns are highly practical and crucial in various real-world tasks, and we want this information to be captured in representations. For instance, in molecular chemistry, bonds between atoms or functional groups often form cycles (rings), which indicate a molecule's properties and can be used to generate molecular fingerprints [Morgan, 1965; Alon et al., 2008; Rahman et al., 2009; O'Boyle and Sayle, 2016]. Similarly, cliques characterize protein complexes in Protein-Protein Interaction networks and help identify community structures in social networks [Girvan and Newman, 2002; Jiang et al., 2010; Fox et al., 2020].

Although some previous works such as [Kosan et al., 2023] aimed to find the most critical subgraph S by solving optimization problems based on perturbation-based reasoning, either factual or counterfactual, this kind of approach assumes that the most important subgraph S mainly contributes to the representation g, neglecting other aspects of the graph, which doesn't align well with our goal of thoroughly understanding graph representations. Analyzing all subgraphs of a graph G is impractical due to their vast number. To address the challenge, we propose to group the subgraphs into different graph patterns, like paths, trees, cycles, cliques, etc, and then analyze the contribution of each graph pattern to the graph representation g.

Our idea of pattern analysis is inspired by graph kernels, which compare substructures of specific graph patterns to evaluate the similarity between two graphs [Kriege et al., 2020]. For example, random walk kernels [Borgwardt et al., 2005; G¨artner et al., 2003] use path patterns, sub-tree kernels [Da San Martino et al., 2012; Smola and Vishwanathan, 2002] examine tree patterns, and graphlet kernels [Prˇzulj, 2007] focus on graphlet patterns. The graph kernel involves learning a pattern counting representation vector h, which counts the occurrences of substructures of a specific pattern within the graph G. While the pattern counting vector h is an explainable representation, it has some limitations, such as the high dimensionality and ignorance of node features.

There also exist some representation methods based on subgraphs and substructures, such as Subgraph Neural Networks (SubGNN) [Kriege and Mutzel, 2012], Substructure Assembling Network (SAN) [Zhao et al., 2018], Substructure Aware Graph Neural Networks (SAGNN) [Zeng et al., 2023], and Mutual Information (MI) Induced Substructureaware GRL [Wang et al., 2020]. However, these methods mainly focus on increasing expressiveness and do not provide explainability for representation learning.

In this work, we propose a novel framework to learn and explain graph representations via graph pattern analysis. We start by sampling graph substructures of various patterns. Then, we learn the representations of these patterns and combine them adaptively, where the weights indicate the importance of each graph pattern's contribution. We also provide theoretical analyses of our methods, including robustness and generalization. Additionally, we compare our method against multiple baselines in both supervised and unsupervised learning tasks to demonstrate its effectiveness and superiority. Our contributions are summarized as follows:

• Unlike previous model-level and instance-level XGL, we introduce a new issue - representation-level explainable graph learning. This issue focuses on understanding what specific information about a graph is embedded within its representations.
• We propose two strategies to learn and explain graph representations, including a graph ensemble kernel method (PXGL-EGK) and a pattern analysis GNN method (PXGL-GNN). The latter involves using GNNs to learn the representations of each pattern and evaluate its contribution to the ensemble graph representation.
• We provide theoretical analyses of our methods, including robustness and generalization.

2 Notations

In this work, we use x, x, X, and X (or X) to denote scalar, vector, matrix, and set, respectively. We denote [n] = {1, 2, ..., n}. Let G = (V,E) be a graph with n nodes and d-dimensional node features {xv ∈ Rd | v ∈ V }. We denote A ∈ {0, 1}n×n the adjacency matrix and X = [x1, . . . , xn]⊤ ∈ Rn×d the node features matrix. Let G = {G1, . . . ,GN} be a dataset of N graphs belonging C classes, where Gi = (Vi,Ei). For Gi, we denote its number of nodes as ni, the one-hot graph label as yi ∈ {0, 1}C , the graph-level representation as a vector gi ∈ Rd , the adjacency matrix as Ai, and the node feature matrix as Xi. Let S = (VS, ES) be a subgraph of graph G = (V, E) such that VS ⊆ V and ES ⊆ E. The the adjacency matrix of S is denoted as AS ∈ {0, 1}|VS|×|VS| and the node feature matrix of S is sampled from the rows of X, denoted as XS ∈ R|VS|×d .

The graph pattern is defined as a set of all graphs that share certain properties, denoted as P = {P1, P2, . . . , Pi, . . .}, where Pi is the i-th example of this pattern. In this work, the graph patterns are basic graph families such as paths, trees, cycles, cliques, etc. For example:

• Ppath = {ph1 , ph2 , . . . , phi , . . .} is a path pattern with phi as a path of length i.
• PT = {T1, T2, . . . , Ti, . . .} is a tree pattern where Ti is the i-th tree.
• Pgl = {gl1 , gl2 , . . . , gli , . . .} is a graphlet pattern where gli is the i-th graphlet.

Figure 1 illustrates some intuitive examples of graph patterns. Notably, there are overlaps among different patterns; for instance, the graph T3 ∈ PT and gl2 ∈ Pgl are identical, being both a tree and a graphlet. Overlaps are inevitable due to the predefined nature of these basic graph families in graph theory. We denote a set of M different patterns as {P1,P2, . . . , Pm, . . . , PM}. Given the pattern Pm and the graph Gi, the pattern sampling set is denoted as S (m) i and the pattern representation is denoted as z(m) i ∈ Rd .

3 XGL via Ensemble Graph Kernel

In this section, we learn and explain the pattern counting graph representation via graph kernels.

3.1 Pattern Counting Kernel

A graph kernel K : G × G → R aims to evaluate the similarity between two graphs. Let Gi and Gj be two graphs in the graph dataset G and let H be a high-dimensional vector space. The key to a graph kernel is defining a mapping from the graph space to the high-dimensional vector space as ϕ : G → H, where hi = ϕ(Gi) and hj = ϕ(Gj). Then, the graph kernel can be defined as the inner product of hi and hj, i.e., K(Gi,Gj) := h⊤i hj. The most widely used mapping ϕ is the one counting the occurrences of each example in the pattern P within graph G. The corresponding pattern counting vector is defined as follows:

Definition 3.1 (Pattern Counting Vector). Given a graph G and a pattern P = {P1, P2, . . . , Pi, . . .}, a pattern counting pattern Pm within the dataset G. Instead of the constrained optimization (3), we may consider replacing λm with exp(wm)/ ∑Mm=1 exp(wm) such that the constraints are satisfied inherently, which leads to an unconstrained optimization in terms of w = [w1, . . . ,wM]⊤. In the following context, for convenience, we focus on (3), though all results are applicable to the unconstrained optimization. To obtain the weight parameter λ, we provide the supervised and unsupervised loss functions as follows.

Supervised Contrastive Loss. Following [Oord et al., 2018], given a kernel matrix K ∈ RN×N , we define the supervised InfoNEC loss of K as follows

where I[·] is an indicator function and µ > 0 is a hyperparameter.

Unsupervised KL Divergence. Inspired by [Xie et al., 2016], given a kernel matrix K ∈ RN×N , we define the unsupervised KL divergence loss as follows

where rj are soft cluster frequencies. By minimizing the KL divergence, the model adjusts the parameters λ to more accurately represent the natural clustering property of the dataset.

We use the LSCL or LKL as our loss function, i.e., Lker(λ) = LSCL(K(λ)) or LKL(K(λ)), when the graphs are labeled or unlabeled. Then the weight parameter λ can be obtain by solving

where λ∗ = [λ∗1 , ..., λ∗m, ...λ∗M ]⊤ and λ∗m indicates the importance of kernel KPm as well as pattern Pm. In Figure 2, we can see that the ensemble Kernel performs better than each single kernel and the pattern analysis identifies the importance of each kernel as well as the related graph pattern. We call this method pattern-based XGL with ensemble graph kernel, abbreviated as PXGL-EGK. This method not only yields explainable similarity learning but also provides an approach to selecting graph kernels and their hyperparameters automatically if we consider different kernel types with different hyperparameters.

mapping ϕ : G → H is defined as

where h(i) is the number of occurrences of pattern example Pi as a substructure within graph G. We call h a pattern counting vector of G related to pattern P.

Then the pattern counting kernel KP : G × G → R based on pattern P is defined as:

Definition 3.2 (Pattern Counting Kernel). Given the a pattern counting mapping ϕ(G; P), a pattern counting kernel is defined as

The pattern counting kernel KP is uniquely determined by the pattern P. For example, if P is selected as the path pattern Ppath, we obtain a random walk kernel [Borgwardt et al., 2005; G¨artner et al., 2003]. If P is the tree pattern PT , we get a sub-tree kernel [Da San Martino et al., 2012; Smola and Vishwanathan, 2002]. Similarly, if P is the graphlet pattern Pgl, we derive a graphlet kernel [Prˇzulj, 2007].

3.2 Pattern Analysis Using Graph Kernels

Let {P1, P2, . . . , PM} be a set of M different graph patterns. For instance, P1 represents the path pattern and P2 represents the tree pattern. Then, we can define a set of M different graph kernels as {KP1 ,KP2 , . . . ,KPM }. Since the pattern counting kernel KPm is uniquely determined by the pattern Pm, we can analyse the importance of pattern Pm by evaluating the importance of its pattern counting kernel KPm . To achieve this, we define a learnable ensemble kernel as follows:

Definition 3.3 (Learnable Ensemble Kernel). Let λ = [λ1, λ2, ..., λm, ..., λM]⊤ be a positive weight parameter vector. The ensemble kernel matrix K(λ) ∈ R|G|×|G| is defined as the weighted sum of M different kernels {KP1 ,KP2 , . . . ,KPM }. Given two graphs Gi and Gj in G, the element at the i-th row and j-th column of K(λ) is given by

Here, the weight parameter λm indicates the importance of the kernel KPm as well as the corresponding graph

3.3 Limitations of Pattern Counting Vector

The pattern counting vector h from Definition 3.1 is easy to understand and its importance can be evaluated using the weight parameter λ∗ from (6). However, it cannot directly explain the representation of graph G due to the following limitations:

• Ignoring Node Features: h captures the topology of G but ignores node features X. As shown by previous GNN works, node features are crucial for learning graph representations.
• High Dimensionality: The pattern set P = {P1, P2, . . . , Pi, . . .} can be vast, making h highdimensional and impractical for many tasks.
• Time Complexity: Counting patterns Pi in G is timeconsuming due to the large number of patterns in P. The function ϕ(G; P) needs to be run for each new graph.
• Lacking Implicit Information and Strong Expressiveness: h is fixed and not learnable. GNN [Kipf and Welling, 2016] shows that message passing can learn implicit information and provide better representations, which should be considered if possible.

4 Learning Explainable Graph Representations via GNNs

In this section, we address the limitations pointed out in Section 3.3 by proposing a GNN framework to learn and explain graph representations via pattern analysis. First, we sample graph substructures of various patterns from graph G. Given that overlaps may occur between patterns, we use the WL-test [Huang and Villar, 2021] in each sampling phase to ensure that new samples are unique from existing ones. The pattern sampling set S is defined as follows.

Definition 4.1 (Pattern Sampling Set). Let S be a subgraph sampled from graph G. Given a graph pattern P, the pattern sampling set S with Q subgraphs of G is defined as

Then, the pattern representation z is learned from the pattern sampling set as follows.

Definition 4.2 (Pattern Representation). Given a graph G and a pattern P, we can obtain a pattern sampling set S using a sampling function Φ. For each subgraph S in the set S, its adjacency matrix is AS and its node feature matrix is XS. Let F : {0, 1}|VS|×|VS| ×R|VS|×d → Rd be a pattern representation learning function with parameter W, then the pattern representation z ∈ Rd related to G and P is defined as

Finally, the ensemble representation g is the weighted sum of the M pattern representations as follows.

Definition 4.3 (Ensemble Representation). Given a set of patterns {P1, P2, . . . , Pm, . . . , PM} and a graph G, the pattern sampling set S (m) and the pattern representation z(m) are related to the m-th pattern Pm. The representation learning function F(·, ·;W(m) ) is used to learn z(m) from S (m) . Let λ = [λ1, λ2, . . . , λm, . . . , λM]⊤ be a positive weight parameter vector, then the ensemble representation g ∈ Rd of graph G is defined as

The weight parameter vector λ is constrained by 1⊤M λ = 1 and λ ≥ 0, and we can use the same softmax trick in computing the ensemble kernel (3) to remove this constraint.

Let W := {W(1) ,W(2) , . . . ,W(m) , . . . ,W(M) } denote the trainable parameters of the GNN framework. To obtain the GNN parameters and the weight parameter λ in ensemble representation learning (9), we define the supervised loss and unsupervised loss functions as follows.

Supervised Classification Loss. Given a graph G, let y = [y1, y2, . . . , yc, . . . , yC]⊤ ∈ {0, 1}C be the ground truth label and ˆ y = [ˆ y1, ˆ y2, . . . , ˆ yc, . . . , ˆ yC]⊤ ∈ RC be the predicted label. Let fc : Rd → RC be a classifier with softmax, i.e., ˆ y = fc(g), where the parameter is WC. Then the multi-class cross-entropy loss is defined as:

UnsupervisedKLDivergence. We use the same KL divergence defined in Eq. (5) as follows:

where LKL(K(λ,W)) is a Gaussian kernel matrix of graph representations and γ is a positive parameter.

Finally, let L(λ,W) be the supervised or unsupervised loss function when the graphs are labeled or unlabeled. The GNN parameters W and the weight parameters λ can be computed by solving

where λ∗ = [λ∗1 , . . . , λ∗m, . . . , λ∗M ]⊤ and λ∗m indicates the contribution of the pattern representation z(m) to the ensemble graph representation g. For convenience, we call this method pattern-based XGL with GNNs, abbreviated as PXGL-GNN.

5 Theoretical Analysis

In this section, we provide a theoretical analysis of our method, focusing on robustness, generality, and complexity. We provide all detailed proof in the supplementary materials.

5.1 Robustness Analysis

Following [O'Bray et al., 2021], a learning method should be robust to small perturbations. Let ∆A and ∆X be perturbations on the adjacency matrix and node attributes. The perturbed graph is ˜G = (A+∆A,X +∆X), of which the representation is denoted as ˜ g. We seek the upper bound of ∥˜ g - g∥. Assume the representation learning function F is an L-layer GCN [Kipf and Welling, 2016] with activation function σ(·) and average pooling as the output. For pattern Pm, F(A,X;W(m) ) has parameters W(m) = {W (m,1) , . . . ,W (m,L) }, where W (m,L) is the parameter in the l-th layer.

Theorem5.1. Let ˜ A=A+∆A and ˜X =X+∆X. Suppose ∥A∥2 ≤ βA, ∥X∥F ≤ βX, ∥W (m,l) ∥2 ≤ βW for all m ∈ [M] and l ∈ [L], and σ(·) is ρ-Lipschitz continuous. Let α be the minimum node degree, and ∆D := I -diag(1⊤(I +A+ ∆A)) 1 2 diag(1⊤A)- 12 . Then,

The bound reveals that the method is sensitive to the perturbation on the graph structure, i.e., A, when L is large. It is relatively insensitive to the perturbation on X. On the other hand, when α, the minimum node degree, is larger, the method is more robust.

5.2 Generalization Analysis

Following [Bousquet and Elisseeff, 2002; Feldman and Vondrak, 2019], we use uniform stability to derive the generalization bound for our model. Let λ and W be known parameters. The supervised loss ℓCE in Eq.(10) is guaranteed with a uniform stability parameter η. The empirical risk E[ℓCE(λ,W; G)] := 1N ∑Ni=1 ℓCE(λ,W;Gi) and true risk E[ℓCE(λ,W;G)] have a high-probability generalization bound: for constant c and δ ∈ (0, 1),

Let D := {G1, . . . ,GN} be the training data. By removing the i-th graph Gi, we get D\i = {G1, . . . , Gi-1, Gi+1, . . . , GN}. Let λD and WD := {WC,W (m,l) D , ∀m ∈ [M], l ∈ [L]} be the parameters trained on D. Let λD\i and WD\i := {WC\i ,W (m,l) D\i , ∀m ∈ [M], l ∈ [L]} be the parameters trained on D\i . We aim to find η such that

Theorem 5.2. Suppose

Suppose the fc in ℓCE (10) is a linear classifier, which is τLipschitz continuous. Suppose Thus the η for estimation error (13) and uniform stability (14) is:

Invoking (15) into (13), we obtain the generalization error bound of our model. We see that when α is larger and βA, βX are smaller, the generalization ability is stronger.

5.3 Time and Space Complexity

Given a dataset with N graphs (each has n nodes and e edges), we select M different patterns and sample Q subgraphs of each pattern. First, our PXGL-EGK requires computing M kernel matrices, of which the space complexity is O(MN 2 ), and the time complexity is related to those of different graph kernels. Assume ψm is the time complexity of the m-th kernel, the total time complexity of PXGL-EGK is O(N 2 ∑Mm=1 ψm). When N is large, the method has high time and space complexities.

Regarding PXGL-GNN, suppose each representation learning function Fm is an L-layer GCN, of which the width is linear with d. Let the batch size in the optimization be B for both supervised and unsupervised learning. In supervised learning, the space complexity and time complexity of supervised learning are O(BMQ(e + nd) + MLd2 + Cd) and O(BMQL(ed + nd2 )) respectively. In unsupervised learning, the space complexity and time complexity of supervised learning are O(BMQ(e + nd) + MLd2 + Cd + B2 ) and O(BMQL(ed + nd2 ) + B2 ) respectively. This method is scalable to large graph datasets because the complexities are linear with BMQ and B2 , where the B2 term, referring to Eq. (11), comes from computing the Gaussian kernel matrix between all pairs of examples in a batch.

6 RelatedWorks

Due to space limitations, we introduce previous works on explainable graph learning (XGL), graph representation learning (GCL), and graph kernels in the supplementary materials.

7 Experiments

We test our method on the TUdataset [Morris et al., 2020] for both supervised and unsupervised learning tasks, as shown in Table 1. Our goal is to learn explainable graph representations. We provide the weight parameter λ and visualize the ensemble representation g and the pattern representation z(m) . We use seven graph patterns: paths, trees, graphlets, cycles, cliques, wheels, and stars, sampling Q = 10 subgraphs for each. We select these patterns based on their discriminative power and computational feasibility. In practice, one could use a subset of these seven patterns and adjust the sampling cardinality Q based on domain knowledge or computational constraints. We use a 5-layer GCN for the representation learning function F and a 3-layer DNN with softmax for the classification function fc. Experiments are repeated ten times and the average value and standard deviation are reported. Due to the space limitation, the results of PXGL-EGK and other figures are shown in the supplementary materials.

7.1 Supervised Learning

We conduct supervised XGL via pattern analysis, the proposed PXGL-GNN, by solving optimization (12) with the classification loss (10). The dataset is split into 80% training, 10% validation, and 10% testing data. The learned weight parameter λ, indicating each pattern's contribution to graph representation learning, is reported in Table 2. We also visualize the graph representation g and three pattern representations z(m) of PROTEINS in Figure 4. Results show the paths pattern is most important for learning g, and the ensemble representation g outperforms single pattern representations z(m) , which reveal underlying structural characteristics and naturally align with domain knowledge since paths are crucial for reflecting protein folding pathways [Yan et al., 2011].

The compared baselines include classical GNNs like GIN [Xu et al., 2018], DiffPool [Ying et al., 2018], DGCNN [Zhang et al., 2018], GRAPHSAGE [Hamilton et al., 2017]; subgraph-based GNNs like SubGNN [Kriege and Mutzel, 2012], SAN [Zhao et al., 2018], SAGNN [Zeng et al., 2023]; and recent methods like S2GAE [Tan et al., 2023] and ICL [Zhao et al., 2024]. The accuracies in Table 3 show that our method performs the best.

7.2 Unsupervised Learning

We conduct unsupervised XGL via pattern analysis, the proposed PXGL-GNN, by solving optimization (12) with the KL

divergence loss (11). The learned weight parameter λ for XGL is reported in the supplementary materials. The visualizations of unsupervised XGL results are in the supplementary materials. Results show that the ensemble representation g outperforms single pattern representations z(m) .

For clustering performance, we use clustering accuracy (ACC) and Normalized Mutual Information (NMI). Baselines include four kernels: Randomwalk kernel (RW) [Borgwardt et al., 2005], Sub-tree kernels [Da San Martino et al., 2012], Graphlet kernels [Prˇzulj, 2007], Weisfeiler-Lehman (WL) kernels [Kriege and Mutzel, 2012]; and three unsupervised graph representation learning methods with Gaussian kernel in Eq. (11): InfoGraph [Sun et al., 2019], GCL [You et al., 2020], GraphACL [Luo et al., 2023]. The results are in Table 4 in our supplementary materials, and Table 5 reports the performance of PXGL-EGK. Our methods outperformed all benchmarks in almost all cases.

8 Conclusion

This paper investigates the explainability of graph representations through two novel approaches. First, we develop PXGL-EGK based on graph ensemble kernels that captures structural similarities while maintaining interpretability. Second, we introduce PXGL-GNN, a framework that incorporates diverse graph patterns (paths, trees, etc.) into GNNs to enhance both performance and explainability. We establish theoretical guarantees for our proposed methods, including robustness certification against perturbations and nonasymptotic generalization bounds. Extensive empirical evaluation demonstrates that our approaches not only achieve superior performance on classification and clustering tasks across multiple datasets, but also provide interpretable explanations for the learned graph representations.

Acknowledgements

This work was supported by the National Natural Science Foundation of China under Grant No.62376236, the Guangdong Provincial Key Laboratory of Mathematical Foundations for Artificial Intelligence (2023B1212010001), Shenzhen Science and Technology Program ZDSYS20230626091302006 (Shenzhen Key Lab of Multi-Modal Cognitive Computing), and Shenzhen Stability Science Program 2023.

Contribution Statement

Xudong Wang and Ziheng Sun contributed equally.