Multiset Distance Positional Encoding

Integrate this into a message-passing GNN immediately before the first graph-convolution or graph-transformer layer. For every training graph, choose k landmarks S, run BFS from each landmark, and form a distance matrix A in R^{|V| x k}; clip distances at D and use an additional overflow bin for distances greater than D. Construct H[x,r]=sum_{j=1}^k 1[A[x,j]=r], normalize H by k, and concatenate z_x=[node_features_x; MLP(H_x)] to the original node feature. Compact pseudocode is: S=select_landmarks(G,k); A=stack(BFS(G,u) for u in S); H=zeros(|V|,D+2); for x,j: H[x,min(A[x,j],D+1)] += 1; z=concat(X, positional_mlp(H)); Y=GNN(G,z). Start with greedy farthest-point sampling: initialize one random landmark, then repeatedly add the vertex maximizing its minimum distance to the current S. Optionally add lambda_collision*C(S) to the loss, where collision groups are obtained by hashing integer histogram rows; for differentiable training, use a soft surrogate based on pairwise squared distances between normalized H rows. The exact mathematics computed is the shortest-path distance histogram and its collision condition; no theorem constants need to be fitted. Estimate D with a few BFS sweeps, and compare k against the join-graph heuristic n-Delta+m-2 only on graphs with an evident diameter-two join structure. The first experiment should use a 5-layer GIN or Graphormer on ZINC and a small molecular node-classification benchmark, comparing raw node features, ordered distance-to-landmark encodings, Laplacian positional encodings, and this multiset encoding at equal feature width and preprocessing budget. Measure validation accuracy, unresolved node-pair count, and BFS preprocessing time. A successful result is higher accuracy or fewer representation collisions at the same k, especially on regular, symmetric, or diameter-two graphs; randomly permuting landmark order should leave this encoding exactly unchanged.