  We consider classes of arbitrary (finite or infinite) graphs of bounded
shrub-depth, specifically the class $\mathrm{TM}_{r, p}(d)$ of $p$-labeled
arbitrary graphs whose underlying unlabeled graphs have tree models of height
$d$ and $r$ labels. We show that this class satisfies an extension of the
classical L\"owenheim-Skolem property into the finite and for $\mathrm{MSO}$.
This extension being a generalization of the small model property, we obtain
that the graphs of $\mathrm{TM}_{r, p}(d)$ are pseudo-finite. In addition, we
obtain as consequences entirely new proofs of a number of known results
concerning bounded shrub-depth classes (of finite graphs) and $\mathrm{TM}_{r,
p}(d)$. These include the small model property for $\mathrm{MSO}$ with
elementary bounds, the classical compactness theorem from model theory over
$\mathrm{TM}_{r, p}(d)$, and the equivalence of $\mathrm{MSO}$ and
$\mathrm{FO}$ over $\mathrm{TM}_{r, p}(d)$ and hence over bounded shrub-depth
classes. The proof for the last of these is via an adaptation of the proof of
the classical Lindstr\"om's theorem characterizing $\mathrm{FO}$ over arbitrary
structures.
