Invariant and Equivariant Graph Networks-JZTXT

Maron H., Ben-Hamu H., Shamir N. and Lipman Y. Invariant and equivariant graph networks. ICLR, 2019.

概

有些时候, 我们希望网络具有:

本文主要讨论, 有那些线性算子在处理(超)图的时候是满足上述(性质之一). 这里不会特别详细推导其中的结果, 单纯知识记一笔以备不时之需.

\(\mathcal{G} = (\mathbb{V}, \mathsf{A})\), 其中 \(\mathbb{V}\) 表示结点的集合, \(\mathsf{A}\) 是图中 (hyper)-edge 的值.
它的使用方式应当视上下文而定, 比如 \(\mathsf{A}_i\) 是 \(i\)-th node 的值, \(\mathsf{A}_{ij}\) 可以是 edge (i, j) 所对应的值, \(\mathsf{A}_{i_1, \ldots, i_k}\) 可以是 hyper-edge \((i_1, i_2, \ldots, i_k)\) 上的值.
\(\text{vec}(X)\) 表示将矩阵 \(X\) 按列拉成向量;
\([\cdot]\) 为 \(\text{vec}(\cdot)\) 的逆, 即 \([\text{vec}(X)] = X\);
\(X \otimes Y\) 表示 Kronecker product.

假设 \(\mathsf{A} = A \in \mathbb{R}^{n \times n}\) 为普通图的邻接矩阵, \(P \in \mathbb{R}^{n \times n}\) 为一置换矩阵, 则映射 \(f\) 是 order-invariant 若:

\[f(P^TAP) = f(A). \]
推广到更加一般的情形, \(\mathsf{A} \in \mathbb{R}^{n^k}\), 并定义 \(\bm{P}\) 为一 permutation 矩阵, 则 \(f\) 是 order-invariant 的若

\[f(\bm{P} \star \mathsf{A}) = f(\mathsf{A}). \]

假设 \(\mathsf{A} = A \in \mathbb{R}^{n \times n}\) 为普通图的邻接矩阵, \(P \in \mathbb{R}^{n \times n}\) 为一置换矩阵, 则映射 \(f\) 是 order-equivarint 若:

\[f(P^TAP) = P^Tf(A)P. \]
推广到更加一般的情形, \(\mathsf{A} \in \mathbb{R}^{n^k}\), 并定义 \(\bm{P}\) 为一 pertutation 矩阵, 则 \(f\) 是 order-equivarint 的若

\[f(\bm{P} \star \mathsf{A}) = \bm{P} \star f(\mathsf{A}). \]

\(\mathsf{A} = \bm{A} \in \mathbb{R}^{n \times n}\).
令 \(L: \mathbb{R}^{n \times n} \rightarrow \mathbb{R}\) 为一线性算子, 则它是 oder-invariant 当且仅当:

\[\bm{L} \text{vec}(\bm{P}^T \bm{AP}) = \bm{L} \text{vec}(\bm{A}), \]
对于任意 permutation matrix \(\bm{P}\) 均成立, 其中 \(\bm{L} \in \mathbb{R}^{1 \times n^2}\) 为算子 \(L\) 的矩阵表示.
则

\[\begin{array}{ll} &\bm{L} \text{vec}(\bm{P}^T \bm{AP}) = \bm{L} \text{vec}(\bm{A}) \\ \Leftrightarrow &\bm{L} \bm{P}^T \otimes \bm{P}^T \text{vec}(\bm{A}) = \bm{L} \text{vec}(\bm{A}) \\ \Leftrightarrow &\bm{L} \bm{P}^T \otimes \bm{P}^T = \bm{L} \\ \Leftrightarrow & (\bm{L} \bm{P}^T \otimes \bm{P}^T)^T = (\bm{L})^T \\ \Leftrightarrow & \bm{P} \otimes \bm{P} \text{vec}(\bm{L}) = \text{vec}(\bm{L}). \end{array} \]
不妨记为:

\[\tag{1} \bm{P}^{\otimes 2} \text{vec}(\bm{L}) = \text{vec}(\bm{L}). \]
类似的, 令 \(L: \mathbb{R}^{n \times n} \rightarrow \mathbb{R}^{n \times n}\) 为一线性算子, 则它是 oder-invariant 当且仅当:

\[[\bm{L} \text{vec}(\bm{P}^T \bm{AP})] = \bm{P}^T[\bm{L}\text{vec}(\bm{A})] \bm{P}, \]
对于任意 permutation matrix \(\bm{P}\) 均成立, 其中 \(\bm{L} \in \mathbb{R}^{n^2 \times n^2}\) 为算子 \(L\) 的矩阵表示.
类似的, 我们可以得到如下的方程:

\[\tag{2} \bm{P}^{\otimes 4} \text{vec}(\bm{L}) = \text{vec}(\bm{L}). \]

一个线性算子 \(L: \mathbb{R}^{n^k} \rightarrow \mathbb{R}\) 是 order-invariant 的若

\[\tag{3} \bm{P}^{\otimes k} \text{vec}(\bm{L}) = \text{vec}(\bm{L}). \]
一个线性算子 \(L: \mathbb{R}^{n^k} \rightarrow \mathbb{R}^{n^k}\) 是 order-invariant 的若

\[\tag{4} \bm{P}^{\otimes 2k} \text{vec}(\bm{L}) = \text{vec}(\bm{L}). \]

注: 作者还介绍了如何求解, 以及推广到 \(\mathsf{A} \in \mathbb{R}^{n^k \times d}\), 即每个 hyper-edge 存在 features 的情形.