It is an old result that the "membership graph" of any countable model of set theory, obtained by joining x and y if x is in y *or* y is in x, is isomorphic to the random graph. This is true for extremely weak set theories but, crucially, they have to satisfy the Axiom of Foundation. In joint work with Bea Adam-Day and John Howe we study the class of "double-membership graphs", obtained by joining x and y if x is in y *and* y is in x, in the case of set theory with the Anti- Foundation Axiom. In contrast with the omega-categorical, supersimple class of "traditional" membership graphs, we show that double-membership graphs are way less well-behaved: their theory is incomplete and each of its completions has the maximum number of countable models and is wild in the sense of neostability theory. By using ideas from finite model theory, we characterise the aforementioned completions, and show that the class of countable double-edge graphs of Anti-Foundation is not even closed under elementary equivalence among countable structures. This answers some questions of Adam-Day and Cameron.