Bump GraphFrames from 0.11.0 to 0.12.2 and use randomized contraction for DBSCAN

[james-willis]

Sedona pins GraphFrames 0.11.0 via <graphframes.version> in the root pom.xml. GraphFrames has shipped 0.12.0, 0.12.1 and 0.12.2 since. Two things in those releases matter to Sedona.

1. The bump

Sedona's only GraphFrames usage is GraphFrame(...).connectedComponents in spark/common/src/main/scala/org/apache/sedona/stats/clustering/DBSCAN.scala. The single breaking change across the 0.12.x line is in the low-level Pregel API — edge attributes are no longer implicitly packed into a persisted StructType and must be requested explicitly via requiredEdgeColumns — which Sedona does not use.

Artifact coordinates are unchanged, and 0.12.2 is published for all three combinations Sedona builds against: graphframes-spark3_2.12, graphframes-spark3_2.13, graphframes-spark4_2.13.

2. Use randomized_contraction for DBSCAN's connected components

GraphFrames offers three connected-components implementations: graphx, two_phase (the default), and randomized_contraction, the last based on Bögeholz, Brand and Todor, "In-database connected component analysis" (ICDE 2020). Following the performance work in graphframes/graphframes#888, the GraphFrames user guide now states that randomized_contraction performs better on benchmarks than two_phase with AQE and needs roughly half the memory, and that it is not the library default only for backwards-compatibility reasons.

DBSCAN is a good fit for it, because Sedona does not expose GraphFrames' component IDs as stable identifiers — they are opaque cluster labels.

Behavior change

two_phase returns the minimum original vertex ID within each component when vertex IDs are integral; randomized_contraction always returns an arbitrary Long.

For DBSCAN this is only visible when the input already has an id column of integral type — those cluster labels change from "smallest core-point id in the cluster" to an arbitrary Long. When the input has no id column, DBSCAN synthesizes one with sha2(to_json(struct("*")), 256); those IDs are non-integral, so two_phase already returns arbitrary Longs today and nothing changes.

Cluster labels remain LongType, the -1 outlier sentinel is unaffected, and the min(component) tie-break used to assign border points to a cluster is unchanged. Callers that treat the cluster column as an opaque grouping key — which is how it is documented — are unaffected. Callers that relied on the numeric value of the label are not.

[james-willis]

Status update: this is now blocked only on a GraphFrames release, not on a defect.

The switch to randomized_contraction was dropped from #3299 because the algorithm could not run against Sedona's DBSCAN at all — DBSCAN.dbscan assigns vertex ids as sha2(to_json(struct("*")), 256), and randomized_contraction mishandled non-integral vertex IDs (graphframes/graphframes#892).

That has since been fixed upstream in graphframes/graphframes#893, now merged to main. Once a GraphFrames release includes it, the switch becomes viable again.

Two things to carry over when it is revisited:

1. Spark 3.4 needs a fallback. randomized_contraction is implemented with functions.call_function, which was only added in Spark 3.5, and the published graphframes-spark3_* artifact is compiled against 3.5.x. On a Spark 3.4 runtime the call links but throws NoSuchMethodError at execution time. Sedona still builds and tests Spark 3.4.0, so the default needs to be gated on the runtime Spark version. This is independent of [SEDONA-318] Switch raster serde to a deep copy implementation #892 and is not fixed by [SEDONA-321] Implement RS_Intersects(rast, geom) #893.

2. Cluster labels change for integral-id inputs. two_phase returns the minimum core-point id per cluster; randomized_contraction returns an arbitrary Long. Inputs without an id column are unaffected, since the synthesized sha2 id is non-integral and two_phase already randomizes there.

[james-willis]

Note for anyone finding this later: #3299 landed only the dependency bump to GraphFrames 0.12.2. The second half of this issue — switching DBSCAN's connected components to randomized_contraction — was not done.

This issue auto-closed because I left Closes #3298 in #3299 after reducing that PR's scope; the close is an artifact of the PR wording, not a signal that the algorithm switch shipped. Leaving it closed since the bump did land, but flagging it so the remaining work is not lost.

Still outstanding, if anyone wants to pick it up once a GraphFrames release includes graphframes/graphframes#893:

1. randomized_contraction mishandled non-integral vertex IDs (randomized_contraction fails on non-integral vertex IDs (CAST_INVALID_INPUT) graphframes/graphframes#892), which is fatal here because DBSCAN.dbscan assigns ids as sha2(to_json(struct("*")), 256). Fixed upstream in [SEDONA-321] Implement RS_Intersects(rast, geom) #893, merged to main, not yet released.
2. Spark 3.4 needs a fallback regardless: randomized_contraction uses functions.call_function, added in Spark 3.5, and graphframes-spark3_* is compiled against 3.5.x — so on a 3.4 runtime it throws NoSuchMethodError. Sedona still builds and tests 3.4.0. This is independent of [SEDONA-318] Switch raster serde to a deep copy implementation #892 and is not fixed by [SEDONA-321] Implement RS_Intersects(rast, geom) #893.
3. Cluster labels change for inputs that already have an integral id column: two_phase returns the minimum core-point id per cluster, randomized_contraction an arbitrary Long. Inputs without an id column are unaffected.