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:

Each node starts with a unique label.
These labels propagate through the network.
At each iteration, nodes update their label to the most frequent label among their neighbors.
This process repeats until no label changes or a set maximum number of iterations is reached.
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.

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.

Procedure implementation¶

To find the community labels for each node based on the most frequent label among their neighbors, a procedure is created to implement the LPA.

The procedure treats Knows edges as undirected and uses active set variables 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. 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	The label of each node.
`node_count`	Node-attached SumAgg aggregator value variable	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	A mapping used to count the occurrences of each label among the neighbors of a node.
`changed`	Node-attached OrAgg aggregator value variable	Whether the node's label changed in this round. Overwritten each time the node is recomputed.
`changed_set`	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	Nodes to recompute in this round: the neighbors of nodes in `changed_set`.
`result_file`	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	A global boolean flag indicating whether any updates occurred in the current iteration; determines whether to continue iterating.
`iter`	Primitive value variable	The count of the iterations the algorithm has performed.
`cur_iter`	Primitive value variable	The index used to iterate over `label_count_list`.
`label_count_list`	Primitive 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 (boolean)	Whether this recomputation updated the node's label. Used to overwrite `changed`.

The following steps outline the logic of the procedure:

Initialize node_label to its own ID for each node and add all nodes to changed_set to start the first round.
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.
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 to check where to run commands and how the directory is mounted.

1. Prepare graph data¶

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)
    }
'''

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

lpa_node.csv: Node data.
lpa_edge.csv: Edge data.

Preview the CSV files

lpa_node.csv

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

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 before continuing.

2. Create a procedure¶

Create a procedure to implement the LPA. For more information about the procedure, see 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 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).