I’d suggest trying SVG. It is cleaner than PDF (smaller? text-based files with less huge-document baggage).
Any way you cut it, an average of 10,000 edges/node is a challenge.
You might also try some of the other engines - fdp, neato, sfdp, circo, twopi - for fun if no other reason.