Entropy-Maximized WL Anchor Selection

1. Integration point: implement this as a preprocessing positional-encoding module for a graph transformer or message-passing GNN. The input is a graph with node features x_i, directed edges E, and optional edge types. The output is a selected anchor set S and a final WL cell ID for each node. Add a learned embedding e_cell(i) to node i before the first graph layer, and add a distinct learned vector u_a to each selected anchor. 2. Pseudocode: set S to the empty set. For b from 1 to anchor_budget, temporarily test every candidate a not in S. Assign unique initial colors to every anchor in S union {a} and color 0 to all other nodes. For t from 1 to T, replace each node color with the collision-free dictionary encoding of its current color and the sorted multiset of incoming neighbor colors. Group equal final colors into cells, compute H=-sum over cells of (cell_size/n)*log(cell_size/n), and choose the candidate with maximum H increase. Append that candidate to S and cache the resulting cell IDs. Construct z_i=x_i+Embedding(cell_id_i), then add AnchorEmbedding[anchor_index] at each selected anchor. 3. Compute exactly from the paper's mathematics: WL refinement, partition entropy, greedy marginal gains, and unresolved-cell statistics. Estimate empirically: the number of WL rounds T, anchor budget, whether to stop when all cells are singletons, and the effect of using edge-weight buckets. Use tuple interning rather than a fixed-size hash to avoid collisions. 4. First cheap experiment: train a 4-layer GIN and a small graph transformer on cycles, grids, strongly regular graphs, and a molecular dataset such as ZINC. Compare entropy-WL anchors against random anchors, highest-degree anchors, and standard Laplacian positional encodings with budgets of 1, 2, 4, and 8 anchors. Report accuracy, performance after node-ID permutations, unresolved-cell count, preprocessing time, and positional-parameter count. Success means higher accuracy on symmetric graphs at equal anchor budget, or equal accuracy with fewer positional parameters and lower memory.