This is an automated email from the ASF dual-hosted git repository.
zhengruifeng pushed a commit to branch branch-4.0
in repository https://gitbox.apache.org/repos/asf/spark.git
The following commit(s) were added to refs/heads/branch-4.0 by this push:
new 1ff8a1343854 [SPARK-60835][GRAPHX] Break label propagation ties with
the lowest label
1ff8a1343854 is described below
commit 1ff8a1343854a177d2f686e4aff834e2a137dc20
Author: Ruifeng Zheng <[email protected]>
AuthorDate: Wed Nov 4 08:19:44 2026 +0800
[SPARK-60835][GRAPHX] Break label propagation ties with the lowest label
### What changes were proposed in this pull request?
When multiple labels have the same maximum frequency, GraphX label
propagation now selects the lowest label instead of the highest. The
implementation documents this rule and the tests cover positive labels,
negative labels, signed vertex ID limits, and frequency priority.
### Why are the changes needed?
Choosing the lowest tied label preserves deterministic results while
aligning GraphX with GraphFrames and Spark SQL's deterministic `mode`, as
discussed in [Sem's review
comments](https://github.com/apache/spark/pull/60026#issuecomment-6592081340).
### Does this PR introduce _any_ user-facing change?
Yes. Compared with the unreleased change in #48871, equal-frequency labels
now resolve to the lowest label. For example, if vertex 0 receives labels 1 and
2 once each, it selects label 1 instead of label 2.
### How was this patch tested?
```
build/sbt 'graphx/testOnly
org.apache.spark.graphx.lib.LabelPropagationSuite' \
'graphx/scalastyle' 'graphx/Test/scalastyle'
```
All 5 tests and both style checks passed. The three tie-breaking cases were
also verified to fail against the previous highest-label implementation.
### Was this patch authored or co-authored using generative AI tooling?
Generated-by: OpenAI Codex (GPT-6)
Closes #60050 from zhengruifeng/graphx-lowest-label-tie-breaking.
Authored-by: Ruifeng Zheng <[email protected]>
Signed-off-by: Ruifeng Zheng <[email protected]>
(cherry picked from commit ce43048a06944e80cdebbcd7a09ce06e1c5d5064)
Signed-off-by: Ruifeng Zheng <[email protected]>
---
.../apache/spark/graphx/lib/LabelPropagation.scala | 4 ++--
.../spark/graphx/lib/LabelPropagationSuite.scala | 23 ++++++++++++++++++++++
2 files changed, 25 insertions(+), 2 deletions(-)
diff --git
a/graphx/src/main/scala/org/apache/spark/graphx/lib/LabelPropagation.scala
b/graphx/src/main/scala/org/apache/spark/graphx/lib/LabelPropagation.scala
index 9d4af50474a8..dc23d9f77ac0 100644
--- a/graphx/src/main/scala/org/apache/spark/graphx/lib/LabelPropagation.scala
+++ b/graphx/src/main/scala/org/apache/spark/graphx/lib/LabelPropagation.scala
@@ -29,7 +29,7 @@ object LabelPropagation {
*
* Each node in the network is initially assigned to its own community. At
every superstep, nodes
* send their community affiliation to all neighbors and update their state
to the mode community
- * affiliation of incoming messages.
+ * affiliation of incoming messages. Ties are broken by choosing the
smallest label.
*
* LPA is a standard community detection algorithm for graphs. It is very
inexpensive
* computationally, although (1) convergence is not guaranteed and (2) one
can end up with
@@ -62,7 +62,7 @@ object LabelPropagation {
map
}
def vertexProgram(vid: VertexId, attr: Long, message: Map[VertexId,
Long]): VertexId = {
- if (message.isEmpty) attr else message.maxBy{ case (key, value) =>
(value, key) }._1
+ if (message.isEmpty) attr else message.minBy { case (key, value) =>
(-value, key) }._1
}
val initialMessage = Map[VertexId, Long]()
Pregel(lpaGraph, initialMessage, maxIterations = maxSteps)(
diff --git
a/graphx/src/test/scala/org/apache/spark/graphx/lib/LabelPropagationSuite.scala
b/graphx/src/test/scala/org/apache/spark/graphx/lib/LabelPropagationSuite.scala
index 95f85d92fca9..a55c68f96505 100644
---
a/graphx/src/test/scala/org/apache/spark/graphx/lib/LabelPropagationSuite.scala
+++
b/graphx/src/test/scala/org/apache/spark/graphx/lib/LabelPropagationSuite.scala
@@ -41,4 +41,27 @@ class LabelPropagationSuite extends SparkFunSuite with
LocalSparkContext {
assert(clique1Labels(0) != clique2Labels(0))
}
}
+
+ gridTest("Label propagation breaks label ties with the lowest vertex ID")(
+ Seq((1L, 2L), (-2L, -1L), (Long.MinValue, Long.MaxValue))) { case (label1,
label2) =>
+ withSpark { sc =>
+ val edges = Seq(Edge(0L, label1, 1), Edge(0L, label2, 1))
+ val graph = Graph.fromEdges(sc.parallelize(edges), 1)
+
+ val labels = LabelPropagation.run(graph, 1).vertices.collect().toSet
+
+ assert(labels === Set((0L, math.min(label1, label2)), (label1, 0L),
(label2, 0L)))
+ }
+ }
+
+ test("Label propagation chooses the most frequent label before breaking
ties") {
+ withSpark { sc =>
+ val edges = Seq(Edge(0L, 1L, 1), Edge(0L, 2L, 1), Edge(0L, 2L, 1))
+ val graph = Graph.fromEdges(sc.parallelize(edges), 1)
+
+ val labels = LabelPropagation.run(graph, 1).vertices.collect().toSet
+
+ assert(labels === Set((0L, 2L), (1L, 0L), (2L, 0L)))
+ }
+ }
}
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]