It's easy to get into situations where you're paying massive costs with serialization, deserialization, and network I/O, and I believe graph operations with Spark are one of those situations. I would be curious if running Spark in local mode with a single thread would actually improve the runtime, or if it would reveal other issues with the Spark graph libraries.