Localization and metric dimension for families of highly structured digraphs

What the math gives to ML

The paper gives a constructive probabilistic method for selecting a small set of landmark vertices whose restricted in-neighborhood signatures distinguish every pair of vertices. The transferable asset is an explicit collision bound: if every vertex pair differs on at least c adjacency coordinates, a uniformly sampled landmark set of size O(n log n / c) is sufficient with positive probability. This can become a graph-token compression or positional-encoding module for graph transformers, replacing all-node adjacency access with a much smaller landmark interface while retaining pairwise structural identifiability. The strongest experiment is to compare random landmarks, degree-based landmarks, and the paper-sized landmark set at equal downstream accuracy and graph-encoder FLOPs.