Actually, I've used the Magic Eraser to clean smoke from my rough
brick fireplace. It works, but the sponge is used up very quickly (it
sort of disintegrates). Never tried it with graffiti... gonna go
spray paint my fireplace now... ;-)
It does work really well around the house, though.