Abstract
Exact substructure counts make graph neural networks (GNNs) provably more expressive than the first-order Weisfeiler–Leman (1-WL) limit on message passing, but two practical walls confine them to small graphs: combinatorial graphlet counters stop at a fixed catalog of patterns on at most five vertices, and exact extraction at scale was widely treated as too costly. We treat exact substructure-feature extraction as a parallel-systems problem. Using HiPerMotif, an edge-centric parallel subgraph-isomorphism engine in the open-source Arkouda/Arachne framework, we convert isomorphism mappings into per-vertex orbit features by normalizing with each pattern’s automorphism group. On a single 128-core shared-memory node, the extraction strong-scales with counts bit-identical across thread counts, reaches a multi-million-vertex, 10⁸-edge graph (a single-node capacity result), and passes the five-vertex graphlet wall by extracting patterns no fixed-catalog counter expresses, such as induced long cycles (C6–C8); we chart this coverage boundary against ORCA, ESCAPE, and PGD. Two reproducible constructs ground the expressivity payoff: the ten-class circulant skip-link (CSL) benchmark, whose 1-WL-identical classes cannot be fully separated by any size-≤ 5 graphlet system but can be separated by induced long cycles, and the cospectral Shrikhande/4×4-rook pair, which a single clique count distinguishes though 1-WL and the adjacency/Laplacian spectrum cannot. The two results demonstrate separate capabilities, each shown in its own regime, not their intersection: the size-4 orbit features give a capacity-independent accuracy benefit on structure-driven graph classification, validated against a dimension-matched random control, with strong native features able to mask this benefit, while HiPerMotif gives feasible at-scale extraction of the beyond-wall patterns. The size-4 orbit counts are verified against the ORCA oracle and the long cycles against an independent enumerator.
Mohammad Dindoost
PhD Student
David A. Bader
Distinguished Professor, Associate Dean for Research, and Director of the Institute for Data Science
David A. Bader is a Distinguished Professor in the Department of Data Science and Associate Dean for Research in the Ying Wu College of Computing at New Jersey Institute of Technology.