Skip to main content

Spectral Modularity Maximization

UDTF: cugraph_spectral_modularity_maximization

Official cuGraph reference: C API

Partition vertices by running k-means on an embedding of the normalized graph Laplacian eigenvectors with the smallest eigenvalues. Modularity is not optimized directly.

Quickstart​

The call below supplies edges from registered relation target_edges with canonical src and dst columns and may include weight.

SELECT *
FROM cugraph_spectral_modularity_maximization(
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​

ArgumentRequiredColumnsDescription
edgesyes
  • src, dst: Int32, Int64, Utf8, LargeUtf8, Utf8View
  • weight (optional): Float32, Float64
  • edge_id (optional): Int32, Int64
edge relation with canonical src and dst columns, plus optional weight and edge_id columns; this algorithm ignores weight

Every edge_id column must have the integer type of src and dst; string-keyed graphs accept no edge IDs.

Named value arguments​

OptionTypeDefaultConstraintsDescription
evs_tolerancenumber0.01min 0; < 1eigenvalue solver tolerance in [0, 1)
n_clustersinteger2min 2; max 2147483647number of spectral clusters, at least 2
n_eigenvectorsinteger2min 2; max 2147483647number of smallest-eigenvalue Laplacian eigenvectors in the embedding, from 2 to n_clusters; the first is constant on a connected graph
seedinteger0min 0; max 18446744073709552000random initialization seed

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​

ColumnTypeNullableDescription
vertexInt64|Utf8noVertex assigned to a spectral clustering partition.
communityInt64noCluster identifier assigned by spectral modularity maximization.

These are generic descriptor schemas. Run gpu_validate_call to get the concrete, table-specific output schema.

Examples​

This example runs on the citation network demo dataset.

How does the dense citation core divide into six research groups?​

A six-group view of the dense citation core can show which catalog fields dominate each group and where labels mix. The query first keeps papers with at least 30 neighbors in the undirected citation graph, then partitions that core and reports each group's two most common primary_fos labels. The call passes the Int64 paper IDs directly. The vertex codebook maps them to Int32 ids internally and decodes the result.

CREATE OR REPLACE TABLE kcore30_edges AS
SELECT src, dst
FROM cugraph_k_core(edges => (SELECT src, dst FROM citation_edges), k => 30);

WITH labeled AS (
SELECT s.community AS cluster, p.primary_fos
FROM cugraph_spectral_modularity_maximization(
edges => (SELECT src, dst FROM kcore30_edges), n_clusters => 6,
n_eigenvectors => 6, evs_tolerance => 0.00001) s
JOIN papers p ON p.paper_id = s.vertex),
counts AS (
SELECT cluster, primary_fos, COUNT(*) AS n FROM labeled GROUP BY 1, 2),
ranked AS (
SELECT cluster, primary_fos, n,
SUM(n) OVER (PARTITION BY cluster) AS members,
ROW_NUMBER() OVER (PARTITION BY cluster ORDER BY n DESC, primary_fos) AS rn
FROM counts)
SELECT cluster, members, primary_fos, n
FROM ranked WHERE rn <= 2
ORDER BY members DESC, rn;
clustermembersprimary_fosn
028,994Convolutional neural network1,112
028,994Object detection912
42,298Probabilistic encryption115
42,298Encryption113
21,089Fuzzy logic159
21,089Group decision-making122
5787Dominance-based rough set approach168
5787Rough set160
3142Feature selection8
3142Software bug8
179Recursive least squares filter11
179Iterative method8

The table shows only the top two labels per cluster, and cluster ids are arbitrary. Labels with equal counts are ordered by name, so cluster 3 shows two of its three labels tied at 8 papers.

Limits​

  • seed sets the Lanczos start vector and the k-means initialization; the same seed can still yield a different partition because k-means centroid sums use floating-point atomics
  • the native graph type indexes Int32 vertices only; Int64 and string vertex columns run through a per-call codebook that fails when the distinct vertex count exceeds Int32::MAX
  • edge_id columns are rejected when Int64 vertices are mapped to Int32 ids
  • cuGraph requires directed=false so the graph is constructed as an undirected/symmetric view