Lovasz Theta Kernel

The Lovász number \(\vartheta(G)\) of a graph \(G=(V,E)\) is a real number that is an upper bound on the Shannon capacity of the graph. It was introduced by László Lovász in \(1979\) [Lovasz79]. The Lovász number is intimately connected with the notion of orthonormal representations of graphs. An orthonormal representation of a graph \(G\) consists of a set of unit vectors \(U_G = \{ \mathbf{u}_i \in \mathbb{R}^d : || \mathbf{u}_i || = 1 \}_{i \in V}\) where each vertex \(i\) is assigned a unit vector \(\mathbf{u}_i\) such that \((i,j) \not \in E \implies \mathbf{u}_i^\top \mathbf{u}_j = 0\). Specifically, the Lovász number of a graph \(G\) is defined as

\[\vartheta(G) = \min_{\mathbf{c}, U_G} \max_{i \in V} \frac{1}{(\mathbf{c}^\top \mathbf{u}_i)^2}\]

where \(\mathbf{c} \in \mathbb{R}^d\) is a unit vector and \(U_G\) is an orthonormal representation of \(G\). Geometrically, \(\vartheta(G)\) is defined by the smallest cone enclosing a valid orthonormal representation \(U_G\). The Lovász number \(\vartheta(G)\) of a graph \(G\) can be computed to arbitrary precision in polynomial time by solving a semidefinite program.

The Lovász \(\vartheta\) kernel utilizes the orthonormal representations associated with the Lovász number to compare graphs [JJDB14]. The kernel is applicable only to unlabeled graphs. Given a collection of graphs, it first generates orthonormal representations for the vertices of each graph by computing the Lovász \(\vartheta\) number. Hence, \(U_G\) is a set that contains the orthonormal representations of \(G\). Let \(S \subseteq V\) be a subset of the vertex set of \(G\). Then, the Lovász value of the set of vertices \(S\) is defined as

\[\vartheta_S(G) = \min_{\mathbf{c}} \max_{i \in S} \frac{1}{(\mathbf{c}^\top \mathbf{u}_i)^2}\]

where \(\mathbf{c} \in \mathbb{R}^d\) is a unit vector and \(\mathbf{u}_i\) is the representation of vertex \(i\) obtained by computing the Lovász number \(\vartheta(G)\) of \(G\). The Lovász value of a set of vertices \(S\) represents the angle of the smallest cone enclosing the set of orthonormal representations of these vertices (ie subset of \(U_G\) defined as \(\{ \mathbf{u}_i : \mathbf{u}_i \in U_G, i \in S \}\)).

The Lovász \(vartheta\) kernel between two graphs \(G, G'\) is then defined as follows:

\[k_{Lo}(G, G') = \sum_{S \subseteq V} \sum_{S' \subseteq V'} \delta(|S|, |S'|) \frac{1}{Z_{|S|}} k(\vartheta_S(G), \vartheta_{S'}(G'))\]

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 Lovász values (eg linear kernel, gaussian kernel).

The Lovász \(\vartheta\) kernel consists of two main steps: (\(1\)) computing the Lovász number \(\vartheta\) of each graph and obtaining the associated orthonormal representations, and (\(2\)) computing the Lovász value for all subgraphs (ie subsets of vertices \(S \subseteq V\)) of each graph. Exact computation of the Lovász \(\vartheta\) kernel is in most real settings infeasible since it requires computing the minimum enclosing cones of \(2^n\) sets of vertices.

When dealing with large graphs, it is thus necessary to resort to sampling. Given a graph \(G\), instead of evaluating the Lovász value on all \(2^n\) sets of vertices, the algorithm evaluates it in on a smaller number of subgraphs \(\mathfrak{S} \in 2^V\). Then, the Lovász \(\vartheta\) kernel is defined as follows

\[\hat{k}_{Lo}(G, G') = \sum_{S \subseteq \mathfrak{S}} \sum_{S' \subseteq \mathfrak{S}'} \delta(|S|, |S'|) \frac{1}{\hat{Z}_{|S|}} k(\vartheta_S(G), \vartheta_{S'}(G'))\]

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}_{Lo}(G, G')\) is \(\mathcal{O}(n^2 m \epsilon^{-1} + s^2 T(k) + sn)\) where \(T(k)\) is the complexity of computing the base kernel \(k\), \(n = |V|\), \(m = |E|\) and \(s = \max(|\mathfrak{S}|, |\mathfrak{S}'|)\). The first term represents the cost of solving the semi-definite program that computes the Lovász number \(\vartheta\). The second term corresponds to the worst-case complexity of computing the sum of the Lovász values. And finally, the third term is the cost of computing the Lovász values of the sampled subsets of vertices.

The implementation of the Lovász \(\vartheta\) kernel can be found below

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

Lovasz theta kernel as proposed in [JJDB14].

Bibliography

JJDB14(1,2)

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.

Lovasz79

László Lovász. On the shannon capacity of a graph. IEEE Transactions on Information Theory, 25(1):1–7, 1979.