cut distance

[[concept]]

Cut distance (arbitrary graphs)

Let $G_{n}$ and $G_{m}$ be two graphs with possibly different node counts $n$ and $m$ respectively. The cut distance is given by

δ_{◻} (G_{n}, G_{m}) = δ_{◻} (W_{n}, W_{m})

Where $W_{n}, W_{m}$ are the induced graphons of the graphs.

Special Cases

cut distance (same node count, same labels)

Let $G$ and $G^{'}$ be graphs with the same $n$ and the same node sets $V = V^{'}$ (ie, same node labelling). The cut distance is given by

d_{◻} (G, G^{'}) = | | A - A^{'} | |_{◻}

where $| | \cdot | |_{◻}$ is the cut norm.

cut distance (same node count, potentially different labels)

Let $G$ and $G^{'}$ have the same number of nodes $n$ . The cut distance is given by

{\hat{δ}}_{◻} (G, G^{'}) = min_{p \in P} | | A - P^{T} A^{'} P | |_{◻}

ie, we look at all possible permutations of the nodes of $G^{'}$ WRT the node labelings of $G$ .

Arbitrary graphs {are not comparable as graphs on their own}, so we compare them as {induced graphons} instead

File
convergent sequence of graph signals
graphon signal
kernel cut metric
2025-03-24 graphs lecture 14
2025-03-26 lecture 15
2025-03-31 lecture 16

Created 2025-03-24 Last Modified 2025-06-04