Fourier — Graph-Spectral Oracle

The Fourier transform on a graph. Fourier reads the natural frequencies of a network: the Laplacian spectrum, the algebraic connectivity λ₂ (the Fiedler value), the Fiedler vector and its spectral bisection, and a spectral embedding. This is the global "how close is this network to splitting in two" structure that no per-node metric can express — and every eigenpair is certified trustlessly in O(E).

Part of the alexar76 oracle family — built natively on oracle-core, discoverable via AIMarket Protocol v2 (signed manifest, priced invoke, signed receipts, measured metrics).

The mathematics

Treat a graph as a vibrating drumhead. Build the adjacency A and degree D; the combinatorial Laplacian is L = D − A (the discrete −∇²), and the symmetric normalized Laplacian is L_sym = I − D^{-1/2} A D^{-1/2} (scale-invariant; spectrum in [0, 2]). Both are real symmetric PSD, so numpy.linalg.eigh gives an exact orthonormal eigendecomposition with 0 = λ₁ ≤ λ₂ ≤ ….

• λ₂ — algebraic connectivity (Fiedler value). Exactly 0 iff the graph is disconnected; small when the graph has a narrow bottleneck (it is near a split).
• Fiedler vector v₂ — the lowest-energy vibration mode. Its sign pattern is the canonical spectral bisection into two communities; the induced cut size and conductance quantify the bottleneck.
• Spectral embedding (v₂, v₃, v₄) — per-node coordinates in the space the connectivity implies (the basis of spectral clustering / graph drawing).

Trustless verification (a bound, not an equality). Given the graph and a claimed eigenpair (λ, x), a verifier checks ‖L x − λ x‖ / ‖x‖ ≤ tol (it really is an eigenpair) and that x ⟂ the trivial λ₁ eigenvector (a genuinely non-trivial mode). That O(E) certificate proves λ is a valid non-trivial Laplacian eigenvalue, and since every non-trivial eigenvalue is ≥ λ₂ (Courant–Fischer), it certifies λ ≥ λ₂ — an upper bound on the algebraic connectivity. It does not prove λ = λ₂: no single-eigenpair check can show λ is the smallest non-trivial eigenvalue without the full O(n³) eigendecomposition. fourier.spectrum@v1 runs that decomposition and returns the exact λ₂.

AIMarket capabilities

fourier.spectrum@v1

// input
{
  "edges": [["a","b"], ["b","c"], ["c","a", 2.0]],   // [u,v] or weighted [u,v,w]
  "nodes": ["a","b","c","d"],                          // optional (covers isolated nodes)
  "laplacian": "normalized",                           // "normalized" (default) | "combinatorial"
  "k": 6                                                // #smallest eigenvalues to return
}
// output
{
  "n": 4, "m": 3, "laplacian": "normalized",
  "eigenvalues": [0.0, 0.7, ...],
  "fiedler_value": 0.072,             // λ₂ of the selected Laplacian
  "combinatorial_lambda2": 0.298,     // always reported (dimensionful connectivity)
  "fiedler_vector": [ ... ],          // per node, in canonical (sorted-label) order
  "spectral_cut": { "set_a": [...], "set_b": [...], "cut_size": 1.0, "conductance": 0.048 },
  "embedding": [[v2,v3,v4], ...],     // per node
  "nodes": ["a","b","c","d"],
  "graph_commitment": "…sha256…"
}

fourier.verify@v1

// input — re-derives L and checks the certificate
{ "edges": [...], "laplacian": "combinatorial", "lambda": 0.298, "vector": [ ... ] }
// output
{ "valid": true, "residual": 1e-12, "orthogonality": 0.0, "is_eigenpair": true,
  "is_nontrivial": true, "lambda2_upper_bound": 0.298, "graph_commitment": "…" }

valid is true iff the residual is within tolerance (≤ tol) and the vector is non-trivial — orthogonal to the all-ones / d^{1/2} λ₁ mode to within the same caller-supplied tol (no hidden threshold). A valid certificate proves λ is a genuine non-trivial eigenvalue, hence λ ≥ λ₂ (reported as lambda2_upper_bound). It is an upper bound on the algebraic connectivity, not a proof that λ is the Fiedler value itself.

Notes

• Size clamp. The dense symmetric eigendecomposition is O(n³); the handler clamps the graph to MAX_NODES = 400. The protocol layer does not validate input against the schema, so the handler validates required fields (raising ValueError, surfaced as {ok:false, error}) and enforces the ceiling.
• Canonicalisation. Node labels are sorted unique, undirected edges de-duplicated (parallel weights summed), self-loops dropped, and the graph hashed to a graph_commitment — the whole analysis is a pure function of that committed graph.
• Determinism. Eigenvector signs are arbitrary; the Fiedler vector is oriented deterministically (largest-magnitude component positive) so results are stable.

Run

# from the monorepo root
PYTHONPATH="oracles/core:oracles/oracles/fourier" \
  platon/backend/.venv/bin/python -m pytest oracles/oracles/fourier/tests/ -q

# serve
FOURIER_PORT=9315 python -m fourier.main