[
https://issues.apache.org/jira/browse/SPARK-42856?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
ASF GitHub Bot updated SPARK-42856:
-----------------------------------
Labels: pull-request-available (was: )
> Inconsistent output from label propagation algorithm in Graph X due to
> tie-breaking logic in vertexProgram
> ----------------------------------------------------------------------------------------------------------
>
> Key: SPARK-42856
> URL: https://issues.apache.org/jira/browse/SPARK-42856
> Project: Spark
> Issue Type: Bug
> Components: GraphX
> Affects Versions: 1.1.0, 3.3.2
> Reporter: Mohammadreza Haghpanah
> Priority: Major
> Labels: pull-request-available
>
> We are experiencing inconsistent output from the label propagation algorithm
> in Graph X. When we run the algorithm on the same input, we observe different
> outputs each time. This behavior is unexpected since the algorithm is not
> designed to be random, and we should be getting the same output for the same
> input.
> We suspect that the issue lies in the tie-breaking logic used by the
> [vertexProgram|https://github.com/apache/spark/blob/master/graphx/src/main/scala/org/apache/spark/graphx/lib/LabelPropagation.scala#L65]
> when picking labels. Currently, the vertexProgram chooses the label with the
> maximum frequency, and in case of a tie, it selects the label that appears
> first. This logic does not handle tie cases correctly, resulting in different
> outputs for the same input.
> {code:scala}
> def vertexProgram(vid: VertexId, attr: Long, message: Map[VertexId, Long]):
> VertexId = {
> if (message.isEmpty) attr else message.maxBy(_._2)._1
> }
> {code}
> To solve this issue, we propose changing the tie-breaking logic to something
> like vertex ID. This change will ensure that the same label is always
> selected in case of a tie, resulting in consistent output from the algorithm
> for the same input.
> {code:scala}
> def vertexProgram(vid: VertexId, attr: Long, message: Map[VertexId, Long]):
> VertexId = {
> if (message.isEmpty) attr else message.maxBy{ case (key, value) =>
> (value, key) }._1
> }
> {code}
> Thanks!
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
