Graph-level clustering stops crowding multi-class graphs into a few clusters: S3GLC adds spectral signatures for global topology and lifts REDDIT-12K accuracy by 14.6%
Synopsis
Graph-level clustering partitions a collection of graphs into semantically meaningful groups, but the widely used GIN encoder cannot see global topology, and deep clustering tends to collapse samples into a few clusters in multi-class settings. S3GLC uses a spectral signature, the sorted adjacency eigenvalues, as a rigorous lower bound on graph edit distance, fuses it with the GIN spatial representation, and enforces cluster balance through Sinkhorn-Knopp normalization from optimal transport. Across 10 real datasets and 15 baselines, it improves ACC by 14.6% on REDDIT-12K and NMI by 35.2% on DD.
Interpretation
Graph-level clustering can now draw on global topology together with local neighborhood information instead of relying only on the graph-level vectors produced by a GIN encoder. GIN matches the discriminative power of the 1-WL test and cannot separate certain non-isomorphic graphs, while graph edit distance captures that difference but is NP-hard to compute. Compared with 15 baselines on 10 real datasets, ACC rises by 14.6% on REDDIT-12K and NMI by 35.2% on DD.
The method computes a spectral signature for each graph separately, using the Euclidean distance between sorted adjacency eigenvalues to approximate graph edit distance. The Hoffman-Wielandt inequality guarantees this distance is a rigorous lower bound on graph edit distance, so the NP-hard pairwise matching problem is avoided. The spectral signature keeps only the top largest eigenvalues of each graph's adjacency matrix, which can be solved directly on small sparse matrices.
Spectral signatures and GIN spatial representations are fused by joint manifold-preserving sparse regression, and the clustering objective imposes an equipartition constraint through optimal transport. Existing deep clustering only minimizes the KL divergence between soft assignments and pseudo-labels, lacks a cluster-size constraint, and collapses on multi-class data. Sinkhorn-Knopp solves the entropy-regularized transport problem so the target distribution is doubly normalized; on ENZYMES the partition collapse ratio of DCGLC and DGLC is far above that of the ground-truth labels.
Perspective
The demonstrated scope is unsupervised graph-level clustering on 10 real graph datasets spanning molecular, biological and social-network data, with class counts from binary to multi-class; the method targets homogeneous, static graph structures. The authors propose extending the algorithm to heterogeneous or dynamic graph data.
The authors state that the current design is mainly tailored to homogeneous graphs and limited to static graph structures. Hyperparameter analysis shows performance drops once the spectral signature dimension grows beyond a point, and larger fused feature dimensions also degrade metrics.
