\section{Electronic Submission}
\label{submission}

Submission to ICML 2023 will be entirely electronic, via a web site
(not email). Information about the submission process and \LaTeX\ templates
are available on the conference web site at:
\begin{center}
\textbf{\texttt{http://icml.cc/}}
\end{center}

The guidelines below will be enforced for initial submissions and
camera-ready copies. Here is a brief summary:
\begin{itemize}
\item Submissions must be in PDF\@.
\item \textbf{New to this year}: If your paper has appendices, submit the appendix together with the main body and the references \textbf{as a single file}. Reviewers will not look for appendices as a separate PDF file. So if you submit such an extra file, reviewers will very likely miss it.
\item Page limit: The main body of the paper has to be fitted to 8 pages, excluding references and appendices; the space for the latter two is not limited. For the final version of the paper, authors can add one extra page to the main body.
\item \textbf{Do not include author information or acknowledgements} in your
    initial submission.
\item Your paper should be in \textbf{10 point Times font}.
\item Make sure your PDF file only uses Type-1 fonts.
\item Place figure captions \emph{under} the figure (and omit titles from inside
    the graphic file itself). Place table captions \emph{over} the table.
\item References must include page numbers whenever possible and be as complete
    as possible. Place multiple citations in chronological order.
\item Do not alter the style template; in particular, do not compress the paper
    format by reducing the vertical spaces.
\item Keep your abstract brief and self-contained, one paragraph and roughly
    4--6 sentences. Gross violations will require correction at the
    camera-ready phase. The title should have content words capitalized.
\end{itemize}

\subsection{Submitting Papers}

\textbf{Paper Deadline:} The deadline for paper submission that is
advertised on the conference website is strict. If your full,
anonymized, submission does not reach us on time, it will not be
considered for publication.

\textbf{Anonymous Submission:} ICML uses double-blind review: no identifying
author information may appear on the title page or in the paper
itself. \cref{author info} gives further details.

\textbf{Simultaneous Submission:} ICML will not accept any paper which,
at the time of submission, is under review for another conference or
has already been published. This policy also applies to papers that
overlap substantially in technical content with conference papers
under review or previously published. ICML submissions must not be
submitted to other conferences and journals during ICML's review
period.
Informal publications, such as technical
reports or papers in workshop proceedings which do not appear in
print, do not fall under these restrictions.

\medskip

Authors must provide their manuscripts in \textbf{PDF} format.
Furthermore, please make sure that files contain only embedded Type-1 fonts
(e.g.,~using the program \texttt{pdffonts} in linux or using
File/DocumentProperties/Fonts in Acrobat). Other fonts (like Type-3)
might come from graphics files imported into the document.

Authors using \textbf{Word} must convert their document to PDF\@. Most
of the latest versions of Word have the facility to do this
automatically. Submissions will not be accepted in Word format or any
format other than PDF\@. Really. We're not joking. Don't send Word.

Those who use \textbf{\LaTeX} should avoid including Type-3 fonts.
Those using \texttt{latex} and \texttt{dvips} may need the following
two commands:

{\footnotesize
\begin{verbatim}
dvips -Ppdf -tletter -G0 -o paper.ps paper.dvi
ps2pdf paper.ps
\end{verbatim}}
It is a zero following the ``-G'', which tells dvips to use
the config.pdf file. Newer \TeX\ distributions don't always need this
option.

Using \texttt{pdflatex} rather than \texttt{latex}, often gives better
results. This program avoids the Type-3 font problem, and supports more
advanced features in the \texttt{microtype} package.

\textbf{Graphics files} should be a reasonable size, and included from
an appropriate format. Use vector formats (.eps/.pdf) for plots,
lossless bitmap formats (.png) for raster graphics with sharp lines, and
jpeg for photo-like images.

The style file uses the \texttt{hyperref} package to make clickable
links in documents. If this causes problems for you, add
\texttt{nohyperref} as one of the options to the \texttt{icml2023}
usepackage statement.

\subsection{Submitting Final Camera-Ready Copy}

The final versions of papers accepted for publication should follow the
same format and naming convention as initial submissions, except that
author information (names and affiliations) should be given. See
\cref{final author} for formatting instructions.

The footnote, ``Preliminary work. Under review by the International
Conference on Machine Learning (ICML). Do not distribute.'' must be
modified to ``\textit{Proceedings of the
$\mathit{40}^{th}$ International Conference on Machine Learning},
Honolulu, Hawaii, USA, PMLR 202, 2023.
Copyright 2023 by the author(s).''

For those using the \textbf{\LaTeX} style file, this change (and others) is
handled automatically by simply changing
$\mathtt{\backslash usepackage\{icml2023\}}$ to
$$\mathtt{\backslash usepackage[accepted]\{icml2023\}}$$
Authors using \textbf{Word} must edit the
footnote on the first page of the document themselves.

Camera-ready copies should have the title of the paper as running head
on each page except the first one. The running title consists of a
single line centered above a horizontal rule which is $1$~point thick.
The running head should be centered, bold and in $9$~point type. The
rule should be $10$~points above the main text. For those using the
\textbf{\LaTeX} style file, the original title is automatically set as running
head using the \texttt{fancyhdr} package which is included in the ICML
2023 style file package. In case that the original title exceeds the
size restrictions, a shorter form can be supplied by using

\verb|\icmltitlerunning{...}|

just before $\mathtt{\backslash begin\{document\}}$.
Authors using \textbf{Word} must edit the header of the document themselves.

\section{Format of the Paper}

All submissions must follow the specified format.

\subsection{Dimensions}

The text of the paper should be formatted in two columns, with an
overall width of 6.75~inches, height of 9.0~inches, and 0.25~inches
between the columns. The left margin should be 0.75~inches and the top
margin 1.0~inch (2.54~cm). The right and bottom margins will depend on
whether you print on US letter or A4 paper, but all final versions
must be produced for US letter size.
Do not write anything on the margins.

The paper body should be set in 10~point type with a vertical spacing
of 11~points. Please use Times typeface throughout the text.

\subsection{Title}

The paper title should be set in 14~point bold type and centered
between two horizontal rules that are 1~point thick, with 1.0~inch
between the top rule and the top edge of the page. Capitalize the
first letter of content words and put the rest of the title in lower
case.

\subsection{Author Information for Submission}
\label{author info}

ICML uses double-blind review, so author information must not appear. If
you are using \LaTeX\/ and the \texttt{icml2023.sty} file, use
\verb+\icmlauthor{...}+ to specify authors and \verb+\icmlaffiliation{...}+ to specify affiliations. (Read the TeX code used to produce this document for an example usage.) The author information
will not be printed unless \texttt{accepted} is passed as an argument to the
style file.
Submissions that include the author information will not
be reviewed.

\subsubsection{Self-Citations}

If you are citing published papers for which you are an author, refer
to yourself in the third person. In particular, do not use phrases
that reveal your identity (e.g., ``in previous work \cite{langley00}, we
have shown \ldots'').

Do not anonymize citations in the reference section. The only exception are manuscripts that are
not yet published (e.g., under submission). If you choose to refer to
such unpublished manuscripts \cite{anonymous}, anonymized copies have
to be submitted
as Supplementary Material via CMT\@. However, keep in mind that an ICML
paper should be self contained and should contain sufficient detail
for the reviewers to evaluate the work. In particular, reviewers are
not required to look at the Supplementary Material when writing their
review (they are not required to look at more than the first $8$ pages of the submitted document).

\subsubsection{Camera-Ready Author Information}
\label{final author}

If a paper is accepted, a final camera-ready copy must be prepared.
For camera-ready papers, author information should start 0.3~inches below the
bottom rule surrounding the title. The authors' names should appear in 10~point
bold type, in a row, separated by white space, and centered. Author names should
not be broken across lines. Unbolded superscripted numbers, starting 1, should
be used to refer to affiliations.

Affiliations should be numbered in the order of appearance. A single footnote
block of text should be used to list all the affiliations. (Academic
affiliations should list Department, University, City, State/Region, Country.
Similarly for industrial affiliations.)

Each distinct affiliations should be listed once. If an author has multiple
affiliations, multiple superscripts should be placed after the name, separated
by thin spaces. If the authors would like to highlight equal contribution by
multiple first authors, those authors should have an asterisk placed after their
name in superscript, and the term ``\textsuperscript{*}Equal contribution"
should be placed in the footnote block ahead of the list of affiliations. A
list of corresponding authors and their emails (in the format Full Name
\textless{}email@domain.com\textgreater{}) can follow the list of affiliations.
Ideally only one or two names should be listed.

A sample file with author names is included in the ICML2023 style file
package. Turn on the \texttt{[accepted]} option to the stylefile to
see the names rendered. All of the guidelines above are implemented
by the \LaTeX\ style file.

\subsection{Abstract}

The paper abstract should begin in the left column, 0.4~inches below the final
address. The heading `Abstract' should be centered, bold, and in 11~point type.
The abstract body should use 10~point type, with a vertical spacing of
11~points, and should be indented 0.25~inches more than normal on left-hand and
right-hand margins. Insert 0.4~inches of blank space after the body. Keep your
abstract brief and self-contained, limiting it to one paragraph and roughly 4--6
sentences. Gross violations will require correction at the camera-ready phase.

\subsection{Partitioning the Text}

You should organize your paper into sections and paragraphs to help
readers place a structure on the material and understand its
contributions.

\subsubsection{Sections and Subsections}

Section headings should be numbered, flush left, and set in 11~pt bold
type with the content words capitalized. Leave 0.25~inches of space
before the heading and 0.15~inches after the heading.

Similarly, subsection headings should be numbered, flush left, and set
in 10~pt bold type with the content words capitalized. Leave
0.2~inches of space before the heading and 0.13~inches afterward.

Finally, subsubsection headings should be numbered, flush left, and
set in 10~pt small caps with the content words capitalized. Leave
0.18~inches of space before the heading and 0.1~inches after the
heading.

Please use no more than three levels of headings.

\subsubsection{Paragraphs and Footnotes}

Within each section or subsection, you should further partition the
paper into paragraphs. Do not indent the first line of a given
paragraph, but insert a blank line between succeeding ones.

You can use footnotes\footnote{Footnotes
should be complete sentences.} to provide readers with additional
information about a topic without interrupting the flow of the paper.
Indicate footnotes with a number in the text where the point is most
relevant. Place the footnote in 9~point type at the bottom of the
column in which it appears. Precede the first footnote in a column
with a horizontal rule of 0.8~inches.\footnote{Multiple footnotes can
appear in each column, in the same order as they appear in the text,
but spread them across columns and pages if possible.}

\begin{figure}[ht]
\vskip 0.2in
\begin{center}
\centerline{\includegraphics[width=\columnwidth]{icml_numpapers}}
\caption{Historical locations and number of accepted papers for International
Machine Learning Conferences (ICML 1993 -- ICML 2008) and International
Workshops on Machine Learning (ML 1988 -- ML 1992). At the time this figure was
produced, the number of accepted papers for ICML 2008 was unknown and instead
estimated.}
\label{icml-historical}
\end{center}
\vskip -0.2in
\end{figure}

\subsection{Figures}

You may want to include figures in the paper to illustrate
your approach and results. Such artwork should be centered,
legible, and separated from the text. Lines should be dark and at
least 0.5~points thick for purposes of reproduction, and text should
not appear on a gray background.

Label all distinct components of each figure. If the figure takes the
form of a graph, then give a name for each axis and include a legend
that briefly describes each curve. Do not include a title inside the
figure; instead, the caption should serve this function.

Number figures sequentially, placing the figure number and caption
\emph{after} the graphics, with at least 0.1~inches of space before
the caption and 0.1~inches after it, as in
\cref{icml-historical}. The figure caption should be set in
9~point type and centered unless it runs two or more lines, in which
case it should be flush left. You may float figures to the top or
bottom of a column, and you may set wide figures across both columns
(use the environment \texttt{figure*} in \LaTeX). Always place
two-column figures at the top or bottom of the page.

\subsection{Algorithms}

If you are using \LaTeX, please use the ``algorithm'' and ``algorithmic''
environments to format pseudocode. These require
the corresponding stylefiles, algorithm.sty and
algorithmic.sty, which are supplied with this package.
\cref{alg:example} shows an example.

\begin{algorithm}[tb]
   \caption{Bubble Sort}
   \label{alg:example}
\begin{algorithmic}
   \STATE {\bfseries Input:} data $x_i$, size $m$
   \REPEAT
   \STATE Initialize $noChange = true$.
   \FOR{$i=1$ {\bfseries to} $m-1$}
   \IF{$x_i > x_{i+1}$}
   \STATE Swap $x_i$ and $x_{i+1}$
   \STATE $noChange = false$
   \ENDIF
   \ENDFOR
   \UNTIL{$noChange$ is $true$}
\end{algorithmic}
\end{algorithm}

\subsection{Tables}

You may also want to include tables that summarize material. Like
figures, these should be centered, legible, and numbered consecutively.
However, place the title \emph{above} the table with at least
0.1~inches of space before the title and the same after it, as in
\cref{sample-table}. The table title should be set in 9~point
type and centered unless it runs two or more lines, in which case it
should be flush left.

\begin{table}[t]
\caption{Classification accuracies for naive Bayes and flexible
Bayes on various data sets.}
\label{sample-table}
\vskip 0.15in
\begin{center}
\begin{small}
\begin{sc}
\begin{tabular}{lcccr}
\toprule
Data set & Naive & Flexible & Better? \\
\midrule
Breast    & 95.9$\pm$ 0.2& 96.7$\pm$ 0.2& $\surd$ \\
Cleveland & 83.3$\pm$ 0.6& 80.0$\pm$ 0.6& $\times$\\
Glass2    & 61.9$\pm$ 1.4& 83.8$\pm$ 0.7& $\surd$ \\
Credit    & 74.8$\pm$ 0.5& 78.3$\pm$ 0.6&         \\
Horse     & 73.3$\pm$ 0.9& 69.7$\pm$ 1.0& $\times$\\
Meta      & 67.1$\pm$ 0.6& 76.5$\pm$ 0.5& $\surd$ \\
Pima      & 75.1$\pm$ 0.6& 73.9$\pm$ 0.5&         \\
Vehicle   & 44.9$\pm$ 0.6& 61.5$\pm$ 0.4& $\surd$ \\
\bottomrule
\end{tabular}
\end{sc}
\end{small}
\end{center}
\vskip -0.1in
\end{table}

Tables contain textual material, whereas figures contain graphical material.
Specify the contents of each row and column in the table's topmost
row. Again, you may float tables to a column's top or bottom, and set
wide tables across both columns. Place two-column tables at the
top or bottom of the page.

\subsection{Theorems and such}
The preferred way is to number definitions, propositions, lemmas, etc. consecutively, within sections, as shown below.
\begin{definition}
\label{def:inj}
A function $f:X {\tilde{o}} Y$ is injective if for any $x,y\in X$ different, $f(x)\ne f(y)$.
\end{definition}
Using \cref{def:inj} we immediate get the following result:
\begin{proposition}
If $f$ is injective mapping a set $X$ to another set $Y$,
the cardinality of $Y$ is at least as large as that of $X$
\end{proposition}
\begin{proof}
Left as an exercise to the reader.
\end{proof}
\cref{lem:usefullemma} stated next will prove to be useful.
\begin{lemma}
\label{lem:usefullemma}
For any $f:X {\tilde{o}} Y$ and $g:Y{\tilde{o}} Z$ injective functions, $f \circ g$ is injective.
\end{lemma}
\begin{theorem}
\label{thm:bigtheorem}
If $f:X{\tilde{o}} Y$ is bijective, the cardinality of $X$ and $Y$ are the same.
\end{theorem}
An easy corollary of \cref{thm:bigtheorem} is the following:
\begin{corollary}
If $f:X{\tilde{o}} Y$ is bijective,
the cardinality of $X$ is at least as large as that of $Y$.
\end{corollary}
\begin{assumption}
The set $X$ is finite.
\label{ass:xfinite}
\end{assumption}
\begin{remark}
According to some, it is only the finite case (cf. \cref{ass:xfinite}) that is interesting.
\end{remark}

\subsection{Citations and References}

Please use APA reference format regardless of your formatter
or word processor. If you rely on the \LaTeX\/ bibliographic
facility, use \texttt{natbib.sty} and \texttt{icml2023.bst}
included in the style-file package to obtain this format.

Citations within the text should include the authors' last names and
year. If the authors' names are included in the sentence, place only
the year in parentheses, for example when referencing Arthur Samuel's
pioneering work \yrcite{Samuel59}. Otherwise place the entire
reference in parentheses with the authors and year separated by a
comma \cite{Samuel59}. List multiple references separated by
semicolons \cite{kearns89,Samuel59,mitchell80}. Use the `et~al.'
construct only for citations with three or more authors or after
listing all authors to a publication in an earlier reference \cite{MachineLearningI}.

Authors should cite their own work in the third person
in the initial version of their paper submitted for blind review.
Please refer to \cref{author info} for detailed instructions on how to
cite your own papers.

Use an unnumbered first-level section heading for the references, and use a
hanging indent style, with the first line of the reference flush against the
left margin and subsequent lines indented by 10 points. The references at the
end of this document give examples for journal articles \cite{Samuel59},
conference publications \cite{langley00}, book chapters \cite{Newell81}, books
\cite{DudaHart2nd}, edited volumes \cite{MachineLearningI}, technical reports
\cite{mitchell80}, and dissertations \cite{kearns89}.

Alphabetize references by the surnames of the first authors, with
single author entries preceding multiple author entries. Order
references for the same authors by year of publication, with the
earliest first. Make sure that each reference includes all relevant
information (e.g., page numbers).

Please put some effort into making references complete, presentable, and
consistent, e.g. use the actual current name of authors.
If using bibtex, please protect capital letters of names and
abbreviations in titles, for example, use \{B\}ayesian or \{L\}ipschitz
in your .bib file.

\section*{Accessibility}
Authors are kindly asked to make their submissions as accessible as possible for everyone including people with disabilities and sensory or neurological differences.
Tips of how to achieve this and what to pay attention to will be provided on the conference website \url{http://icml.cc/}.

\section*{Software and Data}

If a paper is accepted, we strongly encourage the publication of software and data with the
camera-ready version of the paper whenever appropriate. This can be
done by including a URL in the camera-ready copy. However, \textbf{do not}
include URLs that reveal your institution or identity in your
submission for review. Instead, provide an anonymous URL or upload
the material as ``Supplementary Material'' into the CMT reviewing
system. Note that reviewers are not required to look at this material
when writing their review.

\section*{Acknowledgements}

\textbf{Do not} include acknowledgements in the initial version of
the paper submitted for blind review.

If a paper is accepted, the final camera-ready version can (and
probably should) include acknowledgements. In this case, please
place such acknowledgements in an unnumbered section at the
end of the paper. Typically, this will include thanks to reviewers
who gave useful comments, to colleagues who contributed to the ideas,
and to funding agencies and corporate sponsors that provided financial
support.

\nocite{langley00}

\section{Introduction}
\label{sec:intro}

Graph neural networks (GNNs) have been widely used for representation learning on graph-structured data~\cite{hamilton2020graph, ma2021deep}, and they achieve promising state-of-the-art performance on various general graph learning tasks, such as node classification, link prediction, and graph classification~\cite{kipf2016semi,gasteiger2018combining,velivckovic2017graph,wu2019simplifying} as well as a variety of important applications, such as recommendation systems, social network analysis, and transportation prediction.
In particular, recent research in deeper GNNs has generally revealed the performance gains from capturing long-distance relations in graphs by stacking more graph convolution layers or unrolling various fixed point iterations~\cite{gasteiger2018predict, gu2020implicit, liu2020towards, chen2020simple, li2021training, ma2020unified, pan2020_unified, zhu2021interpreting, chen2020graph}.
However, the recursive feature propagations in deeper GNNs lead to the well-known neighborhood explosion problem since the number of neighbors grows exponentially with the number of feature propagation layers~\cite{hamilton2017inductive, chen2018fastgcn}.
This causes tremendous scalability challenges for data sampling, computation, memory, parallelism, and end-to-end training when employing GNNs on large-scale graphs.
It greatly limits GNNs' broad applications in large-scale industry-level applications due to limited computation and memory resources~\cite{ying2018graph, shao2022distributed}.

A large body of existing research focuses on improving the scalability and efficiency of large-scale GNNs using various innovative designs, such as sampling methods, pre-computing or post-computing methods, and distributed methods.
Although these approaches mitigate the neighborhood explosion problem, they still face various limitations when they are applied to deeper GNNs. For instance, sampling approaches~\cite{hamilton2017inductive, chen2018fastgcn, Zeng2020GraphSAINT, zou2019layer,fey2021gnnautoscale, yu2022graphfm} usually incur large approximation errors and suffer from performance degradation as demonstrated in large-scale OGB benchmarks or require large additional memory or storage space to store activation values in hidden layers.
Pre-computing or post-computing methods~\cite{wu2019simplifying, rossi2020sign, sun2021scalable, zhang2022graph, bojchevski2020scaling, zhu2005semi, huang2020combining} lose the benefits of end-to-end training and usually suffer from performance loss. Distributed methods~\cite{chiang2019cluster, chai2022distributed, shao2022distributed} distribute large graphs to multiple servers for parallel training, but they either lose the inter-server edges or suffer from expensive feature communication between servers.

In this work, we take a substantially different and novel perspective and propose to capture long-distance dependency in graphs by shallower GNNs instead of deeper GNNs. The key intuition comes from the fact that node information has been propagated over the graph many times during the training process so we may only need to propagate information lazily by reusing the propagated information over the training iterations. This intuition leads to the proposed LazyGNN that solves the inherent neighborhood explosion problem by significantly reducing the number of aggregation layers while still capturing long-distance dependency in graphs through lazy propagation. Multiple technical challenges such as the risk of over-smoothing, additional variation due to feature dropout, and back-propagation through historical computation graphs are carefully dealt with by innovative designs in LazyGNN.
Moreover, since LazyGNN is a shallow model, it naturally tackles the limitations that existing scalable approaches suffer from when handling large-scale and deeper GNNs. Therefore, various scalable approaches can be used in LazyGNN for further acceleration. We demonstrate this by developing a highly scalable and efficient mini-batch LazyGNN based on sampling methods.
To the best of our knowledge, LazyGNN is the first GNN model being versatilely friendly to data sampling, computation, memory space, parallelism, and end-to-end training but still captures long-distance dependency in graphs.
Our contributions can be summarized as follows:
\vspace{-0.2in}
\begin{itemize}
\itemsep0em
    \item We reveal a novel perspective to solve the neighborhood explosion problem by exploiting the computation redundancy in training GNNs;

    \item A novel shallow model, LazyGNN, is proposed to capture long-distance dependency in graphs for end-to-end graph representation learning through lazy forward and backward propagations;

    \item We demonstrate that existing scalable approaches can be compatible with LazyGNN by introducing a highly efficient and scalable mini-batch LazyGNN to handle large-scale graphs based on sampling methods.

    \item Comprehensive experiments demonstrate superior prediction performance and efficiency on large-scale graph datasets. Notably, the proposed LazyGNN also achieves the best performance on OGB leaderboard.
\end{itemize}

\section{Lazy Graph Neural Networks}
\label{sec:method}

In this section, we propose a novel shallow LazyGNN that uses a few aggregation layers to capture long-distance dependency in graphs through lazy forward and backward propagations. Then a mini-batch LazyGNN is introduced to handle large-scale graphs with efficient data sampling, computation, and memory usage.
Complexity analyses are also provided to illustrate the superior scalability of LazyGNN.

\subsection{GNNs with Lazy Propagation}
\label{sec:lazygnn}

Existing research has demonstrated the benefits of capturing long-distance relations in graphs by stacking more feature aggregation layers or unrolling various fixed point iterations as introduced in Section~\ref{sec:intro}.
However, these deeper GNNs are not efficient due to the neighborhood explosion problem.
Our preliminary study in Section~\ref{sec:preliminary_section} reveals the computation redundancy in GNNs over the training iterations:
the hidden features in GNNs evolve slowly such that the computation of feature aggregations is highly correlated and redundant over training iterations.
This observation motivates us to develop
a novel shallow LazyGNN that captures long-distance relations in graphs by propagating information lazily with very few message-passing layers.

Without loss of generality, we build LazyGNN on the most common graph signal denoising problem:
\begin{align}
\label{eq:denoise_problem}
\min_{{\mathbf{X}}} ~ \|{\mathbf{X}}-{\mathbf{X}}_{\text{in}}\|^2_F + ({1/\alpha}-1)~ {\tilde{r}} ({\mathbf{X}}^{\top}  ({\mathbf{I}}-{\tilde{{\mathbf{A}}}}) {\mathbf{X}}),
\end{align}
\vspace{-0.3in}

\noindent where the first term maintains the proximity with node hidden features ${{\mathbf{X}}_{\text{in}}}$ after feature transformation, and the second Laplacian smoothing regularization encodes smoothness assumption on graph representations.
We take this as an example to illustrate the main idea of lazy propagation but the idea can be applied to other GNNs inspired by general denoising problems or fixed point iterations with different properties. Next, we illustrate the lazy forward and backward propagations in LazyGNN as well as the technical challenges being solved by innovative designs.

\textbf{Forward Computation.}
From Eq.~\eqref{eq:denoise_problem}, we derive the high-order graph diffusion as in APPNP~\cite{klicpera2018predict} with $f$ being the feature transformation:
\begin{align}
{\mathbf{X}}_{\text{in}}^k &= f({\mathbf{X}}_{\text{fea}}, \Theta^k), \\
{\mathbf{X}}_{0}^k &= {\mathbf{X}}_{\text{in}}^k, \\
{\mathbf{X}}_{l+1}^k &= (1-\alpha) {\tilde{{\mathbf{A}}}} {\mathbf{X}}_{l}^k+\alpha {\mathbf{X}}_{\text{in}}^k, \forall l=0,\dots,L-1
\end{align}
where $l$ and $k$ denote the index of layers and training iterations, respectively. The key insight of LazyGNN is that
the approximate solution of Eq.~\eqref{eq:denoise_problem} (i.e., ${\mathbf{X}}^k_{L}$) evolves smoothly since
${\mathbf{X}}_{\text{in}}^k = f({\mathbf{X}}_{\text{fea}}, \Theta^k)$ changes smoothly with model parameters $\Theta^k$.
Intuitively, the features have been propagated over the graph many times in previous training iterations so that it suffices to propagate features lazily by reusing existing computation.
Formally, we propose LazyGNN to leverage the computation redundancy between training iterations by mixing the diffusion output in iteration $k-1$ (i.e., ${\mathbf{X}}_L^{k-1}$) into the initial embedding of the diffusion process in training iteration $k$, namely ${\mathbf{X}}_0^{k} = (1-\beta) {\mathbf{X}}_L^{k-1} + \beta {\mathbf{X}}_{\text{in}}^k$. This is because, in practice, dropout is commonly used in deep learning to prevent overfitting, which introduces additional variations in the feature embedding as demonstrated in Figure~\ref{fig:redundancy}. Therefore, we introduce this momentum correction to compensate for such disturbance by mixing current and history features with hyperparameter $\beta$. To summarize, the forward computation of LazyGNN works as follows:
\begin{align}
{\mathbf{X}}_{\text{in}}^k &= f({\mathbf{X}}_{\text{fea}}, \Theta^k), \\
{\mathbf{X}}_{0}^k &= (1-\beta) {\mathbf{X}}^{k-1}_L + \beta {\mathbf{X}}_{\text{in}}^k, \label{eq:forward_momentum} \\
{\mathbf{X}}_{l+1}^k &= (1-\alpha) {\tilde{{\mathbf{A}}}} {\mathbf{X}}_{l}^k+\alpha {\mathbf{X}}_{\text{in}}^k, \forall l=0,\dots,L-1  \label{eq:mp_iter}
\end{align}
\vspace{-0.2in}

\begin{figure}[htp]
    \centering
    \includegraphics[width=8.3cm]{figure/lazygnn5.png}
    \caption{LazyGNN with Lazy forward \& backward propagation.}
    \label{fig:lazygnn}
\end{figure}
\vspace{-0.1in}

By lingering the computation over training iterations as shown in Figure~\ref{fig:lazygnn}, the feature aggregation layers in Eq.~\eqref{eq:mp_iter} solve the denoising problem in Eq.~\eqref{eq:denoise_problem} with an implicitly large number of steps although there are only $L$ layers in each training iteration. Therefore, it only requires a few feature aggregation layers (a small $L$) to approximate the fixed point solution ${\mathbf{X}}_*^k$. Note that we find $L=1$ and $L=2$ work very well in our experiments in Section~\ref{sec:experiment}.
In the extreme case when the learning rate and dropout rate are $0$, the forward computation of LazyGNN is equivalent to running forward propagations $L\times K$ times continuously with $K$ being the total number of training iterations.

\begin{remark}[Long-distance dependency]
Through lazy propagation, LazyGNN is able to capture long-distance dependency in graphs with a small number of feature aggregation layers because LazyGNN accumulatively propagates information to distant nodes in the graphs over many training iterations. In contrast, existing works try to capture long-distance dependency in graphs by increasing the number of feature propagation layers, which is less efficient.
\end{remark}

\begin{remark}[Over-smoothing]
In contrast to many GNN models such as GCN or GAT that suffer from the over-moothing issue when more layers are stacked,
the accumulation of feature aggregations over training iterations in LazyGNN will not cause the over-smoothing issue
because the residual connection ${\mathbf{X}}_{\text{in}}^k$ in Eq.~\eqref{eq:mp_iter} determines the fixed point and prevents the over-smoothed solution.
\end{remark}

\textbf{Backward Computation.}
While it is feasible to leverage the computation from previous training iterations in the forward computation, it is highly non-trivial to compute the gradient for model update in the backward computation since the computation graphs from previous training iterations have been destroyed and released in the memory. In other words, there is no way to directly compute the backpropagation through the history variables $\{{\mathbf{X}}_L^{k-1}, {\mathbf{X}}_L^{k-2}, \dots\}$ in current iterations $k$. Therefore, we choose to compute the gradient indirectly via the implicit function theorem.

\begin{theorem}[Implicit Gradient]
\label{thm:implicit}
Let ${\mathbf{X}}_*$ be the fixed point solution of function $g({\mathbf{X}}_*, {\mathbf{X}}_{\text{in}})$, i.e., $g({\mathbf{X}}_*, {\mathbf{X}}_{\text{in}})=\mathbf{0}$.
Given the gradient of loss function ${\mathcal{L}}({\mathbf{X}}_*, {\mathbf{Y}})$ with respect to the fixed point ${\mathbf{X}}_*$, i.e., $\frac{\partial {\mathcal{L}}}{\partial {\mathbf{X}}_*}$, the gradient of loss ${\mathcal{L}}$ with respect to feature ${\mathbf{X}}_{\text{in}}$ can be computed as:
\begin{align}
\frac{\partial {\mathcal{L}}}{\partial {\mathbf{X}}_{\text{in}}} = \frac{\partial {\mathcal{L}}}{\partial {\mathbf{X}}_*} ({\mathbf{J}} |_{{\mathbf{X}}_*})^{-1} \frac{\partial g({\mathbf{X}}_*, {\mathbf{X}}_{\text{in}})}{\partial {\mathbf{X}}_{\text{in}}}
\end{align}
where ${\mathbf{J}}|_{{\mathbf{X}}_*} = \frac{\partial g({\mathbf{X}}_*, {\mathbf{X}}_{\text{in}})}{\partial {\mathbf{X}}_*}$ is the Jacobian matrix of $g({\mathbf{X}}_*, {\mathbf{X}}_{\text{in}})$ evaluated at ${\mathbf{X}}_*$.
\end{theorem}
\vspace{-0.1in}
\begin{proof}
Take the first-order derivative on both sides of the fixed point equation $g({\mathbf{X}}_*, {\mathbf{X}}_{\text{in}})=0$:
\begin{align*}
\frac{ \partial{g({\mathbf{X}}_*, {\mathbf{X}}_{\text{in}})}}{\partial {\mathbf{X}}_{\text{in}}} + \frac{ \partial{g({\mathbf{X}}_*, {\mathbf{X}}_{\text{in}})}}{\partial {\mathbf{X}}_*} \frac{d {\mathbf{X}}_*}{d {\mathbf{X}}_{\text{in}}} = \mathbf{0}
\end{align*}
\vspace{-0.2in}
\begin{align*}
\frac{d {\mathbf{X}}_*}{d {\mathbf{X}}_{\text{in}}} = - \Big(\frac{ \partial{g({\mathbf{X}}_*, {\mathbf{X}}_{\text{in}})}}{\partial {\mathbf{X}}_*} \Big )^{-1} \frac{ \partial{g({\mathbf{X}}_*, {\mathbf{X}}_{\text{in}})}}{\partial {\mathbf{X}}_{\text{in}}}
\end{align*}
Using $\frac{\partial {\mathcal{L}}}{\partial {\mathbf{X}}_{\text{in}}} = \frac{\partial {\mathcal{L}}}{\partial {\mathbf{X}}_*} \frac{d {\mathbf{X}}_*}{d {\mathbf{X}}_{\text{in}}}$, we obtain:
\begin{align*}
\frac{\partial {\mathcal{L}}}{\partial {\mathbf{X}}_{\text{in}}} = -\frac{\partial {\mathcal{L}}}{\partial {\mathbf{X}}_*} \Big (\frac{ \partial{g({\mathbf{X}}_*, {\mathbf{X}}_{\text{in}})}}{\partial {\mathbf{X}}_*} \Big)^{-1} \frac{ \partial{g({\mathbf{X}}_*, {\mathbf{X}}_{\text{in}})}}{\partial {\mathbf{X}}_{\text{in}}}.
 \end{align*}
 \vspace{-0.2in}
\end{proof}

Specifically, for the problem in Eq.~\eqref{eq:denoise_problem}, we have the fixed point equation:
\vspace{-0.15in}
\begin{align}
\hspace{-0.1in}
g({\mathbf{X}}_*,{\mathbf{X}}_{\text{in}})={\mathbf{X}}_*-{\mathbf{X}}_{\text{in}} + (\frac{1}{\alpha}-1) ({\mathbf{I}}-{\tilde{{\mathbf{A}}}}) {\mathbf{X}}_* = \mathbf{0}
\end{align}
\vspace{-0.3in}

\noindent which gives $\frac{ \partial{g({\mathbf{X}}_*, {\mathbf{X}}_{\text{in}})}}{\partial {\mathbf{X}}_{\text{in}}} = -{\mathbf{I}}$ and ${\mathbf{J}}|_{{\mathbf{X}}_*}= \frac{1}{\alpha} ({\mathbf{I}}-(1-\alpha) {\tilde{{\mathbf{A}}}})$. Therefore, according to Theorem~\ref{thm:implicit}, the gradient of loss ${\mathcal{L}}$ with respect to ${{\mathbf{X}}_{\text{in}}}$ can be computed as follows:
\vspace{-0.1in}
\begin{align}
\frac{\partial {\mathcal{L}}}{\partial {\mathbf{X}}_{\text{in}}} = \alpha \frac{\partial {\mathcal{L}}}{\partial {\mathbf{X}}_*}
\Big ( {\mathbf{I}} - (1-\alpha) {\tilde{{\mathbf{A}}}} \Big)^{-1}.
\end{align}
\vspace{-0.2in}

\noindent However, it is still infeasible to compute the expensive matrix inversion so we propose to approximate it by the iterative backward gradient propagation:
\vspace{-0.1in}
\begin{align}
{\mathbf{G}}_L &= \frac{\partial {\mathcal{L}}}{\partial {\mathbf{X}}_L} ~~\Big ( \approx \frac{\partial {\mathcal{L}}}{\partial {\mathbf{X}}_*} \Big ) \\
{\mathbf{G}}_{l} &= (1-\alpha) {\tilde{{\mathbf{A}}}} {\mathbf{G}}_{l+1} + \alpha \frac{\partial {\mathcal{L}}}{\partial {\mathbf{X}}_L} ~\forall l=L-1, \dots, 0
\end{align}
\vspace{-0.2in}

\noindent where $\frac{\partial {\mathcal{L}}}{\partial {\mathbf{X}}_*}$ is approximated by $\frac{\partial {\mathcal{L}}}{\partial {\mathbf{X}}_L}$, and ${\mathbf{G}}_0$ provides an approximation for gradient $\frac{\partial {\mathcal{L}}}{\partial {\mathbf{X}}_{\text{in}}}$.
It is clear that the backward computation requires gradient propagation over the graph, which is symmetric to and as expensive as the vanilla forward computation.
Similarly, to reduce the number of gradient propagation layers, we propose to propagate the gradient lazily by leveraging the gradient $\frac{\partial {\mathcal{L}}}{\partial {\mathbf{X}}_{\text{in}}^{k-1}}$ computed in the previous training iteration $k-1$ as shown in Figure~\ref{fig:lazygnn}:
\vspace{-0.2in}
\begin{align}
{\mathbf{G}}_L^k &= (1-\gamma) \frac{\partial {\mathcal{L}}}{\partial {\mathbf{X}}_{\text{in}}^{k-1}} + \gamma \frac{\partial {\mathcal{L}}}{\partial {\mathbf{X}}_L^{k}}  \label{eq:backward_momentum} \\
{\mathbf{G}}_{l}^k &= (1-\alpha) {\tilde{{\mathbf{A}}}} {\mathbf{G}}_{l+1} + \alpha \frac{\partial {\mathcal{L}}}{\partial {\mathbf{X}}_L^k} ~\forall l=L-1, \dots, 0
\end{align}
\vspace{-0.2in}

\noindent where $\frac{\partial {\mathcal{L}}}{\partial {\mathbf{X}}_*^k}$ is approximated by $\frac{\partial {\mathcal{L}}}{\partial {\mathbf{X}}_L^k}$, and ${\mathbf{G}}_0$ provides an approximation for gradient $\frac{\partial {\mathcal{L}}}{\partial {\mathbf{X}}_{\text{in}}^k}$ so that the gradient of model parameters, i.e., $\frac{\partial {\mathcal{L}}}{\partial \Theta^k}$, can be further computed by chain rules.
Similar to the forward computation, the momentum correction in Eq.~\eqref{eq:backward_momentum} compensates the gradient changes over training iterations by mixing the current gradient $\frac{\partial {\mathcal{L}}}{\partial {\mathbf{X}}_L^{k}}$ and history gradient $\frac{\partial {\mathcal{L}}}{\partial {\mathbf{X}}_{\text{in}}^{k-1}}$ with hyperparameter $\gamma$.

\begin{remark}[Computation and memory efficiency]
Since LazyGNN uses very few aggregation layers, it significantly reduces the computation and memory cost. Moreover, LazyGNN does not need to store intermediate hidden activation values in the aggregation layers because the computation of implicit gradient is agnostic to the forward propagation trajectory, which further reduces memory cost.
\end{remark}

\subsection{Mini-batch LazyGNN with Subgraph Sampling}
\label{sec:mini-lazygnn}

As illustrated in Section~\ref{sec:lazygnn}, LazyGNN solves the inherent neighborhood explosion problem so that when handling large-scale graphs, the mini-batch sampling only needs to sample neighboring nodes within a few hop distances. To further demonstrate the superior scalability, we introduce a mini-batch LazyGNN to further improve the computation and memory efficiency with efficient data sampling as shown in Figure~\ref{fig:mini-batch}.
In each training iteration $k$, we sample a target node set $V_1^k$ and their $L$-hop neighbor set $V_2^k$, and we denote the union of these two nodes as $V^k=V_1^k \cup V_2^k$. An induced subgraph ${\tilde{{\mathbf{A}}}}_{V^k}$ is constructed based on the node set $V^k$. Note that LazyGNN works well with small $L\in\{1,2\}$ so that the data sampling is extremely efficient.

\begin{figure}[htp]
    \centering
    \includegraphics[width=8cm]{figure/mini-batch2.png}
    \vspace{-0.1in}
    \caption{Mini-batch LazyGNN with Feature \& Gradient Storage.}
    \label{fig:mini-batch}
\end{figure}

\textbf{Forward Computation.}
The forward computation of mini-batch LazyGNN works as follows:
\vspace{-0.1in}
\begin{align}
({\mathbf{X}}_{\text{in}}^k)_{V_k} &= f \big(({\mathbf{X}}_{\text{fea}})_{V^k}, \Theta^k \big), \\
({\mathbf{X}}_0)_{V_k} &= (1-\beta) ({\mathbf{M}}_{\text{fea}})_{V^k}
+ \beta ({\mathbf{X}}_{\text{in}}^k)_{V_k} \label{eq:mini_mix_forward}\\
({\mathbf{X}}_{l+1}^k)_{V^k} &= (1-\alpha) {\tilde{{\mathbf{A}}}}_{V^k} ({\mathbf{X}}_{l}^k)_{V^k} + \alpha ({\mathbf{X}}_{\text{in}}^k)_{V^k},
\forall l \label{eq:mini_forward_prop} \\
({\mathbf{M}}_{\text{fea}})_{V^k_1} &= ({\mathbf{X}}_{L}^k)_{V^k_1}  \label{eq:save_forward_history}
\end{align}
\vspace{-0.2in}

\noindent The node features $({\mathbf{X}}_{\text{fea}})_{V^k}$ for the node set $V^k$ are sampled to form a mini-batch. The corresponding diffused node features $({\mathbf{M}}_{\text{fea}})_{V^k}$ of the same node set are retrieved from the feature storage ${\mathbf{M}}_{\text{fea}}$ and then combined with current node features $({\mathbf{X}}_{\text{in}}^k)_{V_k}$ in Eq.~\eqref{eq:mini_mix_forward}. The lazy forward propagation runs on the subgraph ${\tilde{{\mathbf{A}}}}_{V^k}$ in Eq.~\eqref{eq:mini_forward_prop}. Finally, $({\mathbf{X}}_{L}^k)_{V^k_1}$ provides the prediction for target nodes $V_1^k$, which is further maintained in the features storage ${\mathbf{M}}_{\text{fea}}$.

\textbf{Backward Computation.}
The backward computation of mini-batch LazyGNN works as follows:
\vspace{-0.1in}
\begin{align}
& ({\mathbf{G}}_L^k)_{V^k} = (1-\gamma) ({\mathbf{M}}_{\text{grad}})_{V^k} + \gamma \frac{\partial {\mathcal{L}}}{\partial ({\mathbf{X}}_L^{k})_{V^k} }   \label{eq:mini_mix_backward} \\
& ({\mathbf{G}}_{l}^k)_{V^k} = (1-\alpha) {\tilde{{\mathbf{A}}}}_{V^k} ({\mathbf{G}}_{l+1})_{V^k} + \frac{ \alpha ~~\partial {\mathcal{L}}}{\partial ({\mathbf{X}}_L^k)_{V^k} } ~\forall l \label{eq:mini_backward_prop} \\
 & ({\mathbf{M}}_{\text{grad}})_{V^k_1} = ({\mathbf{G}}_{0}^k)_{V^k_1} \label{eq:mini_backward_history}
\end{align}
\vspace{-0.3in}

\noindent In Eq.~\eqref{eq:mini_mix_backward}, $({\mathbf{M}}_{\text{grad}})_{V^k}$, the history gradient with respect to node features $({\mathbf{X}}_{{\text{in}}}^{k-1})_{V^k}$, is retrieved from the gradient storage ${\mathbf{M}}_{\text{grad}}$ and then combined with $\frac{\partial {\mathcal{L}}}{\partial ({\mathbf{X}}_L^{k})_{V^k}}$, the gradient with respect to current node features $({\mathbf{X}}_L^{k})_{V^k}$. The lazy backward propagation runs on the subgraph ${\tilde{{\mathbf{A}}}}_{V^k}$ in Eq.~\eqref{eq:mini_backward_prop}. Finally, $({\mathbf{G}}_{0}^k)_{V^k_1}$ provides an estimation for $\frac{\partial {\mathcal{L}}}{\partial ({\mathbf{X}}_{\text{in}}^{k})_{V^k_1} }$, which is used to compute gradient of parameters $\Theta^k$ by chain rules and then maintained in the gradient storage ${\mathbf{M}}_{\text{grad}}$.

\subsection{Complexity Analysis}

As discussed in Section~\ref{sec:lazygnn} and Section~\ref{sec:mini-lazygnn}, LazyGNN is scalable due to its efficiency in computation, memory, and data sampling.
In this section, we provide complexity analyses to further demonstrate its superior scalability. Since the major efficiency difference lies in feature aggregation layers, we focus on the complexity of feature aggregation.
Suppose $L$ is the number of propagation layers, $H$ is the size of hidden units,
$N$ is the number of nodes, $M$ is the number of edges. For simplicity, we assume that $H$ is the same for all hidden layers.
Performing one feature aggregation requires a sparse-dense matrix multiplication that needs ${\mathcal{O}}(MH)$ operations.
Therefore, the computation complexity for forward feature aggregations and backward gradient aggregations is ${\mathcal{O}}(2LMH)$ per epoch. However, the number of layers $L$ in LazyGNN is much smaller than existing approaches, so it significantly reduces the computation cost.

For memory complexity, ${\mathcal{O}}(NH)$ space is required for the storage of history feature ${\mathbf{X}}_L^k$ and gradient $\frac{\partial {\mathcal{L}}}{\partial {\mathbf{X}}_{\text{in}}^k}$ in LazyGNN. LazyGNN does not store the intermediate state at each feature aggregation layer because the backward gradient computation is agnostic to the forward computation trajectory. Therefore, the total memory complexity for LazyGNN is ${\mathcal{O}}(NH)$, which is independent of the number of aggregation layers. In contrast, existing state-of-art history-embedding based models, such as GNNAutoScale~\cite{fey2021gnnautoscale} and GraphFM~\cite{yu2022graphfm}, require the storage of feature embeddings in every layer, which leads to the memory complexity ${\mathcal{O}}(LNH)$. Moreover, they also require the storage of all intermediate layers for gradient computation. Their memory cost increases linearly with the
number of layers, which is essential in capturing long-distance dependency in those models. In fact, because of the large storage requirements, GAS chooses to save the history embedding in CPU memory, but the data movement between CPU and GPU can be dominant compared with the movement in GPU as verified in Section~\ref{sec:efficiency}.

Mini-batch LazyGNN further reduces the computation and memory cost by data sampling, which enjoys the same benefits as existing sampling-based methods. Compared to classic sampling-based models, such as GraphSAGE and GraphSAINT, mini-batch LazyGNN only needs to sample neighbors in one hop or two hops distance so that the data sampling is efficient. Above analyses indicate that LazyGNN is highly efficient in computation, memory, and data sampling. The practical running time and memory cost will be discussed in Section~\ref{sec:efficiency}. Note that although we do not investigate the distributed setting in this paper, LazyGNN is promising for its parallelism since it requires fewer communication rounds due to lazy propagation.

\section{Conclusions}

In this paper, we propose LazyGNN, a novel shallow model to solve the neighborhood explosion problem in large-scale GNNs while capturing long-distance dependency in graphs through lazy propagation. We also develop a highly scalable and efficient variant, mini-batch LazyGNN, to handle large graphs. Comprehensive experiments demonstrate its superior prediction performance and efficiency on large-scale graph datasets. We plan to explore lazy propagation for other types of GNN models and its further acceleration based on other scalable techniques in the future.
\section{Experiments}
\label{sec:experiment}

In this section, we provide comprehensive experiments to validate the superior prediction performance and scalability of LazyGNN. Specifically, we try to answer the following questions:
(Q1) Can LazyGNN achieve strong prediction accuracy on large-scale graph benchmarks? (Section~\ref{sec:performance})
(Q2) Can LazyGNN handle large graphs more efficiently than existing approaches? (Section~\ref{sec:efficiency})
(Q3) What are the impacts of the hyperparameters in LazyGNN? (Section~\ref{sec:ablation})

\subsection{Prediction Performance}
\label{sec:performance}

\textbf{Experimental settings.}
We conduct experiments on multiple large-scale graph datasets including REDDIT, YELP, FLICKR, ogbn-arxiv, and ogbn-products~\cite{hu2020open}. We evaluate the graph representation learning by node classification accuracy in the semi-supervised setting. We provide a performance comparison with multiple baselines including GCN~\cite{kipf2016semi}, GraphSage~\cite{hamilton2017inductive}, FastGCN~\cite{chen2018fastgcn}, LADIES~\cite{zou2019layer}, VR-GCN~\cite{chen2017stochastic}, MVS-GNN~\cite{cong2020minimal}, Cluster- GCN~\cite{chiang2019cluster}, GraphSAINT~\cite{Zeng2020GraphSAINT}, SGC~\cite{wu2019simplifying}, SIGN~\cite{rossi2020sign}, GAS~\cite{fey2021gnnautoscale}.
The hyperparameter tuning of baselines closely follows the setting in GNNAutoScale~\cite{fey2021gnnautoscale}. For LazyGNN, we set $\beta=0.5$, and $\gamma=0.5$. Other hyperparameters are tuned from the following search space: (1) learning rate: $\{0.01, 0.001, 0.0001\}$;  (2) weight decay: $\{0, 5e-4, 5e-5\}$; (3) dropout: $\{0.1, 0.3, 0.5, 0.7\}$; (4) propagation layers : $L \in \{1, 2\}$; (5) MLP layers: $\{3,4\}$; (6) MLP hidden units: $\{256, 512\}$; (7) $\alpha \in \{0.01, 0.1, 0.2, 0.5, 0.8\}$.
For data sampling, while LazyGNN is compatible with any sampling method, we adopt the subgraph sampling strategy in GNNAutoScale to ensure a fair comparison.

\textbf{Performance analysis.} From the prediction accuracy as summarized in Table~\ref{tab:prediction_acc}, we can make the following observations:
(1) LazyGNN achieves state-of-art performance on almost all datasets. In particular, LazyGNN achieves $73.2\%$ and $81.0\%$ accuracy on ogbn-arxiv and ogbn-products.
The only exceptions are that GraphSAINT slightly outperforms LazyGNN by $0.2\%$ on REDDIT and that GCNII outperforms LazyGNN by $1.1\%$ on FLICKR. However, LazyGNN is much more efficient than GraphSAINT and GCNII in computation and memory cost. Note that GCNII achieves the reported performance with 10 transformation layers and 8 propagation layers while LazyGNN only uses 4-layer MLP and 2-layer propagation. We believe a stronger performance can be achieved with a more thorough architecture tuning on LazyGNN;
(2) Importantly, we observe that full-batch LazyGNN closely matches mini-batch LazyGNN, which indidates that the subgraph sampling in LazyGNN can significantly improve the scalibility (as will be discussed in Section~\ref{sec:efficiency}) but do not heavily hurt the prediction performance. Sometimes, LazyGNN even improves the generalization performance due to sampling (such as for REDDIT); (3) LazyGNN also consistently outperforms APPNP with 10 propagation layers, which indicates the advantage of capturing long-distance dependency in graphs by lazy propagation. The reproduction of GAS+GCN on YELP is much worse than reported, therefore we omit the result.

\begin{table}[ht!]
\caption{Prediction accuracy ($\%$) on large-scale graph datasets. ``full'' and ``mini'' stand for full-batch and mini-batch respectively. OOM stands for out-of-memory.}
\label{tab:prediction_acc}
\vspace{-0.2in}
\begin{center}
\begin{small}
\setlength{\tabcolsep}{2pt}
\resizebox{\linewidth}{!}{%
\begin{tabular}{lcccccc}
\toprule
    \mc{1}{l}{\footnotesize{\textbf{\#\,nodes}}} & \footnotesize{230K} & \footnotesize{89K} & \footnotesize{717K} & \footnotesize{169K} & \footnotesize{2.4M} \\ [-0.1cm]
    \mc{1}{l}{\footnotesize{\textbf{\#\,edges}}} & \footnotesize{11.6M} & \footnotesize{450K} & \footnotesize{7.9M} & \footnotesize{1.2M} & \footnotesize{61.9M} \\ [-0.05cm]
    \mc{1}{l}{\mr{2}{\textbf{Method}}} & \mr{2}{\textsc{Reddit}} & \mr{2}{\textsc{Flickr}} & \mr{2}{\textsc{Yelp}} & \texttt{ogbn-} & \texttt{ogbn-} \\
    & & & & \texttt{arxiv} & \texttt{products} \\

\midrule
GraphSAGE    & 95.4 & 50.1 & 63.4 & 71.5 & 78.7 \\
FastGCN    & 93.7 & 50.4 & --- & --- & ---  \\
LADIES    & 92.8 & --- & --- & --- & --- \\
VR-GCN    & 94.5 & --- & 61.5 & --- & ---  \\
MVS-GNN    & 94.9 & --- & 62.0 & --- & ---  \\
Cluster-GCN    & 96.6 & 48.1 & 60.9 & --- & 79.0  \\
GraphSAINT    & \textbf{97.0} & 51.1 & 65.3 & --- & 79.1  \\
SGC    & 96.4 & 48.2 & 64.0 & --- & ---  \\
SIGN    & 96.8 & 51.4 & 63.1 & --- & 77.6  \\
\hline
GCN (full)    & 95.4 & 53.7 & OOM & 71.6 & OOM   \\
APPNP (full)  & 96.1 & 53.4 & OOM & 71.8 & OOM\\
GCNII (full)    & 96.1 & 55.3 & OOM & 72.8 & OOM    \\
\hline
GCN (GAS)   & 95.4 & 54.0 & --- & 71.7 & 76.7   \\
APPNP (GAS)  & 96.0 & 52.4 & 63.8 & 71.9 &76.2 \\
GCNII (GAS)   & 96.7 & \textbf{55.3} & 65.1 & 72.5 & 77.2   \\
\hline
LazyGNN (full)   & 96.2& 54.2 & OOM & \textbf{73.2} & OOM   \\
LazyGNN (mini)   & 96.8& 54.0 & \textbf{65.4}& 73.0 & \textbf{82.0}    \\
\bottomrule
\end{tabular}
}
\end{small}
\end{center}
\vspace{-0.2in}
\end{table}

\textbf{OGB leaderboard.} To further demonstrate the superior prediction performance of LazyGNN, we also compare LazyGNN with the best-ranked GNN models on the OGB Leaderboard as of Jan. 26, 2023\footnote{\url{https://ogb.stanford.edu/docs/leader_nodeprop/}}.
To make a fair comparison, we only consider the models in the leaderboard that \textit{\textbf{do not use any external data}} such as the raw text feature. For ogbn-arxiv dataset, we choose AGDN~\cite{sun2020adaptive}, LGGNN~\cite{LGGNN-link}, C\&S~\cite{huang2020combining}, EnGCN~\cite{duan2022comprehensive} as baselines. For ogbn-products dataset, we compare with SCR~\cite{zhang2021improving}, SAGN~\cite{sun2021scalable}, GAMLP~\cite{zhang2022graph},
C\&S~\cite{huang2020combining}, and
EnGCN~\cite{duan2022comprehensive}.
Note that these top-ranked models use additional techniques to boost the performance. For instance, AGDN uses Bags of Tricks (BoT)~\cite{wang2021bag}, self-Knowledge Distillation (self-KD)~\cite{sun2020adaptive}, and Correct and Smooth (C\&S)~\cite{huang2020combining}; LGGNN uses C\&S and Label Reuse~\cite{LGGNN-link}; GAMLP uses Reliable Label Utilization (RLU)~\cite{zhang2022graph} and SCR~\cite{zhang2021scr}; EnGCN uses self-label enhancement (SLE)~\cite{sun2021scalable}, Label Propagation (LP), and Ensemble with weighted majority voting (MV).
LazyGNN is also compatible with these techniques, and we only integrate self label enhancement (SLE) ~\cite{sun2021scalable} to improve LazyGNN.

\begin{table}[htb!]
\caption{Comparison with top-ranked models on ogbn-arxiv.}
\label{tab:arxiv}
\begin{center}
\resizebox{0.8\linewidth}{!}{%
\begin{tabular}{lc}
\toprule
\textbf{Method} & \textsc{Accuracy (\%)} \\
\midrule
AGDN + BoT + self-KD   & 74.28  \\
AGDN + BoT + self-KD + C\&S   & 74.31 \\
LGGNN + LabelReuse + C\&S   & 75.70 \\
EnGCN + SLE + LP + MV  & 77.98 \\
LazyGNN + SLE & \textbf{78.65} \\
\bottomrule
\end{tabular}
}
\end{center}
\vskip -0.2in
\end{table}

\begin{table}[htb!]
\caption{Comparison with top-ranked models on ogbn-products.}
\label{tab:product}
\begin{center}
\resizebox{0.8\linewidth}{!}{%
\begin{tabular}{lc}
\toprule
\textbf{Method} &  \textsc{Accuracy (\%)} \\
\midrule
GAMLP + RLU + SCR    & 85.05\\
GAMLP + RLU + SCR + C\&S    & 85.20\\
SAGN + SLE  & 84.68\\
SAGN + SLE + C\&S    & 84.85\\
EnGCN + SLE + LP + MV   & 87.98 \\
LazyGNN + SLE & \textbf{88.05} \\
\bottomrule
\end{tabular}
}
\end{center}
\vspace{-0.2in}
\end{table}

The performance on ogbn-arxiv and ogbn-products is summarized in Table~\ref{tab:arxiv} and Table~\ref{tab:product}, respectively. They clearly demonstrate that LazyGNN (mini-batch) achieves the state-of-art performance compared with these top-ranked GNN models on the highly competitive leaderboard. LazyGNN significantly outperforms many strong baselines such as AGDN, LGGNN, GAMLP, and SAGN, and it slightly outperforms the best-performing EnGCN (Ensemble GCN) with significantly better efficiency (1.5 hours vs 2.4 hours).
\subsection{Efficiency Analysis}
\label{sec:efficiency}

To verify the scalability of LazyGNN, we provide empirical efficient analysis compared with state-of-art end-to-end trainable and scalable GNNs such as GNNAutoScale (GAS) since it has been shown to be the most efficient algorithm for training large-scale GNNs~\cite{fey2021gnnautoscale}.
Specifically, we measure the memory usage and running time for the training on ogbn-products dataset using the same batch size.
We run GAS using the authors' code which stores the feature embedding for each layer in CPU memory. For LazyGNN, the memory for storing two small tensors (i.e., feature and gradient) is required. Although the storage memory for LazyGNN can easily fit into the GPU, we measure the running time for two cases depending on whether the storage is on CPU or GPU memory. Note that all methods use similar number of training epochs as will be verified in Section~\ref{sec:ablation}, so we compare them using the running time per epoch.
For GAS baselines, we use the architecture that can reach the best performance.

\vspace{-0.1in}
\begin{table}[ht!]
\caption{Memory usage (MB) and running time for each epoch (seconds per epoch) on ogbn-products.}
\label{tab:memory}
\vskip -0.1in
\begin{center}
\setlength{\tabcolsep}{2pt}
\resizebox{0.9\linewidth}{!}{%
\begin{tabular}{lccccc}
\toprule
\mc{1}{l}{\mr{2}{\textbf{Method}}} & \textsc{GPU} & \textsc{CPU} & \textsc{Running} \\
& {\textsc{Memory}} & {\textsc{Memory}} & {\textsc{Time}} \\
\midrule
GCN (GAS)  & 2512  & 4783 & 28.8\\
GCNII (GAS)  & 3035 & 4783 & 44.3\\
APPNP (GAS) & 2142  & 3952 & 84.5\\
LazyGNN (GPU+CPU) & 2101 & 878 & 44.5\\
LazyGNN (GPU) & 2981 & --- & 7.7\\
\bottomrule
\end{tabular}
}
\end{center}
\vspace{-0.1in}
\end{table}

From the measurements summarized in Table~\ref{tab:memory}, we can make the following observations:
(1) LazyGNN (GPU) has a much shorter running time (7.7s) per epoch compared with all baselines; GAS becomes much slower due to the memory movement between GPU and CPU.
(2) LazyGNN (GPU+CPU) is faster than APPNP (GAS) because APPNP requires more data movement for feature propagation. This further verifies the computation and memory efficiency of LazyGNN.
(3) LazyGNN is memory efficient since only 878 MB additional storage is required to store two small tensors for feature and gradient regardless of the number of layers. In contrast, GAS requires large memory storage due to the feature storage for each layer. These observations verify that LazyGNN is efficient in memory and computation.

\subsection{Ablation Study}
\label{sec:ablation}
We provide detailed ablation studies on the impacts of hyperparameter settings in LazyGNN using ogbn-arixv dataset.

\textbf{Lazy Propagation.}
We conduct the ablation study to analyze the impact of feature propagation layers. Specifically, we use the same MLP for LazyGNN and APPNP, and we change the number of propagation layers $K$. The comparison in Table~\ref{tab:layers} demonstrates that: (1) LazyGNN have much better performance than APPNP when using the same number of propagation layers;
(2) LazyGNN archives great performance with even $1$ propagation layer ($72.5\%$), and it already arrives at the best performance ($73.0\%$) with $2$ propagation layers. These results confirm LazyGNN's advantages and capability in capturing long-distance dependency in graphs with very few feature propagation layers.

\vspace{-0.1in}
\begin{table}[ht!]
\caption{Prediction accuracy with different numbers of feature propagation layers on ogbn-arxiv.}
\label{tab:layers}
\begin{center}
\resizebox{0.6\linewidth}{!}{%
\begin{tabular}{lc}
\toprule
\textbf{Method} & \textsc{Accuracy (\%)}  \\
\midrule
APPNP (K=1) &70.6\\
APPNP (K=2) & 71.4\\
APPNP (K=3) &71.5\\
LazyGNN (K=1)   & 72.5\\
LazyGNN (K=2)   & 73.0 \\
LazyGNN (K=3)   & 73.0 \\
\bottomrule
\end{tabular}
}
\end{center}
\vskip -0.1in
\end{table}

\textbf{Sensitivity Analysis.}
We provide a detailed sensitivity analysis for the two additional hyperparameters $\beta$ and $\gamma$ in LazyGNN.
The results in Table~\ref{tab:hyperparameter-ablation} show that: (1) $\{\beta=0, \gamma=0\}$ produces the worst performance ($71.0\%$) because it fully trusts the history embedding that might be outdated due to the additional variations caused by dropout as demonstrated in Section~\ref{sec:preliminary};
(2) $\{\beta=1, \gamma=1\}$ performs slightly better ($71.7\%$) even without lazy propagation because 2 propagation layers can provide an approximate solution;
(3) $\{\beta=0.5, \gamma=0.5\}$ performs the best ($73.0\%$) because it achieves a good trade-off between historical information and current iteration. It compensates for the staleness in the history storage as designed;
(4) The performance of LazyGNN is quite stable for a large range setting of $\beta$ and $\gamma$. In fact, we fix $\beta=\gamma=0.5$ for LazyGNN in all experiments for simplicity. Therefore, it requires almost negligible effort for additional hyperparameter tuning.

\begin{table}[ht!]
\caption{Prediction accuracy of mini-batch LazyGNN for different hyperparameter settings on ogbn-arxiv.}
\label{tab:hyperparameter-ablation}
\vskip 0.1in
\begin{center}
\begin{tabular}{cc}
\toprule
\textbf{Hyperparameter settings} & \textsc{Accuracy (\%)} \\
\midrule
$\beta=0.0,~\gamma=0.0$ & 71.0\\
$\beta=1.0,~\gamma=1.0$ & 71.7\\
\midrule
$\beta=0.5,~\gamma = 0.1$  & 72.5\\
$\beta=0.5,~\gamma = 0.5$  & 73.0 \\
$\beta=0.5,~\gamma = 0.9$  &  72.8\\
\midrule
$\beta=0.1,~\gamma=0.5$  & 72.4\\
$\beta=0.5,~\gamma=0.5$  & 73.0 \\
$\beta=0.9,~\gamma=0.5$  & 72.7\\
\bottomrule
\end{tabular}
\end{center}
\end{table}

\textbf{Convergence.}
We show the convergence of LazyGNN during the training process using ogbn-arxiv dataset.
The convergence of validation accuracy in Figure~\ref{fig:convergence} demonstrates that LazyGNN has a comparable convergence speed with GCN (GAS) and GCNII (GAS), and is slightly faster than APPNP (GAS) in terms of the number of training epochs.

\begin{figure}[htp]
    \centering
    \includegraphics[width=6cm]{figure/final.png}
    \vspace{-0.1in}
    \caption{Validation performance versus training epochs.}
    \label{fig:convergence}

\end{figure}

\section{Preliminaries}
\label{sec:preliminary_section}

\textbf{Notations.}
A graph is represented by ${\mathcal{G}} = ({\mathcal{V}}, {\mathcal{E}})$ where ${\mathcal{V}} = \{v_1, \dots, v_N\}$ is the set of nodes and $\mathcal{E} = \{e_1, \dots, e_M\}$ is the set of edges. Suppose that each node is associated with a $d$-dimensional feature vector, and the original features for all nodes are denoted as ${\mathbf{X}}_{\text{fea}} \in \mathbb{R}^{N\times d}$.
The graph structure of ${\mathcal{G}}$ can be represented by an adjacency matrix ${\mathbf{A}} \in \mathbb{R}^{N\times N}$, where ${\mathbf{A}}_{ij}>0$ when there exists an edge between node $v_i$ and $v_j$, otherwise ${\mathbf{A}}_{i,j}=0$.
The symmetrically normalized graph Laplacian matrix is defined as ${\tilde{{\mathbf{L}}}}={\mathbf{I}}-{\tilde{{\mathbf{A}}}}$ with ${\tilde{{\mathbf{A}}}}={\mathbf{D}}^{-1/2}{\mathbf{A}}{\mathbf{D}}^{-1/2}$ where ${\mathbf{D}}$ is the degree matrix.
Next, we briefly introduce the graph signal denoising and fixed point iteration perspective of GNNs that provide a better understanding of the computation trajectory and long-distance dependency in graphs.
Finally, we provide a preliminary study to reveal the computation redundancy in GNNs.

\subsection{GNNs as Graph Signal Denoising}
\label{sec:gsp}

It is recently established that many popular GNNs can be uniformly understood as solving graph signal denoising problems with various diffusion properties and that the long-distance dependency can be well captured by unrolling various fixed point iterations~\cite{ma2020unified, pan2020_unified,zhu2021interpreting,chen2020graph,gu2020implicit}. For instance, the message passing in GCN~\cite{kipf2016semi}, ${\mathbf{X}}_{\text{out}} = {\tilde{{\mathbf{A}}}} {\mathbf{X}}_{\text{in}}$, can be considered as one gradient descent iteration for minimizing ${\tilde{r}}({\mathbf{X}}^\top({\mathbf{I}}-{\tilde{{\mathbf{A}}}}){\mathbf{X}})$ with the initialization ${\mathbf{X}}_0={\mathbf{X}}_{\text{in}}$.
The message passing scheme in APPNP~\cite{klicpera2018predict} follows the aggregation ${\mathbf{X}}_{l+1} = (1-\alpha) {\tilde{{\mathbf{A}}}} {\mathbf{X}}_l + \alpha {\mathbf{X}}_{\text{in}}$ that iteratively minimizes $\|{\mathbf{X}}-{\mathbf{X}}_{\text{in}}\|^2_F + ({1/\alpha}-1)~ {\tilde{r}} ({\mathbf{X}}^{\top}  ({\mathbf{I}}-{\tilde{{\mathbf{A}}}}) {\mathbf{X}})$ with the initialization ${\mathbf{X}}_0={\mathbf{X}}_{\text{in}}$ where $l$ is the index of layers.
Implicit GNN~\cite{gu2020implicit} adopts projected gradient descent to solve the fixed point problem ${\mathbf{X}}=\phi({\mathbf{W}}{\mathbf{X}}{\tilde{{\mathbf{A}}}}+{\mathbf{B}})$.
Please refer to the reference~\cite{ma2020unified, pan2020_unified,zhu2021interpreting,chen2020graph} for such understanding of many other popular GNN models. Moreover, a large number of advanced GNN models have been inspired from this perspective~\cite{chen2022optimization,liu2021graph,liu2021elastic,yang2021graph,yang2021implicit,jia2022unifying,jiang2022fmp}.

\subsection{Computation Redundancy in Training GNNs}
\label{sec:preliminary}

In the training process of GNNs, the model parameters are updated following gradient descent style algorithms such as Adam~\cite{kingma2014adam}. Therefore, the model as well as hidden features in GNNs changes smoothly, especially in the late stages when both the learning rate and gradient norm diminish. This intuition motivates us to investigate the computation redundancy in GNNs. Specifically, we measure the relative hidden features changes, i.e.,
$\|{\mathbf{X}}^{k+1}-{\mathbf{X}}^{k}\|_F / \|{\mathbf{X}}^{k}\|_F$,
over the training iterations on Cora dataset
using APPNP. We show two cases in Figure~\ref{fig:redundancy}: (1) when there is no dropout, the hidden features barely change as the training goes; (2) if we use dropout, it will incur additional variation in the hidden features due to the randomness in dropout layers. Both cases demonstrate that the activation values in hidden layers of GNNs indeed change slowly, indicating the existence of \textit{computation redundancy}: the computation in successive training iterations is highly similar. This observation not only validates the rationality of historical embedding used in existing works such as VR-GNN~\cite{chen2017stochastic} and GNNAutoScale~\cite{fey2021gnnautoscale} but also motivates the lazy propagation in this work.

\begin{figure}[htp]
    \centering
    \subfloat[\centering Without dropout]
    {{\includegraphics[width=3.5cm]{figure/pre0.png}}}
    \hspace{0.2in}
    \subfloat[\centering With dropout]
    {{\includegraphics[width=3.5cm]{figure/pre0.3.png}}}%
    \vspace{-0.1in}
    \caption{Feature changes
    $\|{\mathbf{X}}^{k+1}-{\mathbf{X}}^{k}\|_F / \|{\mathbf{X}}^{k}\|_F$ in APPNP.
    }
    \label{fig:redundancy}
    \vspace{-0.1in}
\end{figure}

\section{Related Work}

It has been generally demonstrated that it is beneficial to capture long-distance relations in graphs by stacking more feature aggregation layers or unrolling various fixed point iterations in GNNs~\cite{gasteiger2018predict, gu2020implicit, liu2020towards, chen2020simple, li2021training, ma2020unified, pan2020_unified, zhu2021interpreting, chen2020graph}. But these works suffer from scalability concerns due to the neighborhood explosion problem~\cite{hamilton2017inductive}.

A large body of existing research focuses on improving the efficiency and scalability of large-scale GNNs using various novel designs, such as sampling methods, pre-computing or post-computing methods, and distributed methods.
Sampling methods adopt mini-batch training strategies to reduce computation and memory requirements by sampling nodes and edges. They mitigate the neighbor explosion issue by either removing neighbors~\cite{hamilton2017inductive, chen2018fastgcn, Zeng2020GraphSAINT, zou2019layer} or updating with feature memory~\cite{fey2021gnnautoscale, yu2022graphfm}.
Pre-computing or post-computing methods separate the feature aggregation and prediction models into two stages, such as pre-computing the feature aggregation before training~\cite{wu2019simplifying, rossi2020sign, sun2021scalable, zhang2022graph, bojchevski2020scaling} or post-processing with label propagation after training~\cite{zhu2005semi, huang2020combining}.
Distributed methods distribute large graphs to multiple servers and parallelize GNNs training
~\cite{chiang2019cluster, chai2022distributed, shao2022distributed}.
In retrospect, these existing approaches
still suffer from various limitations, such as high costs in computation, memory, and communication as well as performance degradation due to large approximation errors or multi-stage training.

Different from existing works, in this work, we propose LazyGNN from a substantially different and novel perspective and propose to capture the long-distance dependency in graphs by shallower models instead of deeper models. This leads to a much more efficient LazyGNN for graph representation learning. Moreover, existing approaches for scalable GNNs can be used to further accelerate LazyGNN. The proposed mini-batch LazyGNN is a promising example.

LazyGNN also draws insight from existing research on graph signal processing and implicit modeling. The forward construction of LazyGNN follows the optimization perspective of GNNs~\cite{ma2020unified}, and it is can be easily generalized to other fixed point iterations with various diffusion properties.
LazyGNN is related to recent works in implicit modeling, such as Neural Ordinary Differential Equations~\cite{chen2018neural}, Implict Deep Learning~\cite{el2021implicit}, Deep Equilibrium Models~\cite{bai2019deep}, and Implicit GNNs~\citep{gu2020implicit}.
LazyGNN focuses on developing shallow models with highly scalable and efficient computation while these implicit models demand significantly more computation resources.