Neighbourhood complexity and identification problems for graphs of bounded treewidth and pathwidth

What the math gives to ML

The paper gives sharp upper bounds on the number of distinct closed-neighborhood patterns that a vertex set S can induce in graphs of bounded treewidth or pathwidth. The transferable asset is a provably small dictionary of adjacency signatures, with at most (k-w+1)2^w+w signatures for treewidth w and at most (k-w+2)2^{w-1}+2k-w-2 for pathwidth w. A graph neural network can exploit this by selecting k landmark vertices, grouping all nodes with identical landmark-neighborhood signatures, and computing landmark-mediated messages once per signature rather than traversing every node-landmark relation. This is most promising for graph-transformer or dense landmark-attention layers on graphs with known or estimated low-width decompositions, where the signature dictionary gives a falsifiable memory and inference-speed reduction.