  We present a novel framework closely linking the areas of property testing
and data streaming algorithms in the setting of general graphs. It has been
recently shown (Monemizadeh et al. 2017) that for bounded-degree graphs, any
constant-query tester can be emulated in the random order streaming model by a
streaming algorithm that uses only space required to store a constant number of
words. However, in a more natural setting of general graphs, with no
restriction on the maximum degree, no such results were known because of our
lack of understanding of constant-query testers in general graphs and lack of
techniques to appropriately emulate in the streaming setting off-line
algorithms allowing many high-degree vertices.
  In this work we advance our understanding on both of these challenges. First,
we provide canonical testers for all constant-query testers for general graphs,
both, for one-sided and two-sided errors. Such canonizations were only known
before (in the adjacency matrix model) for dense graphs (Goldreich and Trevisan
2003) and (in the adjacency list model) for bounded degree (di-)graphs
(Goldreich and Ron 2011, Czumaj et al. 2016). Using the concept of canonical
testers, we then prove that every property of general graphs that is
constant-query testable with one-sided error can also be tested in
constant-space with one-sided error in the random order streaming model.
  Our results imply, among others, that properties like $(s,t)$
disconnectivity, $k$-path-freeness, etc. are constant-space testable in random
order streams.
