graph_edit_cost
def
The edit cost $\mathcal{C}_{\mathsf{ed}}(Q)$ of a fractional alignment matrix $Q$ between two $n \times n$ matrices $A$ and $B$ is the sum over all $v, v', w, w' \in \{0, \dots, n-1\}$ of $|A(v, v') - B(w, w')| Q(v, w) Q(v', w')$.
Statement
def graph_edit_cost {n : ℕ} (A B : Matrix (Fin n) (Fin n) ℝ) (Q : Matrix (Fin n) (Fin n) ℝ) : ℝ- Defined in
- arXiv:2611.05048 Section 2 and Section 3
- Verified
- 04 Nov 2026
- Axioms
- none listed
- Used by 4
- perm_edit_cost_eq_graph_edit_costFor any permutation $\pi$ of $\{0, \dots, n-1\}$ and matrices $A, B$, the permutation edit cost $\mathcal{C}_{\mathsf{ed}}(\pi)$ equals…
- simple_graph_edit_cost_permutation_decomposition_le_two_mulFor any simple graphs $G$ and $H$ on $n$ vertices and any doubly stochastic matrix $Q$ with a convex decomposition into permutation…
- graph_edit_cost_permutation_decomposition_le_two_mulLet $Q$ be an $n \times n$ doubly stochastic matrix with a convex decomposition $Q = \sum_{i \in \iota} w_i P_{\pi_i}$, where $w_i \ge 0$,…
- graph_edit_cost_nonnegFor any $n \times n$ real matrices $A$ and $B$ and any matrix $Q$ with non-negative entries, the edit cost $\mathcal{C}_{\mathsf{ed}}(Q)$…
Read back from the Lean
For a natural number n and n × n real matrices A, B, and Q, graph_edit_cost A B Q is defined as the quadruple sum over all v, v', w, w' ∈ Fin n of |A v v' - B w w'| * Q v w * Q v' w'.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- The edit cost of a fractional alignment matrix Q between two matrices A and B. -/ def graph_edit_cost {n : ℕ} (A B : Matrix (Fin n) (Fin n) ℝ) (Q : Matrix (Fin n) (Fin n) ℝ) : ℝ := ∑ v : Fin n, ∑ v' : Fin n, ∑ w : Fin n, ∑ w' : Fin n, |A v v' - B w w'| * Q v w * Q v' w'