Source: https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/lpa/
Documentation version: v5.3.2

# Label Propagation Algorithm (LPA)

## Algorithm introduction

The Label Propagation Algorithm (LPA) is a community detection algorithm for graphs. It operates by propagating labels and forming communities through the network based on the labels of neighboring nodes. The algorithm starts with each node assigned a unique label, and iteratively updates the labels of nodes based on the most frequent label among their neighbors.

The working principle of the algorithm is that labels tend to remain within densely connected groups of nodes and have difficulty spreading across sparsely connected regions. As labels propagate, only a few labels will remain, while most labels will disappear until convergence. At the end, nodes that share the same label are grouped together as a community.

The key steps of the LPA are as follows:

1. Each node starts with a unique label.
2. These labels propagate through the network.
3. At each iteration, nodes update their label to the most frequent label among their neighbors.
4. This process repeats until no label changes or a set maximum number of iterations is reached.
5. The final output contains the community label for each node, representing the detected communities in the graph.

For more information about LPA, see [Label propagation algorithm](https://en.wikipedia.org/wiki/Label_propagation_algorithm).

## Data model

To implement the LPA in GQL, the following data model is used to create a graph type:

- Persons are represented as nodes of type `Person`. Each node is assigned an initial label represented by their own `id`.
- Relationships between persons are encoded as edges of type `Knows`. These edges connect the nodes and serve as conduits for label propagation, enabling the diffusion of labels across the network.

For the complete definition of the graph type, see [Prepare graph data](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/lpa/#1_prepare_graph_data).

## Procedure implementation

To find the community labels for each node based on the most frequent label among their neighbors, a [procedure](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/procedures/create/) is created to implement the LPA.

The procedure treats `Knows` edges as undirected and uses [active set variables](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/active-set-variable/) to track nodes whose labels change. Each round recomputes labels only for the neighbors of those nodes, reducing edge scans as the graph converges. Each recomputed node still counts labels from all its neighbors, including those whose labels did not change. The label selection and update rules remain the same as in the full-scan version.

For the complete definition of the procedure, see [Create a procedure](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/lpa/#2_create_a_procedure). The following section describes the key elements of the procedure and how it works.

The procedure takes the following input parameter:

- `max_iter`: The maximum number of iterations to perform.

Additionally, the following variables are defined within the procedure:

 | Variable name | Variable type | Description
 | `node_label` | Node-attached [SumAgg aggregator value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | The label of each node.
 | `node_count` | Node-attached [SumAgg aggregator value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | The neighbor count for the label when the node's label was last updated. Starts at `0` and is used to decide whether to update the label.
 | `label_count_map` | Node-attached [MapAgg aggregator value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/agg/map_agg/) | A mapping used to count the occurrences of each label among the neighbors of a node.
 | `changed` | Node-attached [OrAgg aggregator value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/agg/or_agg/) | Whether the node's label changed in this round. Overwritten each time the node is recomputed.
 | `changed_set` | [Active set variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/active-set-variable/) | Nodes whose labels changed in the previous round. Initially contains all nodes, then is replaced each round with the nodes whose labels changed in that round.
 | `recompute_set` | [Active set variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/active-set-variable/) | Nodes to recompute in this round: the neighbors of nodes in `changed_set`.
 | `result_file` | [File variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/file-variable/) | The file that saves the final node labels, including the node's ID and their final community labels.
 | `new_active` | Global [OrAgg aggregator value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/agg/or_agg/) | A global boolean flag indicating whether any updates occurred in the current iteration; determines whether to continue iterating.
 | `iter` | [Primitive value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/value-variable/) | The count of the iterations the algorithm has performed.
 | `cur_iter` | [Primitive value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/value-variable/) | The index used to iterate over `label_count_list`.
 | `label_count_list` | [Primitive value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/value-variable/) (list of records) | Label counts read from `label_count_map`. Each record contains a label in `_0` and its count in `_1`.
 | `did_change` | [Primitive value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/value-variable/) (boolean) | Whether this recomputation updated the node's label. Used to overwrite `changed`.

The following steps outline the logic of the procedure:

1. Initialize `node_label` to its own ID for each node and add all nodes to `changed_set` to start the first round.
2. Repeat while `new_active` is `true` and the iteration count is less than the maximum number of iterations (specified by `max_iter`):

  1. Set `new_active` to `false` and increment the iteration counter.
  2. Find nodes to recompute: Traverse from nodes in `changed_set` and collect their neighbors into `recompute_set`, replacing the previous round's set.
  3. Recompute labels: For each node `t` in `recompute_set`, aggregate labels from all its neighbors `s` into its `label_count_map`. Select the most frequent label from `label_count_list`, choosing the largest label value in a tie. Update the node's label and `node_count` only if the candidate label differs from its current label and its count exceeds `node_count`, or if the counts are equal and the candidate label is larger. Set `new_active` to `true` when a label changes. Overwrite the node's `changed` flag with `did_change`, then clear the label count map.
  4. Update the changed set: Select nodes in `recompute_set` whose `changed` flag is `true` and replace `changed_set` with these nodes for the next round.

3. After convergence or reaching the iteration limit, export each node's ID and its final corresponding community label ID to `result_file`.

Isolated nodes have no neighbors and never enter `recompute_set`. Their final labels remain their own IDs.

## Steps

Run the following code blocks in order in the NebulaGraph Studio CONSOLE. For first-time setup, follow [Prepare algorithm sample data](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/prepare-data/) to check where to run commands and how the directory is mounted.

### 1. Prepare graph data

1. 

Create a graph type that matches your data model.

````
'''
CREATE GRAPH TYPE IF NOT EXISTS lpa_graph_type AS {
    NODE Person (LABEL Person {id INT PRIMARY KEY}),
    EDGE Knows (Person)-[LABEL Knows {MULTIEDGE KEY ()}]->(Person)
    }
'''

````

2. 

Download these CSV files and save them with their original names in `examples/algorithms/lpa/` under your deployment directory:

  - [lpa_node.csv](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/files/lpa/lpa_node.csv): Node data.
  - [lpa_edge.csv](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/files/lpa/lpa_edge.csv): Edge data.

Preview the CSV files

lpa_node.csv

````
id
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

````

lpa_edge.csv

````
src,dst
0,1
0,2
0,3
0,4
0,5
0,6
0,7
0,8
0,10
0,11
0,12
0,13
0,17
0,19
0,21
0,31
1,2
1,3
1,7
1,13
1,17
1,19
1,21
1,30
2,3
2,7
2,8
2,9
2,13
2,27
2,28
2,32
3,7
3,12
3,13
4,6
4,10
5,6
5,10
5,16
6,16
8,30
8,32
8,33
9,33
13,33
14,32
14,33
15,32
15,33
18,32
18,33
19,33
20,32
20,33
22,32
22,33
23,25
23,27
23,29
23,32
23,33
24,25
24,27
24,31
25,31
26,29
26,33
27,33
28,31
28,33
29,32
29,33
30,32
30,33
31,32
31,33
32,33

````

3. 

Create a temporary graph based on the graph type and load the data files into the temporary graph.

````
CREATE TEMPORARY GRAPH IF NOT EXISTS #lpa_graph TYPED lpa_graph_type

````

````
'''
USE #lpa_graph IMPORT INTO GRAPH {
    NODE (v@Person {id: id}) FROM DATAFILE {
        PATH: "file:///examples/algorithms/lpa/lpa_node.csv",
        FORMAT: "CSV",
        DELIMITER: ','
    },
    EDGE (id: src)-[e@Knows{}]->(id: dst) FROM DATAFILE {
        PATH: "file:///examples/algorithms/lpa/lpa_edge.csv",
        FORMAT: "CSV",
        DELIMITER: ','
    }
    }
'''

````

After the import succeeds, run this query in the console to check the node count:

````
'''
USE #lpa_graph
MATCH (n)
RETURN count(n) AS node_count
'''

````

The expected `node_count` is `34`. If it differs, [check the files and import results](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/prepare-data/#troubleshooting) before continuing.

### 2. Create a procedure

Create a procedure to implement the LPA. For more information about the procedure, see [Procedure implementation](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/lpa/#procedure_implementation).

````
'''
CREATE OR REPLACE PROCEDURE lpa (max_iter INT) RETURNS () AS {
        NODE VALUE node_label      SumAgg<INT> = 0
        NODE VALUE node_count      SumAgg<INT> = 0
        NODE VALUE label_count_map MapAgg<INT, SumAgg<INT>>
        NODE VALUE changed         OrAgg = false
        FILE       result_file     {id INT, label_id INT}= DATAFILE {
                                    PATH: "file:///examples/algorithms/lpa/output",
                                    FORMAT: "CSV"
                                    }
        VALUE      new_active      OrAgg = true
        VALUE      iter = 0
        VALUE      changed_set     ACTIVE_SET
        VALUE      recompute_set   ACTIVE_SET

        MATCH (a@Person)
        PER NODE (a) {
          SET a.@node_label = a.id
        }
        FINALLY {
          SET changed_set = a
        }

        WHILE @new_active AND iter < max_iter THEN {
          SET @new_active = false
          SET iter = iter + 1

          // P1: collect neighbours of nodes whose labels changed last round
          MATCH (c@Person)-[@Knows]-(t@Person)
          WHERE c IN changed_set
          FINALLY {
            SET recompute_set = t
          }

          // P2: count all neighbour labels for the nodes in recompute_set
          MATCH (t@Person)-[@Knows]-(s@Person)
          WHERE t IN recompute_set
          PER PATH {
            SET t.@label_count_map += TUPLE(s.@node_label, 1)
          }
          PER NODE (t) {
            VALUE max_count INT = 0
            VALUE max_label INT = -1
            VALUE cur_iter = 0
            VALUE did_change = false
            VALUE label_count_list = t.@label_count_map
            WHILE cur_iter < length(label_count_list) THEN {
              VALUE val = label_count_list[cur_iter]
              IF val._1 > max_count OR val._1 = max_count AND val._0 > max_label THEN {
                SET max_count = val._1
                SET max_label = val._0
              }
              SET cur_iter = cur_iter + 1
            }
            IF max_label <> -1 AND (max_count > t.@node_count AND max_label <> t.@node_label
             OR max_count = t.@node_count AND max_label > t.@node_label
            ) THEN {
              SET @new_active += true
              SET t.@node_count = max_count
              SET t.@node_label = max_label
              SET did_change = true
            }
            SET t.@changed = did_change
            SET t.@label_count_map.clear()
          }

          // P3: keep only nodes whose labels changed this round
          MATCH (t@Person)
          WHERE t IN recompute_set AND t.@changed = true
          FINALLY {
            SET changed_set = t
          }
        }

        MATCH (a@Person)
        PER NODE (a) {
          EXPORT a.id, a.@node_label INTO result_file
        }
      }
'''

````

### 3. Call your procedure

Call the procedure to find the final community labels for each node. The following examples set the maximum number of iterations to `10`.

````
USE #lpa_graph CALL lpa(10) FINISH

````

This call writes the results to CSV files and does not return a table in the console.

On the Docker host, open the CSV files in `examples/algorithms/lpa/output/` under your deployment directory. Example contents:

````
"id","label_id"
0,33
1,33
2,33
3,33
4,31
5,31
6,31
7,33
8,33
9,33
10,31
11,33
12,33
13,33
14,33
15,33
16,31
17,33
18,33
19,33
20,33
21,33
22,33
23,33
24,33
25,33
26,33
27,33
28,33
29,33
30,33
31,33
32,33
33,33

````

`id` represents the initial node label, and `label_id` represents the final community label assigned to that node.

Write results to a graph

If you want to persist LPA results in a graph, follow [EXPORT](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/in-out/export/) and adapt the write-back schema for LPA:

- Export LPA result fields to a table variable first (typically `id` and `label_id`).
- For a remote graph, split rows with `table_split(...)` and send batched `USE + INSERT` statements through `nebula_exec`.

Define the target graph type to store the final community label (for example, a `community_id` property on `Person`).