filter permutation invariance

[[concept]]

invariant to permutations

Let $S$ be a graph shift operator. A graph filter $H (S)$ is permutation invariant if $S$ is permutation invariant.

If $S$ is permutation invariant, then since $H$ is also permutation invariant, we have

| | S - S^{'} | |_{p} = 0 ⟹ | | H (S) - H (S^{'}) | |_{p} = 0

Where $| | \cdot | |_{p}$ is the operator distance modulo permutations

For GNNs, we have equivalently $| | S - S^{'} | |_{p} = 0 ⟹ | | Φ (S) - Φ (S^{'}) | |_{p} = 0$ since this is a composed graph convolution

permutation invariant (alternate definition)

Recall the definition for invariant:

Invariant

Let $G$ be a group acting on a (data) set $X$ . Then $F : X \to Y$ is invariant if
$F (g \circ x) = F (x) \forall g \in G and x \in X$

If $G$ is a permutation group and $F$ , then for any $F^{'} = g \circ F$ , we have $F$ is permutation invariant if and only if
$| | F - F^{'} | |_{p (= g)} = 0$
That is, $F$ is invariant to permutations if and only if its operator distance modulo permutations is 0.

This follows directly from the definition of invariance.

Mentions

File
additive perturbations
2025-03-05 graphs lecture 12