Trees are rooted somewhere. The problem is reduced to finding the root account which invited all the spammers and banning that account and its entire invite tree and the guy who invited that root account for good measure. This reduces the number of accounts that must be evaluated, making it much more manageable. Any false positives can be dealt with on a case-by-case basis.

Make accounts and invitations a limited resource. People will think twice before inviting someone who can get them banned. This reduces the problem to one of trust which is the foundation of real security.