# Entropy-Maximized WL Anchor Selection

- ID: 1520
- Canonical URL: https://synthcore.org/idea/1520/entropy-maximized-wl-anchor-selection
- API JSON: https://synthcore.org/api/idea/1520.json
- API Markdown: https://synthcore.org/api/idea/1520.md
- Verification status: unverified
- Source: [arXiv:2607.28168](https://arxiv.org/abs/2607.28168)
- Category: architecture
- Solves: accuracy, scalability, memory
- ML areas: graph-nn, embedding, attention, pooling
- Math tags: graph-theory, information-theory, combinatorics, algebra
- Ratings: usefulness 6/10; difficulty 4/10; novelty 5/10

## Idea description

Replace random or degree-based graph positional anchors with a greedy set chosen to maximize the entropy of the graph's Weisfeiler-Lehman equivalence partition. Give each selected anchor a unique trainable embedding, then run several WL-inspired refinement rounds to produce positional cell features. The resulting positional signal should distinguish nodes that ordinary message passing treats identically while using only a small anchor budget.

## Mathematical statement

Let V be the vertex set, n equal to the number of vertices, and pi equal to the partition pi={C_1,...,C_k} into WL-equivalence cells. The paper defines the Shannon partition entropy H(pi)=-sum_r (|C_r|/n) log(|C_r|/n), where |C_r| is the size of cell C_r. Initialize selected anchors with unique colors and all other vertices with a common color. At WL iteration t, update vertex v_i using c_i^(t+1)=HASH(c_i^(t), MULTISET{c_j^(t):(v_j,v_i) in E}), where c_i^(t) is the current color, E is the directed edge set, MULTISET preserves multiplicities, and HASH is an injective encoding of the current color and neighbor-color multiset. The cells C_r are the sets of vertices with equal final colors. For a candidate anchor a and current anchor set S, select the candidate with largest marginal entropy gain Delta(a|S)=H(pi(S union {a}))-H(pi(S)); with unit anchor cost this is the greedy rule. In a weighted graph, edge types or quantized weights can be included in each neighbor tuple. The neural adaptation adds a trainable embedding for the final cell ID and a unique trainable vector at each selected anchor. Entropy promotes fragmentation of symmetric cells but does not itself guarantee that every cell becomes a singleton, so the implementation must also track the unresolved-cell count.

## Key formulas

- $$\mathcal{H}(\pi)=-\sum_{r=1}^{k}\frac{|C_r|}{n}\log\frac{|C_r|}{n}$$
- $$c_i^{(t+1)}=\operatorname{HASH}\left(c_i^{(t)},\operatorname{MULTISET}\{c_j^{(t)}:(v_j,v_i)\in E\}\right)$$
- $$\Delta(a\mid S)=\mathcal{H}(\pi(S\cup\{a\}))-\mathcal{H}(\pi(S)),\qquad a^{*}=\arg\max_{a\notin S}\Delta(a\mid S)$$
- $$z_i^{\prime}=x_i+e_{\operatorname{cell}(i)}+\sum_{a\in S}\mathbf{1}[i=a]u_a$$

## Implementation notes

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.

## Disclaimer

AI-generated research hypothesis, automatically tested. Not peer-reviewed.