Our solution is based on the idea of mergeable sketches [1]}. Following the COLOGNE sampling template from Figure REF , we iteratively generate sketches at each node. The sketch collected in the \(i\) -th iteration will summarize the \(i\) -hop neighborhood of each node. In [2]} the authors use the Count-Sketch data structure [3]}. This would fit perfectly into the COLOGNE framework as CountSketch is a linear projections of the data. Namely, an input vector \(x \in \mathbb {R}^n\)  is projected onto an \(m\) -dimensional subspace, \(m \ll n\) , as \(Px\)  for \(P \in \mathbb {R}^{m\times n}\)  where the projection matrix \(P\)  is implicitly defined using advanced hash functions. This means that for two vectors \(x\)  and \(y\)  we have \(sketch(x + y) = sketch(x) + sketch(y)\)  and we can iteratively sketch the \(k\) -hop frequency vector from the local neighborhood of each node. The result will be identical to first computing the frequency vector and then sketching it. Unfortunately, we cannot use Count-Sketch because we cannot efficiently retrieve the heavy hitter from the sketch. In the setting in [2]} a single vector is being updated in a streaming fashion. Thus after preprocessing the stream we can afford to query the sketch for each vector index \(i \in [n]\)  as this wouldn't increase the asymptotic complexity of the algorithm. But in our case this would mean we need to know all nodes in the local neighborhood of each node. And even if we knew those nodes, we would need \(O(\sum _{i=0}^k nnz(A^i))\)  queries in total which is likely to be of order \(O(n^2)\) .
