Canonical and Compact Representations in Small Language Model Graph Classification

Small language models can classify graphs serialized as text, but three properties of graphs complicate the conversion: a graph has no intrinsic vertex order, so one graph yields many texts; explicit serializations are long under a fixed input budget; and one serialization shows only a single view of the structure. We evaluate the corresponding design responses under one protocol. Raw adjacency and edge lists are compared with a degree-sorted ordering, two exact canonical serializations, a deterministic BFS profile, compact Graph6 and NetLSD encodings, soft-prompt baselines, and validation-weighted late fusion. On five TUDataset benchmarks and three instruction-tuned small language models, the exact canonical serializations improve over raw adjacency lists in 14 of the 15 settings, and late fusion improves on that baseline in all 15. The compact encodings shorten the input by 67.7% and 42.2%, respectively, and both exceed the baseline in mean accuracy. A paired analysis with correction for multiple comparisons confirms the gain for both canonical serializations, the deterministic profile, the degree-sorted ordering, NetLSD, and late fusion. Serialization is therefore a consequential modeling decision, not merely a preprocessing step. This study provides an empirical basis for that decision by measuring accuracy, permutation robustness, input length, and preprocessing cost under a single protocol.