Anonymize graph by adding edges. No lossy compression considered here. $(k, \ell)$-anonymity is defined in this paper. See also * http://theory.stanford.edu/~tomas/ and * http://theory.stanford.edu/~sunabar/Publications.html