Clustering evaluation metrics with subquadratic time complexity
Rand index is not more expensive than NMI, it's O(n) when implemented correctly.

There are like 40 internal evaluation indexes. I am fairly certain there are several that are not quadratic in runtime. Just go through the list, and document your findings for the next one with the same question.

Spark sucks for clustering. It can do k-means and GMM but both are very slow compared to other tools. They don't scale. The attempts at implementing DBSCAN for Spark are even worse. They were found to return incorrect results to crash, and to scale worse than single-core implementations such as ELKI (not to speak of parallel HPC implementations):


  Helmut Neukirchen. 
  Survey and Performance Evaluation of DBSCAN Spatial Clustering Implementations for Big Data and High-Performance Computing Paradigms


It's just not what Spark is good at. And given all the "extensions" for it - that often have a very low quality - you quickly run into problems and don't know who is to blame and where to fix them.

Make sure to benchmark.