Homomorphism-Vector Positional Encoding

(1) Integration point: add a structural positional-encoding branch before the first graph transformer or message-passing layer. The branch outputs one vector per vertex and is concatenated to the original node embedding; alternatively feed it as an additive bias to graph-attention logits. Choose a small pattern bank \(\mathcal{B}\), for example all colored graphs with 1--4 pattern vertices and up to 2 blocks, including isolated vertices, edges, wedges, triangles, 4-cycles, and two disjoint edges. Sample \(S\) subset tuples \(\boldsymbol{D}^{(s)}=(D_1^{(s)},\ldots,D_k^{(s)})\) per graph using random Bernoulli masks with several densities.

(2) Pseudocode: for each pattern \(F\in\mathcal{B}\) and subset tuple \(\boldsymbol{D}\), compute \(c_F[\boldsymbol{D}]\) by enumerating assignments for patterns of at most four vertices, or by dynamic programming over pattern vertices; reject assignments violating an edge or block-membership constraint. Set \(z_F[\boldsymbol{D}]=\log(1+c_F[\boldsymbol{D}])/\log(1+\prod_i|D_i|^{|C_i|})\). Pool each sampled tuple into its member vertices: \(q_v=\sum_{s:v\in D_1^{(s)}\cup\cdots\cup D_k^{(s)}}\alpha_s\,\mathrm{MLP}(z_{F\in\mathcal{B}}[\boldsymbol{D}^{(s)}],\mathrm{mean}_{u\in\cup_iD_i^{(s)}}x_u)\), then return \(\mathrm{MLP}([x_v,q_v])\). The homomorphism-count definition is the paper-derived computation; the logarithm, normalization, subset sampling, and learnable pooling are engineering adaptations.

(3) Exact counts are feasible for small patterns and graphs; for larger patterns estimate counts by Monte Carlo assignments or color-coded dynamic programming. Cache all subset masks and reuse counts across minibatch augmentations. Monitor the coefficient of variation of estimated counts and increase samples only when it is high.

(4) First experiment: use a 5-layer GIN and a 4-layer graph transformer on dense synthetic graphs, strongly regular graphs, Erdős–Rényi graphs, and a molecular benchmark such as ZINC. Compare the baseline, standard degree/triangle features, and this branch at equal parameter count. The primary signal is higher accuracy or better graph-isomorphism discrimination at equal depth; a useful target is at least 5 percentage points on regular-graph classification and improved validation accuracy on dense graph tasks without increasing message-passing layers.