Vertex Histogram Kernel¶
The vertex histogram kernel is a basic linear kernel on vertex label histograms. The kernel assumes node-labeled graphs. Let \(\mathcal{G}\) be a collection of graphs, and assume that each of their vertices comes from an abstract vertex space \(\mathcal{V}\). Given a set of node labels \(\mathcal{L}\), \(\ell : \mathcal{V} \rightarrow \mathcal{L}\) is a function that assigns labels to the vertices of the graphs. Assume that there are \(d\) labels in total, that is \(d = |\mathcal{L}|\). Then, the vertex label histogram of a graph \(G=(V,E)\) is a vector \(\mathbf{f} = (f_1, f_2, \ldots, f_d)\), such that \(f_i = |\{ v \in V : \ell(v) = i \}|\) for each \(i \in \mathcal{L}\). Let \(\mathbf{f}, \mathbf{f}'\) be the vertex label histograms of two graphs \(G, G'\), respectively. The vertex histogram kernel is then defined as the linear kernel between \(\mathbf{f}\) and \(\mathbf{f}'\), that is
The complexity of the vertex histogram kernel is linear in the number of vertices of the graphs.
An implementation of that kernel can be found below
|
Vertex Histogram kernel as found in [SB15]. |