  In a recent work (ECCC, TR18-171, 2018), we introduced models of testing
graph properties in which, in addition to answers to the usual graph-queries,
the tester obtains {\em random vertices drawn according to an arbitrary
distribution $D$}. Such a tester is required to distinguish between graphs that
have the property and graphs that are far from having the property, {\em where
the distance between graphs is defined based on the unknown vertex distribution
$D$}. These ("vertex-distribution free" (VDF)) models generalize the standard
models in which $D$ is postulated to be uniform on the vertex-set, and they
were studies both in the dense graph model and in the bounded-degree graph
model.
  The focus of the aforementioned work was on testers, called {\sf strong},
whose query complexity depends only on the proximity parameter $\epsilon$.
Unfortunately, in the standard bounded-degree graph model, some natural
properties such as Bipartiteness do not have strong testers, and others (like
cycle-freeness) do not have strong testers of one-sided error (whereas
one-sided error was shown inherent to the VDF model). Hence, it was suggested
to study general (i.e., non-strong) testers of "sub-linear" complexity.
  In this work, we pursue the foregoing suggestion, but do so in a model that
augments the model presented in the aforementioned work. Specifically, we
provide the tester with an evaluation oracle to the unknown distribution $D$,
in addition to samples of $D$ and oracle access to the tested graph. Our main
results are testers for Bipartitness and cycle-freeness, in this augmented
model, having complexity that is almost-linear in the square root of the
"effective support size" of $D$.
