Is this a new feature, an improvement, or a change to existing functionality?
New Feature
How would you describe the priority of this feature request
Low (would be nice)
Please provide a clear description of problem this feature solves
Given a large target graph and a small "pattern" graph, find every place the pattern occurs. This is subgraph matching (subgraph isomorphism / monomorphism), and today cuGraph users who need it have to move their graph off the GPU and use CPU tools.
Real usage examples:
- Qubit mapping / circuit layout (where this implementation came from)
- Motif analysis in scientific graphs.
Describe your ideal solution
note: I have an implementation ready that I am going to attach to this feature request
A GPU-accelerated subgraph matching function in the experimental namespace:
cugraph.experimental.subgraph_isomorphism(G, pattern_G, motifs=None, batch_size=None)
- Inputs: G (undirected cugraph.Graph target) and pattern_G (small, connected, undirected cugraph.Graph pattern). Optional motifs lets advanced users supply motif building blocks that guide the decomposition (a MotifData helper type and a small default library are included); optional batch_size processes intermediate joins in row batches to stay under cuDF's 2^31−1 column-size limit on match-heavy workloads.
- Output: a cuDF DataFrame with one row per embedding found and one column per pattern vertex, containing the matched target vertex ids. Empty DataFrame if no match exists.
- Semantics: returns monomorphisms: pattern edges must map to target edges and the vertex mapping is injective, but additional target edges among matched vertices are permitted. This matches NetworkX GraphMatcher.subgraph_monomorphisms_iter and rustworkx VF2 with induced=False, the default meaning in VF2-family tools and subgraph-matching benchmarks.
How it works: the pattern graph is decomposed into small motifs, each motif's embeddings in the target are materialized as cuDF tables, full embeddings are assembled through cuDF inner joins on shared boundary vertices, with a cuPy broadcast filter. All work proportional to the target graph size happens on the GPU as DataFrame operations.
Implementation properties:
- Pure Python within the cugraph package (cuDF + cuPy only)
- No new dependencies: NetworkX is used only for the pattern-decomposition step, imported via the existing import_optional pattern (it is already a test dependency)
- Follows existing conventions: registered with experimental_warning_wrapper, validates inputs like other algorithms (rejects directed graphs, disconnected patterns)
- Tests cross-validate results against NetworkX subgraph_monomorphisms_iter on the karate dataset and hand-built graphs, plus renumbering, input-validation, and batching-equivalence tests
Describe any alternatives you have considered
NetworkX's GraphMatcher or rustworkx's VF2 are both alternatives but do not offer GPU acceleration
Additional context
No response
Code of Conduct
Is this a new feature, an improvement, or a change to existing functionality?
New Feature
How would you describe the priority of this feature request
Low (would be nice)
Please provide a clear description of problem this feature solves
Given a large target graph and a small "pattern" graph, find every place the pattern occurs. This is subgraph matching (subgraph isomorphism / monomorphism), and today cuGraph users who need it have to move their graph off the GPU and use CPU tools.
Real usage examples:
Describe your ideal solution
note: I have an implementation ready that I am going to attach to this feature request
A GPU-accelerated subgraph matching function in the experimental namespace:
cugraph.experimental.subgraph_isomorphism(G, pattern_G, motifs=None, batch_size=None)
How it works: the pattern graph is decomposed into small motifs, each motif's embeddings in the target are materialized as cuDF tables, full embeddings are assembled through cuDF inner joins on shared boundary vertices, with a cuPy broadcast filter. All work proportional to the target graph size happens on the GPU as DataFrame operations.
Implementation properties:
Describe any alternatives you have considered
NetworkX's GraphMatcher or rustworkx's VF2 are both alternatives but do not offer GPU acceleration
Additional context
No response
Code of Conduct