Independent scholarship · Open accessThe monthly digest

Indexed text attachment

partial-differential-equations-in-machine-learning-and-ai.tex

Source for Partial Differential Equations in Machine Learning and AI: Naturality, Well-Posedness, and Spectral Rates

View paper · Download original file

Lines 661–760 of 1085. Source text is displayed literally.

661 662\section{Graph networks}\label{sec:graphs}663 664Let $L$ be the Laplacian of a connected graph with eigenvalues $0=\lambda_1<\lambda_2\le\dots\le\lambda_n$. The665linear part of a message-passing layer is $X\mapsto(I-\tau L)X$, one explicit Euler step of the heat equation on666the graph \cite{CRGBB21}.667 668\begin{theorem}[Oversmoothing is the spectral gap]\label{thm:oversmooth}669\Scl[\cite{LHW18,OoSu20}] For $0<\tau\le1/\lambda_n$ the non-constant part of $X$ is multiplied by at most670$1-\tau\lambda_2$ per layer, with equality in the limit, and the Dirichlet energy $X^{\T}LX$ by at most671$(1-\tau\lambda_2)^2$. The depth at which features become indistinguishable is of order $1/\tau\lambda_2$.672\end{theorem}673 674\noindent On a random connected graph with $12$ nodes, $\lambda_2=0.6251$, $\lambda_n=8.2655$ and the measured675factor is $0.92437$, as predicted; $99\%$ of the Dirichlet energy of a random input is gone after $15$ layers,676the bound from $\lambda_2$ alone being $29$. \chk{G1} The depth scale varies by orders of magnitude with the677graph: on $32$ nodes, with $\tau$ at its largest stable value, it is $415$ layers for a path678($\lambda_2=0.00963$), $5$ for the hypercube ($\lambda_2=2$, $\lambda_n=10$) and $1$ for the complete graph,679where a single layer returns the mean exactly (\cref{fig:smooth}). \chk{G2} Graphs that are good for propagating information are680the ones that oversmooth fastest; the two are the same eigenvalue.681 682\begin{figure}[t]683\centering684\begin{tikzpicture}685\begin{scope}[shift={(0,0)}]686\draw[ink2] (0,3.6)--(0,0)--(6.3,0);687\draw[ink2] (0,0)--(0,-0.07) node[below,inner sep=1.5pt]{\scriptsize $0$};688\draw[ink2] (2.1,0)--(2.1,-0.07) node[below,inner sep=1.5pt]{\scriptsize $20$};689\draw[ink2] (4.2,0)--(4.2,-0.07) node[below,inner sep=1.5pt]{\scriptsize $40$};690\draw[ink2] (6.3,0)--(6.3,-0.07) node[below,inner sep=1.5pt]{\scriptsize $60$};691\draw[ink2] (0,0)--(-0.07,0) node[left,inner sep=1.5pt]{\scriptsize $10^{-8}$};692\draw[ink2] (0,0.774)--(-0.07,0.774) node[left,inner sep=1.5pt]{\scriptsize $10^{-6}$};693\draw[ink2] (0,1.548)--(-0.07,1.548) node[left,inner sep=1.5pt]{\scriptsize $10^{-4}$};694\draw[ink2] (0,2.322)--(-0.07,2.322) node[left,inner sep=1.5pt]{\scriptsize $10^{-2}$};695\draw[ink2] (0,3.096)--(-0.07,3.096) node[left,inner sep=1.5pt]{\scriptsize $1$};696\node[below] at (3.15,-0.38) {\scriptsize layers};697\draw[thick,accent] plot coordinates {(0,3.096) (0.105,3.318) (0.21,3.323) (0.315,3.125) (0.42,3.116) (0.525,3.297) (0.63,3.315) (0.735,3.189) (0.84,3.118) (0.945,3.285) (1.05,3.305) (1.155,3.206) (1.26,3.149) (1.365,3.277) (1.47,3.293) (1.575,3.222) (1.68,3.161) (1.785,3.264) (1.89,3.302) (1.995,3.215) (2.1,3.168) (2.205,3.264) (2.31,3.293) (2.415,3.222) (2.52,3.201) (2.625,3.253) (2.73,3.265) (2.835,3.248) (2.94,3.234) (3.045,3.237) (3.15,3.237) (3.255,3.249) (3.36,3.263) (3.465,3.249) (3.57,3.206) (3.675,3.219) (3.78,3.298) (3.885,3.255) (3.99,3.183) (4.095,3.206) (4.2,3.291) (4.305,3.289) (4.41,3.172) (4.515,3.166) (4.62,3.298) (4.725,3.307) (4.83,3.122) (4.935,3.166) (5.04,3.311) (5.145,3.303) (5.25,3.103) (5.355,3.16) (5.46,3.322) (5.565,3.302) (5.67,3.089) (5.775,3.138) (5.88,3.326) (5.985,3.311) (6.09,3.088) (6.195,3.134) (6.3,3.311)};698\draw[thick,fwd] plot coordinates {(0,3.096) (0.105,2.805) (0.21,2.707) (0.315,2.632) (0.42,2.569) (0.525,2.514) (0.63,2.466) (0.735,2.424) (0.84,2.388) (0.945,2.356) (1.05,2.329) (1.155,2.305) (1.26,2.284) (1.365,2.266) (1.47,2.249) (1.575,2.234) (1.68,2.22) (1.785,2.206) (1.89,2.194) (1.995,2.182) (2.1,2.17) (2.205,2.159) (2.31,2.148) (2.415,2.137) (2.52,2.127) (2.625,2.116) (2.73,2.106) (2.835,2.096) (2.94,2.087) (3.045,2.077) (3.15,2.067) (3.255,2.058) (3.36,2.049) (3.465,2.04) (3.57,2.031) (3.675,2.022) (3.78,2.014) (3.885,2.005) (3.99,1.997) (4.095,1.988) (4.2,1.98) (4.305,1.972) (4.41,1.964) (4.515,1.956) (4.62,1.949) (4.725,1.941) (4.83,1.934) (4.935,1.926) (5.04,1.919) (5.145,1.912) (5.25,1.905) (5.355,1.898) (5.46,1.891) (5.565,1.884) (5.67,1.878) (5.775,1.871) (5.88,1.865) (5.985,1.858) (6.09,1.852) (6.195,1.846) (6.3,1.84)};699\draw[thick,bwd] plot coordinates {(0,3.096) (0.105,2.849) (0.21,2.662) (0.315,2.52) (0.42,2.407) (0.525,2.31) (0.63,2.223) (0.735,2.141) (0.84,2.062) (0.945,1.984) (1.05,1.908) (1.155,1.832) (1.26,1.757) (1.365,1.682) (1.47,1.606) (1.575,1.531) (1.68,1.456) (1.785,1.381) (1.89,1.306) (1.995,1.231) (2.1,1.156) (2.205,1.081) (2.31,1.006) (2.415,0.931) (2.52,0.856) (2.625,0.781) (2.73,0.706) (2.835,0.631) (2.94,0.556) (3.045,0.481) (3.15,0.406) (3.255,0.331) (3.36,0.256) (3.465,0.181) (3.57,0.106) (3.675,0.031)};700\node[accent] at (4.62,2.74) {\scriptsize wave layer, path};701\node[fwd] at (4.41,2.089) {\scriptsize heat layer, path};702\node[bwd,right] at (2.835,0.959) {\scriptsize heat layer, hypercube};703\end{scope}704\end{tikzpicture}705\caption{Dirichlet energy of a random signal on $32$ nodes against depth, relative to its initial value. Heat-type layers lose it at a rate set by the spectral gap, slowly on a path and quickly on a hypercube; a wave-type layer on the path (\cref{thm:wavegnn}) keeps it.}\label{fig:smooth}706\end{figure}707 708A layer of second order in depth behaves as a wave equation \cite{RCRMB22}.709 710\begin{theorem}[Wave layers]\label{thm:wavegnn}711\Srf[\cite{PDEHC}, Thm.~12.3] The recursion $X_{m+1}=2X_m-X_{m-1}-\tau^2LX_m$ conserves712\[ \tau^{-2}\lVert X_{m+1}-X_m\rVert^2+X_{m+1}^{\T}LX_m, \]713which is positive definite on non-constant signals for $\tau^2\lambda_n<4$. For $\tau^2\lambda_n>4$ the top mode714grows per layer by the modulus of the larger root of $\xi^2+(\tau^2\lambda_n-2)\xi+1=0$.715\end{theorem}716 717\noindent Over $500$ layers at $\tau^2\lambda_n=3.6$ the invariant drifts by $2\times10^{-15}$ and the mean718Dirichlet energy of the last hundred layers is $1.001$ times that of the first hundred: nothing is smoothed. At719$\tau^2\lambda_n=4.4$ the growth factor is $1.8633$. \chk{G3} The bound is the Courant--Friedrichs--Lewy720condition, and the dichotomy between the two theorems is that of \cite[Ch.~4]{PDEHC}: a Markov semigroup721forgets, a symplectic group does not.722 723Both layers assume that neighbouring nodes should agree. A \term{cellular sheaf} \cite{HaGh19} replaces724agreement by agreement after transport: each edge carries linear maps from the data at its ends, and the sheaf725Laplacian $L_{\mathcal F}$ penalizes the mismatch. Its kernel is the space $H^0$ of global sections. The simplest726case is a sign $\sigma_e=\pm1$ on each edge, with $x^{\T}L_{\mathcal F}x=\sum_{e=uv}(x_u-\sigma_ex_v)^2$.727 728\begin{theorem}[Sheaf diffusion]\label{thm:sheaf}729\Sli[\cite{HaGh19,BDCLB22}] Diffusion by $L_{\mathcal F}$ converges to the orthogonal projection of the input730onto $H^0$. For a sign sheaf on a connected graph, $H^0$ has dimension one if the signs are a coboundary,731$\sigma_{uv}=\ell_u\ell_v$, in which case it is spanned by $\ell$; otherwise $H^0=0$. The obstruction is the class732of $\sigma$ in $H^1(G;\Z/2)$, a group of order $2^{E-V+1}$.733\end{theorem}734 735\noindent On a random graph with ten nodes, two classes, and signs $+$ within and $-$ between classes, sheaf736diffusion converges to the class labelling times $\langle\ell,X_0\rangle/n$, to rounding, while ordinary diffusion737converges to a constant and loses the classes. Reversing one edge that lies on a cycle makes the smallest738eigenvalue $0.1606$ and the limit zero; for a cycle of length $7$ with one negative edge it is739$4\sin^2\frac\pi{14}=0.19806$, the antiperiodic Laplacian. \chk{G4} On a graph with $5$ nodes and $7$ edges,740exactly $16=2^{V-1}$ of the $128$ sign assignments have a non-zero section, and they are exactly those whose741Laplacian is singular over the rationals; the $128$ assignments fall into $8=2^{E-V+1}$ classes. \chk{G5} This742is the same first cohomology that classifies flat gauge fields in \cite[Prop.~13.1]{PDEHC}: choosing the743transport maps of a sheaf network is choosing a connection, and heterophily is non-trivial holonomy. A sign744sheaf whose class is non-zero cannot be made consistent by relabelling nodes, and its diffusion has no745non-trivial limit.746 747\section{Depth as time}\label{sec:depth}748 749A residual layer $x\mapsto x+hf(x)$ is one step of forward Euler for $\dot x=f(x)$750\cite{E17,HaRu17}. The type of the linearization of $f$ decides which schemes are admissible, as for partial751differential equations \cite[Ch.~12]{PDEHC}.752 753\begin{theorem}[Layers by type]\label{thm:layers}754\Srf[\cite{HaRu17,CMHRBH18}; \cite{PDEHC}, Thm.~12.2, 12.3]755\begin{enumerate}[label=(\alph*),leftmargin=1.6em,itemsep=1pt,topsep=2pt]756\item \emph{Parabolic}, $f=-Ax$ with $A$ positive definite: forward Euler is stable if and only if757$h\le2/\lambda_{\max}(A)$.758\item \emph{Hyperbolic}, $f=Jx$ with $J$ antisymmetric with eigenvalues $\pm i\omega$: forward Euler multiplies759the norm by $\sqrt{1+h^2\omega^2}$ per layer, for every $h$.760\item For $h,\omega>0$, the leapfrog layer $q\mapsto q+hp$ followed by $p\mapsto p-h\omega^2q$, with the new $q$,