Explainable Graph Representation Learning via Graph Pattern Analysis

AI summary

Overview

Research area: Explainable AI (XAI) applied to graph representation learning — specifically, a new "representation-level" form of explainable graph learning that asks what information a graph embedding actually encodes.

Technical level: Advanced. The paper assumes familiarity with graph kernels, graph neural networks (GCNs), contrastive and KL-divergence losses, and stability-based generalization theory.

Scope: The paper proposes two frameworks (PXGL-EGK and PXGL-GNN) that decompose a graph representation into a weighted sum of pattern-specific representations, where the learned weights reveal the importance of each graph pattern.

What This Paper Is About

Prior explainable graph learning work operates at the model level (explaining a GNN's behavior) or the instance level (explaining a single prediction). This paper examines a different, largely unexplored question: given a graph encoded as a vector, what specific structural information about that graph is captured in the vector? The authors answer this by grouping a graph's substructures into recognizable families ("graph patterns" such as paths, trees, cycles, cliques) and learning how much each pattern family contributes to the overall representation.

Key Contributions

1. A new problem setting — representation-level explainable graph learning. Unlike model-level or instance-level XGL, this work targets understanding what graph information is embedded inside a graph-level representation vector.

2. Two concrete methods. A graph ensemble kernel approach (PXGL-EGK) that learns a weighted combination of pattern counting kernels, and a GNN-based approach (PXGL-GNN) that learns a representation for each pattern and combines them by a weighted sum whose weights indicate each pattern's contribution.

3. Theoretical analysis. The paper provides a robustness bound (sensitivity of the representation to perturbations of the adjacency matrix and node features) and a generalization bound derived via uniform stability, plus time and space complexity analyses for both methods.

4. Empirical validation on real graph datasets. Experiments on eight TUdataset benchmarks in both supervised and unsupervised settings, including visualization of learned pattern weights and pattern-level embeddings.

Main Findings

• Pattern importance varies systematically by dataset. In the supervised PXGL-GNN results (Table 2), the dominant pattern is PROTEINS: paths (0.550 ± 0.070); MUTAG: cycles (0.654 ± 0.085); DD: cliques (0.572 ± 0.073); NCI1: cliques (0.574 ± 0.075); COLLAB: paths (0.587 ± 0.065); IMDB-B: cliques (0.453 ± 0.054); REDDIT-B: stars (0.447 ± 0.006); REDDIT-M5K: stars (0.578 ± 0.033).

• Ensemble kernels outperform individual kernels, and the weights are interpretable. In the PXGL-EGK t-SNE visualization on PROTEINS, the learned weights were 0.7502 for the path kernel, 0.1707 for the tree kernel, and 0.07912 for the graphlet kernel, with the ensemble kernel performing better than any single kernel.

• The GNN variant produces comparable pattern attributions. On PROTEINS (supervised PXGL-GNN), the visualized pattern weights were 0.5504 (path), 0.0746 (tree), and 0.08103 (graphlet), showing that a small number of patterns carries most of the representation's information.

• Pattern counting vectors alone are insufficient. The authors identify four limitations of using raw pattern counts as representations: they ignore node features, they are high-dimensional, counting is time-consuming (and must be recomputed per graph), and they are fixed rather than learnable, so they cannot capture implicit information via message passing.

• Robustness depends on structure more than features. The derived bound shows the method is sensitive to adjacency-matrix perturbation when the GCN depth L is large, relatively insensitive to node-feature perturbation, and more robust when the minimum node degree α is larger.

• Generalization improves with larger minimum degree and smaller norms. From the uniform-stability bound, generalization ability is stronger when the minimum node degree is larger and when the bounds on the adjacency and feature norms (β_A, β_X) are smaller.

• Complexity is favorable for the GNN variant. PXGL-EGK has space complexity O(MN²) and time complexity O(N² Σψ_m), which is expensive for large N. PXGL-GNN's supervised space and time complexities are O(BMQ(e+nd)+MLd²+Cd) and O(BMQL(ed+nd²)) respectively, with extra B² terms in the unsupervised case, making it scalable because complexity is linear in BMQ.

• Baseline comparison results are only partially present in the available content. The comparison table is truncated; the visible portion reports GIN at 84.53 ± 2.38 on MUTAG, 73.38 ± 2.16 on PROTEINS, and 76.38 on DD. The full set of baseline numbers and the authors' own numbers in that table are not available in the provided text, so no complete comparison can be reported here.

Methodology in Plain English

The starting point is the graph kernel idea: represent a graph by counting how many times a given substructure pattern (a path of some length, a tree, a graphlet, etc.) appears inside it. The resulting count vector is interpretable but has the drawbacks listed above.

PXGL-EGK sidesteps these drawbacks at the kernel level. Instead of one pattern, the authors compute one kernel matrix per pattern and learn nonnegative weights that sum to one over these kernels, so that the combined kernel is a weighted sum. The weights serve as the explanation: large weight means that pattern is important for the dataset. If graphs are labeled, the weights are learned with a supervised contrastive (InfoNCE-style) loss; if unlabeled, with a KL-divergence loss against a sharpened target distribution. A softmax reparameterization removes the sum-to-one constraint.

PXGL-GNN fixes the limitations of counting directly. For each of M patterns, the method samples Q subgraphs belonging to that pattern from a graph (using the WL-test to avoid duplicates across overlapping patterns). Each subgraph passes through a shared pattern-specific representation function F — implemented as a GCN — and the resulting subgraph embeddings are averaged into a pattern representation z^(m). The graph's final representation g is a weighted sum of these M pattern representations, with the same kind of learnable weights λ. Training uses a cross-entropy loss in the supervised case or the KL divergence between Gaussian kernel matrices of representations in the unsupervised case.

To justify the design, the authors derive an upper bound on how much the representation changes when the adjacency matrix and node features are perturbed, and a generalization bound from uniform stability. They test on eight TUdataset benchmarks with seven patterns (paths, trees, graphlets, cycles, cliques, wheels, stars) and Q = 10 samples per pattern, using a 5-layer GCN for F and a 3-layer DNN with softmax as the classifier, repeating each experiment ten times and reporting mean and standard deviation.

Why This Matters

Impact on research. This work opens a distinct axis of explainability — representation-level rather than model- or prediction-level — and supplies both a theory-backed formulation and two implementable methods. It also offers a principled way to select graph kernels and their hyperparameters automatically, since a kernel's weight is learned rather than chosen by hand.

Real-world applications:

• Molecular chemistry and drug discovery: rings and cycles in molecules underpin molecular fingerprints, so knowing that a representation weights cycles heavily (as on MUTAG, λ = 0.654 ± 0.085) tells chemists the embedding is capturing chemically meaningful structure.
• Protein and biological network analysis: cliques characterize protein complexes in protein-protein interaction networks; the strong clique weight on DD (0.572 ± 0.073) reflects this.
• Social network community detection: cliques likewise signal community structure, relevant to the COLLAB and IMDB-B datasets.
• High-stakes decision domains more broadly: the paper frames interpretability as essential in transportation, healthcare, law, and finance, where trust in a model's internal encoding matters.

Industry relevance. Because the GNN variant scales linearly in batch size, pattern count, and sample count, it can be applied to large graph datasets — including the 5000-graph COLLAB and 4999-graph REDDIT-M5K benchmarks used here — making the explanation mechanism practical rather than purely theoretical.

Future Directions

• Extending beyond the seven selected patterns. The authors state that practitioners could use a subset of the seven patterns or vary the sampling cardinality Q based on domain knowledge or computational constraints; which patterns should be added for other domains is left open.
• Addressing structural sensitivity at depth. The robustness bound shows that sensitivity to adjacency perturbation grows with GCN depth L, motivating methods that remain stable in deep architectures.
• Scaling PXGL-EGK. Its O(MN²) space and O(N² Σψ_m) time complexity limits it to small datasets; overcoming this is an open engineering problem.
• Broadening empirical coverage. The paper compares against multiple baselines in supervised and unsupervised tasks, but the question of how pattern-level explanations transfer to settings beyond TUdataset benchmarks — large-scale, heterogeneous, or attributed industrial graphs — remains open.

Target Audience

This paper is best suited to researchers and graduate students working on explainable AI, graph representation learning, or graph kernels who want a principled account of what graph embeddings encode. It is also useful for practitioners in chemistry, bioinformatics, and social network analysis who need to justify which structural features their models rely on. Readers should be comfortable with GNN mechanics, kernel methods, and statistical learning theory; the theoretical sections in particular are not beginner-level.

Note: This is the full version of a paper published in the Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence (IJCAI-25), Main Track, pages 3426–3434.

Authors’ abstract

Explainable artificial intelligence (XAI) is an important area in the AI community, and interpretability is crucial for building robust and trustworthy AI models. While previous work has explored model-level and instance-level explainable graph learning, there has been limited investigation into explainable graph representation learning. In this paper, we focus on representation-level explainable graph learning and ask a fundamental question: What specific information about a graph is captured in graph representations? Our approach is inspired by graph kernels, which evaluate graph similarities by counting substructures within specific graph patterns. Although the pattern counting vector can serve as an explainable representation, it has limitations such as ignoring node features and being high-dimensional. To address these limitations, we introduce a framework (PXGL-GNN) for learning and explaining graph representations through graph pattern analysis. We start by sampling graph substructures of various patterns. Then, we learn the representations of these patterns and combine them using a weighted sum, where the weights indicate the importance of each graph pattern's contribution. We also provide theoretical analyses of our methods, including robustness and generalization. In our experiments, we show how to learn and explain graph representations for real-world data using pattern analysis. Additionally, we compare our method against multiple baselines in both supervised and unsupervised learning tasks to demonstrate its effectiveness.