Neighborhood Subgraph Pairwise Distance Kernel¶
The neighborhood subgraph pairwise distance kernel extracts pairs of rooted subgraphs from each graph whose roots are located at a certain distance from each other, and which contain vertices up to a certain distance from the root [CDG10]. It then compares graphs based on these pairs of rooted subgraphs. To avoid isomorphism checking, graph invariants are employed to encode each rooted subgraph.
Let \(G=(V,E)\) be a graph. The distance between two vertices \(u,v \in V\), denoted \(D(u,v)\), is the length of the shortest path between them. The neighborhood of radius \(r\) of a vertex \(v\) is the set of vertices at a distance less than or equal to \(r\) from \(v\), that is \(\{ u \in V : D(u,v) \leq r\}\). Given a subset of vertices \(S \subseteq V\), let \(E(S)\) be the set of edges that have both end-points in \(S\). Then, the subgraph with vertex set \(S\) and edge set \(E(S)\) is known as the subgraph induced by \(S\). The neighborhood subgraph of radius \(r\) of vertex \(v\) is the subgraph induced by the neighborhood of radius \(r\) of \(v\) and is denoted by \(N_r^v\). Let also \(R_{r,d}(A_v,B_u,G)\) be a relation between two rooted graphs \(A_v\), \(B_u\) and a graph \(G=(V,E)\) that is true if and only if both \(A_v\) and \(B_u\) are in \(\{N_r^v : v \in V \}\), where we require \(A_v, B_u\) to be isomorphic to some \(N_r^v\) to verify the set inclusion, and that \(D(u,v) = d\). We denote with \(R^{-1}(G)\) the inverse relation that yields all the pairs of rooted graphs \(A_v\), \(B_u\) satisfying the above constraints. Hence, \(R^{-1}(G)\) selects all pairs of neighborhood graphs of radius \(r\) whose roots are at distance \(d\) in a given graph \(G\). The neighborhood subgraph pairwise distance kernel utilizes the following kernel
where \(\delta\) is \(1\) if its input subgraphs are isomorphic, and \(0\) otherwise. The above kernel counts the number of identical pairs of neighboring graphs of radius \(r\) at distance \(d\) between two graphs. Then, the neighborhood subgraph pairwise distance kernel is defined as
where \(\hat{k}_{r,d}\) is a normalized version of \(k_{r,d}\), that is
The above version ensures that relations of all orders are equally weighted regardless of the size of the induced part sets.
The neighborhood subgraph pairwise distance kernel includes an exact matching kernel over two graphs (ie the \(\delta\) kernel) which is equivalent to solving the graph isomorphism problem. Solving the graph isomorphism problem is not feasible. Therefore, the kernel produces an approximate solution to it instead. Given a subgraph \(G_S\) induced by the set of vertices \(S\), the kernel computes a graph invariant encoding for the subgraph via a label function \(\mathcal{L}^g : \mathcal{G} \rightarrow \Sigma^*\), where \(\mathcal{G}\) is the set of rooted graphs and \(\Sigma^*\) is the set of strings over a finite alphabet \(\Sigma\). The function \(\mathcal{L}^g\) makes use of two other label functions: (\(1\)) a function \(\mathcal{L}^n\) for vertices, and (\(2\)) a function \(\mathcal{L}^e\) for edges. The \(\mathcal{L}^n\) function assigns to vertex \(v\) the concatenation of the lexicographically sorted list of distance-distance from root-label triplets \(\langle D(v,u), D(v,h), \mathcal{L}(u) \rangle\) for all \(u \in S\), where \(h\) is the root of the subgraph and \(\mathcal{L}\) is a function that maps vertices/edges to their label symbol. Hence, the above function relabels each vertex with a string that encodes the initial label of the vertex, the vertex distance from all other labeled vertices, and the distance from the root vertex. The \(\mathcal{L}^e(u,v)\) function assigns to edge \((u,v)\) the label \(\langle \mathcal{L}^n(u)\), \(\mathcal{L}^n(v)\), \(\mathcal{L}((u,v)) \rangle\). The \(\mathcal{L}^e(u,v)\) function thus annotates each edge based on the new labels of its endpoints, and its initial label, if any. Finally, the function \(\mathcal{L}^g(G_S)\) assigns to the rooted graph induced by \(S\) the concatenation of the lexicographically sorted list of \(\mathcal{L}^e(u,v)\) for all \((u,v) \in E(S)\). The kernel then employs a hashing function from strings to natural numbers \(H : \Sigma^* \rightarrow \mathbb{N}\) to obtain a unique identifier for each subgraph. Hence, instead of testing pairs of subgraphs for isomorphism, the kernel just checks if the subgraphs share the same identifier.
The computational complexity of the neighborhood subgraph pairwise distance kernel is \(\mathcal{O}(|V| |S| |E(S)| \log |E(S)|)\) and is dominated by the repeated computation of the graph invariant for each vertex of the graph. Since this is a constant time procedure, for small values of \(d^*\) and \(r^*\), the complexity of the kernel is in practice linear in the size of the graph.
The implementation of the neighborhood subgraph pairwise distance kernel can be found below
The Neighborhood subgraph pairwise distance kernel. |