Edge Histogram Kernel¶
The edge histogram kernel is a basic linear kernel on edge label histograms. The kernel assumes edge-labeled graphs. Let \(\mathcal{G}\) be a collection of graphs, and assume that each of their edges comes from an abstract edge space \(\mathcal{E}\). Given a set of node labels \(\mathcal{L}\), \(\ell : \mathcal{E} \rightarrow \mathcal{L}\) is a function that assigns labels to the edges of the graphs. Assume that there are \(d\) labels in total, that is \(d = |\mathcal{L}|\). Then, the edge 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,u) \in E : \ell(v,u) = i \}|\) for each \(i \in \mathcal{L}\). Let \(\mathbf{f}, \mathbf{f}'\) be the edge label histograms of two graphs \(G, G'\), respectively. The edge histogram kernel is then defined as the linear kernel between \(\mathbf{f}\) and \(\mathbf{f}'\), that is
The complexity of the edge histogram kernel is linear in the number of edges of the graphs.
An implementation of that kernel can be found below
|
Edge Histogram kernel as found in [SB15]. |