#  LoNe Sampler : Graph node embeddings by coordinated local neighborhood
sampling

Konstantin Kutzkov
<EMAIL_ADDRESS>
###### Abstract

Local graph neighborhood sampling is a fundamental computational problem that
is at the heart of algorithms for node representation learning. Several works
have presented algorithms for learning discrete node embeddings where graph
nodes are represented by discrete features such as attributes of neighborhood
nodes. Discrete embeddings offer several advantages compared to continuous
word2vec-like node embeddings: ease of computation, scalability, and
interpretability. We present LoNe Sampler , a suite of algorithms for
generating discrete node embeddings by Local Neighborhood Sampling, and
address two shortcomings of previous work. First, our algorithms have
rigorously understood theoretical properties. Second, we show how to generate
approximate explicit vector maps that avoid the expensive computation of a
Gram matrix for the training of a kernel model. Experiments on benchmark
datasets confirm the theoretical findings and demonstrate the advantages of
the proposed methods.

##  1 Introduction

Graphs are ubiquitous representation for structured data. They model naturally
occurring relations between objects and, in a sense, generalize sequential
data to more complex dependencies. Many algorithms originally designed for
learning from sequential data are thus generalized to learning from graphs.
Learning continuous vector representations of graph nodes, or node embeddings,
have become an integral part of the graph learning toolbox, with applications
ranging from link prediction [9] to graph compression [2]. The first algorithm
[18] for learning node embeddings generates random walks, starting from each
node in the graph, and then feeds the sequences of visited nodes into a word
embedding learning algorithm such as word2vec [15]. The approach was extended
to a more general setting where random walks can consider different properties
of the local neighborhood [9, 26, 27]. An alternative method for training
continuous node embeddings is based on matrix factorization of (powers of) the
graph adjacency matrix.

As an alternative, researchers proposed to use coordinated node sampling for
training discrete node embeddings [28, 29]. In this setting, each sample is an
independent estimator of the similarity between nodes. (There are different
notions of node similarity but most reflect how easy it is to reach one node
from another.) Thus, sampled nodes themselves can be coordinates of the
embedding vectors. We can then compare two node embeddings by their Hamming
distance. There are several advantages of discrete embeddings over continuous
embeddings. First, we avoid the need to train a (possibly slow) word2vec-like
model. Second, the samples are the original graph nodes and contain all meta-
information provided in the original input, be it personal data of users of a
social network or the weather conditions at railway stations. By sampling, all
this information is preserved and this can lead to the design of interpretable
algorithms. And finally, the algorithms are truly local and can deal with
massive or distributed graphs if only access to the local neighborhood of each
node is possible.

The ultimate goal for node embeddings is to represent the structural roles of
nodes by fixed size vectors which reflect the similarity between nodes.
However, there are different notions of node similarity. As an example,
consider the toy graph in Figure 1. It seems that $u_{4}$ is similar to
$u_{3}$ because they are part of the same local clique. But on the the other
hand one can argue that $u_{1}$ is more similar to $u_{3}$ than $u_{4}$
because they are all directly connected to a hub node like $v_{2}$. The goal
of the present work is to design scalable embedding algorithms that can handle
different similarity objectives and have rigorously understood properties.

$u_{1}$$u_{2}$$u_{3}$$u_{4}$$v_{1}$$v_{2}$$v_{3}$$v_{4}$ Figure 1: Is $u_{2}$
or $u_{4}$ more similar to $u_{3}$?

The main contributions of the paper are as follows:

  * •

Theoretical insights. We formally define the problem of coordinated local node
sampling and present novel discrete embedding algorithms that, unlike previous
works based on heuristics, provably preserve the similarity between nodes with
respect to different objectives. Furthermore, the algorithms are highly
efficient.

  * •

Scalable model training. We show how to use the discrete embeddings in
scalable kernel models. More precisely, we design methods that approximate the
Hamming kernel by explicit feature maps such that we can train a linear
support-vector machine for node classification. Previous works require the
computation of a Gram matrix which is unfeasible for massive graphs.

#### Organization of the paper

In the next section we present notation and outline the problem setting. In
Section 3 we present three algorithms for local neighborhood sampling
according to different objectives. We analyze the computational complexity of
each approach and the properties of the generated samples. In Section 4 we
present an approach to the generation of explicit feature maps for the Hamming
kernel, thus enabling the use of discrete node embeddings in scalable kernel
models. We discuss related work in Section 5. An experimental evaluation is
presented in Section 6. The paper is concluded in Section 7.

##  2 Notation and overview of techniques

The input is a graph $G=(V,E)$ over $n=|V|$ nodes and $m=|E|$ edges. The
distance $d(u,v)$ between nodes $u$ and $v$ is the minimum number of edges
that need to be traversed in order to reach $u$ from $v$, i.e., the shortest
path from $u$ to $v$. We consider undirected graphs, thus $d(u,v)=d(v,u)$.
Also, we assume connected graphs, thus $d(u,v)<\infty$ for all $u,v\in V$.
These assumptions are however only for the ease of presentation, all
algorithms work for directed or disconnected graphs. The $k$-hop neighbors of
node $u$ is the set of nodes $N_{k}(u)=\\{v\in V:d(u,v)\leq k\\}$. The set of
neighbors of node $u$ is denoted as $N(u)$. We call the subgraph induced by
$N_{k}(u)$ the local $k$-hop neighborhood of $u$. A discrete embedding vector
is a fixed size vector whose entries come from a discrete set. For example, by
sampling with replacements $\ell$ nodes from the $k$-hop neighborhood of each
node we create embeddings that consists of other nodes. Or attributes of the
neighboring nodes, if existent.

We say $\tilde{q}$ is an $1\pm\varepsilon$-approximation of a quantity $q$ if
$(1-\varepsilon)q\leq\tilde{q}\leq(1+\varepsilon)q$.

Sketch based coordinated sampling. Our algorithms build upon sketching
techniques for massive data summarization. In a nutshell, sketching replaces a
vector ${\bf x}\in\mathbb{R}^{n}$ by a compact data structure
$sketch_{\bf{x}}\in\mathbb{R}^{d}$, $d\ll n$, that approximately preserves
many properties of the original $\bf{x}$. In coordinated sampling [7], given a
universe of elements $U$, and a set of sets $\\{S_{i}\subseteq U\\}$, the goal
is to draw samples from $U$ such that each set $S_{i}$ is represented by a
compact summary $sketch_{S_{i}}$. It should hold
$\texttt{sim}(sketch_{S_{i}},sketch_{S_{j}})\approx\texttt{sim}(S_{i},S_{j})$,
i.e., the summaries approximately preserve the similarity between the original
sets, for different similarity measures.

$L_{p}$ sampling. The $p$-norm of vector $x\in\mathbb{R}^{n}$ is
$\|x\|_{p}=(\sum_{i=1}^{n}|x_{i}|^{p})^{1/p}$ for $p\in\mathbb{N}\cup\\{0\\}$.
111The $0$-norm, the number of nonzero coordinates, is not a norm in the
strict mathematical sense but the notation has become standard. We call
$L_{p}$ sampling a sampling procedure that returns each coordinate $x_{i}$
from $x$ with probability $\frac{|x_{i}|^{p}}{\|x\|_{p}^{p}}$.

Work objective. Let $\mathbf{f}^{k}_{u}$ be the $k$-hop frequency vectors of
node $u$ such that $\mathbf{f}^{k}_{u}[z]$ is the number of unique paths of
length at most $k$ from $u$ to $z$. Let $s_{u}\in N_{k}(u)$ be the node
returned by an algorithm $\mathcal{A}$ as a sample for node $u$. We say that
$\mathcal{A}$ is a coordinated sampling algorithm with respect to a similarity
measure $\texttt{sim}:V\times V\rightarrow[0,1]$ iff

$\Pr[s_{u}=s_{v}]=\texttt{sim}(\mathbf{f}^{k}_{u},\mathbf{f}^{k}_{v})\text{
for }u,v\in V$

The goal of our work is the design of scalable algorithms for coordinated
$L_{p}$ sampling from local node neighborhoods with rigorously understood
properties. We can also phrase the problem in graph algebra terms. Let
$A\in\\{0,1\\}^{n\times n}$ be the adjacency matrix of the graph. The
objective is to implement coordinated $L_{p}$ sampling from each row of
$M_{k}=\sum_{i=0}^{k}A^{i}$ without explicitly generating the $A^{i}$. By
sketching the local $k$-hop neighborhood frequency vector $\mathbf{f}^{k}_{u}$
of each node $u$ we will design efficient $L_{p}$ sampling algorithms.

Algorithm 1 The overall structure of the coordinated local neighborhood
sampling approach.

0: Graph $G=(V,E)$

for each $u\in V$ do

Initialize $sketch_{u}$ with node $u$

for $i=1$ to $k$ do

for each $u\in V$ do

Update $sketch_{u}$ by merging all $sketch_{v}$ for $v\in N(u)$ into
$sketch_{u}$

for $u\in V$ do

Return a node from $sketch_{u}$ as a sample for $u$.

##  3 LoNe Sampler

The general form of our approach is in Figure 1. We first initialize a sketch
at each node $u$ with the node $u$ itself. For $k$ iterations, for each node
we collect the sketches from its neighbors and aggregate them into a single
sketch. At the end we sample from each node’s sketch. The algorithm is used to
generate a single coordinate of the embedding vector of each node. For each
coordinate we will use a different random seed.

Consider a trivial example. We initialize $sketch_{u}$ with a sparse
$n$-dimensional binary vector such that $sketch_{u}[u]=1$ is the only nonzero
coordinate for all $u\in V$. Merging the sketches is simply entrywise vector
addition. We can formally show that after $k$ iterations $sketch_{u}$ is
exactly the $k$-hop frequency vector of $u$, i.e.,
$sketch^{(k)}_{u}[v]=\mathbf{f}^{k}_{u}[v]$. We need to address the following
issues: i) Storing the entire frequency vectors $\mathbf{f}_{u}^{k}$ is very
inefficient. Even for smaller values of $k$, we are likely to end up with
dense $n$-dimensional sketches as most real graphs have a small diameter. ii)
How can we get coordinated samples from the different sketches?

### Coordinated uniform ($L_{0}$) sampling

We first present a simple coordinated sampling algorithm for generating
samples from the local neighborhood of each node. The approach builds upon
min-wise independent permutations [4], a technique for estimating the Jaccard
similarity between sets. Assume we are given two sets $A\subseteq U$ and
$B\subseteq U$, where $U$ is a universe of elements, for example all integers.
We want to estimate the fraction $\frac{|A\cap B|}{|A\cup B|}$. Let
$\pi:U\rightarrow U$ be a random permutation of the elements in $U$. With
probability $\frac{|A\cap B|}{|A\cup B|}$ the smallest element in $A\cup B$
with respect to the total order defined by $\pi$ is contained in $A\cap B$.
The indicator variable denoting whether the smallest elements in $\pi(A)$ and
$\pi(B)$ are identical is an unbiased estimator of the Jaccard similarity
$J(A,B)$. The mean of $t=O(\frac{1}{\alpha\varepsilon^{2}})$ such estimators
is an $1\pm\varepsilon$-approximation of $J(A,B)\geq\alpha$ with high
probability. (If $J(A,B)<\alpha$ then the additive error is bounded by
$\alpha\varepsilon$.)

An algorithm for sampling uniformly from the $k$-hop neighborhood of node $u$
easily follows, see Algorithm 2. We implement a random permutation on the $n$
nodes by generating a random number for each node
$r:V\rightarrow\\{0,1,\ldots,\ell-1\\}$. For a sufficiently large $\ell$ with
high probability $r$ is a bijective function and thus it implements a random
permutation222For $\ell=n^{2}/\delta$ with probability $1-\delta$ the function
is bijective.. For each node $u$, $sketch_{u}$ is initialized with $(r(u),u)$,
i.e., the sketch is just a single (random number, node) pair. The aggregation
after each iteration is storing the pair with the smallest random number from
$u$’s neighbors, $sketch_{u}=\min_{(r_{v},v):v\in N(u)}sketch_{v}$. After $k$
iterations at each node $u$ we have the smallest number from the set
$\\{r(v):v\in N_{k}(u)\\}$, i.e., we have sampled a node from $N_{k}(u)$
according to the permutation defined by the function $r$. The samples for any
two nodes $u$ and $w$ are coordinated as we work with the same permutation on
the set $N_{k}(u)\cup N_{k}(w)\subseteq V$. The next theorem is a
straightforward corollary from the main result on minwise-independent
permutations [4]:

###### Theorem 1

For all nodes $u\in V$, we can sample $s_{u}\in N_{k}(u)$ with probability
$1/|N_{k}(u)|$ in time $O(mk)$ and space $O(m)$. For any pair of nodes $u,v$
it holds

$\Pr[s_{u}=s_{v}]=\frac{|N_{k}(u)\cap N_{k}(v)|}{|N_{k}(u)\cup N_{k}(v)|}$

Proof: We show by induction that after $k$ iterations at each node $u$ we have
the node $v\in N_{k}(u)$ with the smallest random value $r(v)$. The statement
is clearly true for $k=0$. Assume that for each $v\in N(u)$ we have the
smallest value $r(w)$ for $w\in N_{k-1}(v)$. Let $\text{min}_{k}(u)$ be the
smallest node random value for the nodes in $N_{k}(u)$. Observe that
$N_{k}(u)=\bigcup_{v\in N(u)}N_{k-1}(v)$ and thus $\text{min}\\{r(w):w\in
N_{k}(u)\\}=\text{min}\\{\text{min}_{k-1}(v):v\in N(u)\\}$. The theorem then
easily follows from the main result from [4]. $\Box$

In terms of linear algebra, the above algorithm is an efficient implementation
of the following naïve approach: Let $A$ be the the adjacency matrix of $G$.
Randomly permute the columns of $M_{k}=\sum_{i=0}^{k}A^{i}$, and for each row
in the updated $M_{k}$ select the first nonzero coordinate. Thus, the
algorithm implements coordinated $L_{0}$ sampling from each row of $M_{k}$ but
avoids the explicit generation of $M_{k}$.

### Coordinated $L_{p}$ sampling

Algorithm 2 $L_{0}$ and $L_{1}$ sampling for single coordinate.

$L_{0}$ Sampling

0: Graph $G=(V,E)$, random function $r:V\rightarrow(0,1]$

for each $u\in V$ do

Initialize $sketch_{u}$ with $(r(u),u)$

for $i=1$ to $k$ do

for each $u\in V$ do

for each $v\in N(v)$ do

$sketch_{u}=\min(sketch_{u},sketch_{v})$

for $u\in V$ do

Return the node $z$ from the pair $sketch_{u}=(r(z),z)$

$L_{1}$ Sampling

0: Graph $G=(V,E)$, random function $r:V\rightarrow(0,1]$, int $\ell$

for each $u\in V$ do

Initialize $sketch_{u}$ with node, weight pair $(u,w(u)=1/r(u))$

for $i=1$ to $k$ do

for each $u\in V$ do

for each $v\in N(v)$ do

Update $sketch_{u}$ with $sketch_{v}$, keeping the top $\ell$ (node, weight)
pairs.

for $u\in V$ do

Return node $z$ from $sketch_{u}$ if $w(z)\geq\|\bf{f}^{k}_{u}\|_{1}$

The solution for uniform sampling is simple and elegant but it does not fully
consider the graph structure. It only considers if there is a path between two
nodes $u$ and $v$ but, unlike in random walks, not how many paths there are
between $u$ and $v$. We design coordinated sampling algorithms such that
easily accessible nodes are more likely to be sampled.

Let us present an approach to $L_{p}$ sampling from data streams for
$p\in(0,2]$ [13]. Let $\mathcal{S}$ be a data stream of pairs $i,w_{i}$ where
$i$ is the item and $w_{i}\in\mathbb{R}$ is the weight update for item $i$,
for $i\in[n]$. For example, the network traffic for a website where user $i$
spends $w_{i}$ seconds at the site. The objective is $L_{p}$ sampling from the
frequency vector of the stream, i.e., return each item $i$ with probability
roughly $|\mathbf{f}[i]|^{p}/\|\mathbf{f}\|^{p}_{p}$, where
$\mathbf{f}[i]=\sum_{(i,w_{i})\in\mathcal{S}}w_{i}$. (Items can occur multiple
times in the stream.) The problem has a simple solution if we can afford to
store the entire frequency vector $\mathbf{f}$. The solution in [13] is to
reweight each item by scaling it by a random number $1/r_{i}^{1/p}$ for a
uniform random $r_{i}\in(0,1]$. Let $z_{i}=\mathbf{f}[i]/r_{i}^{1/p}$ be the
new weight of item $i$. The crucial observation is that

$\Pr[z_{i}\geq\|\mathbf{f}\|_{p}]=\Pr[r_{i}\leq{\mathbf{f}[i]^{p}}/{\|\mathbf{f}\|_{p}^{p}}]=\frac{\mathbf{f}[i]^{p}}{\|\mathbf{f}\|_{p}^{p}}$

One can show that with constant probability there exists a unique item $i$
with $z_{i}\geq\|\mathbf{f}\|_{p}$. Thus, if we know the value of
$\|\mathbf{f}\|_{p}$, a space-efficient solution is to keep a sketch data
structure from which we can detect the heavy hitter that will be the sampled
item. Estimating the $p$-norm of a frequency vector for $p\in(0,2]$ is a
fundamental problem with known solutions [6].

There are two challenges we need to address when applying the above approach
to local graph neighborhood sampling. First, how do we get coordinated
samples? Second, if we explicitly generate all entries in the frequency vector
of the local neighborhood this would result in time complexity of
$O(\sum_{i=0}^{k}nnz(A^{i}))$, $nnz(A)$ denoting the number of non-zero
elements in the adjacency matrix $A$.

For the first issue, we achieve coordinated sampling by reweighting the nodes
$u\in V$ by $1/r_{u}$ for random numbers $r_{u}\in(0,1]$ for $u\in V$. An
inefficient solution works then as follows. For each node $u$ we generate a
random number $r_{u}\in(0,1]$, initialize $\mathbf{w}^{0}_{u}[u]=1/r_{u}$ and
set $\mathbf{w}^{0}_{u}[v]=0$ for all $v\neq u$. We iterate over the neighbor
nodes and update the vector
$\mathbf{w}^{k}_{u}=\mathbf{w}^{k-1}_{u}\oplus\sum_{v\in
N(u)}\mathbf{w}^{k-1}_{v}$ where $\oplus$ denotes entrywise vector addition.
We sample a node $v$ iff $\mathbf{w}_{u}[v]\geq\|\mathbf{f}^{k}_{u}\|_{1}$.
(Observe that $\|\mathbf{f}^{k}_{u}\|_{1}$ can be computed exactly by the same
iterative procedure.)

Our $L_{1}$ sampling solution in Algorithm 2 is based on the idea of mergeable
sketches [1] such for any vectors $x,y\in\mathbb{R}^{n}$ it holds
$sketch(x+y)=sketch(x)+sketch(y)$. Following the LoNe Sampler template from
Algorithm 1, we iteratively update the sketches at each node. The sketch
collected in the $i$-th iteration at node $u$ results from merging the
sketches in $N(u)$ at iteration $i-1$, and summarizes the $i$-hop neighborhood
$N_{i}(u)$. [13] use the CountSketch data structure [6]. But a CountSketch is
just an array of counters from which the frequency of an item can be
estimated. This wouldn’t allow us to efficiently retrieve the heavy hitter
from the sketch as we would need to query the sketch for all $k$-hop
neighborsof each node. (In the setting in [13] a single vector is being
updated in a streaming fashion. After preprocessing the stream we can afford
to query the sketch for each vector index as this wouldn’t increase the
asymptotic complexity of the algorithm.)

Here comes the main algorithmic novelty of our approach. Observing that in our
setting all weight updates are strictly positive, we design a solution by
using another kind of summarization algorithms for frequent items mining, the
so called counter based algorithms [14]. In this family of algorithms, the
sketch consists of an explicitly maintained list of frequent items candidates.
For a sufficiently large yet compact sketch a heavy hitter is guaranteed to be
in the sketch, thus the sampled node will be the heaviest node in the sketch.
The algorithm is very efficient as we only need to merge the compact sketches
at each node in each iteration.

The above described algorithm can be phrased again in terms of the adjacency
matrix $A$. Let $M_{k}=\sum_{i=0}^{k}A^{i}\cdot R^{-1}$ where
$R\in\mathbb{R}^{n\times n}$ is a diagonal matrix with diagonal entries
randomly selected from $(0,1]$. Then from the $i$-th row we return as sample
the index $j$ with the largest value $M_{i,j}$ for which the sampling
condition $M_{i,j}\geq\|A^{(k)}_{i,:}\|_{1}$ is satisfied. Sampling in this
way is coordinated because the $j$-th column of $A^{(k)}$ is multiplied by the
same random value $1/r_{j}$, thus a node $j$ with a small $r_{j}$ is more
likely to be sampled.

The formal proof for the next theorem is rather technical but at a high level
we show that with high probability we can efficiently detect a node that
satisfies the sampling condition using a sketch with $O(\log n)$ entries at
each node and can be provably detected by an efficient exact heavy hitter
mining algorithm.

###### Theorem 2

Let $G$ be a graph over $n$ nodes and $m$ edges, and let $\mathbf{f}^{k}_{u}$
be the frequency vector of the $k$-hop neighborhood of node $u\in V$. For all
$u\in V$, we can sample a node $s_{u}\in N_{k}(u)$ with probability
$\frac{\mathbf{f}^{k}_{u}[s_{u}]}{\|\mathbf{f}^{k}_{u}\|_{1}}$ in time
$O(mk\log n)$ and space $O(m+n\log n)$. For each pair of nodes $u,v\in V$

$\Pr[s_{u}=s_{v}]=\sum_{x\in
V}\min(\frac{\mathbf{f}^{k}_{u}[x]}{\|\mathbf{f}^{k}_{u}\|_{1}},\frac{\mathbf{f}^{k}_{v}[x]}{\|\mathbf{f}^{k}_{v}\|_{1}})$

Proof: We will show that with constant probability there exists exactly one
node $x\in N_{k}(u)$ that satisfies the sampling condition for node $u$, i.e.,
$\mathbf{w}^{k}_{u}[x]\geq t$ for $t=\|\mathbf{f}^{k}_{u}\|_{1}$ where
$\mathbf{w}_{u}^{k}$ is the reweighted frequency vector $\mathbf{f}_{u}^{k}$.
Denote this event by $\mathcal{E}_{1}$. Consider a fixed node $x\in N_{k}(u)$.
First, node $x$ is reweighted by $r_{x}\sim U(0,1)$, therefore the probability
that node $x$ satisfies the sampling condition is

$\Pr[\mathbf{f}^{k}_{u}[x]/r_{x}\geq
t]=\frac{\mathbf{f}^{k}_{u}[x]}{\|\mathbf{f}^{k}_{u}\|_{1}}$

For fixed $x\in N_{k}(u)$, let $\mathcal{E}^{u}_{x}$ be the event that $x$ is
the only node that satisfies the sampling condition and for all other nodes
$v\neq x$ it holds $\mathbf{w}^{k}_{u}[x]\leq t/2$. We lower bound the
probability for $\mathcal{E}^{u}_{x}$ as follows:

$\displaystyle\Pr[\mathcal{E}^{u}_{x}]=\frac{\mathbf{f}^{k}_{u}[x]}{\|\mathbf{f}^{k}_{u}\|_{1}}\prod_{v\in
N_{k}(u),v\neq x}(1-\frac{2\mathbf{f}^{k}_{u}[v]}{t})\geq$
$\displaystyle\frac{\mathbf{f}^{k}_{u}[x]}{\|\mathbf{f}^{k}_{u}\|_{1}}\prod_{v\in
N_{k}(u),v\neq x}\alpha(1-2/t)^{\mathbf{f}^{k}_{u}[v]}\geq\texttt{(for
$\alpha\in(0,1]$)}$
$\displaystyle\frac{\mathbf{f}^{k}_{u}[x]}{\|\mathbf{f}^{k}_{u}\|_{1}}\alpha(1-2/t)^{\|\mathbf{f}^{k}_{u}\|_{1}}=\frac{\mathbf{f}^{k}_{u}[x]}{\|\mathbf{f}^{k}_{u}\|_{1}}e^{-2\|\mathbf{f}^{k}_{u}\|_{1}/t}=$
$\displaystyle e^{-2}\frac{\mathbf{f}^{k}_{u}[x]}{\|\mathbf{f}^{k}_{u}\|_{1}}$

The first inequality follows by observing that $(1-k/n)^{n}\rightarrow e^{-k}$
and $(1-1/n)^{kn}\rightarrow e^{-k}$ for large $n$, and since both $1-k/n$ and
$1-1/n$ are in (0,1), for any fixed $n$ and $k<n$ there must exist a constant
$\alpha\in(0,1)$ such that $1-k/n\geq\alpha(1-1/n)^{k}$. The second inequality
holds because $a^{\sum_{v\in V:v\neq x}w_{v}}>a^{\sum_{v\in V}w_{v}}$ for
$a\in(0,1)$ and $w_{v}>0$.
For $\mathcal{E}_{1}$ we observe that the events $\mathcal{E}^{u}_{x}$, $x\in
N_{k}(u)$ are pairwise disjoint.

$\Pr[\mathcal{E}_{1}]=\sum_{x\in
N_{k}(u)}\Pr[\mathcal{E}^{u}_{x}]\geq\sum_{x\in
N_{k}(u)}\frac{\mathbf{f}^{k}_{u}[x]}{e^{2}\|\mathbf{f}^{k}_{u}\|_{1}}=\Omega(1)$

Next we show how to efficiently detect the unique element $x$ for which it
holds $\mathbf{f}^{k}_{u}[x]/r_{x}\geq\|\mathbf{f}^{k}_{u}\|_{1}$. With
probability at least $1-1/n$ it holds $r_{x}\in[1/n^{2},1]$ for all $x\in V$.
We obtain for the expected value of
$\mathbf{w}^{k}_{u}[x]=\mathbf{f}^{k}_{u}[x]/r_{x}$:

$\displaystyle\mathbb{E}[\mathbf{f}^{k}_{u}[x]/r_{x}]=O(\mathbf{f}^{k}_{u}[x]\int_{1}^{n^{2}}\frac{1}{t}dt)=O(\mathbf{f}^{k}_{u}[x]\log
n)$

By linearity of expectation
$\mathbb{E}[\|\mathbf{w}_{u}^{k}\|_{1}]={O}(\|\mathbf{f}^{k}_{u}\|\log n)$.
Since the random numbers $r_{x}$ are independent by Hoeffdings’s inequality we
obtain that $\|\mathbf{w}_{u}^{k}\|_{1}={O}(\|\mathbf{f}^{k}_{u}\|\log n)$
almost surely. Note that $\|\mathbf{w}_{u}^{k}\|_{1}$ can be computed exactly
at each node. Thus, we have shown that there exists a unique node $x$ with
weight $\|\mathbf{f}^{k}_{u}\|_{1}$ and the total weight of the nodes in
$N_{k}(u)$ is bounded by ${O}(\|\mathbf{f}^{k}_{u}\|_{1}\log n)$. Using a
deterministic frequent items mining algorithm like Frequent [14] we can detect
this unique heavy hitter using space $O(\log n)$. Since for all other nodes
$v\neq x$ it holds $\mathbf{w}^{k}_{u}[x]\leq\|\mathbf{f}^{k}_{u}\|_{1}/2$, by
the main result from [14] it follows that for a summary size of $>2\log n$ the
heavy hitter will be the only node whose weight in the summary will be at
least $\|\mathbf{f}^{k}_{u}\|_{1}/2$. Note that the summaries generated by
Frequent are mergeable [1], and can be merged in time proportional to the
number of elements stored in the summary. In each iteration we need to perform
exactly $m$ such summary merges, thus each iteration over all nodes takes
$O(m\log n)$ and needs space $O(n\log n)$

To complete the proof consider the probability that $x\in N_{k}(u)\cap
N_{k}(v)$ is sampled for both nodes $u$ and $v$, i.e., $s_{u}=s_{v}=x$. As
shown above, with probability $\Omega(1)$ we have generated samples for $u$
and $v$. Observe that $x=s_{u}$ if
$r_{x}\leq\mathbf{f}^{k}_{u}[x]/\|\mathbf{f}^{k}_{u}\|_{1}$, thus we have

$\displaystyle\Pr[x=s_{u}\wedge
x=s_{v}]=\Pr[\mathcal{E}_{x}^{u}\wedge\mathcal{E}_{x}^{v}]=$
$\displaystyle\Pr[r_{x}\leq\mathbf{f}^{k}_{u}[x]/\|\mathbf{f}^{k}_{u}\|_{1}\wedge
r_{x}\leq\mathbf{f}^{k}_{v}[x]/\|\mathbf{f}^{k}_{v}\|_{1}]=$
$\displaystyle\min(\frac{\mathbf{f}^{k}_{u}[x]}{\|\mathbf{f}^{k}_{u}\|_{1}},\frac{\mathbf{f}^{k}_{v}[x]}{\|\mathbf{f}^{k}_{v}\|_{1}})$

The $\mathcal{E}^{u}_{x}$ events are disjoint for $x\in N_{k}(u)$. Also, nodes
$x\notin N_{k}(u)\cap N_{k}(v)$ contribute 0 to the similarity as they are not
reachable by at least one of $u$ or $v$. Summing over $x\in N_{k}(u)\cap
N_{k}(v)$ completes the proof. $\Box$

For $L_{2}$ sampling we can apply the same approach as for $L_{1}$ sampling.
The only difference is that we need to reweight each node $u$ by
$1/r_{u}^{1/2}$ for $r_{u}\in(0,1]$ and compare the weight of the sample
candidate with $\|\mathbf{f}_{u}^{k}\|_{2}$. However, unlike
$\|\mathbf{f}_{u}^{k}\|_{1}$, we cannot compute exactly
$\|\mathbf{f}_{u}^{k}\|_{2}$ during the $k$ iterations. But we can efficiently
approximate the 2-norm of a vector revealed in a streaming fashion, this is a
fundamental computational problem for which algorithms with optimal complexity
have been designed [6]. We show the following result:

###### Theorem 3

Let $G$ be a graph over $n$ nodes and $m$ edges, and let $\mathbf{f}^{k}_{u}$
be the frequency vector of the $k$-hop neighborhood of node $u\in V$. For all
$u\in V$, we can sample a node $s_{u}\in N_{k}(u)$ with probability
$(1\pm\varepsilon)\frac{\mathbf{f}^{k}_{u}[s_{u}]^{2}}{\|\mathbf{f}^{k}_{u}\|_{2}^{2}}$
in time $O(mk(1/\varepsilon^{2}+\log n))$ and space
$O(m+n(1/\varepsilon^{2}+\log n))$, for a user-defined $\varepsilon\in(0,1)$.
For each pair of nodes $u,v\in V$

$\Pr[s_{u}=s_{v}]=(1\pm\varepsilon)\sum_{x\in
V}\min(\frac{\mathbf{f}^{k}_{u}[x]^{2}}{\|\mathbf{f}^{k}_{u}\|_{2}^{2}},\frac{\mathbf{f}^{k}_{v}[x]^{2}}{\|\mathbf{f}^{k}_{v}\|_{2}^{2}})$

Proof: The same proof as for $L_{1}$ sampling holds except for computing
exactly the norm $\|\mathbf{w}_{u}^{k}\|_{2}$. Instead we will estimate it
using CountSketch [6]. This is a linear data structure that maintains an array
with counters. The critical property of linear sketches is that for each node
it holds

$sketch(\sum_{v\in N_{k}(u)}\mathbf{f}_{v})=\sum_{v\in
N_{k}(u)}sketch(\mathbf{f}_{v})$

Using a sketch with $O(1/\varepsilon^{2})$ counters we obtain a
$1\pm\varepsilon$ approximation of $\|\mathbf{w}_{u}^{k}\|_{2}$ for a user-
defined $\varepsilon\in(0,1)$. Thus, we can recover the heavy hitters in the
local neighborhood of each node using the approach from the proof of Theorem
3. Observing that for any $\varepsilon\in(0,1)$ there exists a constant $c$
such that
$\frac{1}{1\pm\varepsilon}\in[1-c\cdot\varepsilon,1+c\cdot\varepsilon]$, we
obtain the stated bounds on the sampling probability. $\Box$

The similarity measures preserved in the above two theorems may appear non-
intuitive. Below we discuss that in a sense they approximate versions of the
well-known cosine similarity.

### Discussion

Let us provide some intuition for the similarity measures approximated by the
samples in Theorem 2 and Theorem 3. In $L_{0}$ sampling we treat all nodes in
the local neighborhood equally, while in $L_{1}$ sampling the sampling
probability is proportional to the probability that we reach a local neighbor
by a random walk. $L_{2}$ sampling is biased towards high-degree local
neighbors, i.e., if a node is reachable by many paths in the local
neighborhood then it is even more likely to be sampled.

The similarity function approximated by $L_{0}$ sampling is the Jaccard
similarity between node sets in the local neighborhood. But the similarity for
$L_{1}$ and $L_{2}$ sampling is less intuitive. Consider two vectors
$x,y\in\mathbb{R}^{n}$. It holds

$0\leq\sum_{i=1}^{n}\min(\frac{x[i]^{2}}{\|x\|_{2}^{2}},\frac{y[i]^{2}}{\|y|_{2}^{2}})\leq\sum_{i=1}^{n}\frac{x[i]^{2}}{2\|x\|_{2}^{2}}+\sum_{i=1}^{n}\frac{y[i]^{2}}{2\|y|_{2}^{2}}=1$

In particular, if two nodes share no nodes in their $k$-hop neighborhoods the
similarity is 0 and if they have identical frequency vectors the similarity is
1.

Also, for $a\geq 0,b\geq 0$ it holds $\min(a^{2},b^{2})\leq ab$, thus we have
that

$\sum_{i=1}^{n}\min(\frac{x[i]^{2}}{\|x\|_{2}^{2}},\frac{y[i]^{2}}{\|y|_{2}^{2}})\leq\sum_{i=1}^{n}\frac{x[i]y[i]}{\|x\|_{2}\|y\|_{2}}=\cos(x,y)$

On the other hand, assume that $\|x\|_{2}\leq\|y\|_{2}$ and for all $i$ it
holds $x[i]\leq y[i]\leq cx[i]$ for some $c>1$ and
$\frac{x[i]}{\|x\|_{2}}\leq\frac{y[i]}{\|y\|_{2}}$. Then

$\sum_{i=1}^{n}\min(\frac{x[i]^{2}}{\|x\|_{2}^{2}},\frac{y[i]^{2}}{\|y|_{2}^{2}})\geq\sum_{i=1}^{n}\frac{x[i]y[i]/c}{\|x\|_{2}\|y\|_{2}}=\cos(x,y)/c$

Thus, the measure in a sense approximates cosine similarity. And for $L_{1}$
sampling we obtain that the related measure is the so called sqrt-cosine
similarity [25]

$\text{sqrt-
cos}(x,y)=\sum_{i=1}^{n}\frac{x[i]y[i]}{\sqrt{\|x\|_{1}}\sqrt{\|y\|_{1}}}$

### Semi-streaming model of computation

The semi-streaming paradigm was introduced as a computational model for the
computation on massive graphs [8]. In this model, an algorithm is allowed to
use memory of the order $O(n\cdot\text{polylog}(n))$ but $o(m)$, i.e.
sublinear in the number of edges. The assumption is that the graph is stored
on an external device, or edges are generated on the fly, and the graph edges
can be accessed in a sequential manner. Observe that LoNe Sampler can be
implemented in $k$ passes over the edges where we will keep in memory only the
node sketches. Further, the edges can be provided in each pass in arbitrary
order, thus the approach works in the semi-streaming model of computation.

##  4 An explicit map for the Hamming kernel

A typical application for node embeddings is node classification. Previous
works [28, 29] have proposed to train a kernel machine with a Hamming kernel.
The Hamming kernel is defined as the overlap of vectors $x,y\in\mathbb{U}^{d}$
for a universe $\mathbb{U}$: $H(x,y)=\sum_{i=1}^{d}\mathbbm{1}(x_{i}=y_{i})$,
i.e. the number of positions at which $x$ and $y$ are identical. However, this
approach requires the explicit generation of a precomputed Gram matrix with
$t^{2}$ entries, where $t$ is the number of training examples.

A solution would be to represent the embeddings by sparse explicit vectors and
train a highly efficient linear SVM [12] model. For a universe size $N$, we
can represent each vector by a binary $Nd$-dimensional vector $b$ with exactly
$d$ nonzeros. But even a linear SVM would be unfeasible as we will likely end
up with dense decision vectors with $O(Nd)$ entries. We can use TensorSketch
[19], originally designed for the generation of explicit feature maps for the
polynomial kernel. Mapping the discrete vectors to lower dimensional sketches
with $O(1/\varepsilon^{2})$ entries would preserve the Hamming kernel with an
additive error of $\varepsilon d$. Observing that $d$ can be a rather small
constant, we present a simple algorithm that is more space-efficient than
TensorSketch for $d<1/\varepsilon$. The algorithm hashes each nonzero
coordinate of the explicit $Nd$-dimensional vector $b$ to a vector $f(b)$ with
$d/\varepsilon$ coordinates. If there is a collision, i.e., $f(b)[i]=f(b)[j]$
for $i\neq j$, we set $f(b)[i]=1$ without adding up $f(b)[i]$ and $f(b)[j]$ as
in TensorSketch. We show the following result:

###### Theorem 4

Let $\mathbb{U}$ be a discrete space and $x,y\in\mathbb{U}^{d}$ for
$d\in\mathbb{N}$. For any $\varepsilon\in(0,1]$ there is a mapping
$f:\mathbb{U}^{d}\rightarrow\\{0,1\\}^{D}$ such that $D=\lceil
d/\varepsilon\rceil$ and $H(x,y)=f(x)^{T}f(u)\pm\varepsilon d$ with
probability 2/3.

Proof: Let $N=|\mathbb{U}|$ be the dimensionality of the universe from which
the items in the explicit maps are drawn, e.g., the number of graph nodes. Let
further $m_{x},m_{y}\in\\{0,1\\}^{dn}$ be the naïve explicit feature maps of
$x$ and $y$. We hash each nonzero index in $[Nd]$ to a random index in
$[d\varepsilon]$. First observe that by construction each collision of
indices, i.e., $f(i)=f(j)$ for $i\neq j$, can lead to an additive error of
exactly one in the inner product $m_{x}^{T}m_{y}$. Indeed, we either miss a
nonzero coordinate on which $m_{x}$ and $m_{y}$ agree, or we artificially
create such a coordinate because of the collision. Since we don’t add up the
counters, we won’t introduce an error larger than 1 due to a collision.

Thus, we have to bound the number of such collisions. Fix a coordinate $i$.
Using that our hash function is uniform and that
$\Pr[f(j)=k|f(i)=k]=\Pr[f(j)=k]$, the probability that another fixed index $j$
maps to the same location, i.e. $f(i)=f(j)$, is $\varepsilon/d$. Given that
there are $d^{2}$ nonzero coordinate pairs in total, the expected number of
such collisions is bounded by $\varepsilon d$. Implementing the hash function
using tabulation hashing [5] and using a result from [20], the number of
collisions is concentrated around the expected value with high probability.
$\Box$

##  5 Related work

Random walk based embeddings. Pioneering approaches to learning word
embeddings, such as word2vec [15] and GloVe [17], have served as the basis for
graph representation learning. The main idea is that for each graph node $u$,
we learn how to predict $u$’s occurrence from its context [18]. In natural
language the context of each word is the set of surrounding words in a
sequence, and for graph nodes the context is the set of local neighbors, thus
random walks have been used to generate node sequences. Various algorithms
have been proposed that allow some flexibility in selecting local neighbors
according to different criteria [26, 9, 31, 27].

Matrix factorization. A branch of node embeddings algorithms work by
factorization of (powers of) the adjacency matrix of the graph [16, 30]. These
algorithms have well-understood properties but can be inefficient as even if
the adjacency matrix is usually sparse, its powers can be dense, e.g., the
average distance between any two users in the Facebook graph is only 4 [3].
The computational complexity is improved using advanced techniques from linear
algebra.

Deep learning. Node embeddings can be also learned using graph neural networks
[10]. GNNs are inductive and can be applied to previously unseen nodes, while
the above discussed approaches, including ours, are transductive and work only
for a fixed graph. This comes at the price of the typical deep learning
disadvantages such as slow training and the need for careful hyperparameter
tuning.

Coordinated local sampling. Approaches close to ours are NetHash [28] and
NodeSketch [29]. NetHash uses minwise hashing to produce embeddings for
attributed graphs. However, it builds individual rooted trees of depth $k$ for
each node and its complexity is $O(nt(m/n)^{k})$ where $t$ is the maximum
number of attributes per node. LoNe Sampler needs time $O(nt)$ to get the
attribute with the minimum value for each node and thus the total complexity
is $O(nt+mk)$. For $k>1$ this is asymptotically faster by a factor of
$t(m/n)^{k-1}$.

NodeSketch is a highly-efficient heuristic for coordinated sampling from local
neighborhoods. 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 [11]. NodeSketch assigns first random weights to nodes,
similarly to LoNe Sampler . In the $i$-th recursive call of NodeSketch for
each node $u$ we collect samples from $N(u)$. For node $u$, a single node from
$N(u)$ is selected and this is the crucial difference to LoNe Sampler .
Working with a single node for each iteration is prone to random effects, and
the theoretical guarantees from [11] hold only for sampling from the 1-hop
neighborhood. Consider the graph in Figure 2. There are many paths from node
$u$ to node $z$ in $N_{2}(u)$. In the first iteration of NodeSketch it is
likely that most of $u$’s immediate neighbors, the yellow nodes $v_{1}$ to
$v_{12}$, will sample a blue node as each $v_{i}$ is connected with many 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$. By keeping a sketch
LoNe Sampler provably preserves the information that node $z$ is reachable
from $u$ by many different paths. And we control the importance we assign to
sampling easily reachable nodes by reweighting the nodes by $r_{i}^{1/p}$.

$u$$v_{1}$$v_{12}$$z$$w_{1}$$w_{19}$ Figure 2: NodeSketch [29] might miss that
there are many length-2 paths from $u$ to $z$.

##  6 Experiments

Graph | Graph statistics |  Embedding time (in seconds)
---|---|---
| nodes | edges | classes | features | features per node | diameter | $|$ | Random walk | NodeSketch | $L_{0}$ |  $L_{1}$/$L_{2}$
Cora | 2.7K | 5.4K | 7 | 1.4K | 18.2 | 19 | $|$ | 2.1 | 2.7 | 1.5 | 25.7
Citeseer | 3.3K | 4.7K | 6 | 3.7K | 36.1 | 28 | $|$ | 3.3 | 3.8 | 2.3 | 30.4
PubMed | 19.7K | 44.3K | 3 | 500 | 50.5 | 18 | $|$ | 17.3 | 35.2 | 15.3 | 214.3
Deezer | 28.2K | 92.7K | 2 | 31K | 33.9 | 21 | $|$ | 37.0 | 62.5 | 33.4 | 344.4
LastFM | 7.6K | 27.8K | 18 | 7.8K | 195.3 | 15 | $|$ | 20.4 | 68.6 | 18.9 | 128.5
GitWebML | 37.7K | 289K | 2 | 4K | 18.3 | 7 | $|$ | 70.3 | 112.4 | 63.2 | 609.1
Table 1: Information on datasets and embedding generation time.

We evaluate LoNe Sampler on six publicly available graphs, summarized in Table
1. The first three datasets Cora, Citeseer, Pubmed [24] are citation networks
where nodes correspond to scientific papers and edges to citations. Each node
is assigned a unique class label describing the research topic, and nodes are
described by a list of key words. LastFM and Deezer represent the graphs of
the online social networks of music streaming sites LastFM Asia and Deezer
Europe [22]. The links represent follower relationships and the vertex
features are musicians liked by the users. The class labels in LastFM are the
users’ nationality, and for Deezer – the users’ gender. The GitWebML graph
represents a social network where node classes correspond to web or ML
developers who have starred at least 10 repositories and edges to mutual
follower relationships. Node features are location, starred repositories,
employer and e-mail address [23].

We sample node attributes by using the base sampling algorithm. For example,
for each keyword kw describing the citation network nodes we generate a random
number $r_{kw}$ and then at each node we sample keywords according to the
corresponding algorithm (e.g., we take the word with smallest $r_{kw}$ for
$L_{0}$ sampling, sample according to min-max sampling for NodeSketch [29],
etc.)

We compare LoNe Sampler against NodeSketch. Our $L_{0}$ sampling yields
identical results to NetHash but, as discussed, our algorithm is much more
efficient. Note that we don’t compare with continuous embeddings. Such a
comparison can be found in [29] but, as argued in the introduction, discrete
embeddings offer various advantages such as interpretability and scalability.

We generated $d=50$ samples from the $k$-hop neighborhood of each node for
$k\in\\{1,2,3,4\\}$, resulting in $50$-dimensional embeddings, using following
methods: i) A standard random walk (RW) of length $k$ that returns the last
visited node. ii) NodeSketch (NS) as described in [29]. iii) LoNe Sampler for
$L_{p}$ sampling for $p\in\\{0,1,2\\}$, using a sketch with 10 nodes for
$p\in\\{1,2\\}$.

#### Embedding generation time for varying embedding size

In Table 2 we show the embedding generation time for embedding vectors of
dimensionality 10, 25, and 50, for the slowest $L_{1}/L_{2}$ sampling. We
observe almost perfect time increase proportional to the embedding size.

| 10 | 25 | 50
---|---|---|---
Cora | 9.1 | 17.2 | 33
Citeseer | 10.1 | 20.6 | 40.8
Pubmed | 63.9 | 138.9 | 279.6
Deezer | 105 | 225.7 | 442.6
LastFM | 41.1 | 88.3 | 173.4
GitWebML | 202.4 | 429.1 | 852.3
Table 2: Embedding generation time for $L_{1}/L_{2}$ sampling. | kernel SVM | explicit map
---|---|---
Cora | 0.3 | 0.7
Citeseer | 0.5 | 1.2
Pubmed | 26.3 | 12.2
Deezer | 138 | 16.2
LastFM | 2.1 | 2.4
GitWebML | OOM | 15.9
Table 3: SVM training and inference time for NodeSketch (in seconds). | RandomWalk | NodeSketch | $L_{0}$ | $L_{1}$ | $L_{2}$
---|---|---|---|---|---
Cora | Accuracy |  0.454 $\pm$ 0.013 (hop 1) | 0.833 $\pm$ 0.016 (hop 1) |  0.824 $\pm$ 0.018 (hop 1) | 0.831 $\pm$ 0.018 (hop 1) |  0.829 $\pm$ 0.019 (hop 1)
Balanced accuracy |  0.393 $\pm$ 0.015 (hop 1) | 0.820 $\pm$ 0.020 (hop 1) |  0.808 $\pm$ 0.023 (hop 1) | 0.814 $\pm$ 0.023 (hop 1) |  0.812 $\pm$ 0.023 (hop 1)
Micro AUC |  0.811 $\pm$ 0.008 (hop 1) |  0.972 $\pm$ 0.006 (hop 1) |  0.970 $\pm$ 0.006 (hop 1) | 0.974 $\pm$ 0.005 (hop 1) | 0.973 $\pm$ 0.005 (hop 1)
Macro AUC |  0.786 $\pm$ 0.008 (hop 1) | 0.969 $\pm$ 0.006 (hop 1) |  0.967 $\pm$ 0.006 (hop 1) | 0.971 $\pm$ 0.005 (hop 1) | 0.969 $\pm$ 0.005 (hop 1)
Citeseer | Accuracy |  0.346 $\pm$ 0.016 (hop 1) |  0.706 $\pm$ 0.013 (hop 3) |  0.702 $\pm$ 0.017 (hop 2) |  0.711 $\pm$ 0.015 (hop 2) | 0.722 $\pm$ 0.015 (hop 2)
Balanced accuracy |  0.318 $\pm$ 0.013 (hop 1) |  0.672 $\pm$ 0.015 (hop 2) |  0.668 $\pm$ 0.019 (hop 2) | 0.676 $\pm$ 0.017 (hop 2) | 0.691 $\pm$ 0.016 (hop 2)
Micro AUC |  0.679 $\pm$ 0.010 (hop 2) |  0.906 $\pm$ 0.008 (hop 2) |  0.911 $\pm$ 0.009 (hop 1) | 0.915 $\pm$ 0.007 (hop 2) | 0.917 $\pm$ 0.007 (hop 2)
Macro AUC |  0.648 $\pm$ 0.012 (hop 1) |  0.891 $\pm$ 0.010 (hop 4) |  0.892 $\pm$ 0.008 (hop 2) | 0.898 $\pm$ 0.007 (hop 2) | 0.903 $\pm$ 0.007 (hop 2)
PubMed | Accuracy |  0.589 $\pm$ 0.008 (hop 2) |  0.798 $\pm$ 0.006 (hop 4) |  0.781 $\pm$ 0.005 (hop 1) | 0.818 $\pm$ 0.004 (hop 2) | 0.804 $\pm$ 0.007 (hop 4)
Balanced accuracy |  0.577 $\pm$ 0.007 (hop 2) |  0.785 $\pm$ 0.007 (hop 4) |  0.778 $\pm$ 0.004 (hop 1) | 0.809 $\pm$ 0.004 (hop 2) | 0.793 $\pm$ 0.006 (hop 2)
Micro AUC |  0.789 $\pm$ 0.004 (hop 2) |  0.927 $\pm$ 0.003 (hop 1) |  0.919 $\pm$ 0.002 (hop 1) | 0.938 $\pm$ 0.002 (hop 2) | 0.932 $\pm$ 0.002 (hop 2)
Macro AUC |  0.778 $\pm$ 0.004 (hop 2) |  0.924 $\pm$ 0.003 (hop 1) |  0.915 $\pm$ 0.002 (hop 1) | 0.935 $\pm$ 0.002 (hop 2) | 0.928 $\pm$ 0.002 (hop 2)
DeezerEurope | Accuracy |  0.540 $\pm$ 0.006 (hop 3) |  0.550 $\pm$ 0.007 (hop 1) |  0.554 $\pm$ 0.003 (hop 1) | 0.558 $\pm$ 0.008 (hop 2) | 0.565 $\pm$ 0.006 (hop 2)
Balanced accuracy |  0.518 $\pm$ 0.008 (hop 2) |  0.542 $\pm$ 0.006 (hop 1) |  0.545 $\pm$ 0.004 (hop 1) | 0.548 $\pm$ 0.005 (hop 1) | 0.556 $\pm$ 0.006 (hop 2)
Micro AUC |  0.571 $\pm$ 0.004 (hop 3) |  0.588 $\pm$ 0.005 (hop 1) | 0.589 $\pm$ 0.004 (hop 1) | 0.589 $\pm$ 0.006 (hop 2) | 0.594 $\pm$ 0.005 (hop 2)
Macro AUC |  0.529 $\pm$ 0.004 (hop 3) |  0.561 $\pm$ 0.005 (hop 1) |  0.564 $\pm$ 0.004 (hop 1) | 0.565 $\pm$ 0.006 (hop 2) | 0.577 $\pm$ 0.005 (hop 2)
LastFM | Accuracy |  0.424 $\pm$ 0.010 (hop 3) |  0.809 $\pm$ 0.008 (hop 4) |  0.725 $\pm$ 0.015 (hop 1) | 0.825 $\pm$ 0.008 (hop 4) | 0.818 $\pm$ 0.009 (hop 4)
Balanced accuracy |  0.294 $\pm$ 0.022 (hop 3) | 0.720 $\pm$ 0.021 (hop 4) |  0.62 $\pm$ 0.02 (hop 2) | 0.707 $\pm$ 0.025 (hop 3) |  0.695 $\pm$ 0.028 (hop 4)
Micro AUC |  0.877 $\pm$ 0.007 (hop 3) | 0.971 $\pm$ 0.003 (hop 2) |  0.966 $\pm$ 0.002 (hop 1) |  0.969 $\pm$ 0.003 (hop 1) | 0.970 $\pm$ 0.003 (hop 1)
Macro AUC |  0.768 $\pm$ 0.007 (hop 3) |  0.935 $\pm$ 0.003 (hop 1) |  0.924 $\pm$ 0.002 (hop 1) | 0.936 $\pm$ 0.003 (hop 1) | 0.939 $\pm$ 0.003 (hop 1)
GitWebML | Accuracy |  0.811 $\pm$ 0.004 (hop 1) |  0.823 $\pm$ 0.004 (hop 1) |  0.831 $\pm$ 0.003 (hop 1) | 0.835 $\pm$ 0.003 (hop 1) | 0.837 $\pm$ 0.003 (hop 1)
Balanced accuracy |  0.685 $\pm$ 0.005 (hop 1) |  0.751 $\pm$ 0.006 (hop 1) |  0.759 $\pm$ 0.006 (hop 1) | 0.764 $\pm$ 0.006 (hop 1) | 0.763 $\pm$ 0.006 (hop 1)
Micro AUC |  0.851 $\pm$ 0.003 (hop 1) |  0.899 $\pm$ 0.003 (hop 1) |  0.904 $\pm$ 0.002 (hop 1) | 0.908 $\pm$ 0.002 (hop 1) | 0.905 $\pm$ 0.002 (hop 1)
Macro AUC |  0.757 $\pm$ 0.003 (hop 1) |  0.848 $\pm$ 0.003 (hop 1) |  0.854 $\pm$ 0.002 (hop 1) | 0.862 $\pm$ 0.002 (hop 1) | 0.855 $\pm$ 0.002 (hop 1)
Table 4: The best result for each approach for the different hop depths. The overall best result is given in bold font, and the second best – in italics.  | RandomWalk | NodeSketch | $L_{0}$ | $L_{1}$ | $L_{2}$
---|---|---|---|---|---
Cora | Precision |  0.002 $\pm$ 0.01 (hop 3) |  0.014 $\pm$ 0.003 (hop 1) |  0.014 $\pm$ 0.004 (hop 1) |  0.016 $\pm$ 0.003 (hop 1) | 0.017 $\pm$ 0.003 (hop 1)
Recall |  0.037 $\pm$ 0.02 (hop 3) |  0.266 $\pm$ 0.057 (hop 1) |  0.271 $\pm$ 0.063 (hop 1) | 0.317 $\pm$ 0.045 (hop 1) | 0.334 $\pm$ 0.041 (hop 1)
Citeseer | Precision | $<0.001$ | 0.020 $\pm$ 0.003 (hop 2) |  0.017 $\pm$ 0.004 (hop 4) |  0.020 $\pm$ 0.003 (hop 2) | 0.021 $\pm$ 0.003 (hop 2)
Recall |  0.015 $\pm$ 0.02 (hop 1) | 0.453 $\pm$ 0.041 (hop 2) |  0.385 $\pm$ 0.055 (hop 2) |  0.452 $\pm$ 0.045 (hop 2) | 0.491 $\pm$ 0.066 (hop 2)
PubMed | Precision |  0.001 $\pm$ 0.001 (hop 1) |  0.001 $\pm$ 0.001 (hop 1) | 0.011 $\pm$ 0.003 (hop 1) | 0.025 $\pm$ 0.007 (hop 1) |  0.007 $\pm$ 0.003 (hop 1)
Recall |  0.002 $\pm$ 0.002 (hop 1) |  0.002 $\pm$ 0.002 (hop 1) | 0.025 $\pm$ 0.006 (hop 1) | 0.056 $\pm$ 0.015 (hop 1) |  0.016 $\pm$ 0.007 (hop 1)
DeezerEurope | Precision | $<0.001$ | $<0.001$ | $<0.001$ | $<0.001$ | $<0.001$
Recall | $<0.001$ | $<0.001$ | $<0.001$ | $<0.001$ | $<0.001$
LastFM | Precision | $<0.001$ |  0.024 $\pm$ 0.005 (hop 1) |  0.031 $\pm$ 0.004 (hop 1) | 0.038 $\pm$ 0.004 (hop 1) | 0.047 $\pm$ 0.005 (hop 1)
Recall | $<0.001$ |  0.084 $\pm$ 0.016 (hop 1) |  0.112 $\pm$ 0.016 (hop 1) | 0.136 $\pm$ 0.016 (hop 1) | 0.167 $\pm$ 0.018 (hop 1)
GitWebML | Precision | $<0.001$ |  0.001 $\pm$ 0.001 (hop 1) |  0.002 $\pm$ 0.001 (hop 1) | 0.018 $\pm$ 0.005 (hop 1) | 0.016 $\pm$ 0.004 (hop 1)
Recall | $<0.001$ |  0.002 $\pm$ 0.002 (hop 1) |  0.003 $\pm$ 0.002 (hop 1) | 0.031 $\pm$ 0.008 (hop 1) | 0.027 $\pm$ 0.006 (hop 1)
Table 5: The best result (precision@1000 and recall@1000) for each approach
for the different hop depths for link prediction. The overall best result is
given in bold font, and the second best – in italics.

### Embedding evaluation

#### Running time.

The algorithms were implemented in Python 3 and run on a Linux machine with 16
GB main memory and a 4.3 GHz Ryzen 7 CPU. In the right half of Table 1 we
present results for the running time of embeddings generation for
50-dimensional embeddings. We observe that $L_{0}$ sampling and NodeSketch are
highly efficient, $L_{0}$ sampling is even faster than random walks as we need
to generate only a single random number per node. $L_{1}/L_{2}$ sampling is
slower which is due to the fact that we update a sketch at each node.

#### Parallelization

Parallelization of the embedding generation approach is easy. Each coordinate
of the embedding vector is generated by running a copy of the LoNe Sampler
algorithm. The pseudocode for the general case in Algorithm 1, and the $L_{0}$
and $L_{1}$ versions from Algorithm 2, are for sampling a single coordinate of
the embedding vector. Clearly, we can run copies of the algorithm in parallel,
we only have to ensure that each copy has a unique random seed. For example,
in order to generate 50-dimensional embeddings we can run 5 copies of the
algorithm such that each of them produces 10-dimensional embeddings. The final
embedding vector is then a concatenation of the 10-dimensional embeddings
generated by different threads. Note that we can also generate embeddings in a
distributed setting.

We implemented parallelized versions of NodeSketch and $L_{1}$ sampling. We
used Python’s multiprocessing library for parallelization. The results can be
seen in Table 6 (NodeSketch) and Table 7 (LoNe Sampler ).

# threads | 1 | 5 | 10
---|---|---|---
Cora | 2.3 | 0.9 | 0.9
Citeseer | 3.0 | 1.4 | 1.1
Pubmed | 30.1 | 9.4 | 8.9
Deezer | 52.6 | 15.4 | 13.8
LastFM | 55.9 | 16.7 | 14.1
GitWebML | 88.9 | 31.6 | 23.8
Table 6: Time for NodeSketch sampling using parallelization for 50-dimensional embeddings generation. # threads | 1 | 5 | 10
---|---|---|---
Cora | 25.7 | 6.7 | 5.4
Citeseer | 30.4 | 8.1 | 6.3
Pubmed | 214.3 | 57.4 | 42.2
Deezer | 344.4 | 93.5 | 62.9
LastFM | 128.5 | 35.2 | 26.5
GitWebML | 609.1 | 166.3 | 120.0
Table 7: Running time for $L_{1}$ sampling with sketch size 10 using
parallelization for 50-dimensional embeddings generation.

#### Sketch quality.

We set $\varepsilon=0.01$ and as we have $d=50$, the expected error for each
inner product is bounded by $0.5$. We observe that the higher variance in
TensorSketch leads to outliers. In Figure 3 we show the ratio of the actual
error to the expected error for the sketching procedure from Theorem 4, and
for TensorSketch [19] for a sample of 1,000 vector pairs for NodeSketch. (The
approximation quality is similar for the LoNe Sampler algorithms.)

Figure 3: Comparison of the approximation quality for our approach from
Theorem 4 and TensorSketch.

#### Node classification.

We consider node classification for comparison of the different approaches. We
use a linear SVM model with explicit feature maps as presented in Theorem 4,
with tabulation hashing which is known to approximate the behavior of truly
random hash functions [20]. We split the data into 80% for training and 20%
for testing, and use the default $C=1$ as an SVM regularization parameter.

#### Training and prediction time.

In Table 3 we compare the running time for training and prediction of the
linear SVM model as presented in Theorem 4, and an SVM model with precomputed
kernel. The embedding vectors are computed by NodeSketch (the values for LoNe
Sampler are similar). Kernel SVMs are considerably slower for larger graphs
and for GitWebML result in out-of-memory errors.

#### Node classification.

We evaluate the performance of the algorithms with respect to accuracy,
balanced accuracy, micro-AUC, and macro-AUC metrics333The definitions can be
found at https://scikit-learn.org/stable/modules/classes.html#module-
sklearn.metrics. We report the mean and standard deviation of 10 independent
train/test splits in Table 4. We see that overall $L_{1}$ and $L_{2}$ sampling
achieve the best results. In particular, we observe that $L_{0}$ sampling
yields good results only for a smaller neighborhood depth $k$, this can be
clearly seen in the plots in Figures 4 and 5 where we show the micro-AUC and
macro-AUC scores for different neighborhood depths. The reason is that for
larger $k$ and a small graph diameter many nodes end up with identical
samples: for a connected graph with diameter at most $k$ all nodes will have
the same sampled node as their $k$-hop neighborhood is the node set $V$. In
contrast, $L_{1}$ and $L_{2}$ sampling do not suffer from this drawback as
samples depend on the graph structure, not just the set of reachable nodes.

We provide additional details to the experimental evaluation. In Figures 4,
and 5 we plot the micro-AUC and macro-AUC scores for each of the six graphs
for the explicit feature map approach.

|  |
---|---|---
|  |
Figure 4: Micro AUC scores for the six graphs for varying neighborhood depth. |  |
---|---|---
|  |
Figure 5: Macro AUC score for the six graphs for varying neighborhood depth.

#### Link prediction.

We evaluated the generated sketches on a link prediction task following a
similar approach as in [29]. We remove 20% of the edges from each graph such
that the graph remains connected. Then we sampled 5% of all node pairs in the
graph. We sorted the sampled pairs in reverse order according to their overlap
and considered the 1,000 pairs with the largest overlap. For these 1,000 pairs
we computed the precision@1000 and recall@1000. We report the mean and
standard deviation for the best neighborhood depth for each approach in Table
5. We observe that LoNe Sampler consistently achieves better results than
NodeSketch, one order of magnitude better for the PubMed and GitWebML graphs.
All approaches fail on Deezer because of the large number of node attributes
which make the overlap very small. We observe that the average overlap for the
LoNe Sampler approaches is larger than for NodeSketch, and this has a more
pronounced effect for link prediction, see discussion in the next paragraph.
The best values are achieved for hop-1 neighborhoods, i.e., sampling from the
feature set of the node’s immediate neighbors, and this is contrast to the
node classification task where the majority of best results for most graphs
were achieved when sampling from higher order neighborhoods. (Here, we would
like to reiterate that we first create a sketch at each node consisting of the
node attributes, and then runs LoNe Sampler for 1 iteration by merging the
neighborhood sketches.) The large overall number of node features in the
Deezer graph results again in very low quality predictions. This appears to be
a limitation of discrete node embedding algorithms, and one should look for
remedies such as reducing the number of features.

#### Average overlap

In Table 8 we show that the LoNe Sampler approaches have a significantly
higher overlap than NodeSketch, for a sample of 1,000 node pairs. This can be
also visually observed in Figure 11 where we show the approximation quality of
the explicit feature maps. Apparently, this has a less significant impact on
node classification than on link prediction. In the latter, we create an
ordered list of candidate nodes based on the overlap with a query node. Thus,
the lower overlap is apparently more likely to lead to random fluctuations and
thus more inaccurate link predictions.

# | NodeSketch | $L_{0}$ | $L_{1}$ | $L_{2}$
---|---|---|---|---
Cora | 1.816 | 8.06 | 8.498 | 7.986
Citeseer | 1.516 | 3.983 | 4.029 | 3.533
Pubmed | 1.538 | 27.61 | 15.93 | 15.15
Deezer | 2.286 | 6.273 | 8.494 | 8.048
LastFM | 3.983 | 23.49 | 18.928 | 15.69
GitWebML | 14.65 | 18.02 | 32.364 | 39.509
Table 8: Average overlap between node pairs NodeSketch and LoNe Sampler (hop
2, embedding size 50).

### Optimal values for the hyperparameters.

We analyze the optimal values for the different hyperparameters: the
neighborhood depth $k$, the dimensionality of the embeddings $d$, and the
sketch size $\ell$ for $L_{1}/L_{2}$ sampling. While the optimal $k$ appears
to be graph specific, we observe the improvements for larger $d$, see Figures
6, 7 and 8444The recall scores for the DeezerEurope graph are very low for all
methods and we omit the plot from Figure 8., and the sketch size $\ell$ for
$L_{1}/L_{2}$ sampling to follow a diminishing returns pattern (Figures 9 and
10). It is worth noting that even for very small embedding dimensions we still
achieve very good results for node classification. Also, for larger $d$
NodeSketch catches up with $L_{1}/L_{2}$ sampling as more samples compensate
for the inconsistencies due to its heuristic nature but this is still not the
case for link prediction as the overall overlap remains low and still subject
to random fluctuations.

|  |
---|---|---
|  |
Figure 6: Micro AUC scores for varying embedding size. |  |
---|---|---
|  |
Figure 7: Macro AUC scores for varying embedding size for node classification. |  |
---|---|---
|  |
Figure 8: Recall@1000 for varying embedding size for link prediction. |  |
---|---|---
|  |
Figure 9: Micro AUC scores for varying sketch size for node classification. |  |
---|---|---
|  |
Figure 10: Macro AUC scores for varying sketch size for node classification. # | $L_{1}/L_{2}$ | DeepWalk | node2vec
---|---|---|---
Cora | 7.5 | 8.1 | 16.0
Citeseer | 8.5 | 9.2 | 16.7
Pubmed | 53.4 | 68.3 | 154.2
Deezer | 75.6 | 122.8 | 239.8
LastFM | 32.3 | 24.2 | 64.1
GitWebML | 145.8 | 206.7 | 1037.8
Table 9: Embedding generation time for 50-dimensional embeddings generation (8 cores). | DeepWalk | node2vec | $L_{1}$ | $L_{2}$
---|---|---|---|---
Cora | Accuracy |  0.802 $\pm$ 0.014 |  0.815 $\pm$ 0.016 | 0.831 $\pm$ 0.018 (hop 1) |  0.829 $\pm$ 0.019 (hop 1)
Balanced accuracy |  0.777 $\pm$ 0.013 |  0.804 $\pm$ 0.023 | 0.814 $\pm$ 0.023 (hop 1) |  0.812 $\pm$ 0.023 (hop 1)
Micro AUC |  0.954 $\pm$ 0.005 |  0.964 $\pm$ 0.004 | 0.974 $\pm$ 0.005 (hop 1) | 0.973 $\pm$ 0.005 (hop 1)
Macro AUC |  0.946 $\pm$ 0.006 |  0.959 $\pm$ 0.004 | 0.971 $\pm$ 0.005 (hop 1) | 0.969 $\pm$ 0.005 (hop 1)
Citeseer | Accuracy |  0.551 $\pm$ 0.010 |  0.572 $\pm$ 0.018 |  0.711 $\pm$ 0.015 (hop 2) | 0.722 $\pm$ 0.015 (hop 2)
Balanced accuracy |  0.512 $\pm$ 0.011 |  0.522 $\pm$ 0.014 | 0.676 $\pm$ 0.017 (hop 2) | 0.691 $\pm$ 0.016 (hop 2)
Micro AUC |  0.828 $\pm$ 0.007 |  0.832 $\pm$ 0.014 | 0.915 $\pm$ 0.007 (hop 2) | 0.917 $\pm$ 0.007 (hop 2)
Macro AUC |  0.803 $\pm$ 0.006 |  0.816 $\pm$ 0.0168 | 0.898 $\pm$ 0.007 (hop 2) | 0.903 $\pm$ 0.007 (hop 2)
PubMed | Accuracy |  0.792 $\pm$ 0.004 |  0.807 $\pm$ 0.005 | 0.818 $\pm$ 0.004 (hop 2) | 0.804 $\pm$ 0.007 (hop 4)
Balanced accuracy |  0.772 $\pm$ 0.005 |  0.790 $\pm$ 0.005 | 0.809 $\pm$ 0.004 (hop 2) | 0.793 $\pm$ 0.006 (hop 2)
Micro AUC |  0.917 $\pm$ 0.003 |  0.928 $\pm$ 0.002 | 0.938 $\pm$ 0.002 (hop 2) | 0.932 $\pm$ 0.002 (hop 2)
Macro AUC |  0.912 $\pm$ 0.003 |  0.923 $\pm$ 0.002 | 0.935 $\pm$ 0.002 (hop 2) | 0.928 $\pm$ 0.002 (hop 2)
DeezerEurope | Accuracy |  0.556 $\pm$ 0.003 |  0.561 $\pm$ 0.002 | 0.558 $\pm$ 0.008 (hop 2) | 0.565 $\pm$ 0.006 (hop 2)
Balanced accuracy |  0.509 $\pm$ 0.004 |  0.522 $\pm$ 0.003 | 0.548 $\pm$ 0.005 (hop 1) | 0.556 $\pm$ 0.006 (hop 2)
Micro AUC |  0.581 $\pm$ 0.004 |  0.585 $\pm$ 0.003 | 0.589 $\pm$ 0.006 (hop 2) | 0.594 $\pm$ 0.005 (hop 2)
Macro AUC |  0.547 $\pm$ 0.005 |  0.555 $\pm$ 0.003 | 0.565 $\pm$ 0.006 (hop 2) | 0.577 $\pm$ 0.005 (hop 2)
LastFM | Accuracy | 0.857 $\pm$ 0.005 | 0.866 $\pm$ 0.006 |  0.825 $\pm$ 0.008 (hop 4) |  0.818 $\pm$ 0.009 (hop 4)
Balanced accuracy | 0.766 $\pm$ 0.007 | 0.773 $\pm$ 0.007 |  0.707 $\pm$ 0.025 (hop 3) |  0.695 $\pm$ 0.028 (hop 4)
Micro AUC | 0.974 $\pm$ 0.002 | 0.975 $\pm$ 0.004 |  0.969 $\pm$ 0.003 (hop 1) |  0.970 $\pm$ 0.003 (hop 1)
Macro AUC | 0.943 $\pm$ 0.011 | 0.944 $\pm$ 0.010 |  0.936 $\pm$ 0.003 (hop 1) |  0.939 $\pm$ 0.003 (hop 1)
GitWebML | Accuracy | 0.857 $\pm$ 0.003 | 0.863 $\pm$ 0.004 |  0.835 $\pm$ 0.003 (hop 1) |  0.837 $\pm$ 0.003 (hop 1)
Balanced accuracy | 0.771 $\pm$ 0.004 | 0.779 $\pm$ 0.005 |  0.764 $\pm$ 0.006 (hop 1) |  0.763 $\pm$ 0.006 (hop 1)
Micro AUC | 0.923 $\pm$ 0.002 | 0.926 $\pm$ 0.003 |  0.908 $\pm$ 0.002 (hop 1) |  0.905 $\pm$ 0.002 (hop 1)
Macro AUC | 0.886 $\pm$ 0.003 | 0.891 $\pm$ 0.003 |  0.862 $\pm$ 0.002 (hop 1) |  0.855 $\pm$ 0.002 (hop 1)
Table 10: The best result for DeepWalk, node2vec and LoNe Sampler . The
overall best result is given in bold font, and the second best – in italics.

### Comparison with continuous embeddings

In Table 9 we show the computational time for each approach. Even the slow
$L_{1}/L_{2}$ sampling are considerably faster for larger graphs than the two
continuous embedding approaches.

We would like to emphasize that comparing the performance of discrete and
continuous embeddings is not really fair. The two embeddings types have very
different properties. We want to compare embeddings that look like

    cell,gene,infection,..,cell,young,dna

with embeddings that look like

    0.234,-0.67,0.012,..,0.848,-0.703,-0.447

The main advantages of discrete embeddings are their interpetability, easiness
to compute, and that do not depend on optimization techniques like gradient
descent. On the other hand, continuous embeddings are much more powerful as
they can be used by virtually every machine learning algorithm, from logistic
regression to deep learning. In the case of discrete embeddings our options
are much more limited.

Having said that, in Table 10 we provide the classification accuracy for the
four considered metrics of $L_{1}$, $L_{2}$ sampling and DeepWalk [18] and
node2vec[9] for a Linear SVM with 80%-20% train–test split, and report the
mean and standard deviation for 10 runs. We use the default parameters
provided in the respective libraries, i.e., 10 random walks of length 80 per
node, and 5 training epochs. For node2vec we report the best score of all 9
combinations for the hyperparameters $p$ and $q$ from the set {0.5, 1, 2}. We
observe that LoNe Sampler achieves better results for the lower density
graphs. It is tempting to conjecture that for denser graphs random walks
explore more of the neighborhood while the discrete embeddings fail to visit
some nodes.

#### Approximation guarantee

In Figure 11 we plot the approximation of the Hamming kernel using the
explicit map approach from Section 4 for 10,000 randomly selected node pairs
for each of the six graphs, for the NodeSketch and $L_{2}$ embeddings. One
observation is that the overlap for LoNe Sampler is on average larger than for
NodeSketch. This is due to the fact that NodeSketch samples only a single node
at each iteration and is susceptible to random fluctuations. Interestingly
though, the larger overlap does not always translate into improved
classification accuracy but the effects on link prediction are more clearly
pronounced.

|
---|---
|
|
|
|
|
Figure 11:  Approximation quality of the overlap kernel.

### Embedding interpretability

Finally, we discuss how discrete node embeddings can be used in interpretable
machine learning. Consider the PubMed graph. The nodes represent scientific
articles. Each article is described by a list of key words that appear in the
paper abstract, these are the node features that we list in Table 1. We sample
a feature for each node and then propagate the sampled features using LoNe
Sampler or NodeSketch. For example, if the word cell appears in many abstracts
in the local neighborhood of a given node, it is likely to be sampled. After
sampling $d$ samples, we end up with a vector consisting of key words. An
embedding vector can look like

    [cell, oral, complex, cell, ... , insulin, cell, young, dna]

We can compare two such embedding vectors by the overlap kernel discussed in
Section 4 and design a kernel SVM model. But we can also use other, more
interpretable approaches. For example, using a model like a decision tree we
can explain predictions by looking at the splits of the tree when classifying
a new example. (A research paper is classified as belonging to the category
“Genetics” because when splitting on coordinate 10 it had a value of cell, and
then splitting on coordinate 16 the value is dna).

The embeddings can be also used in unsupervised learning. In Figure 12 we show
the result of clustering the Pubmed vectors into three clusters, the distance
measure is based on the overlap between the discrete embedding vectors from
the 2-hop neighborhood using $L_{1}$ sampling. (This is part of another
ongoing project of ours and we include it only in order to address the
reviewer’s comment.) We plot the distribution of the words (on a log scale) of
embeddings in each cluster for the top words and observe the distributions are
very different between clusters. We can then divide papers into different
groups depending on the vocabulary of their local neighborhood.

Figure 12: Top words distribution in the three different clusters of Pubmed
nodes.

##  7 Conclusions and future work

We presented new algorithms for coordinated local graph sampling with
rigorously understood theoretical properties. We demonstrate that using
sketching techniques with well-understood properties also has practical
advantages and can lead to more accurate algorithms in downstream tasks, and
explicit feature maps open the door to highly scalable classification
algorithms.

Finally, we would like to pose an open question. Can we learn structural roles
[21] by assigning appropriate node attributes? In particular, can we combine
the sampling procedure with approaches for graph labeling?

## References

  * [1] P. K. Agarwal, G. Cormode, Z. Huang, J. M. Phillips, Z. Wei, and K. Yi.  Mergeable summaries.  ACM Trans. Database Syst., 38(4):26:1–26:28, 2013.
  * [2] N. K. Ahmed, N. G. Duffield, T. L. Willke, and R. A. Rossi.  On sampling from massive graph streams.  Proc. VLDB Endow., 10(11):1430–1441, 2017.
  * [3] L. Backstrom, P. Boldi, M. Rosa, J. Ugander, and S. Vigna.  Four degrees of separation.  In Web Science 2012, 2012.
  * [4] A. Z. Broder, M. Charikar, A. M. Frieze, and M. Mitzenmacher.  Min-wise independent permutations.  J. Comput. Syst. Sci., 60(3):630–659, 2000.
  * [5] Larry Carter and Mark N. Wegman.  Universal classes of hash functions.  J. Comput. Syst. Sci., 18(2):143–154, 1979.
  * [6] M. Charikar, K. C. Chen, and M. Farach-Colton.  Finding frequent items in data streams.  Theor. Comput. Sci., 312(1):3–15, 2004.
  * [7] E. Cohen.  Coordinated sampling.  In Encyclopedia of Algorithms, pages 449–454. 2016.
  * [8] Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang.  On graph problems in a semi-streaming model.  Theor. Comput. Sci., 348(2-3):207–216, 2005.
  * [9] A. Grover and J. Leskovec.  node2vec: Scalable feature learning for networks.  In KDD 2016, 2016.
  * [10] William L. Hamilton, Zhitao Ying, and Jure Leskovec.  Inductive representation learning on large graphs.  In NIPS 2017, 2017.
  * [11] S. Ioffe.  Improved consistent sampling, weighted minhash and L1 sketching.  In ICDM 2010, 2010.
  * [12] Thorsten Joachims.  Training linear svms in linear time.  In Proceedings of the Twelfth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2006, pages 217–226, 2006\.
  * [13] H. Jowhari, M. Saglam, and G. Tardos.  Tight bounds for lp samplers, finding duplicates in streams, and related problems.  In PODS 2011, 2011.
  * [14] R. M. Karp, S. Shenker, and C. H. Papadimitriou.  A simple algorithm for finding frequent elements in streams and bags.  ACM Trans. Database Syst., 28:51–55, 2003.
  * [15] T. Mikolov, I. Sutskever, K. Chen, G. S. Corrado, and J. Dean.  Distributed representations of words and phrases and their compositionality.  In NIPS 2013, 2013.
  * [16] M. Ou, P. Cui, J. Pei, Z. Zhang, and W. Zhu.  Asymmetric transitivity preserving graph embedding.  In KDD 2016, 2016.
  * [17] J. Pennington, R. Socher, and C. D. Manning.  Glove: Global vectors for word representation.  In EMNLP 2014, 2014.
  * [18] B. Perozzi, R. Al-Rfou, and S. Skiena.  Deepwalk: online learning of social representations.  In KDD 2014, 2014.
  * [19] N. Pham and R. Pagh.  Fast and scalable polynomial kernels via explicit feature maps.  In KDD, pages 239–247. ACM, 2013.
  * [20] Mihai Pǎtraşcu and Mikkel Thorup.  The power of simple tabulation hashing.  J. ACM, 59(3):14, 2012.
  * [21] R. A. Rossi, D. Jin, S. Kim, N. K. Ahmed, D. Koutra, and J. B. Lee.  On proximity and structural role-based embeddings in networks: Misconceptions, techniques, and applications.  ACM Trans. Knowl. Discov. Data, 14(5):63:1–63:37, 2020.
  * [22] B. Rozemberczki and R. Sarkar.  Characteristic Functions on Graphs: Birds of a Feather, from Statistical Descriptors to Parametric Models.  In CIKM 2020, page 1325–1334, 2020.
  * [23] Benedek Rozemberczki, Carl Allen, and Rik Sarkar.  Multi-Scale Attributed Node Embedding.  Journal of Complex Networks, 9(2), 2021.
  * [24] P. Sen, G. Namata, M. Bilgic, L. Getoor, B. Gallagher, and T. Eliassi-Rad.  Collective classification in network data.  AI Mag., 29(3):93–106, 2008.
  * [25] S. Sohangir and D. Wang.  Improved sqrt-cosine similarity measurement.  J. Big Data, 4:25, 2017.
  * [26] J. Tang, M. Qu, M. Wang, M. Zhang, J. Yan, and Q. Mei.  LINE: large-scale information network embedding.  In WWW 2015, 2015.
  * [27] A. Tsitsulin, D. Mottin, P. Karras, and E. Müller.  VERSE: versatile graph embeddings from similarity measures.  In WWW 2018, 2018.
  * [28] W. Wu, B. Li, L. Chen, and C. Zhang.  Efficient attributed network embedding via recursive randomized hashing.  In IJCAI 2018, 2018.
  * [29] D. Yang, P. Rosso, B. Li, and P. Cudré-Mauroux.  Nodesketch: Highly-efficient graph embeddings via recursive sketching.  In KDD 2019, 2019.
  * [30] Z. Zhang, P. Cui, X. Wang, J. Pei, X. Yao, and W. Zhu.  Arbitrary-order proximity preserved network embedding.  In KDD 2018, 2018.
  * [31] C. Zhou, Y. Liu, X. Liu, Z. Liu, and J. Gao.  Scalable graph embedding for asymmetric proximity.  In AAAI 2017, 2017.