A Dense Weisfeiler-Leman Algorithm for Deciding Bounded-Cliquewidth Homomorphism Indistinguishability
arXiv:2608.13382
2026
Architecture
1 ideas extracted · analyzed Sep 1, 2026
What the math gives to ML
The paper replaces vertex-tuples by tuples of vertex subsets, yielding a dense analogue of Weisfeiler–Leman that can distinguish structures invisible to ordinary message passing on dense graphs. Its most transferable object is the homomorphism vector: a structured feature indexed by subset tuples whose coordinates count constrained graph mappings. A practical neural adaptation is to use low-order homomorphism-vector coordinates as dense-graph positional features or as a subset-tuple refinement layer, with approximation and sampling to avoid the full powerset cost. The main opportunity is improved expressivity on dense and highly regular graphs, not generic speedup.
Ideas from this paper
Unverified
2026
Augment a graph neural network with structural features computed from counts of small pattern homomorphisms whose pattern vertices are constrained to lie in selected vertex subsets. Unlike ordinary local aggregation, these features encode dense subgraph structure and can separate graphs or node sets that have identical low-order neighborhood statistics. Use a small learned bank of pattern graphs and sampled subset tuples so the method remains practical.
Useful6/10
Difficulty6/10
Novelty7/10