graph edit distance

[[concept]]

L_{1}

norm for graphs

Let $G$ and $G^{'}$ be graphs with the same $n$ and the same node sets $V = V^{'}$ (ie, same node labelling). The $L_{1}$ norm or “edit distance” is given by

d_{1} (G, G^{'}) = | | A - A^{'} | |_{1} $ $ w h e r e $ A, A^{'} $ a r e t h e u n w e i g h t e d [[C o n c e p t W i k i / a d j a c e n c y m a t r i x ∥ a d j a c e n c y m a t r i c e s]] o f $ G, G^{'} $ r e s p e c t i v e l y .

Mentions

File
cut norm
2025-03-24 graphs lecture 14

Created 2025-03-24 Last Modified 2025-05-13