Structure Discovery via Interaction Matrix

Hypothesis

The gradient interaction matrix \(\alpha_{ij} = \cos(\nabla L_i, \nabla L_j)\) can serve as a topology probe, recovering the constraint graph of a multi-objective problem. Independent constraints should produce orthogonal gradients (\(\alpha_{ij} = 0\)), while coupled constraints should produce cooperative gradients (\(\alpha_{ij} > 0\)). The skeptic diagnostic should estimate problem hardness, and a phase transition in solvability should be detectable as the constraint-to-variable ratio \(M/N\) increases.

Method

1. Constraint graph discovery: Construct a 3-constraint problem where C1 and C3 operate on disjoint variable sets (should be orthogonal) while C1↔C2 and C2↔C3 share variables (should be cooperative). Measure pairwise gradient cosines \(\alpha_{ij}\) at convergence.
2. Hardness diagnostic: Apply the skeptic diagnostic to estimate problem difficulty from the interaction structure at the current coupling level.
3. Phase transition: Sweep \(M/N\) from under-constrained to over-constrained regimes and measure the residual at convergence to detect the satisfiability transition.

Results

Constraint Graph Discovery

C1↔C3 correctly identified as orthogonal (\(\cos = 0\) exactly). The cooperative pairs show non-zero cosines, but the magnitudes (0.20 vs 0.87) do not directly reflect the number of shared variables — they reflect how similarly the gradients point in parameter space.

Key Finding: Gradient Topology vs Constraint Topology

The cosine values reveal the gradient topology (how gradients align), not the constraint topology (which variables are shared). C2↔C3 has cosine 0.87 despite potentially fewer shared variables than C1↔C2, because the gradient directions happen to be more aligned. Orthogonality (\(\alpha = 0\)) reliably indicates independence, but \(\alpha > 0\) encodes gradient geometry, not constraint graph edges.

Hardness Diagnostic

The skeptic diagnostic did not produce a definitive hardness ranking at this coupling strength. The interaction magnitudes are too moderate for the skeptic to distinguish easy from hard instances. This suggests the diagnostic requires stronger coupling or more constraints to become informative.

Phase Transition

Sharp phase transition at \(M/N \approx 0.75\): the residual jumps from 0 to 1.92 over a narrow interval. Below the threshold all constraints are simultaneously satisfiable; above it the system is forced into a non-zero residual compromise.

Analysis

• Orthogonality detection works: The interaction matrix correctly identifies C1↔C3 as independent (\(\cos = 0\)). This is the reliable signal — zero cosine means zero gradient coupling.
• Non-zero cosines are ambiguous: The magnitude of \(\alpha_{ij}\) for coupled constraints reflects gradient alignment geometry, not the degree of variable sharing. This is a weaker signal than originally hypothesised. The interaction matrix is a gradient topology probe, not a constraint topology probe.
• Skeptic diagnostic needs stronger signal: At moderate coupling, the skeptic cannot reliably rank hardness. This is an open question for future work — the diagnostic may require a threshold coupling strength to activate.
• Phase transition is clear: The \(M/N \approx 0.75\) transition is sharp and unambiguous. The residual serves as a direct satisfiability indicator.

Conclusion

Partial — Orthogonality detection confirmed (C1↔C3 cosine = 0 exactly). Phase transition detected at \(M/N \approx 0.75\). However, gradient cosines reveal gradient topology rather than constraint topology, and the skeptic diagnostic is inconclusive at current coupling. Theorem 4 is partially validated: the topology discovery mechanism works for independence but requires refinement for quantitative coupling strength.

Reproducibility

../simplex/build/sxc exp_structure_discovery.sx -o build/exp_structure_discovery.ll

OPENSSL_PREFIX=$(brew --prefix openssl)
clang -O2 build/exp_structure_discovery.ll \
  ../simplex/runtime/standalone_runtime.c \
  -o build/exp_structure_discovery \
  -lm -lssl -lcrypto -L${OPENSSL_PREFIX}/lib

./build/exp_structure_discovery

Related Theorems

• Theorem 4 — Interaction Matrix / Topology Discovery
• Theorem 6 — Belief Systems
• exp-interaction-matrix — Interaction Matrix Validation
• exp-equilibrium-mapping — Equilibrium from Gradient Topology