A Boolean-weighted graph is a finite graph whose edges carry DNF formulas over a common variable set. This paper studies two isomorphism problems on such graphs, distinguished by whether the per-edge condition requires the matched edge labels to be syntactically DNF-isomorphic (BWG-ISO) or syntactically DNF non-isomorphic (BWG-NI), each over a vertex bijection that preserves edges. The two sit at opposite ends of one phenomenon: imposing local syntactic DNF-isomorphism on every edge does not raise complexity above graph isomorphism, whereas replacing it by local non-isomorphism makes the problem NP-hard, the jump being driven by the search over host isomorphisms rather than by the complexity of the labels. For the isomorphism requirement, BWG-ISO $\equiv_m^p$ GI: although syntactic DNF isomorphism is itself GI-complete (Ausiello, Cristiano, and Laura 2012), attaching such a label to every edge leaves the global problem exactly at GI. For the non-isomorphism requirement, the per-edge test is a graph-non-isomorphism query, placing BWG-NI in $NP^{GI}$; the paper shows it is GI-hard and GNI-hard and not coNP-hard unless PH $= \Sigma_2^P$, and proves it is NP-hard. The hardness already holds when labels are restricted to monotone DNFs, equivalently $\{0,1\}$-matrices, so it stems from the interaction with host automorphisms, not from rich Boolean structure. This NP-hardness is unconditional; the hardest NP set known to $\le_m^p$-reduce to FI is GI (Agrawal and Thierauf 2000). BWG-NI is thereby a natural inhabitant of $NP^{GI}$: with the NP-hardness, $NP^{GI}$ membership places it outside $P^{GI}$, $coNP^{GI}$, and $Low_2$ unless PH $= \Sigma_2^P$, making it a natural candidate to separate $NP^{GI}$ from $P^{GI}$ when the hierarchy is infinite. The second-level collapse that would be forced by its $\Sigma_2^P$-completeness is one level below the third-level collapse Agrawal and Thierauf obtain for the formula isomorphism problem FI, reflecting that BWG-NI, unlike the coNP-hard FI, lies in $NP^{GI}$. The counting problem #BWG-NI is #P-hard.

Corrections to statements and to attributions; no result is retracted; two statements are reworded to what the proofs establish (item 1).

(1) The conjunctive closure of GNI is the class of sets $\le_m^p$-reducible to GNI, not its degree; corrected at five sites, Theorem 7.2 and Proposition 7.3 restated accordingly.

(2) Theorem 3.5: output size is quadratic, the map polynomial-time (previously stated as linear).

(3) Fact 2.3: value-encoding order corrected to match [ACL12].

(4) Figure 3: host-host chords not in Construction 3.1 removed.

(5) Proposition 4.2: guard added for $|V_G| \ne |V_H|$.

(6) Attributions: USAT $\le_m^p$ FC to [BRS98, Proposition 10]; Lemma 6.1 after [Sch88]; [BR93] title corrected; [AT00, Corollary 3.4] pinpointed.

(7) DNF term-multiset convention declared.

(8) Section 9: exhaustive machine verification of Theorem 5.1 recorded; section reorganised as scope, provenance, and open problems.

(9) Added: an introduction motivation paragraph and two consequences of the precomputable-oracle question.

(10) Minor wording, caption, and bibliography corrections; layout changed to a standard article format.

A Boolean-weighted graph is a finite graph whose edges carry DNF formulas over a common variable set. This paper studies two isomorphism problems on such graphs, distinguished by whether the per-edge condition requires the matched edge labels to be syntactically DNF-isomorphic (BWG-ISO) or syntactically DNF non-isomorphic (BWG-NI), each over a vertex bijection that preserves edges. The two sit at opposite ends of one phenomenon: imposing local syntactic DNF-isomorphism on every edge does not raise complexity above graph isomorphism, whereas replacing it by local non-isomorphism makes the problem NP-hard, the jump being driven by the search over host isomorphisms rather than by the complexity of the labels. For the isomorphism requirement, BWG-ISO $\equiv_m^p$ GI: although syntactic DNF isomorphism is itself GI-complete (Ausiello, Cristiano, and Laura 2012), attaching such a label to every edge leaves the global problem exactly at GI. For the non-isomorphism requirement, the per-edge test is a graph-non-isomorphism query, placing BWG-NI in $NP^{GI}$; the paper shows it is GI-hard and GNI-hard and not coNP-hard unless PH $= \Sigma_2^P$, and proves it is NP-hard. The hardness already holds when labels are restricted to monotone DNFs, equivalently $\{0,1\}$-matrices, so it stems from the interaction with host automorphisms, not from rich Boolean structure. This NP-hardness is unconditional; the hardest NP set known to $\le_m^p$-reduce to FI is GI (Agrawal and Thierauf 2000). BWG-NI is thereby a natural inhabitant of $NP^{GI}$: with the NP-hardness, $NP^{GI}$ membership places it outside $P^{GI}$, $coNP^{GI}$, and $Low_2$ unless PH $= \Sigma_2^P$, making it a natural candidate to separate $NP^{GI}$ from $P^{GI}$ when the hierarchy is infinite. The second-level collapse that would be forced by its $\Sigma_2^P$-completeness is one level below the third-level collapse Agrawal and Thierauf obtain for the formula isomorphism problem FI, reflecting that BWG-NI, unlike the coNP-hard FI, lies in $NP^{GI}$. The counting problem #BWG-NI is #P-hard.