SVM Theta Kernel

The SVM-\(\vartheta\) kernel is very related to the Lovász \(\vartheta\) kernel [JJDB14]. The Lovász \(\vartheta\) kernel suffers from high computational complexity, and the SVM-\(\vartheta\) kernel was developed as a more efficient alternative. Similar to the Lovász \(\vartheta\) kernel, this kernel also assumes unlabeled graphs.

Given a graph \(G=(V,E)\) such that \(|V| = n\), the Lovász number of \(G\) can be defined as

\[\vartheta(G) = \min_{\mathbf{K} \in L} \omega(\mathbf{K})\]

where \(\omega(\mathbf{K})\) is the one-class SVM given by

(1)\[\omega(\mathbf{K}) = \max_{\alpha_i > 0} 2\sum_{i=1}^{n} \alpha_i - \sum_{i=1}^{n} \sum_{j=1}^{n} \alpha_i \alpha_j \mathbf{K}_{ij}\]

and \(L\) is a set of positive semidefinite matrices defined as

\[L = \{ \mathbf{K} \in S_{n}^+ : \mathbf{K}_{ii} = 1, \mathbf{K}_{ij}=0 \: \forall (i,j) \not \in E \}\]

where \(S_{n}^+\) is the set of all \(n \times n\) positive semidefinite matrices.

The SVM-\(\vartheta\) kernel first computes the matrix \(\mathbf{K}_{LS}\) which is equal to

\[\mathbf{K}_{LS} = \frac{\mathbf{A}}{\rho} + \mathbf{I}\]

where \(\mathbf{A}\) is the adjacency matrix of \(G\), \(\mathbf{I}\) is the \(n \times n\) identity matrix, and \(\rho \geq -\lambda_n\) with \(\lambda_n\) the minimum eigenvalue of \(\mathbf{A}\). The matrix \(\mathbf{K}_{LS}\) is positive semidefinite by construction and it has been shown in [JMBD13] that

\[\omega(\mathbf{K}_{LS}) = \sum_{i=1}^n \alpha_i\]

where \(\alpha_i\) are the maximizers of Equation (1). Furthermore, it was shown that on certain families of graphs (e.g. Erdős–Rényi random graphs), \(\omega(\mathbf{K}_{LS})\) is with high probability a constant factor approximation to \(\vartheta(G)\).

Then, the SVM-\(\vartheta\) kernel is defined as follows

\[k_{SVM}(G, G') = \sum_{S \subseteq V} \sum_{S' \subseteq V'} \delta(|S|, |S'|) \frac{1}{Z_{|S|}} k \Big(\sum_{i \in S} \alpha_i, \sum_{j \in S'} \alpha_j \Big)\]

where \(Z_{|S|} = \binom{|V|}{|S|} \binom{|V'|}{|S|}\), \(\delta(|S|, |S'|)\) is a delta kernel (equal to \(1\) if \(|S|=|S'|\), and \(0\) otherwise), and \(k\) is a positive semi-definite kernel between real values (eg linear kernel, gaussian kernel).

The SVM-\(\vartheta\) kernel consists of three main steps: (\(1\)) constructing matrix \(\mathbf{K}_{LS}\) of \(G\) which takes \(\mathcal{O}(n^3)\) time (\(2\)) solving the one-class SVM problem in \(\mathcal{O}(n^2)\) time to obtain the \(\alpha_i\) values, and (\(3\)) computing the sum of the \(\alpha_i\) values for all subgraphs (ie subsets of vertices \(S \subseteq V\)) of each graph. Computing the above quantity for all \(2^n\) sets of vertices is not feasible in real-world scenarios.

To address the above issue, the SVM-\(\vartheta\) kernel employs sampling schemes. Given a graph \(G\), the kernel samples a specific number of subgraphs \(\mathfrak{S} \in 2^V\). Then, the SVM-\(\vartheta\) kernel is defined as follows

\[\hat{k}_{SVM}(G, G') = \sum_{S \subseteq \mathfrak{S}} \sum_{S' \subseteq \mathfrak{S}'} \delta(|S|, |S'|) \frac{1}{\hat{Z}_{|S|}} \Big(\sum_{i \in S} \alpha_i, \sum_{j \in S'} \alpha_j \Big)\]

where \(\hat{Z}_{|S|} = |\mathfrak{S}_{|S|}| |\mathfrak{S}'_{|S|}|\) and \(\mathfrak{S}_{|S|}\) denotes the subset of \(\mathfrak{S}\) consisting of all sets of cardinality \(|S|\), that is \(\mathfrak{S}_{|S|} = \{ B \in \mathfrak{S} : |B| = |S| \}\).

The time complexity of computing \(\hat{k}_{SVM}(G, G')\) is \(\mathcal{O}(n^3 + s^2 T(k) + sn)\) where \(T(k)\) is the complexity of computing the base kernel \(k\) and \(s = \max(|\mathfrak{S}|, |\mathfrak{S}'|)\). The first term represents the cost of computing \(\mathbf{K}_{LS}\) (dominated by the eigenvalue decomposition). The second term corresponds to the worst-case complexity of comparing the sums of the \(\alpha_i\) values. And finally, the third term is the cost of computing the sum of the \(\alpha_i\) values for the sampled subsets of vertices.

The implementation of the SVM-\(\vartheta\) kernel can be found below

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

Calculate the SVM theta kernel.

Bibliography

JMBD13

Vinay Jethava, Anders Martinsson, Chiranjib Bhattacharyya, and Devdatt Dubhashi. Lovász ϑ function, SVMs and Finding Dense Subgraphs. The Journal of Machine Learning Research, 14(1):3495–3536, 2013.

JJDB14

Fredrik Johansson, Vinay Jethava, Devdatt Dubhashi, and Chiranjib Bhattacharyya. Global graph kernels using geometric embeddings. In Proceedings of the 31st International Conference on Machine Learning, 694–702. 2014.