Aczel's version of the Mostowski Collapsing Lemma appears to be a generalisation of the usual one. Recall that the Mostowski Collapsing Lemma in Jech (p.69) says the following (emphasis mine):
If $E$ is a well-founded and extensional relation of a class $P$, then there is a transitive class $M$ and an isomorphism $\pi$ between $(P,E)$ and $(M,\in)$. The transitive class $M$ and the isomorphism $\pi$ are unique.
Note that the above version requires not only there to be a strong relationship between the decoration of a node/set and its children/elements, but also that each decoration is given to a unique node/set. Aczel's version does not require that the mapping $x \mapsto dx$ be injective (let alone be an isomorphism), but only that there be a strong relationship between the decoration of a node and the decorations of its children.
A consequence of the construction would be that if the edge relation of the graph is additionally extensional, then you would produce such an isomorphism. But clearly not all graphs have an extensional edge relationship.
At one level, AFA provides for the existence of sets which are somewhat counterintuitive (in my eye, anyway);
- Consider how you would produce a decoration for the graph whose set of nodes is $\mathbb{N}$ and $n \rightarrow m$ iff $m = n+1$. This is a single infinite path, and if $d$ were a decoration you must have $d0 \ni d1 \ni d2 \ni \cdots$.
- For finite cyclic graphs you must accept that there are sets satisfying $d0 \ni d1 \ni \cdots \ni dn \ni d0$.
But AFA works a dual function in this theory. Suppose we are given the directed $2$-cycle $a \rightarrow b \rightarrow a$. If $d$ is any decoration for this graph, then $da = \{ db \}; \quad db = \{ da \} \quad \Longrightarrow \quad da = \{ db \} = \{ \{ da \} \},$ and also note that $db = \{ \{ db \} \}$. It is quite easy to show that by switching the decorations of the nodes $a$ and $b$ ($\partial a = db , \partial b = da$) we get another decoration of the graph. But AFA says that decorations are unique, so in fact $db = da$! To make a more concrete statement, by AFA there is a unique set $x$ satisfying $x = \{ \{ x \} \}$. It is not too difficult to extend this to say that for each natural number $n \geq 1$ there is a unique set $x$ satisfying $x = \overbrace{ \{ \{ \cdots \{ }^{n \text{ times}} x \} \cdots \} \}.$ (Similar statements can be made about witnessing sets for all ill-founded graphs.)
As for the Leap of Faith required to believe or disbelieve AFA? I guess it depends on whether you believe the $\in$ relation to be really well-founded, or possibly ill-founded (and perhaps additionally that ZF(C) only focuses on the well-founded fragment of these sets). But these appear to me to be meta-theoretical issues that cannot be proved or refuted.