Graph Random Neural Features for Distance-Preserving Graph
  Representations
  We present Graph Random Neural Features (GRNF), a novel embedding method from
graph-structured data to real vectors based on a family of graph neural
networks. The embedding naturally deals with graph isomorphism and preserves
the metric structure of the graph domain, in probability. In addition to being
an explicit embedding method, it also allows us to efficiently and effectively
approximate graph metric distances (as well as complete kernel functions); a
criterion to select the embedding dimension trading off the approximation
accuracy with the computational cost is also provided. GRNF can be used within
traditional processing methods or as a training-free input layer of a graph
neural network. The theoretical guarantees that accompany GRNF ensure that the
considered graph distance is metric, hence allowing to distinguish any pair of
non-isomorphic graphs.
