  We establish a new and surprisingly strong link between two previously
unrelated theories: the theory of moduli spaces of curves ${\mathcal M}_{g,n}$
(which, according to Penner, is controlled by the ribbon graph complex) and the
homotopy theory of $E_d$ operads (controlled by ordinary graph complexes with
no ribbon structure, introduced first by Kontsevich). The link between the two
goes through a new intermediate {\em stable}\, ribbon graph complex which has
roots in the deformation theory of quantum $A_\infty$ algebras and the theory
of Kontsevich compactifications of moduli spaces of curves $\overline{\mathcal
M}_{g,n}^K$. Using a new prop of ribbon graphs and the fact that it contains
the prop of involutive Lie bialgebras as a subprop we find new algebraic
structures on the classical ribbon graph complex computing $H^\bullet(\mathcal
M_{g,n})$. We use them to prove Comparison Theorems, and in particular to
construct a non-trivial map from the ordinary to the ribbon graph cohomology.
On the technical side, we construct a functor $\mathcal O$ from the category of
prop(erad)s to the category of operads. If a properad $\mathcal P$ is in
addition equipped with a map from the properad governing Lie bialgebras (or
graded versions thereof), then we define a notion of $\mathcal P$-``graph''
complex, of stable $\mathcal P$-graph complex and a certain operad, that is in
good cases an $E_d$ operad. In the ribbon case, this latter operad acts on the
deformation complexes of any quantum $A_\infty$-algebra. We also prove that
there is a highly non-trivial, in general, action of the
Grothendieck-Teichm\"uller group $GRT_1$ on the space of so-called {\em
non-commutative Poisson structures}\, on any vector space $W$ equipped with a
degree $-1$ symplectic form (which interpolate between cyclic $A_\infty$
structures in $W$ and ordinary polynomial Poisson structures on $W$ as an
affine space).
