Label Propagation

Overview

The Label Propagation algorithm (LPA) is a community detection method based on label propagation. Initially, each node is assigned a label. During each iteration, every node updates its label to the one most common among its neighbors. Through this iterative process, densely connected groups of nodes tend to reach a consensus on a shared label, with nodes sharing the same label ultimately forming a community.

LPA does not optimize any specific predefined measure of community quality, nor does it require the number of communities to be specified in advance. Instead, it relies purely on the network's structure to guide the progression. Its simplicity makes LPA highly efficient for analyzing large and complex networks.

Related material of the algorithm:

• U.N. Raghavan, R. Albert, S. Kumara, Near linear time algorithm to detect community structures in large-scale networks (2007)

Concepts

Label

Label of a node is initialized with a specified property value or its unique UUID.

Nodes sharing the same label at the end of the algorithm are considered members of the same community.

Label Propagation

In the simplest setting, at each propagation iteration, a node updates its label to the one held by the largest number of its neighbors.

For example, in the diagram below, the blue node’s label will change from d to c.

When node and edge weights are considered, the label weight is calculated as the sum of the products of corresponding node and edge weights. In this case, each node updates its label to the one with the highest total weight.

As the weights of nodes and edges shown in the example below, the label of the blue node will be updated from d to a.

Multi-label Propagation

In multi-label propagation, each node can hold multiple labels simultaneously. In this case, each label is assigned a label probability proportional to its weight, while the sum of all label probabilities for each node equals 1.

In the example below, each node keeps 2 labels with their probabilities written next to them. The labels of the blue node will be updated from d, c to a, c with label probabilities P_a = 6.3/(6.3+1.85) = 0.77 and P_c = 1.85/(6.3+1.85) = 0.23.

Considerations

• The LPA algorithm treats all edges as undirected, ignoring their original direction.
• A Node with self-loops propagates its current label(s) to itself, with each self-loop counted twice.
• The LPA algorithm follows a synchronous update principle, where all nodes update their labels simultaneously based on their neighbors' current labels. However, in some cases—especially in bipartite graphs—label oscillations may occur. To address this issue, LPA incorporates an interrupt mechanism that detects and prevents excessive oscillations.
• Due to factors such as the order of nodes, the random selection among labels with equal weights and parallel computations, the community detection results of LPA may vary between runs.

Example Graph

Run the following statements on an empty graph to define its structure and insert data:

GQLUQL
ALTER GRAPH CURRENT_GRAPH ADD NODE {
  user ({interest string, level int32})
};
ALTER GRAPH CURRENT_GRAPH ADD EDGE {
  connect ()-[{strength int32}]->()
};
INSERT (A:user {_id:"A",interest:"flute",level:2}),
       (B:user {_id:"B",interest:"football",level:4}),
       (C:user {_id:"C",interest:"piano",level:4}),
       (D:user {_id:"D",interest:"violin",level:2}),
       (E:user {_id:"E",interest:"piano",level:4}),
       (F:user {_id:"F",interest:"movie",level:1}),
       (G:user {_id:"G",interest:"piano",level:4}),
       (H:user {_id:"H",interest:"tennis",level:2}),
       (I:user {_id:"I",interest:"violin",level:3}),
       (J:user {_id:"J",interest:"badminton",level:5}),
       (K:user {_id:"K",interest:"swimming",level:4}),
       (L:user {_id:"L",interest:"cello",level:1}),
       (M:user {_id:"M",interest:"saxophone",level:2}),
       (N:user {_id:"N",interest:"novel",level:3}),
       (O:user {_id:"O",interest:"swimming",level:3}),
       (A)-[:connect {strength:3}]->(B),
       (A)-[:connect {strength:5}]->(C),
       (A)-[:connect {strength:8}]->(F),
       (A)-[:connect {strength:6}]->(K),
       (B)-[:connect {strength:2}]->(C),
       (C)-[:connect {strength:9}]->(D),
       (D)-[:connect {strength:5}]->(A),
       (D)-[:connect {strength:6}]->(E),
       (E)-[:connect {strength:5}]->(A),
       (F)-[:connect {strength:9}]->(G),
       (F)-[:connect {strength:4}]->(J),
       (G)-[:connect {strength:10}]->(H),
       (H)-[:connect {strength:3}]->(F),
       (I)-[:connect {strength:2}]->(F),
       (I)-[:connect {strength:4}]->(H),
       (J)-[:connect {strength:1}]->(I),
       (K)-[:connect {strength:1}]->(F),
       (K)-[:connect {strength:10}]->(N),
       (L)-[:connect {strength:1}]->(M),
       (L)-[:connect {strength:4}]->(N),
       (M)-[:connect {strength:10}]->(K),
       (M)-[:connect {strength:8}]->(N),
       (N)-[:connect {strength:4}]->(M),
       (O)-[:connect {strength:1}]->(N);

Running on HDC Graphs

Creating HDC Graph

To load the entire graph to the HDC server hdc-server-1 as my_hdc_graph:

GQLUQL
CREATE HDC GRAPH my_hdc_graph ON "hdc-server-1" OPTIONS {
  nodes: {"*": ["*"]},
  edges: {"*": ["*"]},
  direction: "undirected",
  load_id: true,
  update: "static"
}

Parameters

Algorithm name: lpa

File Writeback

GQLUQL
CALL algo.lpa.write("my_hdc_graph", {
  return_id_uuid: "id",
  k: 2,
  loop_num: 5,
  edge_weight_property: 'strength'
}, {
  file: {
    filename: "lpa"
  }
})

DB Writeback

Writes each label_<N> and the corresponding probability_<N> from the results to the specified node properties. The property types are string and float, respectively.

GQLUQL
CALL algo.lpa.write("my_hdc_graph", {
  node_label_property: 'interest',
  k: 2,
  loop_num: 10
}, {
  db: {
    property: "lab"
  }
})

The label and label probability of each node is written to new properties lab_1, probability_1, lab_2, and probability_2.

Stats Writeback

GQLUQL
CALL algo.lpa.write("my_hdc_graph", {
  node_label_property: 'interest',
  k: 2,
  loop_num: 10
}, {
  stats: {}
})

Result:

Full Return

GQLUQL
CALL algo.lpa.run("my_hdc_graph", {
  return_id_uuid: "id",
  node_label_property: "@user.interest",
  k: 2
}) YIELD r
RETURN r

Result:

Stream Return

GQLUQL
CALL algo.lpa.stream("my_hdc_graph", {
  return_id_uuid: "id",
  node_label_property: "@user.interest",
  node_weight_property: "@user.level",
  edge_weight_property: "strength",
  loop_num: 10
}) YIELD r
RETURN r.label_1 AS label, count(r) GROUP BY label

Result:

Stats Return

GQLUQL
CALL algo.lpa.stats("my_hdc_graph", {
  node_label_property: "interest",
  edge_weight_property: "strength",
  k: 1,
  loop_num: 5
}) YIELD s
RETURN s

Result:

Running on Distributed Projections

Creating Distributed Projection

To project the entire graph to its shard servers as myProj:

GQLUQL
CREATE PROJECTION myProj OPTIONS {
  nodes: {"*": ["*"]}, 
  edges: {"*": ["*"]},
  direction: "undirected",
  load_id: true
}

Parameters

Algorithm name: lpa

File Writeback

UQL
algo(lpa).params({
  projection: "myProj",
  loop_num: 5,
  edge_weight_property: 'strength'
}).write({
  file: {
    filename: "lpa"
  }
})

DB Writeback

Writes each label_<N> and the corresponding probability_<N> from the results to the specified node properties. The property types are string and float, respectively.

GQLUQL
CALL algo.lpa.write("myProj", {
  node_label_property: 'interest',
  loop_num: 10
}, {
  db: {
    property: "lab"
  }
})