[Rule] GraphPartitioning to SpinGlass

[zazabap]

Source: GraphPartitioning
Target: SpinGlass
Motivation: Maps graph bisection to the Ising model, enabling solvers from statistical physics and quantum computing; the natural formulation in spin variables.
Reference: Barahona, 1982; Lucas, 2014

Reduction Algorithm

Notation:

• Source: undirected graph $G = (V, E)$, $n = |V|$ (even), $m = |E|$
• Target: SpinGlass (Ising model) with $n$ spin variables $s_i \in {-1, +1}$

Variable mapping:

$$s_i = 2x_i - 1 \in {-1, +1}$$

where $x_i \in {0,1}$ is the partition variable ($x_i = 0 \Rightarrow s_i = -1 \Rightarrow i \in A$).

Ising Hamiltonian:

An edge $(u,v)$ is cut iff $s_u \neq s_v$, i.e., $s_u s_v = -1$. The number of cut edges is:

$$\text{cut} = \sum_{(u,v) \in E} \frac{1 - s_u s_v}{2}$$

The balance constraint $|A| = |B| = n/2$ becomes $\sum_i s_i = 0$, enforced as a penalty:

$$H = -\sum_{(u,v) \in E} J_{uv} s_u s_v + P \left(\sum_{i \in V} s_i\right)^2$$

Setting $J_{uv} = -1/2$ for each edge and minimizing $H$ minimizes cut edges under the balance constraint.

Equivalently, the coupling constants are:

• $J_{uv} = -1/2$ for $(u,v) \in E$ (antiferromagnetic — prefers aligned spins = uncut edges)
• $J_{ij} = P$ for all pairs (balance enforcement via a global field)

Solution extraction: $A = {i : s_i = -1}$, $B = {i : s_i = +1}$.

Size Overhead

Target metric (code name)	Polynomial (using symbols above)
num_spins	$n$
num_couplings	$\binom{n}{2}$ (pairwise for balance) or $m$ (if balance via external field)

Validation Method

Closed-loop testing: solve GraphPartitioning by brute-force, solve the reduced SpinGlass, and verify both give the same optimal partition.

Example

Source: 6 vertices, 9 edges: $(0,1), (0,2), (1,2), (1,3), (2,3), (2,4), (3,4), (3,5), (4,5)$.

SpinGlass: 6 spins, couplings $J_{uv} = -1/2$ for each edge, penalty $P = 5$ for balance.

Optimal: $s = (-1, -1, -1, +1, +1, +1)$, $\sum s_i = 0$ (balanced).

Cut edges: $(1,3), (2,3), (2,4)$ — each has $s_u s_v = -1$, contributing $+1/2$ to $H$.

$H = -(-1/2)(3 \cdot (-1) + 6 \cdot (+1)) + 5 \cdot 0 = 3/2 + 0$. Minimized among all balanced spin configurations.

[zazabap]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	⚠️ Warn	Source "GraphPartitioning" not yet in codebase
Non-trivial	✅ Pass	Penalty terms for balance constraint via pairwise couplings
Correctness	❌ Fail	Critical sign error — Hamiltonian encodes Max-Bisection, not Min-Bisection
Well-written	❌ Fail	Wrong metric name; internal inconsistencies

Overall: 1 passed, 2 failed, 1 warning

---

Usefulness

GraphPartitioning does not exist in the codebase. Requires a [Model] issue first.

Non-trivial

Maps partition variables to Ising spins with quadratic penalty for balance constraint, creating O(n²) pairwise couplings. Not a simple relabeling.

Correctness — FAIL

Critical sign error in the Hamiltonian:

The issue sets J_uv = −1/2 with H = −Σ J_uv s_u s_v + P(Σsᵢ)². Substituting:

H = (1/2)Σ s_u s_v + penalty

Since s_u·s_v = −1 for cut edges, minimizing H maximizes cut edges (Max-Bisection). But the issue claims it minimizes cut edges (Min-Bisection).

Proof by counterexample: For the issue's graph (6 vertices, 9 edges):

• Claimed optimal A={0,1,2}, B={3,4,5}: cut=3, H = 3/2
• Alternative A={0,2,4}, B={1,3,5}: cut=5, H = 9/2−5 = −1/2 (lower!)

The "optimal" in the example is actually the worst balanced partition for this Hamiltonian.

The issue also states "antiferromagnetic — prefers aligned spins" but antiferromagnetic couplings with the −Σ J·s·s convention prefer opposite spins (cut edges).

References are valid: Barahona (1982) and Lucas (2014) are both real, verified papers. The error is in translating Lucas's binary formulation to spin variables.

Fix: Flip J_uv to +1/2 (ferromagnetic), which in H = −Σ J s_u s_v prefers aligned spins and penalizes cuts.

Well-written — FAIL

1. Wrong metric name. Overhead uses num_couplings but SpinGlass's actual getter is num_interactions (confirmed via pred show SpinGlass --json). Would cause compile error.

2. Ambiguous overhead. Two conflicting values given: "C(n,2) (pairwise for balance) or m (if balance via external field)." Must commit to one formula.

3. Algorithm not step-by-step. Mixes derivation with construction — should be numbered construction steps.

4. Internal inconsistency. Claims "coupling constants are J_ij = P for all pairs (balance enforcement via a global field)" but SpinGlass supports on-site fields h_i, not "global fields."

Required fixes

1. Fix Hamiltonian sign: use J_uv = +1/2 for Min-Bisection
2. Recalculate example with corrected signs
3. Replace num_couplings → num_interactions
4. Commit to single overhead formula
5. Restructure as numbered construction steps

[zazabap]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	⚠️ Warn	Source problem GraphPartitioning does not exist in the codebase yet
Non-trivial	✅ Pass	Genuine structural transformation with penalty terms for balance constraint
Correctness	✅ Pass	Both references verified; claims supported by literature
Well-written	❌ Fail	Wrong target metric name; ambiguous overhead; algorithm presents two formulations without committing

Overall: 2 passed, 1 warning, 1 failed

---

Usefulness

The source problem GraphPartitioning does not currently exist in the reduction graph (pred show GraphPartitioning fails). This means:

• No existing path can exist, so the reduction is novel in principle.
• However, implementing this rule requires first implementing the GraphPartitioning model. A separate [Model] issue should exist or be created for GraphPartitioning before this rule can proceed.

The motivation is reasonable — mapping graph bisection to the Ising model enables physics-based and quantum solvers.

Non-trivial

The reduction constructs an Ising Hamiltonian with:

• Antiferromagnetic couplings ($J_{uv} = -1/2$) for edge-cut objective
• A quadratic penalty term $P(\sum s_i)^2$ for the balance constraint

This involves genuine structural transformation (penalty encoding, variable domain change from binary to spin), not a trivial relabeling. Pass.

Correctness

Barahona, 1982 — "On the computational complexity of Ising spin glass models," J. Phys. A 15(10):3241–3253. ✅ Verified. Already in references.bib as barahona1982. Establishes NP-hardness of Ising ground state problems.

Lucas, 2014 — "Ising formulations of many NP problems," Frontiers in Physics 2:5. ✅ Verified. Already in references.bib as lucas2014. Explicitly covers graph partitioning as an Ising formulation (Section 2 of the paper). The claims in this issue are consistent with Lucas's treatment.

The example computation was manually verified: with $s = (-1,-1,-1,+1,+1,+1)$, 6 edges have $s_u s_v = +1$ (uncut) and 3 edges have $s_u s_v = -1$ (cut), giving $H = 3/2$ with zero balance penalty. This is correct.

Well-written

Failures:

1. Wrong target metric name. The overhead table uses num_couplings, but SpinGlass's actual size field is num_interactions (verified via pred show SpinGlass --json). The valid fields are num_spins and num_interactions. This must be corrected.

2. Ambiguous overhead. The num_couplings (should be num_interactions) entry says: "$\binom{n}{2}$ (pairwise for balance) or $m$ (if balance via external field)." A reduction algorithm must commit to a single construction. The two options correspond to fundamentally different SpinGlass instances — one with $O(n^2)$ interactions (encoding balance as pairwise couplings) and one with $O(m)$ interactions (using external fields). The issue must pick one approach and state it definitively.

3. Algorithm does not commit to one construction. The Ising Hamiltonian section presents the penalty term $P(\sum s_i)^2$ which expands to pairwise all-to-all couplings ($\binom{n}{2}$ terms), but then the "Equivalently" section mentions both pairwise couplings and a "global field." These are different constructions. The algorithm should describe exactly one step-by-step procedure.

4. Symbol P not given a concrete value or formula. The penalty parameter $P$ is used in the Hamiltonian but no guidance is given for choosing its value (e.g., $P > m/2$ to ensure feasibility dominates). The example uses $P = 5$ but does not explain why this value suffices.

Warnings:

• The coupling constant $J_{uv} = -1/2$ is described as "antiferromagnetic — prefers aligned spins = uncut edges." Actually, antiferromagnetic coupling ($J < 0$) penalizes alignment and prefers anti-alignment. The parenthetical note is physically backwards, though the math itself is correct because SpinGlass minimization with $-J_{uv} s_u s_v$ and $J_{uv} = -1/2$ yields $+1/2 \cdot s_u s_v$, which indeed prefers aligned spins ($s_u s_v = +1$). The terminology should be clarified.

Recommendations

• Create a [Model] issue for GraphPartitioning first (if one does not already exist), since it is a prerequisite.
• Commit to the pairwise penalty construction (expanding $P(\sum s_i)^2$ into $\binom{n}{2}$ pairwise terms absorbed into $J_{ij}$), since SpinGlass supports pairwise couplings but may not support external fields directly. Update the overhead table to num_interactions = n * (n - 1) / 2 (or m + n * (n - 1) / 2 if edge couplings and balance couplings are combined).
• Define $P$ explicitly in terms of the input size (e.g., $P > m$).
• Correct the field name from num_couplings to num_interactions.

[isPANN]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	✅ Pass	No existing path from GraphPartitioning to SpinGlass; novel connection
Non-trivial	✅ Pass	Genuine structural transformation with penalty encoding and variable domain change
Correctness	❌ Fail	Critical sign error — Hamiltonian encodes Max-Bisection, not Min-Bisection
Well-written	❌ Fail	Wrong metric name, ambiguous overhead, algorithm not step-by-step

Overall: 2 passed, 2 failed, 0 warnings

---

Usefulness

pred path GraphPartitioning SpinGlass returns no path — this reduction would be the first connection between these problems. The motivation (enabling physics-based and quantum solvers) is concrete and reasonable. Pass.

Non-trivial

The reduction constructs an Ising Hamiltonian with:

• Variable domain change: binary partition variables → spin variables $s_i \in {-1,+1}$
• Quadratic penalty term $P(\sum s_i)^2$ for the balance constraint, introducing $O(n^2)$ pairwise couplings
• Coupling constants encoding the edge-cut objective

This is genuinely structural, not a relabeling or subtype coercion. Pass.

Correctness

References verified:

• Barahona (1982): "On the computational complexity of Ising spin glass models," J. Phys. A 15(10):3241–3253. ✅ In bibliography as barahona1982. Establishes NP-hardness of Ising ground state problems.
• Lucas (2014): "Ising formulations of many NP problems," Frontiers in Physics 2:5. ✅ In bibliography as lucas2014. Covers graph partitioning Ising formulations.

Critical sign error in the Hamiltonian:

The issue defines $H = -\sum_{(u,v) \in E} J_{uv} s_u s_v + P(\sum s_i)^2$ with $J_{uv} = -1/2$. Substituting:

$$H = +\frac{1}{2}\sum_{(u,v) \in E} s_u s_v + P(\sum s_i)^2$$

For balanced partitions ($\sum s_i = 0$), this simplifies to $H = \frac{|E| - 2c}{2}$ where $c$ = number of cut edges. Minimizing $H$ maximizes $c$ — this is Max-Bisection, not Min-Bisection.

Verified by exhaustive enumeration of all 20 balanced partitions on the issue's 6-vertex graph:

• Claimed optimal $A={0,1,2}, B={3,4,5}$: $c=3$, $H=1.5$ — highest $H$ among balanced partitions (rank 19/20)
• Actual $H$-minimizer: $A={0,3,4}, B={1,2,5}$: $c=7$, $H=-2.5$ — the maximum cut bisection

The issue's stated goal (minimize cuts) contradicts the constructed Hamiltonian (which minimizes H ⟹ maximizes cuts).

Fix: Use $J_{uv} = +1/2$ (ferromagnetic). Then $H = -\frac{1}{2}\sum s_u s_v + \text{penalty} = \frac{2c - |E|}{2}$, and minimizing $H$ correctly minimizes cut edges.

Additional note: The parenthetical "antiferromagnetic — prefers aligned spins = uncut edges" is physically backwards. Antiferromagnetic coupling ($J < 0$) in the convention $-J \cdot s_u s_v$ prefers anti-alignment (cut edges), not alignment.

Well-written

Failures:

1. Wrong metric name. Overhead table uses num_couplings but SpinGlass's actual size field is num_interactions (confirmed via pred show SpinGlass --json). This would cause a compile error in the #[reduction(overhead = {...})] macro.

2. Ambiguous overhead. The num_couplings entry gives two conflicting formulas: "$\binom{n}{2}$ (pairwise for balance) or $m$ (if balance via external field)." A reduction must commit to exactly one construction. These correspond to fundamentally different SpinGlass instances.

3. Algorithm not step-by-step. The reduction is presented as a derivation mixing motivation with construction. Should be numbered construction steps: (1) create $n$ spin variables, (2) set coupling constants, (3) set on-site fields, (4) define solution extraction.

4. Penalty parameter $P$ undefined. The Hamiltonian uses $P$ but gives no concrete formula for choosing its value ($P > m/2$ would suffice). The example uses $P=5$ without justification.

5. Internal inconsistency. Claims "coupling constants are $J_{ij} = P$ for all pairs (balance enforcement via a global field)" but then gives two formulations. SpinGlass supports on-site fields $h_i$ (which could encode $\sum s_i$ linearly via a squared-penalty decomposition), but this is not the same as a "global field." The algorithm must clearly specify which SpinGlass fields are populated.

6. Overhead variable names vs source size_fields. The overhead expressions reference $n$ and $m$ informally. These must map to GraphPartitioning's getter methods (num_vertices, num_edges) — the issue should use the code names consistently.

Recommendations

• Fix the sign: use $J_{uv} = +1/2$ for Min-Bisection (or explicitly target Max-Bisection and rename accordingly)
• Commit to the pairwise penalty construction: absorb $P(\sum s_i)^2$ into $\binom{n}{2}$ pairwise coupling terms added to the edge couplings, giving num_interactions = num_vertices * (num_vertices - 1) / 2
• Define $P$ concretely (e.g., $P = \text{numedges} + 1$)
• Restructure as numbered steps
• Replace num_couplings → num_interactions
• Rework the example with corrected signs and fully enumerate all constructed couplings