PaperlayerView exact revision on arXiv

Source-linked AI summary

KerGNNs: Interpretable Graph Neural Networks with Graph Kernels

Aosong Feng, Chenyu You, Shiqiang Wang, Leandros Tassiulas

arXiv:2201.00491v2cs.LGcs.AI

TL;DR

MPNN aggregation is compared with the 1-WL algorithm’s multiset-based neighborhood updates, motivating methods that can distinguish structures beyond that framework. KerGNNs use graph-kernel-based subgraph aggregation, and the paper reports competitive performance across datasets alongside improved explainability and transparency.

Abstract

from arXiv · show

Graph kernels are historically the most widely-used technique for graph classification tasks. However, these methods suffer from limited performance because of the hand-crafted combinatorial features of graphs. In recent years, graph neural networks (GNNs) have become the state-of-the-art method in downstream graph-related tasks due to their superior performance. Most GNNs are based on Message Passing Neural Network (MPNN) frameworks. However, recent studies show that MPNNs can not exceed the power of the Weisfeiler-Lehman (WL) algorithm in graph isomorphism test. To address the limitations of existing graph kernel and GNN methods, in this paper, we propose a novel GNN framework, termed \textit{Kernel Graph Neural Networks} (KerGNNs), which integrates graph kernels into the message passing process of GNNs. Inspired by convolution filters in convolutional neural networks (CNNs), KerGNNs adopt trainable hidden graphs as graph filters which are combined with subgraphs to update node embeddings using graph kernels. In addition, we show that MPNNs can be viewed as special cases of KerGNNs. We apply KerGNNs to multiple graph-related tasks and use cross-validation to make fair comparisons with benchmarks. We show that our method achieves competitive performance compared with existing state-of-the-art methods, demonstrating the potential to increase the representation ability of GNNs. We also show that the trained graph filters in KerGNNs can reveal the local graph structures of the dataset, which significantly improves the model interpretability compared with conventional GNN models.

Related Work

Prior work extends GNN expressivity and combines kernels with neural networks in several ways, while KerGNNs are distinguished by applying graph kernels to local subgraphs and providing trained filters for interpretation.

Expressivity

  • Higher-order GNNs can exceed the 1-WL test but involve heavy computation; KerGNNs offer a different approach to breaking the 1-WL limit.Other approaches include mix-hop aggregation, port numbering, molecular coordinates, and graph homomorphism numbers, each with stated limitations.Source: Expressivity · p. 2

Combination of Graph Kernel and GNNs

  • Earlier kernel-neural combinations either place kernels and neural networks at different stages or derive kernels from GNN architectures.KerGNNs compare trainable hidden graphs with local subgraphs, unlike approaches using unstructured references or the entire graph.Source: Combination of Graph Kernel and GNNs · p. 2

Explainability

  • KerGNNs provide trained hidden graphs that encode structural characteristics common across a dataset, alongside visualizations of output graphs.The hidden graphs are produced without additional computations and may help interpret predictions.Source: Explainability · p. 3

Background: Graph Kernels

Graph kernels compare graphs through sums of pairwise base-kernel terms, including random-walk comparisons. The paper also describes direct-product and attribute-similarity formulations, plus a weighted variation.

Background: Graph Kernels

  • Graph kernels assess graph similarity by summing pairwise base-kernel terms, enabling classification and regression with graph-structured data.The paper focuses on positive-definite node-attribute kernels and uses the random-walk kernel in its model.Source: Background: Graph Kernels · p. 3
  • The P-step random-walk kernel compares walks up to length P, with p = 0 reducing to a node-pair kernel.The recurrence uses neighboring nodes and a coefficient λ; the graph-level value aggregates node-pair comparisons.Source: Background: Graph Kernels · p. 3
  • The direct product graph pairs vertices from two graphs and connects pairs when both component vertex pairs are adjacent.A walk on this product graph corresponds to simultaneous walks in the input graphs; powers of its adjacency matrix count common walks.Source: Background: Graph Kernels · p. 3
  • Node-attribute similarity for two graphs is encoded as S = X1X2^T, whose entries compare node pairs; flattening S gives the vector s.The random-walk kernel calculation incorporates this pairwise similarity.Source: Background: Graph Kernels · p. 3
  • A deep random-walk-kernel variation assigns trainable weights to its base-kernel terms.The weight w(v,v′) is associated with a base-kernel term.Source: Background: Graph Kernels · p. 3

Proposed Model

KerGNN updates node representations by comparing centered subgraphs with trainable graph filters through graph kernels. Its subgraph-based aggregation is analyzed for expressivity, connections to CNNs and MPNNs, and computational cost.

Proposed Model

  • The proposed-model section introduces the framework, develops subgraph-based aggregation, and examines its expressivity, CNN and MPNN connections, and complexity.Source: Proposed Model · p. 3

KerGNN Framework

Expressivity of Subgraph-based Aggregation

  • With injective updates, aggregation, and readout, subgraph-based GNNs distinguish every graph pair separated by 1-WL and can separate some 1-WL-equivalent pairs.The random-walk feature map is injective with respect to the multiset of contained node attributes, and KerGNN uses the kernel trick to work with subgraph feature maps.Source: Expressivity of Subgraph-based… · p. 5

Connections to CNNs

  • KerGNN extends CNNs to graphs by treating subgraphs and topology-aware graph filters as counterparts of image patches and filters, using graph kernels.Under suitable assumptions, 2-D convolution can also be viewed through kernel functions between image patches and filters.Source: Connections to CNNs · pp. 5–6

Connections to Existing GNNs

  • MPNNs are special cases of KerGNNs with one-node graph filters and suitable kernels; multiple-node filters with learnable adjacency matrices generalize most MPNN structures.Source: Connections to Existing GNNs · p. 6

Time Complexity Analysis

  • KerGNN complexity ranges from O(n^2) to O(n^3) for fully connected graphs; experiments report runtime at least as good as the fastest benchmark and lower than higher-order GNNs.Source: Time Complexity Analysis · p. 6

Experiments

Experiments compare KerGNNs with GNNs and graph kernels on graph classification, and visualize learned filters and node attributes to examine model behavior. Results report competitive benchmark performance and dataset-specific structures in learned filters and output graphs.

Experiments

  • Evaluation covers eight graph-classification datasets, using 10-fold cross-validation with an inner 90%/10% training-validation split and comparisons against GNN and graph-kernel baselines.The datasets span biological, chemical, and social graphs; input node features vary by dataset group.Source: Datasets · p. 6, Setup · p. 6, Baseline Models · p. 6

Results

  • For larger graphs, deeper KerGNNs or deep random-walk kernels perform better; optimal filter parameters vary with dataset structures such as stars, rings, and chains.Single-layer KerGNN performs well on the smaller IMDB social datasets.Source: Results · pp. 6–7
  • KerGNNs outperform conventional 1-WL-limited GNNs and achieve performance similar to high-order GNNs with less running time.The table reports test classification accuracies as mean and standard deviation; OOR denotes time or GPU-memory limits.Source: Results · p. 6, Table 1 · p. 7

Model Interpretability

  • MUTAG is used for visualization but excluded from cross-validation because it contains too few graphs.Source: Model Interpretability · p. 7
  • In MUTAG output graphs, ring-junction carbons rank above carbons attached to atom groups, while atom-group atoms rank below ring carbons.Relative attribute values indicate node importance in the output graphs.Source: Model Interpretability · p. 7, Figure 2 · p. 7
  • Most MUTAG graph filters contain rings resembling input carbon rings, which kernels match against local input structures.Some filters contain small connected rings; filter rings need not have six nodes because their size is limited to eight.Source: Model Interpretability · p. 7

Conclusion

KerGNNs are presented as a graph-neural-network framework that is not restricted by the theoretical limits of message passing. The paper reports competitive performance across datasets and improved explainability through visualizing filters and output graphs.

Conclusion

  • KerGNNs are not restricted to the theoretical limits of message-passing aggregation.Source: Conclusion · p. 8
  • The framework extends CNN ideas to graphs from the viewpoint of kernel methods.Source: Conclusion · p. 8
  • KerGNNs achieve competitive performance across datasets and provide improved explainability and transparency through filter and output-graph visualization.Source: Conclusion · p. 8

Calculation of Random Walk Kernel

The passage derives an efficient calculation for the random-walk kernel in KerGNNs. It specifies the matrix transformations and identifies the graph filter and input graph used in the comparison.

Calculation of Random Walk Kernel

Proofs

The proofs establish that the stated graph-neural-network conditions yield embeddings that distinguish graphs separated by 1-WL, and give an example of distinguishing graphs that 1-WL cannot. A separate construction makes a kernel inner product injective with respect to a finite feature vector.

Proof of Theorem 1

  • If 1-WL distinguishes two graphs, the proof derives different graph embeddings by mapping equal neural node features to equal 1-WL labels and using injective readout.Source: Proof of Theorem 1 · pp. 10–11
  • A graph pair indistinguishable by 1-WL can be separated by subgraph-based aggregation when a suitable graph filter makes their random-walk-kernel embeddings differ.Source: Proof of Theorem 1 · p. 11

Proof of Lemma 2

  • For a finite feature vector with bounded entries, choosing powers of base 2c for Φ(H) makes its inner product injective with respect to Φ(Gv).Source: Proof of Lemma 2 · p. 11

Connections between KerGNNs and CNNs

The section interprets image convolution as a kernel operation between local patches and filters, then carries that pattern into graphs by comparing node subgraphs with graph filters.

Connections between KerGNNs and CNNs

Rethinking CNNs from the Kernel’s Perspective

  • Under suitable assumptions, image convolution can be approximated by kernel comparisons between input patches and trainable filters, with kernel values updating output features.The finite-dimensional approximation assumes the RBF kernel's infinite-dimensional RKHS can be represented by a span of trainable filters.Source: Rethinking CNNs from the Kernel’s… · pp. 11–12

Generalizing CNNs to KerGNNs

  • KerGNNs compare each node’s neighborhood subgraph with trainable graph filters and use the resulting kernel values as node features.Subgraphs and filters need not have the same size or topology, and subgraphs share filters across nodes.Source: Generalizing CNNs to KerGNNs · pp. 12–13

Connections between KerGNNs and MPNNs

The paper expresses standard MPNN aggregation within the KerGNN framework and identifies it as a special case using one-node graph filters.

Connections between KerGNNs and MPNNs

  • MPNN neighborhood aggregation can be represented with one-node graph filters, while KerGNNs generalize it using multi-node filters with learnable adjacency.The GCN vertex update is interpreted through a neighborhood subgraph and a node-wise kernel.Source: Connections between KerGNNs and MPNNs · p. 13

Model Implementation Details

Implementation uses bounded, uniformly sized subgraph matrices and consistent filter and kernel choices within a model.

Model Implementation Details

  • Node subgraphs are truncated at a maximum size, retaining nearer neighbors, and smaller subgraphs are zero-padded to a common matrix size.The construction starts from each node and its j-hop neighbors.Source: Model Implementation Details · p. 13
  • An optional first-layer linear mapping aligns input node-attribute dimensions with graph-filter attributes for kernel computation.Source: Model Implementation Details · p. 14
  • Filters within a layer share a node count, and each model uses one kernel type, although different kernel types could be mixed across filters.Source: Model Implementation Details · p. 14

Experiment Details and More Results

Experiments assess graph and node classification, parameter sensitivity, and runtime; KerGNNs compare favorably with high-order GNNs in runtime and with conventional GNNs in performance.

Graph Classification Task

  • Graph classification experiments cover five bioinformatics and four social datasets, with hyperparameters selected by grid search during cross-validation.Source: Details of Datasets · p. 14, Hyper-parameter Search · p. 14, Table 2 · p. 14
  • Optimal graph-filter size varies by dataset, longer random walks generally help except on ENZYMES, and larger subgraphs improve DD and ENZYMES accuracy.Other datasets are less affected by subgraph size; mismatch between subgraph and filter sizes can degrade performance.Source: Model Parameters · p. 14, Figure 4 · p. 15
  • KerGNNs run much faster than high-order GNN benchmarks and achieve similar performance to conventional GNNs with 1-WL constraints.Runtime is measured per epoch, averaged over 50 epochs, using the same GPU card.Source: Model Running Time · pp. 14–15, Table 3 · p. 15

Node Classification Task

  • KerGNNs achieve similar or better results than state-of-the-art baselines on Cora, Citeseer, Pubmed, and Chameleon node classification.The comparison reports mean test accuracy across 10 random splits.Source: Node Classification Task · p. 15

More Visualizations

Trained KerGNN graph filters show dataset-specific patterns: MUTAG filters tend toward rings and circles, while REDDIT filters tend toward stars.

More Visualizations

Related papers

Loading 2201.00491v2…