Leiden
UDTF: cugraph_leiden
Official cuGraph reference: C API
Find modularity-based communities with a refinement step, and split each community into the connected components of its internal edges, so every returned community induces a connected subgraph.
Quickstart
The call below supplies edges from registered relation target_edges with canonical src and dst columns and may include weight.
SELECT *
FROM cugraph_leiden(
edges => (SELECT src, dst FROM target_edges)
);
Inputs
Every relation is a named parenthesized SELECT subquery. The required edges role uses canonical src and dst columns. Every role, its canonical columns, and their accepted Arrow types are listed under Relation arguments. Metadata validation resolves registered tables named in its JSON request.
The vertex-ID types this UDTF accepts, the numeric types a per-call codebook maps to native ids, and its string-key limits are listed in Vertex ID support; the concrete call-specific schema comes from gpu_validate_call.
Arguments and options
Relation arguments
Every edge_id column must have the integer type of src and dst; string-keyed graphs accept no edge IDs.
Named value arguments
Graph construction options
This UDTF requires directed=false (undirected/symmetric graph). All other graph construction options follow the shared defaults documented in Graph Construction Options.
Output
These are generic descriptor schemas. Run gpu_validate_call to get the concrete, table-specific output schema.
Examples
- MerRec
- Citation network
Which brands belong on the same discovery page?
The query groups brands by overlapping audiences, including combinations that cross catalog categories. It uses May to October 2023 likes: a fan is a distinct shopper who liked a brand.
SQL reduces 182,889,825 like events to user-brand pairs and selects the 5,000 brands with the most fans. Jaccard measures shared audience divided by combined audience for each brand pair. Similarities of at least 0.02 become edges for Leiden. The resulting groups join back to brand names. Leiden uses the retained connections and currently ignores edge weights.
WITH fans AS (
SELECT -(e.user_id + 1) AS src, CAST(i.brand_id AS BIGINT) AS dst
FROM merrec_events e JOIN merrec_items i ON i.item_id = e.item_id
WHERE e.event_type = 'item_like' AND i.brand_id <> 0
GROUP BY e.user_id, i.brand_id
), top_brands AS (
SELECT dst AS brand_id, COUNT(*) AS fans FROM fans GROUP BY dst ORDER BY fans DESC, dst LIMIT 5000
), worlds AS (
SELECT vertex AS brand_id, community AS world
FROM cugraph_leiden(
edges => (
SELECT first AS src, second AS dst, CAST(similarity AS DOUBLE) AS weight
FROM cugraph_jaccard(
edges => (SELECT src, dst FROM fans),
vertex_pairs => (SELECT a.brand_id AS first, b.brand_id AS second
FROM top_brands a JOIN top_brands b ON a.brand_id < b.brand_id),
directed => false)
WHERE similarity >= 0.02),
directed => false, resolution => 3, seed => 42)
), members AS (
SELECT w.world, n.brand_name, t.fans
FROM worlds w
JOIN top_brands t ON t.brand_id = w.brand_id
JOIN (SELECT CAST(brand_id AS BIGINT) AS brand_id, MIN(brand_name) AS brand_name
FROM merrec_items WHERE brand_id <> 0 GROUP BY brand_id) n ON n.brand_id = w.brand_id
), ranked AS (
SELECT world, brand_name, fans,
ROW_NUMBER() OVER (PARTITION BY world ORDER BY fans DESC, brand_name) AS rk,
COUNT(*) OVER (PARTITION BY world) AS brands,
SUM(fans) OVER (PARTITION BY world) AS fan_links
FROM members
)
SELECT world, brands, fan_links, rk, brand_name, fans
FROM ranked
WHERE rk <= 5 AND brands >= 15
ORDER BY fan_links DESC, rk;
The query returns five leading brands for each of 38 groups with at least 15 members. Three selected groups illustrate different audience relationships:
The 101-brand group places power tools beside kitchen appliances, providing a candidate home-project collection to inspect.
The saved capture contains every returned group and the execution record. Leiden returned the same groups in all 4 runs under different group numbers.
Would another community algorithm split our largest research groups?
A research catalog may use citation communities to organize a field into reading groups. Before treating those groups as fixed boundaries, compare Louvain and Leiden on the same 2010s AI subgraph of the citation network. For each large Louvain group, this query counts how many Leiden groups contain at least 50 of its papers. The overlap measures sensitivity to the choice of algorithm.
CREATE OR REPLACE VIEW ai_nodes AS
SELECT paper_id FROM papers
WHERE year >= 2010 AND primary_fos IN (
'Deep learning', 'Artificial neural network', 'Convolutional neural network',
'Recurrent neural network', 'Natural language processing',
'Reinforcement learning', 'Image segmentation', 'Feature extraction',
'Object detection', 'Speech recognition');
CREATE OR REPLACE VIEW ai_edges AS
SELECT e.src, e.dst
FROM citation_edges e
JOIN ai_nodes a ON a.paper_id = e.src
JOIN ai_nodes b ON b.paper_id = e.dst;
WITH lv AS (
SELECT vertex, community AS louvain_c FROM cugraph_louvain(edges => (SELECT src, dst FROM ai_edges))),
ld AS (
SELECT vertex, community AS leiden_c FROM cugraph_leiden(edges => (SELECT src, dst FROM ai_edges))),
joint AS (
SELECT lv.louvain_c, ld.leiden_c, COUNT(*) AS n
FROM lv JOIN ld ON ld.vertex = lv.vertex
GROUP BY lv.louvain_c, ld.leiden_c)
SELECT louvain_c,
SUM(n) AS members,
COUNT(*) FILTER (WHERE n >= 50) AS leiden_parts
FROM joint
GROUP BY louvain_c
HAVING SUM(n) > 2500
ORDER BY leiden_parts DESC, members DESC;
In this capture, the largest Louvain group overlaps five Leiden groups with
at least 50 papers each. A leiden_parts value of 1 allows smaller fragments
below that threshold. It does not establish that the group remained intact.
Community IDs are local labels, and membership can vary between GPU runs even
with a fixed seed. Compare the membership of papers, rather than label values
from separate executions.
Limits
- seed sets the random choices in the refinement step; the same seed does not guarantee identical communities across runs