Jaccard
UDTF: cugraph_jaccard
Official cuGraph reference: C API
Compare explicit vertex pairs by dividing the size of their shared-neighbor intersection by the size of their neighbor union.
Quickstart
The call below supplies edges from registered relation target_edges with canonical src and dst columns and may include weight, plus the registered relation candidate_pairs (the vertex_pairs relation with columns first, second).
SELECT *
FROM cugraph_jaccard(
edges => (SELECT src, dst FROM target_edges),
vertex_pairs => (SELECT first, second FROM candidate_pairs)
);
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
Vertex columns of vertex_pairs must use the same vertex domain as edges: the integer type of src and dst, or any listed string type when the endpoints are strings. 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
- EMBER2024 import review
Which catalog entries are one brand listed twice?
Sellers can enter the same brand under several names. Two entries liked by
the same people are candidates for one brand. The input is every item_like
event of the six months, reduced to distinct user-brand pairs.
Jaccard divides the shared fans of two entries by the union of their fan sets. The query scores all 1,999,000 pairs of the 2,000 most-liked brands in one call, then joins names and fan counts and keeps the 30 highest scores.
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 2000
), brands AS (
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
)
SELECT ba.brand_name AS brand_a, bb.brand_name AS brand_b,
a.fans AS fans_a, b.fans AS fans_b, r.similarity AS jaccard
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
) r
JOIN top_brands a ON a.brand_id = r.first
JOIN top_brands b ON b.brand_id = r.second
JOIN brands ba ON ba.brand_id = r.first
JOIN brands bb ON bb.brand_id = r.second
ORDER BY r.similarity DESC, brand_a
LIMIT 30;
The table shows the first 14 of 30 rows. The query took 3.34 s over Flight SQL.
Most of the highest-scoring pairs are one brand entered twice: TXT and Tomorrow X Together, Air Jordan and Jordan, Mugler and Thierry Mugler, Yves Saint Laurent and its YSL variant, Christian Dior and Dior, A Bathing Ape and Bape, Hermès and HERMES, BabyBjorn and BABYBJÖRN. No name was compared to find them. The remaining pairs are distinct brands that one audience follows together, such as Hello Kitty and Sanrio, Konami and Yu-Gi-Oh!, or Panini and Topps.
The pair list is a SQL relation, so the same query could join each pair's leaf categories or price ranges to separate duplicates from companions. Scores over the full six months hide seasonal pairs; a date filter on the events restricts the window.
The plan had 6 native fragments and zero host DataFusion boundaries. The largest query allocator peak was 75.07 GiB of the 90 GiB query limit. The capture contains the executed SQL, query IDs, timings and every result row.
Which papers share the Transformer's references?
The seed is Attention is all you need, and related reading is ranked by shared references. Candidates are papers from 2017 to 2020 with at least ten references and one of four catalog labels: natural language processing, language model, machine translation or question answering. Papers with the seed's title are excluded.
Jaccard divides shared references by the union of the reference lists. The query gives cited papers negative reference-role IDs and citing papers positive IDs, allowing an undirected Jaccard call to compare outgoing lists. SQL filters the candidates and joins the returned scores to paper metadata.
CREATE OR REPLACE VIEW similarity_seed AS
SELECT paper_id, title, n_references
FROM papers
WHERE title = 'Attention is all you need' AND year = 2017;
CREATE OR REPLACE VIEW similarity_candidates AS
SELECT p.paper_id, p.title, p.n_references, p.year
FROM papers p
WHERE p.year BETWEEN 2017 AND 2020
AND p.n_references >= 10
AND p.primary_fos IN (
'Natural language processing', 'Language model',
'Machine translation', 'Question answering');
CREATE OR REPLACE VIEW bibliography_edges AS
SELECT e.src, -e.dst AS dst
FROM citation_edges e
JOIN (
SELECT paper_id FROM similarity_seed
UNION
SELECT paper_id FROM similarity_candidates
) selected ON selected.paper_id = e.src;
SELECT p.year, p.title, p.n_references,
ROUND(r.similarity, 3) AS jaccard
FROM cugraph_jaccard(
edges => (SELECT src, dst FROM bibliography_edges),
vertex_pairs => (
SELECT s.paper_id AS first, c.paper_id AS second
FROM similarity_seed s
CROSS JOIN similarity_candidates c
WHERE LOWER(c.title) <> LOWER(s.title)),
directed => false) r
JOIN papers p ON p.paper_id = r.second
ORDER BY r.similarity DESC, p.paper_id
LIMIT 5;
The first three of the saved result rows are:
The query took 0.24 s.
Follow-up: inspect the shared references. The leading pair has 22 and 13 references. This SQL returns their eight shared records, including Adam, Sequence to Sequence Learning with Neural Networks, and Neural Machine Translation by Jointly Learning to Align and Translate.
WITH seed AS (
SELECT paper_id FROM papers
WHERE title = 'Attention is all you need' AND year = 2017
), candidate AS (
SELECT paper_id FROM papers
WHERE title = 'Self-Attention with Relative Position Representations' AND year = 2018
)
SELECT p.paper_id, p.year, p.title
FROM citation_edges a
JOIN seed s ON s.paper_id = a.src
JOIN citation_edges b ON b.dst = a.dst
JOIN candidate c ON c.paper_id = b.src
JOIN papers p ON p.paper_id = a.dst
ORDER BY p.year, p.paper_id;
- Adam: A Method for Stochastic Optimization (2014)
- Neural Machine Translation by Jointly Learning to Align and Translate (2014)
- Sequence to Sequence Learning with Neural Networks (2014)
- Effective Approaches to Attention-based Neural Machine Translation (2015)
- End-To-End Memory Networks (2015)
- A Decomposable Attention Model for Natural Language Inference (2016)
- Google's Neural Machine Translation System: Bridging the Gap between Human and Machine Translation (2016)
- Neural Machine Translation in Linear Time (2016)
The query took 0.33 s.
The score is 8 / (22 + 13 − 8) = 0.296 after rounding. The shared works explain what produced the ranking and form a bibliography to inspect.
The capture records a
native_preferred run with one host execution boundary for the similarity
query. It demonstrates composition with SQL but not a fully native execution
path. The shared-reference result was independently checked.
What connects these files to the seed?
The seed is the unlabeled Win32 file 20005740, with 58 retained imports.
The query returns candidates with related imports and the symbols behind
each match. The seed was selected by SHA-256 order among files with 10 to 100
retained imports and at least five neighbors in a separate histogram graph.
Family labels were not used to select it.
Personalized PageRank creates a 25-file queue. Jaccard ranks import overlap within that queue, and relational joins retrieve shared symbols and file metadata. The sample-to-symbol edges were prepared before SQL, retaining symbols occurring in 3 to 100 Win32 challenge files.
WITH candidates AS (
SELECT p.vertex
FROM cugraph_personalized_pagerank(
edges => (
SELECT src_id AS src, dst_id AS dst
FROM ember_48_challenge_import_edges
),
personalization => (
SELECT id AS vertex, CAST(1.0 AS DOUBLE) AS value
FROM ember_49_challenge_graph_seed
),
directed => false
) p
JOIN ember_48_challenge_import_sample_counts c ON c.id = p.vertex
CROSS JOIN ember_49_challenge_graph_seed seed
WHERE p.vertex <> seed.id AND c.retained_import_count >= 5
ORDER BY p.value DESC, p.vertex
LIMIT 25
), similarities AS (
SELECT * FROM cugraph_jaccard(
edges => (
SELECT src_id AS src, dst_id AS dst
FROM ember_48_challenge_import_edges
),
vertex_pairs => (
SELECT seed.id AS first, c.vertex AS second
FROM candidates c CROSS JOIN ember_49_challenge_graph_seed seed
),
directed => false
)
)
SELECT j.second AS candidate_id, m.sha256, m.family,
counts.retained_import_count, j.similarity,
COUNT(*) AS shared_rare_imports,
MIN(symbols.symbol) AS example_shared_import
FROM similarities j
JOIN ember_48_challenge_import_edges seed_edges ON seed_edges.src_id = j.first
JOIN ember_48_challenge_import_edges candidate_edges
ON candidate_edges.src_id = j.second AND candidate_edges.dst_id = seed_edges.dst_id
JOIN ember_48_challenge_import_symbols symbols ON symbols.symbol_id = seed_edges.dst_id
JOIN ember_metadata_challenge m ON m.id = j.second
JOIN ember_48_challenge_import_sample_counts counts ON counts.id = j.second
GROUP BY j.second, m.sha256, m.family, counts.retained_import_count, j.similarity
ORDER BY j.similarity DESC, j.second
LIMIT 15;
The first four candidates share 54 imports with the seed. Each has 130
retained imports, giving Jaccard 54 / (58 + 130 - 54) = 0.403.
The query took 0.10 s.
One shared symbol is msvbvm60.dll!MSVBVM60.DLL:ordinal521.
All 15 returned family fields are empty.
The common msvbvm60.dll runtime can account for strong import overlap
without establishing a shared malware family or campaign. The symbol join
lets an analyst inspect what produced a graph match before assigning meaning
to its score. An empty family field is missing attribution.
Edges exist for only 926 of 3,225 Win32 challenge files; 2,299 files have no retained edges and are outside this candidate search. Changing the import frequency bounds requires preparing a new edge table.
The capture records all results, preparation counts and CPU checks.
Limits
- similarity is explicit-pair only; all-pairs candidate generation and all-pairs top-k search are not exposed
- vertex_pairs is a required relation with canonical first and second columns
- candidate-pair columns must match the graph vertex domain; logical string graphs accept Utf8, LargeUtf8, or Utf8View independently per column
- null candidate-pair values are rejected at execution and are never dropped
- candidate pairs are a multiset: duplicate, reversed, and self pairs remain distinct output rows
- result rows have no global ordering; use ORDER BY when order is required
- providing edges.weight selects weighted similarity; omitting it selects unit-weight similarity
- cuGraph requires directed=false so the graph is constructed as an undirected/symmetric view