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}\to \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,\dots ,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}}^{\prime }$ be the edge label histograms of two graphs $G,G^{\prime }$, respectively. The edge histogram kernel is then defined as the linear kernel between $\mathbf{f}$ and ${\mathbf{f}}^{\prime }$, that is

$$k(G,G^{\prime })=⟨\mathbf{f},{\mathbf{f}}^{\prime }⟩$$

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

EdgeHistogram([n_jobs, normalize, verbose, …])

Edge Histogram kernel as found in [SB15].