11. label_propagation - fast seeded communities

what this does

label_propagation gives every node the label held by most of its neighbours and repeats until the labels stop moving. GET /v1/tenants/:t/graph/:schema/label_propagation returns one row per node with the label it converged to. It is far cheaper than louvain and far less stable: the algorithm is order-sensitive, so the engine shuffles visit order from a seeded generator, and the seed is what makes a run repeatable.

when to use it

• A cheap first look at community structure on a graph too large to be worth a modularity pass.
• Recomputing a grouping often, where near-linear cost matters more than the quality of the partition.
• A cross-check against louvain. Where the two agree the grouping is robust; where they disagree the boundary is genuinely fuzzy.

schema requirement

The relation must be declared in the schema's [[relations]] block and must target the table it is declared on. See schemas/reference#relations.

the request

rel is required and max_iter defaults to 20. seed is optional in the protocol but effectively mandatory in practice: omit it and the engine picks the current unix timestamp, and because the response does not echo the seed back, an unseeded run can never be reproduced or explained afterwards.

curl -G "https://$OC_HOST/v1/tenants/$OC_TENANT/graph/social.users/label_propagation" \
  --data-urlencode "rel=follows" \
  --data-urlencode "max_iter=20" \
  --data-urlencode "seed=42" \
  -H "Authorization: Bearer $OC_TOKEN"

labels = db.graph.label_propagation(
    "social.users",
    rel="follows",
    seed=42,
    max_iter=20,
)
# The wire `pk` is an array, so the SDK keys the dict by its JSON
# encoding: {'["alice"]': 0, '["heidi"]': 7, ...}

// The TypeScript SDK does not wrap the graph algorithms - use fetch.
const qs = new URLSearchParams({
  rel: "follows",
  max_iter: "20",
  seed: "42",
});
const res = await fetch(
  `https://${OC_HOST}/v1/tenants/${OC_TENANT}/graph/social.users/label_propagation?${qs}`,
  { headers: { Authorization: `Bearer ${OC_TOKEN}` } },
);
const rows = await res.json();

// The Go SDK does not wrap the graph algorithms - use net/http.
url := "https://" + OC_HOST + "/v1/tenants/" + OC_TENANT +
    "/graph/social.users/label_propagation?rel=follows&max_iter=20&seed=42"

req, _ := http.NewRequestWithContext(ctx, "GET", url, nil)
req.Header.Set("Authorization", "Bearer "+OC_TOKEN)

resp, _ := http.DefaultClient.Do(req)
defer resp.Body.Close()

var rows []struct {
    PK    []string `json:"pk"`
    Label uint64   `json:"label"`
}
json.NewDecoder(resp.Body).Decode(&rows)

what you get back

[
  { "pk": ["alice"],   "label": 0 },
  { "pk": ["bob"],     "label": 0 },
  { "pk": ["carol"],   "label": 0 },
  { "pk": ["dave"],    "label": 0 },
  { "pk": ["heidi"],   "label": 7 },
  { "pk": ["ivan"],    "label": 7 },
  { "pk": ["judy"],    "label": 7 },
  { "pk": ["mallory"], "label": 10 }
]

One row per node, ordered by primary key. pk is the primary-key array and label is an unsigned integer. Labels start as one-per-node identifiers and most of them die off during convergence, so the surviving values are not contiguous and carry no ordering - the only thing a label means is equality. Two nodes with the same label are in the same community.

how it works

• Every node starts with its own label. Each round visits nodes in a shuffled order and moves each node to whichever label most of its neighbours hold.
• The shuffle is the only thing the seed drives. Ties within a tally are broken deterministically by the smaller label, so the same seed on the same graph gives byte-identical output.
• The pass repeats until no label changes or max_iter rounds have run. There is no convergence guarantee, which is exactly why the iteration cap exists.
• Self-loops are ignored - a node never votes for itself by force.
• max_iter=0 is refused with a 400 rather than returning an unconverged answer.