Graph kernel: Difference between revisions

Revision as of 19:19, 22 April 2021

Latest revision as of 11:56, 31 July 2025

(8 intermediate revisions by 7 users not shown)

Line 1:

{{About|machine learning|the graph-theoretical notion|Glossary of graph theory}}

In [[structure mining]], a '''graph kernel''' is a [[Positive-definite kernel|kernel function]] that computes an [[inner product space|inner product]] on [[Graph (abstract data type)|graphs]].<ref name="Vishwanathan">{{cite journal|title=Graph kernels|author1=S.V. N. Vishwanathan|author2=Nicol N. Schraudolph|author3=Risi Kondor|author4=Karsten M. Borgwardt|author4-link=Karsten Borgwardt|journal=[[Journal of Machine Learning Research]]|volume=11|pages=1201–1242|year=2010|url=http://jmlr.csail.mit.edu/papers/volume11/vishwanathan10a/vishwanathan10a.pdf}}</ref>

Graph kernels can be intuitively understood as functions measuring the similarity of pairs of graphs. They allow [[Kernel trick|kernelized]] learning algorithms such as [[support vector machine]]s to work directly on graphs, without having to do [[feature extraction]] to transform them to fixed-length, real-valued [[feature vector]]s. They find applications in [[bioinformatics]], in [[chemoinformatics]] (as a type of [[molecule kernel]]s<ref name="Ralaivola2005">{{cite journal |author1=L. Ralaivola |author2=S. J. Swamidass |author3=H. Saigo |author4=P. Baldi |title=Graph kernels for chemical informatics |journal=Neural Networks |year=2005 |volume=18 |issue=8 |pages=1093–1110 |doi=10.1016/j.neunet.2005.07.009|pmid=16157471 }}</ref>), and in [[social network analysis]].<ref name="Vishwanathan"/>

Concepts of graph kernels have been around since the 1999, when D. Haussler<ref>{{Cite book|title=Convolution Kernels on Discrete Structures|last=Haussler|first=David|date=1999|citeseerx = 10.1.1.110.638}}</ref> introduced convolutional kernels on discrete structures. The term graph kernels was more officially coined in 2002 by R. I. Kondor and [[John D. Lafferty|J. Lafferty]]<ref>{{cite conference

|title=Diffusion Kernels on Graphs and Other Discrete Input Spaces

|author1=Risi Imre Kondor

Line 12:

|url=http://people.cs.uchicago.edu/~risi/papers/diffusion-kernels.pdf

}}</ref>

as kernels ''on'' graphs, i.e. similarity functions between the nodes of a single graph, with the [[World Wide Web]] [[hyperlink]] graph as a suggested application. In 2003, GaertnerGärtner ''et al.''<ref name="Gaertner">{{cite conference

|title=On graph kernels: Hardness results and efficient alternatives

|author1=Thomas GaertnerGärtner

|author2=Peter A. Flach

|author3=Stefan Wrobel

|conference=Proc. the 16th Annual Conference on Computational Learning Theory (COLT) and the 7th Kernel Workshop

Line 53:

An example of a kernel between graphs is the '''random walk kernel''',<ref name="Gaertner"/><ref name="Kashima"/> which conceptually performs [[random walk]]s on two graphs simultaneously, then counts the number of [[Path (graph theory)|path]]s that were produced by ''both'' walks. This is equivalent to doing random walks on the [[Tensor product of graphs|direct product]] of the pair of graphs, and from this, a kernel can be derived that can be efficiently computed.<ref name="Vishwanathan"/>

Another examples is the '''Weisfeiler-LehmanLeman graph kernel'''<ref>Shervashidze, Nino, et al. "Weisfeiler-lehman graph kernels." Journal of Machine Learning Research 12.9 (2011).</ref> which computes multiple rounds of the [[Weisfeiler-LehmanLeman algorithm]] and then computes the similarity of two graphs as the inner product of the histogram vectors of both graphs. In those histogram vectors the kernel collects the number of times a color occurs in the graph in every iteration. For two isomorphic graphs, the kernel returns a maximal similarity since the two feature vectors are identical.

Note that the Weisfeiler-LehmanLeman kernel in theory has an infinite dimension as the number of possible colors assigned by the Weisfeiler-LehmanLeman algorithm is infinite. By restricting to the colors that occur in both graphs, the computation is still feasible.

==See also==

Line 65:

[[Category:Graph algorithms]]

[[Category:Kernel methods for machine learning]]

{{comp-sci-stub}}

{{machine-learning-stub}}