  We introduce in this paper the mechanism of graph random features (GRFs).
GRFs can be used to construct unbiased randomized estimators of several
important kernels defined on graphs' nodes, in particular the regularized
Laplacian kernel. As regular RFs for non-graph kernels, they provide means to
scale up kernel methods defined on graphs to larger networks. Importantly, they
give substantial computational gains also for smaller graphs, while applied in
downstream applications. Consequently, GRFs address the notoriously difficult
problem of cubic (in the number of the nodes of the graph) time complexity of
graph kernels algorithms. We provide a detailed theoretical analysis of GRFs
and an extensive empirical evaluation: from speed tests, through Frobenius
relative error analysis to kmeans graph-clustering with graph kernels. We show
that the computation of GRFs admits an embarrassingly simple distributed
algorithm that can be applied if the graph under consideration needs to be
split across several machines. We also introduce a (still unbiased) quasi Monte
Carlo variant of GRFs, q-GRFs, relying on the so-called reinforced random
walks, that might be used to optimize the variance of GRFs. As a byproduct, we
obtain a novel approach to solve certain classes of linear equations with
positive and symmetric matrices.
