Must Graph Structure Remain Implicit? Explicit Topological Representations via Sparse Decomposition

Graph neural networks and graph transformers achieve strong predictive performance but typically encode topology in latent coordinates without directly identifiable structural meaning. Classical graphlet representations expose structural patterns through predefined families. This raises a broader question: can an explicit, data-driven representation support competitive graph learning while keeping topology and attributes separately accessible? Building on sparse network decomposition, we show that explicit, learnable structural coordinates can support competitive prediction while making structural evidence independently auditable and traceable. Our framework combines shared-dictionary encoding of rooted patches with permutation-invariant readout, preserving occurrence-level links and supporting separate topology, attribute, and binding channels. The exact radius-$r$ rooted-patch profile refines $r$ rounds of 1-WL, while radius-one profiles distinguish some graph pairs unresolved by stable 1-WL. On BREC, the exact pair-rooted profile distinguishes 300 of 400 graph pairs, and a compact 128 atom representation retains nearly all of these distinctions. Across node- and graph-level benchmarks, the framework achieves competitive performance against recent GNN and graph Transformer baselines using conventional predictors. Coalition retraining quantifies standalone and conditional information-source contributions, while molecular case studies demonstrate how structural tracing supports testable chemical hypotheses and fixed-model interventions that identify split-specific structural shortcuts.