On the equivalence between graph isomorphism testing and function approximation with GNNs
Graph Neural Networks (GNNs) have achieved much success on graph-structured data. In light of this, there have been increasing interests in studying their expressive power. One line of work studies the capability of GNNs to approximate permutation-invariant functions on graphs, and another focuses on the their power as tests for graph isomorphism. Our work connects these two perspectives and proves their equivalence. We further develop a framework of the expressive power of GNNs that incorporates both of these viewpoints using the language of sigma-algebra, through which we compare the expressive power of different types of GNNs together with other graph isomorphism tests. In particular, we prove that the second-order Invariant Graph Network fails to distinguish non-isomorphic regular graphs with the same degree. Then, we extend it to a new architecture, Ring-GNN, which succeeds in distinguishing these graphs and achieves good performances on real-world datasets.
\section{Conclusions}

In this work we address the important question of organizing the fast-growing zoo 
of GNN architectures in terms of what functions they can and cannot represent. 
We follow the approach via the graph isomorphism test, and show that is equivalent 
to the other perspective via function approximation. 
We leverage our graph isomorphism reduction to augment order-$2$ G-invariant nets 
with the ring of operators associated with matrix multiplication, which gives provable gains in expressive power with complexity $O(n^3)$, and is amenable to efficiency gains by leveraging sparsity in the graphs. 

Our general framework leaves many interesting questions unresolved. First, a more comprehensive analysis on which elements of the 
algebra are really needed depending on the application. Next, our current GNN taxonomy is still incomplete, and in particular we believe 
it is important to further discern the abilities between spectral and neighborhood-aggregation-based architectures. 
Finally, and most importantly, our current notion of invariance (based on permutation symmetry) defines a topology in the space of graphs that is too strong; in other words, two graphs are either considered equal (if they are isomorphic) or not. Extending the theory of symmetric universal 
approximation to take into account a weaker metric in the space of graphs, such as the Gromov-Hausdorff distance, is a natural next step, that will better reflect the stability requirements of powerful graph representations to small graph perturbations in real-world applications. 


\paragraph{Acknowledgements} We would like to thank Haggai Maron for fruitful discussions and for pointing us towards $G$-invariant networks as powerful models to study representational power in graphs. 
This work was partially supported by NSF grant RI-IIS 1816753, NSF CAREER CIF 1845360, the Alfred P. Sloan Fellowship, Samsung GRP and Samsung Electronics.
SV was partially funded by EOARD FA9550-18-1-7007 and the Simons Collaboration Algorithms and Geometry.
\section{Graph G-invariant Networks with maximum tensor order 2} \label{app.Ginvariant}




In this section we prove Theorem \ref{prop.Ginvariant} that says that graph G-invariant Networks with tensor order 2 cannot distinguish between non-isomorphic regular graphs with the same degree.

First, we need to state our definition of the order-2 Graph $G$-invariant Networks. In general, given $G \in \mathbb{R}^{n \times n}$, we let $A^{(0)} = G$, $d^{(0)} = 1$, and
\[
A^{(t+1)} = \sigma(L^{(t)}(A^{(t)}))
\]
and outputs $m \circ h \circ A^{(L)}$, where each $L^{(t)}$ is an equivariant linear layer from $\mathbb{R}^{n \times n \times d^{(t)}}$ to $\mathbb{R}^{n \times n \times d^{(t+1)}}$, $\sigma$ is a point-wise activation function, $h$ is an invariant linear layer from $\mathbb{R}^{n \times n}$ to $\mathbb{R}$, and $m$ is an MLP.

$d^{(t)}$ is the feature dimension in layer $t$, interpreted as the dimension of the hidden state attached to each pair of nodes. For simplicity of notations, in the following proof we assume that $d^{(t)} = 1, \forall t = 1, ..., L$, and thus each $A^{(t)}$ is essentially a matrix.
The following results can be extended to the cases where $d^{(t)} > 1$, by adding more subscripts in the proof.

Given an unweighted graph $G$, let $E \subseteq [n]^2$ be the edge set of $G$, i.e., $(u, v) \in E$ if $u \neq v$ and $G_{uv} = 1$; set $S \subseteq [n]^2$ to be $\{ (u, u) \}_{u \in [n]^2}$; and let $N = [n]^2 \setminus (E \cup S)$. Thus, $E \cup N \cup S = [n]^2$.

\begin{lemma}
Let $G, G'$ be the adjacency matrices of two unweighted regular graphs with the same degree $d$, and let $A^{(t)}, E, N, S$ and $A'^{(t)}, E', N', S'$ be defined as above for $G$ and $G'$, respectively. Then $\forall n \leq L, \exists \xi_1^{(t)}, \xi_2^{(t)}, \xi_3^{(t)} \in \mathbb{R}$ such that $A^{(t)}_{uv} = \xi_1^{(t)} \mathds{1}_{(u, v) \in E} + \xi_2^{(t)} \mathds{1}_{(u, v) \in N} + \xi_3^{(t)} \mathds{1}_{(u, v) \in S}$, and $A'^{(t)}_{uv} = \xi_1^{(t)} \mathds{1}_{(u, v) \in E'} + \xi_2^{(t)} \mathds{1}_{(u, v) \in N'} + \xi_3^{(t)} \mathds{1}_{(u, v) \in S'}$
\end{lemma}

\begin{proof}
We prove this lemma by induction. For $t=0$, $A^{(0)} = G$ and $A'^{(0)} = G'$. Since the graph is unweighted, $G_{uv} = 1$ if $u \neq v$ and $(u, v) \in E$, and $0$ otherwise. Similar is true for $G'$. Therefore, we can set $\xi_1^{(0)} = 1$ and $\xi_2^{(0)} = \xi_3^{(0)} = 0$.

Next, we consider the inductive steps. Assume that the conditions in the lemma are satisfied for layer $t-1$. To simplify the notation, we use $A, A'$ to stand for $A^{(t-1)}, A'^{(t-1)}$, and we assume to satisfy the inductive hypothesis with $\xi_1, \xi_2$ and $\xi_3$. We thus want to show that if $L$ is any equivariant linear, then $\sigma(L(A)), \sigma(L(A'))$ also satisfies the inductive hypothesis. Also, in the following, we use $p_1, p_2, q_1, q_2$ to refer to nodes, $a, b$ to refer to pairs of nodes, $\lambda$ to refer to any equivalence class of 2-tuples (i.e. pairs) of nodes, and $\mu$ to refer to any equivalence class of 4-tuples of nodes.


$\forall a = (p_1, p_2), b = (q_1, q_2) \in [n]^2$, let $\mathcal{E}(a, b)$ denote the equivalence class of 4-tuples containing $(p_1, p_2, q_1, q_2)$, and let $\mathcal{E}(b)$ represent the equivalence class of 2-tuples containing $(q_1, q_2)$. 
Two 4-tuples $(u, v, w, x), (u', v', w', x')$ are considered equivalent if $\exists \pi \in S_n$ such that $\pi(u) = u', \pi(v) = v', \pi(w) = w', \pi(x) = x'$. Similarly is equivalence between 2-tuples defined. By equation 9(b) in \cite{maron2018invariant}, using the notations of $T, B, C, w, \beta$ defined there, $L$ is described by, given $A$ as an input as $b$ as the subscript index on the output,
\begin{equation}
    \begin{split}
        L(A)_{b} &= \sum_{a = (p_1, p_2) = (1, 1)}^{(n, n)} T_{a, b} A_a + Y_b \\
        &= \sum_{a, \mu} w_{\mu} B_{a, b}^{\mu} A_a + \sum_\lambda \beta_\lambda C_b^\lambda\\
        &= \sum_\mu (\mathop{\sum_{a \in [n]^2}}_{(a, b) \in \mu} A_a) w_\mu + \beta_{\mathcal{E}(b)}
    \end{split}
\end{equation}
 

First, let 
\[S_{\mu}^b = \mathop{\sum_{a \in [n]^2}}_{(a, b) \in \mu} A_a\]
By the inductive hypothesis, 
\begin{equation}
\begin{split}
    S_{\mu}^b &= \mathop{\mathop{\sum_{a \in [n]^2}}_{(a, b) \in \mu}}_{a \in E} A_a + \mathop{\mathop{\sum_{a \in [n]^2}}_{(a, b) \in \mu}}_{a \in N} A_a + \mathop{\mathop{\sum_{a \in [n]^2}}_{(a, b) \in \mu}}_{a \in S} A_a \\
    &= \mathop{\mathop{\sum_{a \in [n]^2}}_{(a, b) \in \mu}}_{a \in E} \xi_1 + \mathop{\mathop{\sum_{a \in [n]^2}}_{(a, b) \in \mu}}_{a \in N} \xi_2 + \mathop{\mathop{\sum_{a \in [n]^2}}_{(a, b) \in \mu}}_{a \in S} \xi_3 \\
    &= m_E(b, \mu) \xi_1 + m_N(b, \mu) \xi_2 + m_S(b, \mu) \xi_3
\end{split}
\end{equation}
where $m_E(b, \mu)$ is defined as the total number of distinct $a \in [n]^2$ that satisfies $(a, b) \in \mu$ and $a \in E$, and similarly for $m_N(b, \mu)$ and $m_S(b, \mu)$. Formally, for example, $m_E(b, \mu) = card\{ a \in [n]^2 : (a, b) \in \mu, a \in E\}$.

Since $E \cup N \cup S = [n]^2$, $b$ belongs to one of $E, N$ and $S$. Thus, let $\tau(b) = E$ if $b \in E$, $\tau(b) = N$ if $b \in N$ and $\tau(b) = S$ if $b \in S$. It turns out that if $A$ is the adjacency matrix of a undirected regular graph with degree $d$, then $m_E(b, \mu), m_N(b, \mu), m_S(b, \mu)$ can be instead written (with an abuse of notation) as $m_E(\tau(b), \mu), m_N(\tau(b), \mu), m_S(\tau(b), \mu)$, meaning that for a fixed $\mu$, the values of $m_E, m_N$ and $m_S$ only depend on which of the three sets ($E, N$ or $S$) $b$ is in, and changing $b$ to a different member in the set $\tau(b)$ won't change the three numbers. In fact, for each $\tau(b)$ and $\mu$, the three numbers can be computed as functions of $n$ and $d$ using simple combinatorics, and their values are seen in the three tables \ref{table:mE}, \ref{table:mN} and \ref{table:mS}. An illustration of these numbers is given in Figure \ref{coloredreg}.
\begin{figure}
\label{coloredreg}
    \centering
    \includegraphics[width=0.25\textwidth,trim={6cm 4cm 20cm 7cm},clip]{skl2color2}
    \includegraphics[width=0.25\textwidth,trim={6cm 4cm 20cm 7cm},clip]{skl3color2}
    \caption{$m_E(E, \mathcal{E}(1, 2, 3, 4))$, $m_E(E, \mathcal{E}(1, 2, 3, 2))$, $m_E(E, \mathcal{E}(1, 2, 3, 1))$, $m_E(E, \mathcal{E}(1, 2, 2, 3))$ and $m_E(E, \mathcal{E}(1, 2, 1, 3))$ of $G_{8, 2} $ and $G_{8, 3}$. In either graph, twice the total number of black edges equal $m_E(E, \mathcal{E}(1, 2, 3, 4)) = 18$ (it is twice because each undirected edge corrspond to two pairs $(p_1, p_2)$ and $(p_2, p_1)$, which combined with $(q_1, q_2)$ both belongs to $\mathcal{E}(1, 2, 3, 4)$); the total number of of red edges, $3$, equals both $m_E(E, \mathcal{E}(1, 2, 2, 3))$ and $m_E(E, \mathcal{E}(1, 2, 1, 3))$; the total number of green edges, also $3$, equals both $m_E(E, \mathcal{E}(1, 2, 3, 2))$, $m_E(E, \mathcal{E}(1, 2, 3, 1))$.}
    \label{fig:my_label}
\end{figure}

\begin{table}[h]
\centering
\begin{tabular}{llll}
\multicolumn{1}{l|}{$\mu$}        & $m_E(E, \mu)$ & $m_E(N, \mu)$ & $m_E(S, \mu)$ \\ \hline
\multicolumn{1}{l|}{(1, 2, 3, 4)} & $(n-4)d+2$      & $(n-4)d$        & 0             \\
\multicolumn{1}{l|}{(1, 1, 2, 3)} & 0             & 0             & 0             \\
\multicolumn{1}{l|}{(1, 2, 2, 3)} & $d-1$           & $d$             & 0             \\
\multicolumn{1}{l|}{(1, 2, 1, 3)} & $d-1$           & $d$             & 0             \\
\multicolumn{1}{l|}{(1, 2, 3, 2)} & $d-1$           & $d$             & 0             \\
\multicolumn{1}{l|}{(1, 2, 3, 1)} & $d-1$           & $d$             & 0             \\
\multicolumn{1}{l|}{(1, 1, 1, 2)} & 0             & 0             & 0             \\
\multicolumn{1}{l|}{(1, 1, 2, 1)} & 0             & 0             & 0             \\
\multicolumn{1}{l|}{(1, 2, 1, 2)} & 1             & 0             & 0             \\
\multicolumn{1}{l|}{(1, 2, 2, 1)} & 1             & 0             & 0             \\
\multicolumn{1}{l|}{(1, 2, 3, 3)} & 0             & 0             & $(n-2)d$        \\
\multicolumn{1}{l|}{(1, 1, 2, 2)} & 0             & 0             & 0             \\
\multicolumn{1}{l|}{(1, 2, 2, 2)} & 0             & 0             & $d$             \\
\multicolumn{1}{l|}{(1, 2, 1, 1)} & 0             & 0             & $d$             \\
\multicolumn{1}{l|}{(1, 1, 1, 1)} & 0             & 0             & 0             \\ \hline
\multicolumn{1}{l|}{Total}                             & $nd$            & $nd$            & $nd$           
\end{tabular}
\caption{$m_E$}
\label{table:mE}
\end{table}

\begin{table}[h]
\centering
\begin{tabular}{llll}
\multicolumn{1}{l|}{$\mu$}        & $m_N(E, \mu)$ & $m_N(N, \mu)$ & $m_N(S, \mu)$ \\ \hline
\multicolumn{1}{l|}{(1, 2, 3, 4)} & $(n-4)(n-d-1)$      & $(n-4)(n-d-1) + 2$        & 0             \\
\multicolumn{1}{l|}{(1, 1, 2, 3)} & 0             & 0             & 0             \\
\multicolumn{1}{l|}{(1, 2, 2, 3)} & $n-d-1$           &$ n-d-2$             & 0             \\
\multicolumn{1}{l|}{(1, 2, 1, 3)} & $n-d-1$           & $n-d-2$             & 0             \\
\multicolumn{1}{l|}{(1, 2, 3, 2)} & $n-d-1$           & $n-d-2$             & 0             \\
\multicolumn{1}{l|}{(1, 2, 3, 1)} & $n-d-1$           & $n-d-2$             & 0             \\
\multicolumn{1}{l|}{(1, 1, 1, 2)} & 0             & 0             & 0             \\
\multicolumn{1}{l|}{(1, 1, 2, 1)} & 0             & 0             & 0             \\
\multicolumn{1}{l|}{(1, 2, 1, 2)} & 0             & 1             & 0             \\
\multicolumn{1}{l|}{(1, 2, 2, 1)} & 0             & 1             & 0             \\
\multicolumn{1}{l|}{(1, 2, 3, 3)} & 0             & 0             & $(n-2)(n-d-1)$        \\
\multicolumn{1}{l|}{(1, 1, 2, 2)} & 0             & 0             & 0             \\
\multicolumn{1}{l|}{(1, 2, 2, 2)} & 0             & 0             & $n-d-1$             \\
\multicolumn{1}{l|}{(1, 2, 1, 1)} & 0             & 0             & $n-d-1$             \\
\multicolumn{1}{l|}{(1, 1, 1, 1)} & 0             & 0             & 0             \\ \hline
\multicolumn{1}{l|}{Total}                             & $n(n-d-1)$            & $n(n-d-1)$            & $n(n-d-1)$           
\end{tabular}
\caption{$m_N$}
\label{table:mN}
\end{table}

\begin{table}[h]
\centering
\begin{tabular}{llll}
\multicolumn{1}{l|}{$\mu$}        & $m_S(E, \mu)$ & $m_S(N, \mu)$ & $m_S(S, \mu)$ \\ \hline
\multicolumn{1}{l|}{(1, 2, 3, 4)} & 0           & 0        & 0             \\
\multicolumn{1}{l|}{(1, 1, 2, 3)} & $n-2$             & $n-2$             & 0             \\
\multicolumn{1}{l|}{(1, 2, 2, 3)} & 0           & 0             & 0             \\
\multicolumn{1}{l|}{(1, 2, 1, 3)} & 0           & 0             & 0             \\
\multicolumn{1}{l|}{(1, 2, 3, 2)} & 0           & 0             & 0             \\
\multicolumn{1}{l|}{(1, 2, 3, 1)} & 0           & 0             & 0             \\
\multicolumn{1}{l|}{(1, 1, 1, 2)} & 1             & 1             & 0             \\
\multicolumn{1}{l|}{(1, 1, 2, 1)} & 1             & 1             & 0             \\
\multicolumn{1}{l|}{(1, 2, 1, 2)} & 0             & 0             & 0             \\
\multicolumn{1}{l|}{(1, 2, 2, 1)} & 0             & 0             & 0             \\
\multicolumn{1}{l|}{(1, 2, 3, 3)} & 0             & 0             & 0        \\
\multicolumn{1}{l|}{(1, 1, 2, 2)} & 0             & 0             & $n-1$             \\
\multicolumn{1}{l|}{(1, 2, 2, 2)} & 0             & 0             & 0             \\
\multicolumn{1}{l|}{(1, 2, 1, 1)} & 0             & 0             & 0             \\
\multicolumn{1}{l|}{(1, 1, 1, 1)} & 0             & 0             & 1             \\ \hline
\multicolumn{1}{l|}{Total}                             & $n$            & $n$            & $n $          
\end{tabular}
\caption{$m_S$}
\label{table:mS}
\end{table}

Therefore, we have $L(A)_b = \sum_\mu w_\mu (m_E(\tau(b), \mu) + m_N(\tau(b), \mu) + m_S(\tau(b), \mu)) + \beta_{\mathcal{E}(b)}$. Moreover, notice that $\tau(b)$ determines $\mathcal{E}(b)$: if $\tau(b) = E$ or $N$, then $\mathcal{E}(b) = \mathcal{E}(1, 2); $ if $\tau(b) = S$, then $\mathcal{E}(b) = \mathcal{E}(1, 1)$. Hence, we can write $\beta_{\tau(b)}$ instead of $\beta_{\mathcal{E}(b)}$ without loss of generality. Then in particular, this means that $L(A)_b = L(A)_{b'}$ if $\tau(b) = \tau(b')$. Therefore, $L(A)_b = \overline{\xi}_1 \mathds{1}_{b \in E} + \overline{\xi}_2 \mathds{1}_{b \in N} + \overline{\xi}_3 \mathds{1}_{b \in S}$, where $\overline{\xi}_1 = \sum_\mu w_\mu (m_E(E, \mu) + m_N(E, \mu) + m_S(E, \mu)) + \beta_E$, $\overline{\xi}_2 = \sum_\mu w_\mu (m_E(N, \mu) + m_N(N, \mu) + m_S(N, \mu)) + \beta_N$, and $\overline{\xi}_3 = \sum_\mu w_\mu (m_E(S, \mu) + m_N(S, \mu) + m_S(S, \mu)) + \beta_S$. 

Similarly, $L(A')_b = \overline{\xi'}_1 \mathds{1}_{b \in E'} + \overline{\xi'}_2 \mathds{1}_{b \in N'} + \overline{\xi'}_3 \mathds{1}_{b \in S'}$. But importantly, $\forall$ equivalence class of 4-tuples, $\mu$, and $\forall \lambda_1, \lambda_2 \in \{E, N, S \}, m_{\lambda_1}(\lambda_2, \mu) =  m'_{\lambda_1}(\lambda_2, \mu)$, as both of them can be obtained from the same entry of the same table. Therefore, $\overline{\xi}_1 = \overline{\xi'}_1, \overline{\xi}_2 = \overline{\xi'}_2$, $\overline{\xi}_3 = \overline{\xi'}_3$.

Finally, let $\xi^*_1 = \sigma(\overline{\xi}_1), \xi^*_2 = \sigma(\overline{\xi}_2)$, and $\xi^*_3 = \sigma(\overline{\xi}_3)$. Then, there is $\sigma(L(A))_b = \xi^*_1 \mathds{1}_{b \in E} + \xi^*_2 \mathds{1}_{b \in N} + \xi^*_3 \mathds{1}_{b \in S}$, and $\sigma(L(A'))_b = \xi^*_1 \mathds{1}_{b \in E'} + \xi^*_2 \mathds{1}_{b \in N'} + \xi^*_3 \mathds{1}_{b \in S'}$, as desired.
\end{proof}

Since $h$ is an invariant function, $h$ acting on $A^{(L)}$ essentially computes the sum of all the diagonal terms (i.e., for $b \in S$) and the sum of all the off-diagonal terms (i.e., for $b \in E \cup N$) of $A^{(L)}$ separately and then adds the two sums with two weights. If $G, G'$ are regular graphs with the same degree, then $|E| = |E'|, |S| = |S'|$ and $|N| = |N'|$. Therefore, by the lemma, there is $h(A^{(L)}) = h(A'^{(L)})$, and as a consequence $m(h(A^{(L)})) = m(h(A'^{(L)}))$. 
\section{Universal approximation, graph isomorphism and motif counting}

\section{Introduction}
Graph structured data naturally occur in many areas of knowledge, including computational biology, chemistry and social sciences. Graph neural networks, in all their forms, yield useful representations of graph data partly because they take into consideration the intrinsic symmetries of graphs, such as invariance and equivariance with respect to a relabeling of the nodes \cite{scarselli2008graph, duvenaud2015convolutional, kipf2016semi, gilmer2017neural, hamilton2017representation, velivckovic2017graph, bronstein2017geometric}.

All these different architectures are proposed with different purposes (see \cite{wu2019comprehensive} for a survey and references therein), and a priori it is not obvious how to compare their power. The recent work \cite{xu2018powerful} proposes to study the representation power of GNNs via their performance on graph isomorphism tests. They developed the Graph Isomorphism Networks (GINs) that are as powerful as the one-dimensional Weisfeiler-Lehman (1-WL or just WL) test for graph isomorphism \cite{weisfeiler1968reduction}, and showed that no other neighborhood-aggregating (or message passing) GNN can be more powerful than the 1-WL test. Variants of message passing GNNs include \cite{scarselli2008graph, hamilton2017inductive}. 



On the other hand, for feed-forward neural networks, many results have been obtained regarding their ability to approximate continuous functions, commonly known as the universal approximation theorems, such as the seminal works of \cite{cybenko1989approximation, hornik1991hornik}. Following this line of work, it is natural to study the expressivity of graph neural networks in terms of function approximation. Since we could argue that many if not most functions on a graph that we are interested in are invariant or equivariant to permutations of the nodes in the graph, GNNs are usually designed to be invariant or equivariant, and therefore the natural question is whether certain classes GNNs can approximate any continuous and invariant or equivariant functions. Recent work \cite{maron2019universality} showed the universal approximation of $G$-invariant networks, constructed based on the linear invariant and equivariant layers studied in \cite{maron2018invariant}, if the order of the tensor involved in the networks can grow as the graph gets larger. Such a dependence on the graph size was been theoretically overcame by the very recent work \cite{keriven2019universal}, though there is no known upper bound on the order of the tensors involved. 
With potentially very-high-order tensors, these models that are guaranteed of univeral approximation are not quite feasible in practice.  

The foundational part of this work aims at building the bridge between graph isomorphism testing and invariant function approximation, the two main  perspectives for studying the expressive power of graph neural networks. We demonstrate an equivalence between the the ability of a class of GNNs to distinguish between any pairs of non-isomorphic graph and its power of approximating any (continuous) invariant functions, for both the case with finite feature space and the case with continuous feature space. Furthermore, we argue that the concept of sigma-algebras on the space of graphs is a natural description of the power of graph neural networks, allowing us to build a taxonomy of GNNs based on how their respective sigmas-algebras interact.
Building on this theoretical framework, we identify an opportunity to increase the expressive power of order-$2$ $G$-invariant networks with computational tractability, by considering a ring of invariant matrices under addition and multiplication. We show that the resulting model, which we refer to as \emph{Ring-GNN}, is able to distinguish between non-isomorphic regular graphs where order-$2$ $G$-invariant networks provably fail. We illustrate these gains numerically in synthetic and real graph classification tasks. 

Summary of main contributions:
\begin{itemize}
    \item We show the equivalence between graph isomorphism testing and approximation of permutation-invariant functions for analyzing the expressive power of graph neural networks.
    \item We introduce a language of sigma algebra for studying the representation power of graph neural networks, which unifies both graph isomorphism testing and function approximation, and use this framework to compare the power of some GNNs and other methods.
   
    \item We propose Ring-GNN, a tractable extension of order-2 Graph $G$-invariant Networks that uses the ring of matrix addition and multiplication. We show this extension is necessary and sufficient to distinguish Circular Skip Links graphs.
   
\end{itemize}

\section{Related work}
\paragraph{Graph Neural Networks and graph isomorphism.} Graph isomorphism is a fundamental problem in theoretical computer science. It amounts to deciding, given two graphs $A,B$, whether there exists a permutation $\pi$ such that $\pi A = B\pi$. There exists no known polynomial-time algorithm to solve it, but recently Babai made a breakthrough by showing that it can be solved in quasi-polynomial-time \cite{babai2016graph}. Recently  
\cite{xu2018powerful} introduced graph isomorphism tests as a characterization of the power of graph neural networks. They show that if a GNN follows a neighborhood aggregation scheme, then it cannot distinguish pairs of non-isomorphic graphs that the 1-WL test fails to distinguish. Therefore this class of GNNs is at most as powerful as the 1-WL test. They further propose the Graph Isomorphism Networks (GINs) based on approximating injective set functions by multi-layer perceptrons (MLPs), which can be as powerful as the 1-WL test. Based on $k$-WL tests \cite{cai1992optimal}, \cite{morris2019higher} proposes $k$-GNN, which can take higher-order interactions among nodes into account. Concurrently to this work, \cite{maron2019provably} proves that order-$k$ invariant graph networks are at least as powerful as the $k$-WL tests, and similarly to us, it and augments order-2 networks with matrix multiplication. They show they achieve at least the power of 3-WL test. \cite{murphy2019relational} proposes relational pooling (RP), an approach that combines \textit{permutation-sensitive} functions under all permutations to obtain a permutation-invariant function. If RP is combined with permutation-sensitive functions that are sufficiently expressive, then it can be shown to be a universal approximator. A combination of RP and GINs is able to distinguish certain non-isomorphic regular graphs which GIN alone would fail on. A drawback of RP is that its full version is intractable computationally, and therefore it needs to be approximated by averaging over randomly sampled permutations, in which case the resulting functions is not guaranteed to be permutation-invariant. 

\paragraph{Universal approximation of functions with symmetry.} Many works have discussed the function approximation capabilities of neural networks that satisfy certain symmetries.
\cite{bloemreddy2019probabilistic} studies the symmetry in neural networks from the perspective of probabilistic symmetry and characterizes the deterministic and stochastic neural networks that satisfy certain symmetry. \cite{ravanbakhsh2017sharing} shows that equivariance of a neural network corresponds to symmetries in its parameter-sharing scheme. \cite{yarotsky2018universal} proposes a neural network architecture with polynomial layers that is able to achieve universal approximation of invariant or equivariant functions.  
\cite{maron2018invariant} studies the spaces of all invariant and equivariant linear functions, and obtained bases for such spaces. Building upon this work, \cite{maron2019universality} proposes the $G$-invariant network for a symmetry group $G$, which achieves universal approximation of $G$-invariant functions if the maximal tensor order involved in the network to grow as $\frac{n (n-1)}{2}$, but such high-order tensors are prohibitive in practice. Upper bounds on the approximation power of the $G$-invariant networks when the tensor order is limited remains open except for when $G = A_n$ \cite{maron2019universality}. The very recent work \cite{keriven2019universal} extends the result to the equivariant case, although it suffers from the same problem of possibly requiring high-order tensors. Within the computer vision literature, this problem has also been addressed, in particular \cite{herzig2018mapping} proposes an architecture that can potentially express all equivariant functions.

To the best our knowledge, this is the first work that shows an explicit connection between the two aforementioned perspectives of studying the representation power of graph neural networks - graph isomorphism testing and universal approximation. Our main theoretical contribution lies in showing an equivalence between them, for both finite and continuous feature space cases, with a natural generalization of the notion of graph isomorphism testing to the latter case. Then we focus on the Graph $G$-invariant network based on \cite{maron2018invariant,maron2019universality}, and showed that when the maximum tensor order is restricted to be 2, then it cannot distinguish between non-isomorphic regular graphs with equal degrees. As a corollary, such networks are not universal. Note that our result shows an upper bound on order 2 $G$-invariant networks, whereas concurrently to us, \cite{maron2019provably} provides a lower bound by relating to $k$-WL tests. Concurrently to \cite{maron2019provably}, we propose a modified version of order-2 graph networks to capture higher-order interactions among nodes without computing tensors of higher-order.



\section{Graph isomorphism testing and universal approximation}
In this section we show that there exists a very close connection between the universal approximation of permutation-invariant functions by a class of functions, and its ability to perform graph isomorphism tests. We consider graphs with nodes and edges labeled by elements of a compact set $\mathcal{X}\subset \mathbb R$. We represent graphs with $n$ nodes by an $n$ by $n$ matrix $G \in \mathcal{X}^{n \times n}$, where a diagonal term $G_{ii}$ represents the label of the $i$th node, and a non-diagonal $G_{ij}$ represents the label of the edge from the $i$th node to the $j$th node. An undirected graph will then be represented by a symmetric $G$.  

Thus, we focus on analyzing a collection $\mathcal{C}$ of functions from $\mathcal{X}^{n \times n}$ to $\mathbb{R}$. We are especially interested in collections of \textit{permutation-invariant functions}, defined so that $f(\pi^\intercal G \pi) = f(G)$, for all $G \in \mathcal{X}^{n \times n}$, and all $\pi \in S_n$, where $S_n$ is the permutation group of $n$ elements. For classes of functions, we define the property of being able to discriminate non-isomorphic graphs, which we call \textit{GIso-discriminating}, which as we will see generalizes naturally to the continuous case.

\begin{definition}
\label{pd}
Let $\mathcal{C}$ be a collection of permutation-invariant functions from $\mathcal{X}^{n \times n}$ to $\mathbb{R}$. We say $\mathcal C$ is \textbf{GIso-discriminating} if for all non-isomorphic $G_1, G_2 \in \mathcal X^{n\times n}$ (denoted $G_1 \not\simeq G_2$),  there exists a function $ h \in \mathcal{C}$ such that $h(G_1) \neq h(G_2)$. This definition is illustrated by figure 2 in the appendix. 
\end{definition}

\begin{definition}
Let $\mathcal{C}$ be a collection of permutation-invariant functions from $\mathcal{X}^{n \times n}$ to $\mathbb{R}$. We say $\mathcal C$ is \textbf{universally approximating} if for all permutation-invariant function $f$ from $\mathcal{X}^{n \times n}$ to $\mathbb{R}$, and for all $\epsilon > 0$, there exists $h_{f,\epsilon} \in \mathcal{C}$ such that $\| f - h_{f,\epsilon} \|_{\infty} := \sup_{G \in \mathcal X^{n\times n}} |f(G) - h(G)| < \epsilon$
\end{definition}



\subsection{Finite feature space}
As a warm-up we first consider the space of graphs with a finite set of possible features for nodes and edges, $\mathcal X=\{1,\ldots, M\}$.  

\begin{theorem}
\label{UA2PD}
Universally approximating classes of functions are also GIso-discriminating.
\end{theorem}
\vspace{-1.0em}
\begin{proof}
Given $G_1, G_2 \in \mathcal X^{n\times n}$, we consider the permutation-invariant function $\mathds{1}_{\simeq G_1}:\mathcal X^{n\times n}\to \mathbb R$ such that $\mathds{1}_{\simeq G_1}(G)=1$ if  $G$ is isomorphic to $G_1$ and 0 otherwise. Therefore, it can be approximated with $\epsilon = 0.1$ by a function $h \in \mathcal{C}$. Then $h$ is a function that distinguishes $G_1$ from $G_2$, as in Definition~\ref{pd}. Hence $\mathcal{C}$ is GIso-discriminating.
\end{proof}

To obtain a result on the reverse direction, we first introduce the concept of an augmented collection of functions, which is especially natural when $\mathcal{C}$ is a collection of neural networks.

\begin{definition}
Given $\mathcal{C}$, a collection of functions from $\mathcal{X}^{n \times n}$ to $\mathbb{R}$, we consider an augmented collection of functions also from $\mathcal{X}^{n \times n}$ to $\mathbb{R}$ consisting of functions that map an input graph $G$ to $\mathcal{NN}([h_1(G), ..., h_d(G)])$ for some finite $d$, where $\mathcal{NN}$ is a feed-forward neural network / multi-layer perceptron, and $h_1, ..., h_d \in \mathcal{C}$. When $\mathcal{NN}$ is restricted to have $L$ layers, we denoted this augmented collection by $\mathcal{C}^{+L}$. In this work, we consider ReLU as the nonlinear activation function in the neural networks.
\end{definition}

\begin{remark}
If $\mathcal{C}_{L_0}$ is the collection of feed-forward neural networks with $L_0$ layers, then $\mathcal{C}_{L_0}^{+L}$ represents the collection of feed-forward neural networks with $L_0 + L$ layers.
\end{remark}

\begin{remark}
If $\mathcal{C}$ is a collection of permutation-invariant functions, so is $\mathcal{C}^{+L}$.
\end{remark}

\begin{theorem}
\label{PD2UAfin}
If $\mathcal{C}$ is GIso-discriminating, then $\mathcal{C}^{+2}$ is universal approximating.
\end{theorem}

The proof is simple and it is a consequence of the following lemmas that we prove in Appendix~\ref{app.universal}.

\begin{lemma} \label{lemma1}
If $\mathcal{C}$ is GIso-discriminating, then for all $G \in \mathcal{X}^{n \times n}$, there exists a function $\tilde{h}_G \in \mathcal{C}^{+1}$ such that for all $G', \tilde{h}_G(G') = 0$ if and only if $G \simeq G'$.
\end{lemma}

\begin{lemma} \label{lemma2}
Let $\mathcal C$ be a class of permutation-invariant functions from $\mathcal X^{n\times n}$ to $\mathbb R$ satisfying the consequences of Lemma \ref{lemma1},
then  $\mathcal{C}^{+1}$ is universally approximating.
\end{lemma}












\subsection{Extension to the case of continuous (Euclidean) feature space}
Graph isomorphism is an inherently discrete problem, whereas universal approximation is usually more interesting when the input space is continuous. With our definition \ref{pd} of \textit{GIso-discriminating}, we can achieve a natural generalization of the above results to the scenarios of continuous input space. All proofs for this section can be found in Appendix~\ref{app.universal}.

Let $\mathcal{X}$ be a compact subset of $\mathbb{R}$, and we consider graphs with $n$ nodes represented by $G \in K = \mathcal{X}^{n \times n}$; that is, the node features are $\{G_{ii}\}_{i = 1, \ldots, n}$ and the edge features are $\{G_{ij}\}_{i, j = 1,\ldots, n; i \neq j}$.



\begin{theorem}\label{ua2pdinf}
If $\mathcal{C}$ is universally approximating, then it is also GIso-discriminating
\end{theorem}

The essence of the proof is similar to that of Theorem~\ref{UA2PD}. The other direction - showing that  pairwise discrimination can lead to universal approximation - is less straightforward. As an intermediate step between, we make the following definition:

\begin{definition}
\label{locate}
Let $\mathcal{C}$ be a class of functions $K \to \mathbb{R}$. We say it is able to \textbf{locate every isomorphism class} if for all $G \in K$ and for all $\epsilon > 0$ there exists $h_G \in \mathcal{C}$ such that:
\begin{itemize}
    \item for all $G' \in K, h_G(G') \geq 0$;
    \item for all $G' \in K$, if $G' \simeq G$, then $h_G(G') = 0$; and
    \item there exists $\delta_G > 0$ such that if $h_G < \delta_G$, then $\exists \pi \in S_n$ such that $d(\pi(G'), G) < \epsilon$, where $d$ is the Euclidean distance defined on $\mathbb{R}^{n \times n}$
\end{itemize}
\end{definition}

\begin{lemma} \label{lemma.C+1}
If $\mathcal{C}$, a collection of continuous permutation-invariant functions from $K$ to $\mathbb{R}$, is GIso-discriminating, then $\mathcal{C}^{+1}$ is able to locate every isomorphism class.
\end{lemma}

Heuristically, we can think of the $h_G$ in the definition above as a ``loss function'' that penalizes the deviation of $G'$ from the equivalence class of $G$. In particular, the second condition says that if the loss value is small enough, then we know that $G'$ has to be close to the equivalence class of $G$.





\begin{lemma} \label{lemma.locate.approx}
Let $\mathcal{C}$ be a class of permutation-invariant functions $K \to \mathbb{R}$. 
If $\mathcal{C}$ is able to locate every isomorphism class, then $\mathcal{C}^{+2}$ is universally approximating.
\end{lemma}


Combining the two lemmas above, we arrive at the following theorem:

\begin{theorem}
If $\mathcal{C}$, a collection of continuous permutation-invariant functions from $K$ to $\mathbb{R}$, is GIso-discriminating, then $\mathcal{C}^{+3}$ is universaly approximating.
\end{theorem}



\section{A framework of representation power based on sigma-algebra}
\label{sec.sigma}
\subsection{Introducing sigma-algebra to this context}
Let $K = \mathcal{X}^{n \times n}$ be a finite input space. Let $Q_K:=K/_{\simeq}$ be the set of isomorphism classes under the equivalence relation of graph isomorphism. That is, for all $\tau \in Q_K, \tau = \{ \pi^\intercal G \pi : \pi \in \Gamma_n \}$ for some $G \in K$.

Intuitively, a maximally expressive collection of permutation-invariant functions, $\mathcal{C}$, will allow us to know exactly which isomorphism class $\tau$ a given graph $G$ belongs to, by looking at the outputs of certain functions in the collection applied to $G$. Heuristically, we can consider each function in $\mathcal{C}$ as a ``measurement'', which partitions that graph space $K$ according to the function value at each point. If $\mathcal{C}$ is powerful enough, then as a collection it will partition $K$ to be as fine as $Q_K$. If not, it is going to be coarser than $Q_K$. These intuitions motivate us to introduce the language of sigma-algebra.

Recall that an algebra on a set $K$ is a collection of subsets of $K$ that includes $K$ itself, is closed under complement, and is closed under finite union. Because $K$ is finite, we have that an algebra on $K$ is also a sigma-algebra on $K$, where a sigma-algebra further satisfies the condition of being closed under countable unions. Since $Q_K$ is a set of (non-intersecting) subsets of $K$, we can obtain the algebra generated by $Q_K$, defined as the smallest algebra that contains $Q_K$, and use $\sigma(Q_K)$ to denote the algebra (and sigma-algebra) generated by $Q_K$.

\begin{observation}
If $f : \mathcal{X}^{n \times n} \to \mathbb{R}$ is a permutation-invariant function, then $f$ is measurable with respect to $\sigma(Q_K)$, and we denote this by $f \in \mathcal{M}[\sigma(Q_K)]$
\end{observation}

Now consider a class of functions $\mathcal{C}$ that is permutation-invariant. Then for all $f \in \mathcal{C}, f \in \mathcal{M}[\sigma(Q_K)]$. We define the sigma-algebra generated by $f$ as the set of all the pre-images of Borel sets on $\mathbb{R}$ under $f$, and denote it by $\sigma(f)$. It is the smallest sigma-algebra on $K$ that makes $f$ measurable. For a class of functions $\mathcal{C}$, $\sigma(\mathcal{C})$ is defined as the smallest sigma-algebra on $K$ that makes all functions in $\mathcal{C}$ measurable. Because here we assume $K$ is finite, it does not matter whether $\mathcal{C}$ is a countable collection.


\subsection{Reformulating graph isomorphism testing and universal approximation with sigma-algebra}
\label{sec.reformulating}

We restrict our attention to the case of finite feature space. Given a graph $G \in \mathcal{X}^{n \times n}$, we use $\mathcal{E}(G)$ to denote its isomorphism class, $\{ G' \in \mathcal{X}^{n \times n}: G' \simeq G \}$. The following results are proven in Section~\ref{sec.proofs.reformulating}

\begin{theorem}\label{teo5}
If $\mathcal{C}$ is a class of permutation-invariant functions on $\mathcal{X}^{n \times n}$ and $\mathcal{C}$ is GIso-discriminating, then $\sigma(\mathcal{C}) = \sigma(Q_K)$
\end{theorem}


Together with Theorem \ref{UA2PD}, the following is an immediate consequence:

\begin{corollary}
If $\mathcal{C}$ is a class of permutation-invariant functions on $\mathcal{X}^{n \times n}$ and $\mathcal{C}$ achieves universal approximation, then $\sigma(\mathcal{C}) = \sigma(Q_K)$.
\end{corollary}

\begin{theorem} \label{teo6}
Let be $\mathcal{C}$ a class of permutation-invariant functions on $\mathcal{X}^{n \times n}$ with $\sigma(\mathcal{C}) = \sigma(Q_K)$. Then $\mathcal{C}$ is GIso-discriminating.
\end{theorem}


Thus, this sigma-algebra language is a natural notion for characterizing the power of graph neural networks, because as shown above, generating the finest sigma-algebra $\sigma(Q_K)$ is equivalent to being GIso-discriminating, and therefore to universal approximation. 

Moreover, when $\mathcal{C}$ is not GIso-discriminating or universal, we can evaluate its representation power by studying $\sigma(\mathcal{C})$, which gives a measure for comparing the power of different GNN families. 
Given two classes of functions $\mathcal{C}_1, \mathcal{C}_2$, there is $\sigma(\mathcal{C}_1) \subseteq \sigma(\mathcal{C}_2)$ if and only if $\mathcal{M}[\sigma(\mathcal{C}_1)] \subseteq \mathcal{M}[\sigma(\mathcal{C}_2)]$ if and only if $\mathcal{C}_1$ is less powerful than $\mathcal{C}_2$ in terms of representation power. 

In Appendix \ref{app.comparison} we use this notion to compare the expressive power of different families of GNNs as well as other algorithms like 1-WL, linear programming and semidefinite programming in terms of their ability to distinguish non-isomorphic graphs. We summarize our findings in Figure 1.


\begin{figure}[ht]
\label{diagram_main_text}
\small
\centering
\begin{tikzcd}
& \text{sGNN}(I,A) \arrow[d, hook] \arrow[ddr, hook]& \\
& LP\equiv 1-WL \equiv GIN \arrow[d, hook] \arrow[dl, hook] &  \\
\text{SDP}\arrow[dd,hook]& \text{MPNN}^* \arrow[d,hook] & \text{sGNN}(I,D,A,\{\min\{A^t,1\}\}_{t=1}^T) \arrow[ddl,hook]\\
& \text{order 2 $G$-invariant networks}^*  \arrow[d,hook] & \text{spectral methods}\arrow[dl,hook] \\
\text{SoS hierarchy}& \text{Ring-GNN}&
\end{tikzcd}
\caption{\small Relative comparison of function classes in terms of their ability to solve graph isomorphism.
\newline $^*$Note that, on one hand GIN is defined by \cite{xu2018powerful} as a form of message passing neural network justifying the inclusion GIN $\hookrightarrow$ MPNN. On the other hand \cite{maron2018invariant} shows that message passing neural networks can be expressed as a modified form of order 2 $G$-invariant networks (which may not coincide with the definition we consider in this paper). 
Therefore the inclusion GIN $\hookrightarrow$ order 2 $G$-invariant networks has yet to be established rigorously.
\vspace{-15pt} }
\label{fig.diagram}
\end{figure}









\section{Ring-GNN: a GNN defined on the ring of equivariant functions}

We now investigate the $G$-invariant network framework proposed in \cite{maron2019universality} (see Appendix~\ref{app.Ginvariant} for its definition and a description of an adapted version that works on graph-structured inputs, which we call the \textit{Graph $G$-invariant Networks}). The architecture of $G$-invariant networks is built by interleaving compositions of equivariant linear layers between tensors of potentially different orders and point-wise nonlinear activation functions. It is a powerful framework that can achieve universal approximation
if the order of the tensor can grow as $\frac{n(n-1)}{2}$, where $n$ is the number of nodes in the graph, but less is known about its approximation power when the tensor order is restricted. One particularly interesting subclass of $G$-invariant networks is the ones with maximum tensor order 2, because \cite{maron2018invariant} shows that it can approximate any Message Passing Neural Network \cite{gilmer2017neural}. Moreover, it is both mathematically cumbersome and computationally expensive to include equivariant linear layers involving tensors with order higher than 2.

Our following result shows that the order-2 Graph $G$-invariant Networks subclass of functions is quite restrictive. The proof is given in Appendix \ref{app.Ginvariant}. 

\begin{theorem} \label{prop.Ginvariant}
Order-2 Graph $G$-invariant Networks cannot distinguish between non-isomorphic regular graphs with the same degree.
\end{theorem}


Motivated by this limitation, we propose a GNN architecture that extends the family of order-2 Graph $G$-invariant Networks without going into higher order tensors. In particular, we want the new family to include GNNs that can distinguish some pairs of non-isomorphic regular graphs with the same degree. For instance, take 
the pair of Circular Skip Link graphs $G_{8, 2}$ and $G_{8,3}$,
illustrated in Figure \ref{cslfig}.
Roughly speaking, if all the nodes in both graphs have the same node feature, then because they all have the same degree, the updates of node states in both graph neural networks based on neighborhood aggregation and the WL test will fail to distinguish the nodes. However, the \textit{power graphs}\footnote{If $A$ is the adjacency matrix of a graph, its power graph has adjacency matrix $\min(A^2, 1)$. The matrix $\min(A^2, 1)$ has been used in \cite{chen2019cdsbm} in graph neural networks for community detection and in \cite{nowak2017note} for the quadratic assignment problem.} of $G_{8, 2}$ and $G_{8,3}$ have different degrees. 
Another important example comes from spectral methods that operate on \emph{normalized} operators, such as the normalized Laplacian $\Delta = I - D^{-1/2} A D^{-1/2}$, where $D$ is the diagonal degree operator. Such normalization preserves the permutation symmetries and in many clustering applications leads to dramatic improvements \cite{von2007tutorial}. 

This motivates us to consider a polynomial ring generated by the matrices that are the outputs of permutation-equivariant linear layers, rather than just the linear space of those outputs. Together with point-wise nonlinear activation functions such as ReLU, power graph adjacency matrices like $\min(A^2, 1)$ can be expressed with suitable choices of parameters. We call the resulting architecture the \textit{Ring-GNN}  \footnote{We call it Ring-GNN since the main object we consider is the ring of matrices, but technically we can express an associative algebra since our model includes scalar multiplications.}.

\begin{definition}[Ring-GNN] Given a graph in $n$ nodes with both node and edge features in $\mathbb R^d$, we represent it with a matrix $A\in \mathbb R^{n\times n\times d}$.
\cite{maron2018invariant}
shows that all linear equivariant layers from $\mathbb{R}^{n \times n}$ to $\mathbb{R}^{n \times n}$ can be expressed as $L_\theta(A)=\sum_{i=1}^{15} \theta_i L_i(A) + \sum_{i=16}^{17} \theta_i \overline{L}_i$, where the $\{L_i\}_{i = 1, ..., 15}$ are the 15 basis functions
of all linear equivariant functions from $\mathbb{R}^{n \times n}$ to $\mathbb{R}^{n \times n}$, $\overline{L}_{16}$ and $\overline{L}_{17}$ are the basis for the bias terms, and $\theta \in \mathbb{R}^{17}$ are the parameters that determine $L$. Generalizing to an equivariant linear layer from $\mathbb{R}^{n \times n \times d}$ to $\mathbb{R}^{n \times n \times d'}$, we set $L_{\theta}(A)_{\cdot, \cdot, k'} = \sum_{k=1}^d \sum_{i=1}^{15} \theta_{k, k', i} L_i(A_{\cdot, \cdot, i}) + \sum_{i=16}^{17} \theta_{k, k', i} \overline{L}_i$, with $\theta \in \mathbb{R}^{d \times d' \times 17}$.


With this formulation, we now define a Ring-GNN with $T$ layers. First, set $A^{(0)}=A$. In the $t^{th}$ layer, let
\begin{eqnarray*}
B_1^{(t)}&=& \rho(L_{\alpha^{(t)}}(A^{(t)})) \\
B_2^{(t)}&=& \rho(L_{\beta^{(t)}}(A^{(t)})\cdot L_{\gamma^{(t)}}(A^{(t)})) \\
A^{(t+1)}&=& k_1^{(t)} B_1^{(t)} + k_2^{(t)} B_2^{(t)}
\end{eqnarray*}
where $k_1^{(t)}, k_2^{(t)} \in \mathbb{R}$, $\alpha^{(t)}, \beta^{(t)}, \gamma^{(t)} \in \mathbb{ R}^{d^{(t)} \times {d'}^{(t)} \times 17}$ are learnable parameters. If a scalar output is desired, then in the general form, we set the output to be $\theta_S \sum_{i,j} A_{ij}^{(T)} + \theta_D \sum_{i,i} A_{ii}^{(T)} + \sum_{i} \theta_{i} \lambda_{i}(A^{(T)})$, where $\theta_S, \theta_D, \theta_1, \ldots, \theta_n \in \mathbb{R}$ are trainable parameters, and  $\lambda_{i}(A^{(T)})$ is the $i$-th eigenvalue of $A^{(L)}$.
\end{definition}

Note that each layer is equivariant, and the map from $A$ to the final scalar output is invariant. A Ring-GNN can reduce to an order-2 Graph $G$-invariant Network if $k_2^{(t)} = 0$. With $J+1$ layers and suitable choices of the parameters, it is possible to obtain $\min(A^{2^{J}}, 1)$ in the $(J+1)^{th}$ layer. Therefore, we expect it to succeed in distinguishing certain pairs of regular graphs that order-2 Graph $G$-invariant Networks fail on, such as the Circular Skip Link graphs. Indeed, this is verified in the synthetic experiment presented in the next section. The normalized Laplacian can also be obtained, since the degree matrix can be inverted by taking the reciprocal on the diagonal, and then entry-wise inversion and square root on the diagonal can be approximated by MLPs.


The terms in the output layer involving eigenvalues are optional, depending on the task. For example, in community detection spectral information is commonly used \cite{krzakala2013spectral}. We could also take a fixed number of eigenvalues instead of the full spectrum. In the experiments, Ring-GNN-SVD includes the eigenvalue terms while Ring-GNN does not, as explained in appendix \ref{archi}. Computationally, the complexity of running the forward model grows as $O(n^3)$, dominated by matrix multiplications and possibly singular value decomposition for computing the eigenvalues. 
We note also that Ring-GNN can be augmented with matrix inverses or more generally with functional calculus on the spectrum of any of the intermediate representations \footnote{When $A=A^{(0)}$ is an undirected graph, one easily verifies that $A^{(t)}$ contains only symmetric matrices for each $t$.} while keeping $O(n^3)$ computational complexity.
Finally, note that a Graph $G$-invariant Network with maximal tensor order $d$ will have complexity at least $O(n^d)$. Therefore, the Ring-GNN explores higher-order interactions in the graph that order-2 Graph $G$-invariant Networks neglects while remaining computationally tractable.


\begin{figure}
    \label{cslfig}
    \centering
    \includegraphics[width=0.15\textwidth,trim={6cm 4.8cm 20cm 7.8cm},clip]{skl2black}
    \includegraphics[width=0.15\textwidth,trim={6cm 4.8cm 20cm 7.8cm},clip]{skl3black}
    \caption{The Circular Skip Link graphs $G_{n,k}$ are undirected graphs in $n$ nodes $q_0,\ldots, q_{n-1}$ so that $(i,j)\in E$ if and only if $|i-j|\equiv 1 \text{ or } k \pmod n$. In this figure we depict (left) $G_{8,2}$ and (right) $G_{8,3}$. It is very easy to check that $G_{n,k}$ and $G_{n',k'}$ are not isomorphic unless $n=n'$ and $k\equiv \pm k' \pmod n$. Both 1-WL and $G$-invariant networks fail to distinguish them. \vspace{-10pt}}
    \label{fig.skiplength}
\end{figure}

\section{Experiments}
\label{experiments}
The different models and the detailed setup of the experiments are discussed in Appendix \ref{archi}.

\subsection{Classifying Circular Skip Links (CSL) graphs}
\label{cslexp}
The following experiment on synthetic data demonstrates the connection between function fitting and graph isomorphism testing. The Circular Skip Links graphs are undirected regular graphs with node degree 4 \cite{murphy2019relational}, as illustrated in Figure \ref{cslfig}. Note that two CSL graphs $G_{n,k}$ and $G_{n',k'}$ are not isomorphic unless $n=n'$ and $k\equiv \pm k' \pmod n$. In the experiment, which has the same setup as in \cite{murphy2019relational}, we fix $n=41$, and set $k \in \{2, 3, 4, 5, 6, 9, 11, 12, 13, 16 \}$, and each $k$ corresponds to a distinct isomorphism class. The task is then to classify a graph $G_{n, k}$ by its skip length $k$.

Note that since the 10 classes have the same size, a naive uniform classifier would obtain $0.1$ accuracy. As we see from Table \ref{table.synthetic}, both GIN and $G$-invariant network with tensor order 2 do not outperform the naive classifier. Their failure in this task is unsurprising: WL tests are proved to fall short of distinguishing such pairs of non-isomorphic regular graphs \cite{cai1992optimal}, and hence neither can GIN \cite{xu2018powerful}; by the theoretical results from the previous section, order-2 Graph $G$-invariant network are unable to distinguish them either. Therefore, their failure as graph isomorphism tests is consistent with their failure in this classification task, which can be understood as trying to approximate the function that maps the graph to their class labels.

It should be noted that, since graph isomorphism tests are not entirely well-posed as classfication tasks, the performance of GNN models could vary due to randomness. But the fact that Ring-GNNs achieve a relatively high maximum accuracy (compared to RP for example) demonstrates that as a class of GNNs it is rich enough to contain functions that distinguish the CSL graphs to a large extent. 

\begin{table}[ht]
\centering
\begin{tabular}{l|lll||ll|ll}
\hline
& \multicolumn{3}{|c||}{Circular Skip Links} & \multicolumn{2}{c|}{IMDBB} & \multicolumn{2}{c}{IMDBM} \\
GNN architecture              & max  & min & std  & mean & std & mean & std \\
\hline \hline
RP-GIN $\dagger$               & 53.3 & 10  & 12.9 & -     & -     & -     & -     \\
GIN $\dagger$                 & 10   & 10  & 0    & 75.1  & 5.1   & 52.3  & 2.8   \\
Order 2 G-invariant $\dagger$ & 10   & 10  & 0    & 71.27 & 4.5   & 48.55 & 3.9   \\
sGNN-5                        & 80   & 80  & 0    & 72.8  & 3.8   & 49.4  & 3.2   \\
sGNN-2                        & 30   & 30  & 0    & 73.1  & 5.2   & 49.0    & 2.1   \\
sGNN-1                        & 10   & 10  & 0    & 72.7  & 4.9   & 49.0    & 2.1   \\
LGNN \cite{chen2019cdsbm}                         & 30   & 30  & 0    & 74.1  & 4.6   & 50.9  & 3.0     \\
Ring-GNN                          & 80   & 10  & 15.7    & 73.0  & 5.4   & 48.2  & 2.7  \\
Ring-GNN-SVD                          & 100   & 100  &  0   & 73.1  & 3.3   & 49.6  & 3.0  \\
\hline
\end{tabular}
\vspace{5pt}
\caption{\textbf{(left)} Accuracy of different GNNs at classifying CSL (see Section \ref{cslexp}). We report the best performance and worst performance among 10 experiments.
\textbf{(right)} Accuracy of different GNNs at classifying real datasets (see Section \ref{cslexp}). We report the best performance among all epochs on a 10-fold cross validation dataset, as was done in \cite{xu2018powerful}. 
$\dagger$: Reported performance by \cite{murphy2019relational}, \cite{xu2018powerful} and \cite{maron2018invariant}.
}
\vspace{-1.5em}
\label{table.synthetic}
\end{table}

\subsection{IMDB datasets} \label{sec.imbdb}
We use the two IMDB datasets (IMDBBINARY, IMDBMULTI) to test different models in real-world scenarios. Since our focus is on distinguishing graph structures, these datasets are suitable as they do not contain node features, and hence the adjacency matrix contains all the input data. IMDBBINARY dataset has 1000 graphs, with average number of nodes 19.8 and 2 classes. The dataset is randomly partitioned into 900/100 for training/validation. IMDBMULTI dataset has 1500 graphs, with average number of nodes 13.0 and 3 classes. The dataset is randomly partitioned into 1350/150 for training/validation. All models are evaluated via 10-fold cross validation and best accuracy is calculated through averaging across folds followed by maximizing along epochs~\cite{xu2018powerful}. Importantly, the architecture hyper-parameter of Ring-GNN we use is close to that provided in \cite{maron2018invariant} to show that order-2 $G$-invariant Network is included in model family we propose. The results show that Ring-GNN models achieve higher performance than Order-2 G-invariant networks in both datasets.
Admittedly its accuracy does not reach that of the state-of-the-art. 
However, the main goal of this part of our work is not necessarily to invent the best-performing GNN through hyperparameter optimization, but rather to propose Ring-GNN as an augmented version of order-2 Graph $G$-invariant Networks and show experimental results that support the theory. 




















































































\input{conclusions.tex}

\bibliographystyle{plain}

2019-05-30T02:21:13.000
1905
1905.12560
en
https://arxiv.org/abs/1905.12560
Graph Neural Networks (GNNs) have achieved much success on graph-structured data. In light of this, there have been increasing interests in studying their expressive power. One line of work studies the capability of GNNs to approximate permutation-invariant functions on graphs, and another focuses on the their power as tests for graph isomorphism. Our work connects these two perspectives and proves their equivalence. We further develop a framework of the expressive power of GNNs that incorporates both of these viewpoints using the language of sigma-algebra, through which we compare the expressive power of different types of GNNs together with other graph isomorphism tests. In particular, we prove that the second-order Invariant Graph Network fails to distinguish non-isomorphic regular graphs with the same degree. Then, we extend it to a new architecture, Ring-GNN, which succeeds in distinguishing these graphs and achieves good performances on real-world datasets.
Machine Learning (cs.LG); Machine Learning (stat.ML)
On the equivalence between graph isomorphism testing and function approximation with GNNs
Qwen/Qwen-72B
1. YES
2. YES