Source-linked AI summary
Subgraph Matching Kernels for Attributed Graphs
Nils Kriege, Petra Mutzel
TL;DR
Existing graph kernels often do not support attributed graphs, despite the importance of attribute-aware similarity for graph learning. This paper introduces polynomial-time subgraph matching kernels that score structure-preserving mappings using vertex and edge attribute kernels. The approach generalizes several known kernels and yields promising classification results, while runtime remains constrained for large subgraphs and datasets.
Problem
Existing graph kernels based on simple labels or common subgraphs often cannot support attributed graphs with continuous vertex and edge attributes.
Method
The method counts structure-preserving subgraph matchings up to a fixed size and scores mapped vertex and edge attributes with flexible kernel functions.
Results
The experiments show promising attributed-graph classification results, with CSM reaching the highest accuracy on ENZYME with attributes.
Takeaways & Limitations
Subgraph matching kernels are presented as a viable alternative for attributed graphs, especially on medium-sized graphs or sparse or restricted subgraphs.
Takeaways & Limitations
Practical performance requires restricting subgraph size, and improving runtime for large-scale datasets and large graphs remains future work.
Abstract
from arXiv · showhide
We propose graph kernels based on subgraph matchings, i.e. structure-preserving bijections between subgraphs. While recently proposed kernels based on common subgraphs (Wale et al., 2008; Shervashidze et al., 2009) in general can not be applied to attributed graphs, our approach allows to rate mappings of subgraphs by a flexible scoring scheme comparing vertex and edge attributes by kernels. We show that subgraph matching kernels generalize several known kernels. To compute the kernel we propose a graph-theoretical algorithm inspired by a classical relation between common subgraphs of two graphs and cliques in their product graph observed by Levi (1973). Encouraging experimental results on a classification task of real-world graphs are presented.
1. Introduction
Graph similarity is fundamental for applying machine learning to structured data, but attributed graphs require kernels that handle continuous vertex and edge attributes while remaining suitable for kernel methods. The paper addresses this with polynomial-time subgraph matching kernels and flexible attribute comparisons.
- Graph comparison supports machine learning on structured data, although exact problems such as maximum common subgraph are typically NP-hard.
- Kernel methods require similarity measures to be symmetric and positive semidefinite, while continuous attributes require tolerance for divergence.
- The proposed kernel counts subgraph matchings up to a fixed size, giving polynomial runtime instead of relying on a maximum common subgraph.
- The method compares vertex and edge attributes through a flexible scoring scheme and arbitrary kernel functions.
- Existing graph-kernel families include random-walk, graphlet, tree-pattern, and chemistry-specific approaches, with differing support for attributes and repeated vertices.
2. Preliminaries
The preliminaries formalize labeled or attributed undirected graphs, their subgraphs, paths, connectivity, and graph isomorphisms. Isomorphisms are bijections preserving both adjacency and label equivalence.
- A graph is represented as G = (V, E, l), with labels or attributes assigned to vertices and edges.
- A subgraph G′ ⊆ G uses vertex and edge subsets, while an induced subgraph contains exactly the edges among its selected vertices.
- A graph isomorphism is a bijection that preserves adjacencies and equivalent vertex and edge labels.
- An automorphism is an isomorphism from a graph to itself, and Aut(G) denotes the set of such automorphisms.
3. A Subgraph Matching Kernel
The subgraph matching kernel scores structure-preserving bijections between subgraphs, extending exact isomorphism-based kernels to attributed graphs. It is positive semidefinite, relates to several established kernels, and can be computed by enumerating cliques in a product graph, with polynomial runtime when subgraph size is bounded.
- Definition and construction: The subgraph matching kernel scores bijections between subgraphs using vertex and edge kernels, allowing flexible comparison of attributed graphs.Unlike exact common-subgraph approaches, mappings need not preserve attributes exactly.
- Definition and construction: The kernel is positive semidefinite, as established by Theorem 1 through an R-convolution construction over graph encodings.Graphs are encoded as vertex tuples and edge matrices, with permutations yielding valid encodings.
- Relation to the CSI kernel: The CSI kernel is a special case of the subgraph matching kernel, obtained by using exact compatibility scores for vertices and edges.These scores enforce the conditions of graph isomorphism.
- Relation to the subgraph kernel: The subgraph kernel and CSI kernel become equivalent when CSI mappings are weighted by the number of automorphisms of the matched subgraph.The correction factor is λ_csi(ϕ) = λ_s(G)|Aut(G)|.
- Relation to the pharmacophore kernel: The pharmacophore kernel is recovered by restricting matchings to three vertices and using feature and distance kernels on a complete graph representation.The factor of 6 accounts for the six permutations of each three-vertex matching.
- Computation and runtime: The computation maps common subgraph isomorphisms to cliques in the product graph, while restricting subgraph size to k yields worst-case runtime O(kn^(k+1)).The product graph contains compatible vertex pairs, and cliques correspond to CSIs.
4. Experimental Evaluation
The experiments compare subgraph matching kernels with several graph kernels on molecular and protein classification tasks, including attributed graphs. Results show strong attributed-graph performance, while runtime depends substantially on graph structure, sparsity, and subgraph size.
- Experimental setup: The evaluation compares SM and CSM with random-walk, tree-pattern, geometric-random-walk, shortest-path, Weisfeiler-Lehman, and pharmacophore kernels.All kernels were adapted to account for vertex and edge labels where applicable.
- Datasets: The experiments cover molecule and protein datasets, including MUTAG, PTC, and ENZYME, plus attributed ENZYME and molecular distance graphs.ENZYME contains 600 enzymes assigned to six EC top-level classes, with structural and sequential edge annotations.
- Classification results: Additional vertex annotations significantly improve classification, and CSM achieves the highest accuracy on ENZYME with attributes.WL and WLSP cannot be applied to ENZYME once attributes are included.
- Classification results: On molecular distance graphs, SM performs best in two of four cases and remains competitive on the other datasets, although differences are small.The pharmacophore extension to more than three points did not significantly increase accuracy on the tested instances.
- Runtime results: Explicit-mapping computation schemes outperform other approaches on simple-label graphs, while CSM is slower than FLRW and TP.For attributed ENZYME, shortest-path runtime becomes the slowest among four tested approaches, whereas other kernels benefit from vertex-kernel sparsity.
- Runtime results: TP required more than 24h to compute a molecular-distance Gram matrix, whereas SM was approximately five times faster than PH with Gaussian RBF distance kernels.CSM is significantly faster than SM on sparse graphs while maintaining comparable prediction accuracy.
5. Conclusion & Future Work
The paper proposes subgraph matching kernels for complex attributed graphs and reports promising classification results in cheminformatics and bioinformatics. The approach is practical for medium-sized graphs, sparse attribute kernels, or restricted small or connected subgraphs, while runtime improvements for large-scale settings remain future work.
- Conclusion: The proposed kernel handles complex graph structures without repeated vertices and supports attributed graphs without restriction.The conclusion identifies the method as a viable alternative to existing approaches for attributed graphs.
- Conclusion: The experiments show promising results for attributed graphs from chemistry and bioinformatics.
- Future work: Runtime improvements for large-scale datasets and large graphs remain future work.The approach already works well for medium-sized graphs, sparse vertex and edge kernels, or small or connected subgraphs.