Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Graph kernel
open-in-new
<p>In <a href="/facts/Structure_mining/wTYpHwGA">structure mining</a>, a graph kernel is a <a href="/facts/Positive-definite_kernel/Ws3zkxfl">kernel function</a> that computes an <a href="/facts/Inner_product_space/HoyjElEy">inner product</a> on <a href="/facts/Graph_(abstract_data_type)/b8qcddXa">graphs</a>. Graph kernels can be intuitively understood as functions measuring the similarity of pairs of graphs. They allow <a href="/facts/Kernel_trick/fYuURIPk">kernelized</a> learning algorithms such as <a href="/facts/Support_vector_machine/XobxpdBG">support vector machines</a> to work directly on graphs, without having to do <a href="/facts/Feature_extraction/BSMX5e8I">feature extraction</a> to transform them to fixed-length, real-valued <a href="/facts/Feature_vector/nzAhYxfu">feature vectors</a>. They find applications in <a href="/facts/Bioinformatics/D5x2L8ee">bioinformatics</a>, in <a href="/facts/Chemoinformatics/BwBkT11c">chemoinformatics</a> (as a type of <a href="/facts/Molecule_kernel/4rtTgF8d">molecule kernels</a>), and in <a href="/facts/Social_network_analysis/CsJIFjVw">social network analysis</a>. </p><p>Concepts of graph kernels have been around since the 1999, when D. Haussler introduced convolutional kernels on discrete structures. The term graph kernels was more officially coined in 2002 by R. I. Kondor and <a href="/facts/John_D._Lafferty/hfny3wX4">J. Lafferty</a> as kernels <i>on</i> graphs, i.e. similarity functions between the nodes of a single graph, with the <a href="/facts/World_Wide_Web/wvnTrWFq">World Wide Web</a> <a href="/facts/Hyperlink/LqNsa84e">hyperlink</a> graph as a suggested application. In 2003, Gärtner <i>et al.</i> and Kashima <i>et al.</i> defined kernels <i>between</i> graphs. In 2010, Vishwanathan <i>et al.</i> gave their unified framework. In 2018, Ghosh et al. described the history of graph kernels and their evolution over two decades. </p>