Weakly Connected Components
UDTF: cugraph_weakly_connected_components
Official cuGraph reference: C API
Label maximal connected subgraphs after treating directed edges as undirected.
Quickstart
The call below supplies edges from registered relation target_edges with canonical src and dst columns and may include weight.
SELECT *
FROM cugraph_weakly_connected_components(
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.
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
Is session_id a per-user session key?
The events table has a session_id column, and grouping by it looks like
the obvious way to build sessions. A graph checks that assumption before
any session analysis depends on it. A standard GROUP BY session_id HAVING COUNT(DISTINCT user_id) > 1
identifies whether session IDs collide, but does not calculate transitive collisions across multiple keys and users.
Constructing a bipartite graph between users and session IDs and computing Weakly Connected Components (WCC) uncovers transitive chains. If User A shares Session 1 with User B, and User B shares Session 2 with User C, WCC assigns all three to one component. If every session ID belonged to an isolated user, every connected component would contain exactly one user.
Graph vertices can be strings, so a user vertex is user: followed by the
user ID and a session vertex is the session ID itself. The two kinds cannot
collide. The query groups the components by how many users they contain.
WITH october AS (
SELECT DISTINCT user_id, session_id
FROM merrec_events
WHERE event_time >= TIMESTAMP '2023-10-01 00:00:00'
), components AS (
SELECT vertex, component FROM cugraph_weakly_connected_components(
edges => (SELECT CONCAT('user:', CAST(user_id AS VARCHAR)) AS src, session_id AS dst FROM october),
directed => false)
), user_components AS (
SELECT component, COUNT(*) AS users FROM components WHERE STARTS_WITH(vertex, 'user:') GROUP BY component
)
SELECT CASE WHEN users = 1 THEN '1 user'
WHEN users <= 10 THEN '2-10 users'
WHEN users <= 1000 THEN '11-1,000 users'
ELSE 'over 1,000 users' END AS component_size,
COUNT(*) AS components, SUM(users) AS users, MAX(users) AS largest
FROM user_components
GROUP BY 1
ORDER BY largest;
The query took 1.58 s over Flight SQL. An equivalent CPU pipeline combining 32-thread DuckDB with scipy's connected components took 12.3 s on the same machine (9.3 s in string deduplication and renumbering, 3.0 s in WCC) and produced identical components.
One component links 2,649,977 of
October's 2,986,296 users through shared session IDs. Only
335,591 users have session
IDs that nobody else uses. Across the six months, 15,138,756 of the
25,864,474 distinct session IDs appear for more than one user, and one ID
appears for 54 users. Session analysis on this dataset has to group by
(user_id, session_id).
The same query, with the column substituted, audits any other identifier such as a device, cart or order ID. A component with more than one owner is the case to investigate.
The plan had 2 native fragments and zero host DataFusion boundaries. The largest query allocator peak was 33.83 GiB of the 90 GiB query limit. The capture contains the executed SQL, query IDs, timings and every result row.
Which research pockets are disconnected from the main citation network?
An exploration that starts in the largest connected component cannot reach the other components, even when citations can be followed in either direction. This query finds the largest disconnected groups of the citation network and names the most-cited paper in each. Papers without any citation edge are outside this graph.
Component labels belong to one execution. Save one result table so the size calculation and paper lookup use matching labels.
CREATE OR REPLACE TABLE wcc_snapshot AS
SELECT vertex, component
FROM cugraph_weakly_connected_components(
edges => (SELECT src, dst FROM citation_edges), directed => false);
WITH sizes AS (
SELECT component, COUNT(*) AS members FROM wcc_snapshot
GROUP BY component ORDER BY members DESC LIMIT 3 OFFSET 1),
detail AS (
SELECT s.members, p.year, p.venue, p.title,
ROW_NUMBER() OVER (PARTITION BY s.component ORDER BY p.n_citation DESC) AS rn
FROM sizes s
JOIN wcc_snapshot c ON c.component = s.component
JOIN papers p ON p.paper_id = c.vertex)
SELECT members, year, venue, title
FROM detail WHERE rn = 1
ORDER BY members DESC;
The displayed groups have no citation links to the main component in this snapshot. Their representative papers suggest subject areas for a separate search. Missing links in this corpus do not establish that the research fields are disconnected in the wider literature.
Limits
- cuGraph requires directed=false so the graph is constructed as an undirected/symmetric view