Well, well, well. It turns out the memory leak was not in the graph processing at all. The function to extract the certs from HTML (via regexes) was holding on to stuff, appearently. Forcing evaluation of the extracted certs makes the program run on full CPU power with a maximum residency of eight megabytes. It took around 80 seconds to process all users.
But by the way, my self-made graph module was still very useful. Most importantly, it allows arbitrary node types, as long as they are ordered. Amazingly, this generalization makes the code hugely prettier. I will have to see how the algorithms work out.