  Weighted First Order Model Counting (WFOMC) is fundamental to probabilistic
inference in statistical relational learning models. As WFOMC is known to be
intractable in general ($\#$P-complete), logical fragments that admit
polynomial time WFOMC are of significant interest. Such fragments are called
domain liftable. Recent works have shown that the two-variable fragment of
first order logic extended with counting quantifiers ($\mathrm{C^2}$) is
domain-liftable. However, many properties of real-world data, like acyclicity
in citation networks and connectivity in social networks, cannot be modeled in
$\mathrm{C^2}$, or first order logic in general. In this work, we expand the
domain liftability of $\mathrm{C^2}$ with multiple such properties. We show
that any $\mathrm{C^2}$ sentence remains domain liftable when one of its
relations is restricted to represent a directed acyclic graph, a connected
graph, a tree (resp. a directed tree) or a forest (resp. a directed forest).
All our results rely on a novel and general methodology of "counting by
splitting". Besides their application to probabilistic inference, our results
provide a general framework for counting combinatorial structures. We expand a
vast array of previous results in discrete mathematics literature on directed
acyclic graphs, phylogenetic networks, etc.
