Hadamard Code Kernel

A similar framework to the neighborhood-hashing kernel and the Weisfeiler-Lehman kernel was introduced by Tetsuya Kataoka and Akihito Inokuchi in [KI16], known as Hadamard-code kernel. Given a collection of labeled graphs \(\mathbf{G}=[G]^{N}_{i=1}\) collect the set \(\Sigma\) of all distinct labels inside \(\mathbf{G}\). A \(2^{k}\)-th Hadamard code matrix \(H_{2^{k}}\) is defined as follows:

\[\begin{split}H_{2^{k+1}}= \begin{cases} \begin{pmatrix} 1 & 1\\ 1 & -1 \end{pmatrix},\text{ if }k = 0 \\\\ \begin{pmatrix} H_{2^{k}} & H_{2^{k}}\\ H_{2^{k}} & -H_{2^{k}} \end{pmatrix},\text{if } k > 0 \end{cases}\end{split}\]

Now by defining a Hadamard matrix \(\mathbb{H} = H_{2^{\lceil \log_{2}|\Sigma|\rceil}}\), then we initially label each node inside a graph:

\[l^{(0)}(v) = \mathtt{row}_{i}\mathbb{H},\text{ }\textbf{iff}\text{ }label(v) = \Sigma_{i}\]

Based on this initial labeling the following relabeling rule:

\[l^{(k+1)}(v) = l^{(k)}(v) + \sum_{u \in N(v)}l^{(k)}(u)\]

was used. \(N(v)\) is used to denote the neighborhood of a node \(v\). Following the above scheme, relabeling is applied iteratively for a fixed number of iterations, while each kernel matrix (calculated from a give base-kernel) between relabeled graphs is aggregated to a total one, through summation.

An example of the relabeling procedure of the Hadamard code kernel for a single graph.

The implementation of the hadamard code kernel framework can be found below. Note that use can use base_kernel to attach as a base kernel any kernel for labeled graphs.

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

The simple Hadamard code kernel, as proposed in [KI16].

Bibliography

KI16(1,2)

Tetsuya Kataoka and Akihiro Inokuchi. Hadamard code graph kernels for classifying graphs. In Proceedings of the 5th International Conference on Pattern Recognition Applications and Methods, 24–32. 2016.