Kernel Lifting (Graph to Hypergraph)

Description

This is a novel lifting that utilizes kernels over graphs to infer the hyperedges. The kernels in the proposed method are in the following form: $$K(v_i, v_j) = C(K_v(v_i, v_j), K_x(x_i, x_j)),$$ where $K_v$ is a kernel over the nodes of the graph, $K_x$ is a kernel over the features of the graph (see kernel cookbook), and $C$ is a combining function (for instance, Hadamard product or sum). The resulting kernel defines a similarity measure over the graph, and we use this similarity to construct the hyperedges (it filters out the closest vertices by a threshold). Currently, we've implemented heat and Matérn graph kernels, but the method can also be used with custom kernels $$K = \exp(-Lt), \quad \quad K=\left(2 \nu / \kappa^2 I+L\right)^{-\nu},$$ where $L$ is the graph Laplacian, I is the identity matrix, and $\nu, \kappa$ and $t$ are hyperparameters. In the following figures, we show visualizations of continuous and graph kernels:

Kernel lifting is applicable to weighted undirected graphs and can use features, graph, or features and graph topology combined for lifting.

Examples:

1. In order to apply kernel lifting only to features, use $K_v = I$ (graph_kernel) and $C(K_1, K_2) = K_1 \odot K_2$, and $K_x$ (feat_kernel) a continuous kernel.

lifting = HypergraphKernelLifting(
    graph_kernel="identity", fraction=0.1, feat_kernel=lambda X: rbf_kernel(X, X), C="prod")

2. In order to apply kernel lifting using only graph topology, similarly to previous, use $K_x = I$ and $C(K_1, K_2) = K_1 \odot K_2$, and $K_v$ a graph kernel.

lifting = HypergraphKernelLifting(
    graph_kernel="heat", t=2, fraction=0.1, feat_kernel="identity", C="prod")

3. To mix vertex and graph kernel, setup separately $K_x$ and $K_v$, and setup a combination function $C(K_1, K_2) = K_1 \odot K_2$ or $C(K_1, K_2) = K_1 + K_2$.

lifting = HypergraphKernelLifting(
    graph_kernel="heat", t=2, fraction=0.1, feat_kernel=lambda X: rbf_kernel(X, X), C="sum")

References

[1] Kondor, R. I., & Lafferty, J. (2002, July). Diffusion kernels on graphs and other discrete structures. URL [2] Borovitskiy, V., Azangulov, I., Terenin, A., Mostowsky, P., Deisenroth, M., & Durrande, N. (2021, March). Matérn Gaussian processes on graphs. URL [3] Nikitin, A. V., John, S. T., Solin, A., & Kaski, S. (2022, May). Non-separable spatio-temporal graph kernels via SPDEs. URL [4] Schölkopf, B., & Smola, A. J. (2002). Learning with kernels: support vector machines, regularization, optimization, and beyond. MIT press. URL

From https://github.com/pyt-team/challenge-icml-2024/pull/30