Subgraph Matching Kernels for Attributed Graphs

By Nils M. Kriege, Petra Mutzel. 2012

319 citations recorded by the source corpus.

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 exible 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.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

Citations in the corpus

An End-to-End Deep Learning Architecture for Graph Classification (2018, background): “Common types of substructures include walks (Vishwanathan et al. 2010), subgraphs (Kriege and Mutzel 2012), paths (Borgwardt and Kriegel 2005), and subtrees (Shervashidze et al. 2011; Neumann et al. 2016).”
Propagation kernels: efficient graph kernels from propagated information (2014, background): “There are also more flexible but slower graph kernels such as the shortest path kernel (Borgwardt and Kriegel 2005) or the common subgraph matching kernel (Kriege and Mutzel 2012).”
Weisfeiler and Lehman Go Cellular: CW Networks (2021, methodology): “TUD Amongst the datasets from this benchmarking suite: the task in MUTAG is to recognise mutagenic molecular compounds for potentially marketable drug [45, 61]; the one in PTC is to recognise the chemical compounds according to carcinogenicity on rodents [39, 48]; PROTEINS is about to categorising p”
Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting (2020, methodology): “In particular, subgraph patterns have been used to define Graph Kernels (GKs) [83], [84], [85], [86], [87], with the most prominent being the graphlet kernel [84].”
An Aligned Subtree Kernel for Weighted Graphs (2015, background): “Another kernel related to ours is the subgraph matching kernel (Kriege & Mutzel, 2012).”
Glocalized Weisfeiler-Lehman Graph Kernels: Global-Local Feature Maps of Graphs (2017, methodology): “MUTAG is a data set consisting of mutagenetic aromatic and heteroaromatic nitro compounds [53], [54] with seven discrete node labels.”
Towards a practical k-dimensional Weisfeiler-Leman algorithm (2019, background): “Mutag is a dataset consisting of mutagenetic aromatic and heteroaromatic nitro compounds [11, 21] with seven discrete vertex labels.”
Link Prediction Based on Graph Neural Networks (2018, background): “Common of substructures include walks [54, 55], subgraphs [56, 57], paths [58], and subtrees [34, 59].”
RetGK: Graph Kernels based on Return Probabilities of Random Walks (2018, methodology): “We compare our graph kernels with many state-of-the-art graph classification algorithms: (i) the shortest path kernel (SP) [1], (ii) the Weisfeiler-Lehman subtree kernel (WL) [25], (iii) the graphlet count kernel (GK)[26], (iv) deep graph kernels (DGK) [31], (v) PATCHY-SAN convolutional neural netwo”
A Degeneracy Framework for Graph Similarity (2018, unknown): “…[G¨artner et al. , 2003; Vishwanathan et al. , 2010; Sugiyama and Borgwardt, 2015], subtrees [G¨artner et al. , 2003; Mah´e and Vert, 2009], cycles [Horv´ath et al. , 2004], shortest paths [Borgwardt and Kriegel, 2005], and small sub-graphs [Shervashidze et al. , 2009; Kriege and Mutzel, 2012].”
A survey on graph kernels (2019, methodology): “79 + + – – [124, 34] NCI1 4110 2 29.”
Weisfeiler and Leman go sparse: Towards scalable higher-order graph embeddings (2019, unknown): “tworkofanactororactress.Thevertices areunlabeledandeachdatasetisdividedintotwo(three)classescorrespondingto moviesgenres. Mutag isadatasetconsistingofmutageneticaromaticandheteroaromaticnitrocompounds[11,21]withsevendiscretevertexlabels. NCI1andNCI109 are(balanced)subsetsofdatasetsmadeavailablebythe”
Graph Invariant Kernels (2015, background): “Kriege and Mutzel (2012) propose graph kernels in which subgraphs are matched with a score which computed as the product between a weight function and the kernels on vertex and edge attributes.”
Tree-Based Kernel for Graphs With Continuous Attributes (2015, background): “The proposed ODDCL ST kernel performs better than GH, SP, CSM and P2K, while its approximated version is below SP in terms of accuracy but still performs better than P2K, GH and CSM. Note however that the computational requirements of SP are prohibitive on this dataset, as it will be detailed later ”