PED finite-state graph layer
Implementation & benchmark of arXiv:2607.03894 — Counting perfect edge dominating sets: extremal results and linear-time algorithms
Source paper: Counting perfect edge dominating sets: extremal results and linear-time algorithms arXiv:2607.03894 ⓘ · analyzed Aug 29, 2026
AI-generated research hypothesis, automatically tested. Not peer-reviewed.
Idea description
Add a finite-state message-passing layer that tracks local configurations corresponding to perfect edge domination or dominating induced matchings instead of transmitting unconstrained node embeddings alone. On graphs with a tree, series-parallel, or small-separator decomposition, the layer produces an exact or differentiable partition function over globally valid edge configurations, which can be used as node features, an auxiliary loss, or a structural prior.
Formulas
Mathematical statement
The paper defines a perfect edge dominating set as an edge subset in which every edge outside the subset is dominated by exactly one selected edge; a selected edge dominates itself and every adjacent edge. A dominating induced matching (DIM) is therefore an edge set whose closed edge-neighborhoods partition E(G). The paper encodes feasible configurations with three vertex colors, white \(\mathsf{w}\), yellow \(\mathsf{y}\), and black \(\mathsf{b}\), and introduces boundary-state counts for a generalized series-parallel graph \(G=G(u,v)\): $$p_{\alpha,\beta}(G)=\begin{cases}\Upsilon(G,u,v,\sigma(u),\sigma(v))&\text{if }\alpha\neq4\text{ and }\beta\neq4,\\\Phi(G,u,v,\sigma(v))&\text{if }\alpha=4\text{ and }\beta\neq4,\\\Phi(G,v,u,\sigma(u))&\text{if }\alpha\neq4\text{ and }\beta=4,\\\Gamma(G,u,v)&\text{if }\alpha=4\text{ and }\beta=4.\end{cases}$$ Here \(\alpha,\beta\in\{0,1,2,3,4\}\) specify endpoint conditions: state 0 means white, state 1 means yellow with endpoint degree at least two, state 2 means yellow with degree one, state 3 means black, and state 4 means that endpoint is not fixed and is summarized by the auxiliary functions \(\Phi\) or \(\Gamma\). The neural adaptation replaces integer counts by weighted partition functions. For edge variables \(z_e\in\{0,1\}\), let \(N[e]\) be the closed edge-neighborhood of edge \(e\), and define the feasible set $$\mathcal{F}(G)=\{z\in\{0,1\}^{E(G)}:\sum_{f\in N[e]}z_f=1\text{ for every }e\in E(G)\}.$$ With learned edge scores \(\theta_e\), use $$Z(G)=\sum_{z\in\mathcal{F}(G)}\exp(\sum_{e\in E(G)}\theta_ez_e).$$ Each boundary vector stores partial partition functions \(Z_{\alpha,\beta}\), and compatible subgraphs merge according to $$Z^{\mathrm{merge}}_s=\sum_{s_1,s_2:\,C(s_1,s_2)=s}Z^{(1)}_{s_1}Z^{(2)}_{s_2},$$ where \(C\) is a local compatibility table that rejects configurations causing an edge to be dominated zero or more than once. The fixed finite state space is the mathematical asset; the edge scores and differentiable use of \(Z\) are the ML adaptation.
Implementation notes
Integrate this as a graph-level structural branch alongside a standard GNN, operating on edge logits rather than replacing the main node embeddings. First obtain a tree decomposition, series-parallel decomposition, or a heuristic elimination order with small separators. For every subgraph, maintain a tensor of boundary messages indexed by the paper's five states per boundary endpoint: 0=white, 1=yellow/non-leaf, 2=yellow/leaf, 3=black, and 4=free/auxiliary. Initialize leaf edges by enumerating their few valid local edge selections. At each introduce-edge, forget-vertex, and merge operation, enumerate the constant-size state pairs, reject incompatible pairs using the exact condition that every edge has one selected edge in its closed edge-neighborhood, and update the message with log-sum-exp. Use neural edge scores \(\theta_e=g([h_u,h_v,x_e])\) as the weights in \(Z\). The compatibility function \(C\) should be implemented as a precomputed lookup table generated by brute-force enumeration on one separator edge; cache this table permanently. Compute \(h_G=\log\sum_s Z_s\) and concatenate it to the graph representation, or add \(-\lambda h_G\) as a soft structural objective when valid configurations are desirable. Exact integer counting is recovered by setting every \(\theta_e=0\); differentiable training uses float log-domain messages. The state semantics and finite boundary alphabet come from the paper, while the decomposition and neural edge scores are engineering choices. First test on synthetic trees and series-parallel graphs with labels equal to DIM existence or the exact PED count, using a 3-layer GIN baseline. Measure count prediction error, DIM-existence accuracy at small sample sizes, and robustness when edge features are noisy. Success is a significant sample-efficiency gain and near-zero constraint violations compared with an unconstrained GNN, with runtime linear in graph size for bounded-width decompositions.
Verification
This idea has not been verified yet.
Verification happens in two stages: Stage 1 — a mechanism check on a toy system confirms the claimed mathematical phenomenon reproduces; Stage 2 — a benchmark implements the idea on a real (small) neural network task and compares it against a tuned baseline over 8 paired seeds with a permutation test.
Artifacts
Artifacts unavailable.