The original NodeSketch approach does not consider interpretability but it is essentially a sampling based approach. It works by recursively sketching the neighborhood at each node until recursion depth \(k\)  is reached. It builds upon an algorithm for min-max similarity estimation [1]}. The approach is conceptually similar to our \(L_p\)  sampling algorithm but no theoretical guarantee for the quality of the returned samples can be provided. To understand the main difference, the main goal of COLOGNE is to detect a node that satisfies a predefined sampling condition. The sampling condition is the key to showing the stated sampling probability and the similarity function that pairs of sampled nodes approximate. NodeSketch assigns first random weights to nodes using the Ioffe algorithm, similarly to what we do in \(L_1\)  and \(L_2\)  sampling. In the \(i\) -th recursive call of NodeSketch for each node \(u\)  we collect samples from \(N(u)\)  and add up the corresponding weights in case two nodes appear more than once as samples in \(N(u)\) . For node \(u\)  we select the node with the smallest weight from \(N(u)\)  and this is the crucial difference to COLOGNE. Working with a single node is subject to random effects that could make the behavior of the algorithm difficult to explain. Consider the graph in Figure REF . There are many paths from node \(u\)  to node \(z\)  in \(N_2(u)\) . In the first iteration of NodeSketch it is very possible that most of \(u\) 's immediate neighbors, the yellow nodes \(v_1\)  to \(v_{12}\) , will sample a blue node as each \(v\)  is connected with several blue \(w\)  nodes, i.e., \(s_{v_i} = w_j\) . Thus, in the second iteration it is likely that \(u\)  ends up with a sample for \(u\)  different from \(z\) . In contrast, by keeping a sketch for \(L_1\)  and \(L_2\)  sampling COLOGNE will provably preserve the information that node \(z\)  is reachable from \(u\)  by many different paths. And we can control the importance we assign to sampling easily reachable nodes by weighting the items with \(r_i^{1/p}\) , \(r_i \in (0, 1]\)  such in \(L_2\)  sampling we are more likely to have \(s_u = z\) .
<FIGURE>