I faced the same problem when I tried to visualize my GPG keyring.

My workaround was to create the graphics only very seldom, and use mapit to display the results. Not very convient, if you ask me.

I guess the problem isn't graphviz itself (which is quite fast, actually) but the problem domain itself.

You could try to preprocess your data, and instead of displaying every single node, you could create clusters and display them as one node, with the size being proportional to the number of nodes iin the cluster.

You won't lose much in terms of graphics, because the human eye can't possibly process 10⁶ nodes.

But the cluster analysis will take quite some time, I fear.