XX XX 8 May/June

# A brief history on Homomorphic learning: A privacy-focused approach to
machine learning

Aadesh Neupane

(2019)

###### Abstract

Cryptography and data science research grew exponential with the internet
boom. Legacy encryption techniques force users to make a trade-off between
usability, convenience, and security. Encryption makes valuable data
inaccessible, as it needs to be decrypted each time to perform any operation.
Billions of dollars could be saved, and millions of people could benefit from
cryptography methods that don’t compromise between usability, convenience, and
security. Homomorphic encryption is one such paradigm that allows running
arbitrary operations on encrypted data. It enables us to run any sophisticated
machine learning algorithm without access to the underlying raw data. Thus,
homomorphic learning provides the ability to gain insights from sensitive data
that has been neglected due to various governmental and organization privacy
rules.

In this paper, we trace back the ideas of homomorphic learning formally posed
by Ronald L. Rivest and Len Alderman as “Can we compute upon encrypted data?”
in their 1978 paper [1]. Then we gradually follow the ideas sprouting in the
brilliant minds of Shafi Goldwasser, Kristin Lauter, Dan Bonch, Tomas Sander,
Donald Beaver, and Craig Gentry to address that vital question. It took more
than 30 years of collective effort to finally find the answer “yes” to that
important question.

††journal: BYU CS611 Project

Homomorphic learning is a cryptographic “holy grail” that allows a worker to
perform arbitrary computations on client-encrypted data, without learning
anything about the data itself. In simple terms, homomorphic learning is where
a data owner wants to send data up to the cloud for processing but does not
trust a service provider with their critical data. Using a homomorphic
encryption scheme, the data owner encrypts their data and sends it to the
server. The server performs the relevant computations on the data without ever
decrypting it and sends the encrypted results to the data owner. The data
owner is the only one able to decrypt the results since they alone have the
secret key. Figure 1 shows a simple diagram that depicts the whole process
involved in homomorphic learning. The paragraph below illustrates a few
motivating examples of homomorphic learning.

Figure 1: A simple system processing the user’s sensitive information using
homomorphic learning.

Internet companies like Google, Facebook, and Amazon, along with healthcare
companies like Accumen, AccuPoint, and Cigna collect huge amounts of data from
users. Internet companies use sophisticated machine learning algorithms to
learn patterns from the rich set of data and provide innovative user-focused
services. Healthcare companies and government organizations are lagging behind
others to mine the tons of data that could benefit millions of users and save
billions of dollars due to strict privacy and data protection rules such as
CCPA, GDPR, HIPPA, and FERPA. Homomorphic learning might be one way for these
companies to mine sensitive data without violating privacy and data protection
laws.

Recently, the Dutch broadcaster VRT report [2] uncovered that the smart
speakers (Amazon Echo, Google Home) are eavesdropping to every conversation
even when not activated, and google employees are systematically listening to
these recordings. Google spokesman said, “This work is of crucial importance
to develop technologies sustaining products such as Google Assistant.”
Homomorphic learning might be key for these companies in the future to improve
AI technologies without access to the raw data.

There is an unprecedented amount of data breaches happening these days. But
not every breach comes about as the result of outside attackers. There are
other threat models to consider. Insider threats and privileged access account
for about 35% to 60% of breaches, according to industry reports. Although the
data collected by the companies is stored in the encrypted database using
standard encryption (private key cryptography), the database administrators
and developers still have access to all of the data. Tragically the raw data
is released with the help of these private keys in the event of a data breach.
Since homomorphic encryption allows learning without decrypting the data,
there is no need for private keys. Thus, the use of homomorphic encryption
could help to reduce data breaches.

Homomorphic learning holds big promises for secure data storage and
manipulation. It is far off from an efficient real-world enterprise
implementation, but there has been substantial progress in the homomorphic
learning area, such as secure multi-party computation and federation learning.
It is both captivating and illuminating to witness the progress happening in
this area. This paper tells the story of homomorphic learning: the web of
people and ideas associated with it. Our story will begin from the time when
Rivest asked the question “Can we compute upon encrypted data?” to “fully
homomorphic encryption for machine learning” [3]. Before describing the great
question, we are going on a short detour to describe the history of modern
cryptography.

## A Brief History of Cryptography

There are historical records that the ancient civilization of the Incans,
Aztecs, Greeks, and Romans practiced cryptography. Pieces of evidence suggest
that their practice of cryptography was elementary. Though rudimentary
cryptography was widely practiced until the seventeenth century, there were no
formal tools to analyze the cryptography methods.

Johann Carl Friedrich Gauss (1777 - 1855), who had exceptional influence in
many fields of mathematics and science, wrote an important statement about
prime numbers which later became the foundation of modern cryptography. At the
age of 21, in his famous book, “Disquisitions Aritmeticae” he wrote, “The
problem of distinguishing prime numbers from composite numbers and of
resolving the latter into their prime factors is known to be one of the most
important and useful in arithmetic.” Most of modern cryptography is built on
these two problems: finding if a given number is prime, and resolving
composite numbers into their prime factors.

The significant revolution in cryptography started with the World War, as the
war introduced a qualitative change in patterns of communication. Radio
communication was most popular during the war as the signals could be
transmitted to very long distances. It could be used to give orders, convey
strategies, and so on, but the enemy could easily intercept the line and
discover what their strategies were. So this pitfall of radio provided a very
strong demand for the use of cryptography. During World War II, special
computing machines were used for cryptography. The Germans in particular had
the famous enigma machine to encipher their messages. Alan Turing and others
who had familiarity with notions of computation broke these ciphers, which had
a significant impact on the war. The war was arguably shortened by several
years because of these cryptographic breakthroughs.

Modern cryptography was only limited to military and government secret
organizations, before the publication of David Kahn’s book “The Codebreakers -
The Story of Secret Writing” [4]. This book inspired general masses and lots
of modern-day cryptographers, including Rivest, to become interested in the
field. The NSA (National Security Agency), tried to suppress publication of
the book because it brought attention to the field, and had a lot of
interesting technical detail. But Kahn went ahead and published it anyway. He
has updated the book since to include more recent developments.

Alan Turing was highly influential in the development of theoretical computer
science, and one of his major contributions was to show that some class of
problems were unsolvable on any computer; but then there were other classes of
interesting problems which seem solvable in principle, but take a lot of time
to solve. Thus he developed the theory of computational complexity. The
problems in cryptography usually fall in the second class. So the hard
problems are important for cryptography. Cryptographers want the problem to be
very hard for the adversary to solve.

Ralph Merkle, Marty Hellman, and Whit Diffie revolutionized cryptography by
formalizing the idea of public-key cryptography in the paper “New Directions
on Cryptography” [5]. Public-key cryptography was a marvelous idea which is
qualitatively different notion than classical cryptography, because it
separates the public key and the private key.

The idea of public-key cryptography was on its way. Everybody would have a
public key, and they could use that public key to encrypt a message. The
public key would do the encryption, and a separate key (private) would do the
decryption. Having these two keys be different supported by the notion of
computational difficulty, made public-key cryptography secure. The core idea
of public-key cryptography was that publishing one of the keys shouldn’t
reveal the other, and it should be computationally hard to figure out the
secret key given the public key. So somebody could tell us the public key, and
we wouldn’t be able to figure out the secret key.

The invention of the worldwide web, just like Marconi’s invention of the
radio, made cryptography essential and drove the demand for
cryptography.111All the content of this section is based on the talk by Ronald
L.Rivest at the award ceremony for Marconi Prize in 2007

## RSA’s Dream

RSA (Rivest–Shamir–Adleman) is one of the most popular public-key
cryptosystems and is widely used for secure data transmission. Ronal Linn
Rivest is one of the authors of the RSA [6] paper that introduced a public-key
cryptosystem. He grew up in Niskayuna, New York, a suburb of Schenectady, New
York where he attended public school. He graduated from Niskayuna High School
in 1965. He received a B.A. in Mathematics from Yale University in 1969. The
David Kahn’s book “The Codebreakers - The Story of Secret Writing” [4] made
him interested in cryptography during his undergraduate days.

During his Ph.D., he briefly worked in the area of Artificial Intelligence,
but soon realized that his real passion was for mathematics and theoretical
computer science. He received a Ph.D. in Computer Science from Stanford
University in 1974. His Ph.D. research was mainly on the analysis of
associative retrieval algorithms [7] under supervisor Professor Robert Floyd.
After appointment as a faculty in the Department of Computer Science at MIT,
we are fortunate that he got a chance to communicate with Ralph Merkle, Marty
Hellman, and Whit Diffie about public-key cryptography. Their paper “New
Directions on Cryptography” [5] had a long-lasting impact on Rivest that
inspired him to work with Shamir and Adleman to formulate RSA in their seminal
paper “A method for obtaining digital signatures and public-key cryptosystems”
[6].

Figure 2: Computer scientist who first thought about privacy homomorphism.
From left to right: Ronal Linn Rivest, Len Adleman, and Mike Dertouzos

With the success of public-key cryptosystems, Rivest was dreaming about doing
computations with encrypted data. So just after the publication of their
seminal paper, Len Adleman and Ronal Linn had a fruitful discussion with Mike
Dertouzos, who was the Director of the MIT Laboratory for Computer Science
(LCS). During the discussion they asked him the, “Can we compute upon
encrypted data? Can we work with data that’s been encrypted piece by piece and
combine the pieces while leaving them encrypted so we can end up taking two
ciphertexts, combine them, and end up with a new ciphertext in such a way that
the underlying plain text for that new ciphertext is the appropriate operation
on the underlying plain text?”

They found out that one way of answering their question was with a process
called homomorphism, and they dreamed of a cryptosystem that’s homomorphic.
They imagined a cryptosystem with a sufficiently rich set of operations, that
supports arbitrary computations on encrypted data. But they had no idea on how
to pursue this dream. They get credit for asking this important question: but
they didn’t solve it. They formally asked this question in their paper “On
data banks and privacy homomorphisms” [1]. They defined the term “privacy
homomorphism” as a special encryption function which permits encrypted data to
be operated on without preliminary decryption of the operands, for many sets
of interesting operations.

The “privacy homomorphism” idea developed in their famous paper was borrowed
from mathematics. Homomorphic is an adjective that describes something of the
same or similar form. Specifically, in algebra, a homomorphism is a structure-
preserving map between two algebraic structures of the same type (such as two
groups, two rings, or two vector spaces).

## Spring Break

The question Rivest et al. [1] asked in 1978 about computation on encrypted
data was way ahead of its time. It was too abstruse to be answered as a whole
with the current state of research in cryptography. There was a long silence
in the research community. It felt like the researchers were on a long spring
vacation. Every four/five years, sporadically, a few researchers would pursue
somewhat related topics to “privacy homomorphism”. It took more than thirty
years for the community to catch up with the question.

During this “spring break”, Shafi Goldwasser was one of the prominent
researchers who formalized vital ideas like probabilistic encryption and zero-
knowledge interactive proofs. Her paper on probabilistic encryption was
responsible for turning encryption from an art to a science, and allowing
better security in the internet age [8]. Furthermore, she worked on a paper on
zero-knowledge interactive proofs [9], which makes it possible to prove a
statement or concept without revealing any new information. These ideas were
not directly applicable to answer the question posed by Rivest el al. [1], but
it was a powerful tool for cryptographers to peek into the formalism of
cryptography. Shafi Goldwasser was honored with the Turing Award, the highest
honor in computer science, for her work in revolutionizing the field of
cryptography.

The story about how Goldwasser got interested in computer science is both
inspiring and fascinating for all the women in STEM. She was born in 1959 in
New York City. Her parents were Israeli, and her joint American/Israeli
citizenship presaged the two countries that would play such an important role
in her research. Her family returned to Israel, where Shafi attended grade
school in Tel Aviv. In high school, she was especially interested in physics,
mathematics, and literature. After her schooling, she returned to the U.S. and
became an undergraduate in the mathematics department at Carnegie Mellon
University (CMU). One computer science course that she especially remembers,
taught by Jon Bentley, was an algorithms and discrete math course that she
loved. Soon, however, she became interested in programming (which she had
never done before) and computer science. She also worked on the CM* project at
CMU, a 50-processor multiprocessor system. Shafi next had a summer internship
at the RAND Corporation in Los Angeles that cemented her love for computer
science.

Her interest in cryptography came a little late. After completing her
undergraduate in 1979, she went on a vacation to California and decided to
enroll in graduate school in computer science at the University of California,
Berkeley, without knowing what she wanted to study. Her interaction with some
of the computer scientists (Silvio Micali, Eric Bach, Manuel Blum, and others)
during her graduate years in Berkeley initiated some interest in theoretical
computer science, especially cryptography.

The first problem Shafi began working on with Micali was how to hide partial
information in “mental poker” [8]. Their solution was an essentially perfect
way of encrypting a single bit (against a computationally limited adversary),
and they invented a “hybrid” technique to show that independently encrypting
individual bits causes the whole message to be secure. These proof were
precursors to the proofs required for the theory of homomorphic encryption.

After finishing up her Ph.D. from Berkeley, Shafi joined M.I.T. It was an
exciting time when she came to M.I.T, as Ron Rivest, Micali, and Mike Sipser
were still there. With Goldreich and Micali [10], Shafi investigated whether
the notion of a pseudorandom number generator could be generalized so that one
could generate exponentially many bits (or equivalently, a function)
pseudorandomly. This definition was in itself important, and is why we
understand today what it means for a block cipher such as AES to be secure.
They also showed how to provably transform a pseudorandom number generator
into a pseudorandom function generator. These ideas had applications to the
(then) new field of Learning Theory, providing examples of things that cannot
be learned. These ideas were equally applicable to homomorphic encryption to
show that the ciphertext didn’t reveal any information about the raw data.

After working for a few years on “Probabilistic encryption” and “pseudorandom
functions”, her interest shifted towards Number theory [11]. It took decades
for her to return to homomorphic learning. Just after Shafi switched her
interests around 1995, Josh Daniel Cohen Benaloh came to the scene. In his
Ph.D. dissertation “Verifiable secret-ballot elections” [12], he developed
theoretical tools and proofs for ensuring that the privacy of the voters
remains intact though all communications are made public. He described a
practical scheme for conducting secret-ballot elections in which the outcome
of an election can be verified by all participants and even by non-
participating observers. The theoretical tools developed for the secret-ballot
election were equally applicable to allow a prover to convince verifiers that
either statement A or statement B is true without revealing substantial
information. His method of secret sharing homomorphisms enabled the
computation of shared (secret) data and presented with a method of
distribution of shares of secret such that each shareholder can verify the
validity of all shares.

Again, there were a few years of silence after the publication of Josh
Benaloh’s Ph.D. dissertation before the publication of “Non-interactive crypto
computing” [13] paper by Tomos Sander.

Sander’s paper focused on this classical problem:

### Alice has an input x and Bob has function c. Alice should learn the value
of C(x) but nothing else substantial about C. Bob should learn nothing else
substantial about Alice’s input x.

This problem can be viewed as computing over encrypted data where the parties
do not engage in additional communication. Tomas Sander et al. [13] introduced
a new protocol for secure evaluation of functions in polynomial time. The
protocol involved one party sending encrypted input to a second party (crypto
computer), which evaluates the input securely, and provides the output to the
input party without learning the underlying function within a single round.
This new protocol allowed the computation of logical AND operation using the
encrypted data. Moreover, this scheme was homomorphic over a semigroup
(instead of a group), thus expanding the range of algebraic structures that
can be encrypted homomorphically. This was a huge accomplishment. Their
protocol allowed some limited number of operations on the encrypted data.

Just one year after the publication of “Non-interactive crypto computing”
[13], Donald Beaver extended the protocol developed by Tomas Sander’s team to
include non-deterministic log-space functions [14]. Moreover, Beaver
introduced novel parallelization techniques to reduce the sub-computations on
the functions to constant time complexity. This made the computation on the
encrypted data faster, with reduced latency.

It took almost five years for another promising result. Dan Boneh, a Professor
of the Computer Science Department at Stanford University published a landmark
paper titled “Evaluating 2-DNF formulas on ciphertexts”. In this paper, they
presented a homomorphic public-key encryption scheme, that allowed the public
evaluation of a 2-DNF formula ($\Phi$) on boolean variables
($x_{1},x_{2},\dots,x_{n}$), given the encryption (cyphertexts) of those
boolean variables.

In other words, their formulation allowed the evaluation of quadratic
multivariate polynomials on ciphertext, provided the resulting value was
within a small set. This formulation had the following major benefits: 1) it
reduced the total number of communications required, 2) it facilitated the
construction of a viable election system without the need of zero-knowledge
proofs, and 3) it provided a protocol for universally verifiable computation.
This was a keystone towards a plausible implementation of homomorphic
learning. Dan Boneh then recruited a graduate student named Craig Gentry to
extend their homomorphic scheme.

Figure 3: Fully homomorphic encryption pioneers. From left to right: Shafi
Goldwasser, Dan Boneh, and Craig Gentry

## The Promised Prince

Craig Gentry appeared as the promised prince to fulfill a prophecy of making
the dream of a fully homomorphic encryption (FHE) a reality. He worked with
the Gödel Prize-winning Stanford Professor Dan Boneh and Turing award winner
Shafi Goldwasser to come up with the first viable FHE scheme. In 2009, he
published a plausible candidate construction of a fully homomorphic encryption
[15] scheme, answering the problem posed in 1978 by Rivest and thought by many
to be impossible to resolve.

FHE makes it possible to perform arbitrary computations (mathematical
operations like sum or product as well as more complicated operations) on
encrypted data and without needing a secret key, and while keeping the
individual pieces of data hidden and secure [15]. For example, a web
application could prepare an individual’s tax return using her encrypted
financial information, without seeing any data in the raw form. Although FHE
is not yet efficient enough for widespread implementation, Gentry’s
breakthrough has initiated a surge of new research globally in computer
science as it has enormous implications for making the cloud computing
environment more secure and compatible with data privacy for individuals.

The path followed by Gentry to develop an FHE scheme started with viewing RSA
encryption as multiplicatively homomorphic: i.e, given an RSA public key and
ciphertexts, one can efficiently compute a temporary ciphertext that encrypts
the product of the original plain-texts. So, RSA is homomorphic concerning
multiplicative operators. The encryption scheme that is homomorphic with any
operator would enable arbitrary computation on encrypted data without the
decryption key.

The fully homomorphic encryption scheme [15] developed by Gentry is tied to a
somewhat homomorphic scheme. His doctorate work shows that if the somewhat
homomorphic encryption scheme is “bootstrappable”, then a fully homomorphic
encryption scheme can be built from it. Suppose there is an encryption scheme
with a “noise parameter” (n) attached to each ciphertext. The noise parameter
can be viewed as the random variable used in the encryption scheme, which
generates different ciphertexts for the same raw text. The decryption works as
long as the noise is less than some threshold $N>>n$. Furthermore, imagine if
we have algorithms $Add$ and $Mult$ that can take ciphertexts $E(a)$ and
$E(b)$ and compute $E(a+b)$ and $E(a*b)$, but at the cost of adding or
multiplying the noise parameters. This immediately gives a “somewhat
homomorphic” encryption scheme that can handle functions of depth roughly
$(log\,logN-log\,log\,n)$.

Now suppose that we have an algorithm Recrypt that takes a ciphertext $E(a)$
with noise $N^{\prime}<N$ and outputs a fresh ciphertext $E(a)$ that also
encrypts $a$, but which has noise parameter smaller than $\sqrt{N}$. This
Recrypt algorithm is enough to construct a fully homomorphic scheme out of the
somewhat homomorphic one. In his paper, the somewhat homomorphic encryption
scheme is modified so that its decryption function has multiplicative depth at
most $(log\,logN-log\,log\,n-1)$ i.e., less depth than what the scheme can
handle. The somewhat homomorphic encryption scheme that has this self-
referential property of being able to handle functions that are deeper than
its own decryption function is known as “bootstrappable”, and thus the
somewhat homomorphic scheme which is “bootstrappable” is fully homomorphic.

To get a feel for the actual working of the homomorphic scheme, let’s go into
details about a somewhat homomorphic encryption scheme on a toy problem. Let’s
look at a secret key encryption scheme which uses integers. The key is an odd
integer $p>2N$. An encryption of a bit $b$ is simply a random multiple of $p$,
plus a random integer $B$ with the same parity as $b$, i.e $B$ is even if
$b=0$ and is odd if $b=1$. More concretely, the ciphertext is

$c=b+2x+kp,$

where $x$ is a random integer in range ($-n/2,n/2$), and $k$ is an integer
chosen from some range. Then we can decrypt the ciphertext by setting

$b\leftarrow(c\,mod\,p)\,mod\,2,$

where $(c\,mod\,p)$ is the “noise parameter” in this scheme, which will be in
the range $[-n,n]$. Decryption would work correctly as long as
$(b+2x)\in[-N,N]$.

Let’s take a concrete example and show that the simple homomorphic encryption
scheme works. Suppose we want to encrypt the user’s current balance on their
account and find the total amount for all the users using the homomorphic
encryption scheme for integers. Let the user’s balance be represented by
$b_{1},b_{2},\dots,b_{n}$. Specifically, let

$b_{1}=3,b_{2}=4,b_{3}=5$

and its corresponding binary representations are

$b_{1}=00011,b_{2}=00100,b_{3}=00101$

respectively. Let the private key be $p=5$. Then $[-N,N]\subset(-p/2,p/2)$.
Let $k$ be 2, which is inside the range $(-p/2,p/2)$. Let $x$ be a random
integer inside $[-1,1]$.

Figure 4 describes how the cyphertext is generated for the integers. The
integers are converted to binary and then encrypted using the cyphertext
generating equation. The resulting ciphertexts can be operated on using any
operator. For our example, we add the cyphertexts. The resulting cyphertext
from the addition can be decrypted. Figure 5 shows the process of decryption
of the augmented cyphertext. The result of decrypting the augmented cyphertext
is the same as the addition of the raw text. Thus, the simple homomorphic
encryption scheme preserved the addition operation when applied to the
cyphertext.

Figure 4: The encryption process for a simple homomorphic encryption scheme.

Figure 5: The decryption process for a simple homomorphic encryption scheme
after the cyphertext obtained from encryption has been added.

This toy example shows that the simple encryption is homomorphic when $N>>n$
and valid for $+,*$ operators. For these encryption schemes to be useful in
the real world, we need fully homomorphic encryption that can operate on any
arbitrary operators in a reasonable amount of time. Gentry’s FHE supports
arbitrary operators, at least in theory.

Gentry used the lattice-based approach in his doctorate dissertation to
describe the first plausible construction for a fully homomorphic encryption
scheme. His original cryptosystem reported the timing of about 30 minutes per
basic bit operation, which is way too slow for real-world applications. Over
the years, with extensive design and implementation work, the results have
improved by many orders of magnitude.

In 2010, Marten van Dijk, Craig Gentry, Shai Halevi, and Vinod Viakuntanathan
[16] presented a second fully homomorphic encryption scheme based on the
Gentry’s construction that doesn’t require ideal lattices. They showed that
the ideal lattices could be replaced by a very simple somewhat homomorphic
scheme that uses integers. This scheme was conceptually simpler than Gentry’s
ideal lattice scheme, but had similar properties with regards to homomorphic
operations and efficiency.

Gentry went on to tackle another longstanding open problem, moving beyond
cryptographic bilinear maps (which have been used widely in encryption,
cryptographic digital signatures, and key agreement) to multilinear maps. He
and his collaborators were the first to publish a plausible candidate
multilinear map. In 2013, he and his colleagues leveraged those findings to
present the first example of cryptographic software obfuscation, a discovery
that is paving the way for the encryption of entire programs while keeping
their functionality intact, thereby making it infeasible to reverse engineer
the program [17]. This is one solid practical example of homomorphic
encryption. He is inspiring not only a flood of practical applications but
also opening doors for new intellectual pursuits across the whole of
cryptography.

## The Opensource Factory

The publication of Gentry’s doctorate dissertation in 2009 made the fully
homomorphic encryption (FHE) a buzz word. Still, FHE was not computationally
efficient to be applied to real-world applications. Over the last few years,
with extensive research and opensource tools like Seal [18], Palisade [19],
HElib [20] and others started to change the landscape of the homomorphic
encryption. The integration of these tools into popular Machine Learning
libraries such as TensorFlow and PyTorch enabled amateurs and researches alike
to build applications focused on privacy. These opensource tools are
responsible for the homomorphic encryption to reach the masses. Still, only a
few specialized companies provide homomorphic learning as a service to
healthcare and government organizations, and it might take a few more years
for homomorphic learning to be ubiquitous among the cloud service providers.

Secure multi-party computation, differential privacy, and federated learning
are the popular form of privacy-focused learning. In 2018/2019, there were
more than ten privacy-focused learning library released as open-source
software. Secure multi-party computation is all about computing a function
jointly by different parties over their inputs while keeping those inputs
private. Shafi, with Yael Tauman Kalai and Guy Rothblum, introduced [21] one
practical formulation of secure multi-party computation, and showed how to
efficiently delegate the computation of small-depth functions to the untrusted
“cloud”.

Differential privacy addresses the paradox of learning nothing about an
individual while learning useful information about a population. In general,
differential privacy is not an algorithm but a definition that outlines ways
to perform privacy-preserving data analysis [22]. In a simplified differential
privacy model of computation, we assume the existence of a trusted and
trustworthy curator who holds the data of individuals in a database D,
typically comprised of some number n of rows, and each row contains the data
of a single individual. The differential privacy goal employs a mechanism to
simultaneously protect every individual row while permitting statistical
analysis of the database as a whole. This mechanism is an algorithm that takes
as input a database, the set of all possible database rows, random bits, and a
set of queries, and produces an output string. The output string can be
decoded to produce relatively accurate answers to the queries without
revealing the information of the individuals. Tang et al. [23] combined
homomorphic encryption with differential privacy to create a novel privacy-
preserving algorithm Heda to train an ML classifier on the UCI ML datasets
[24].

Federated learning is a distributed architecture for learning a predictive
model using decentralized mobile devices or servers, keeping the local data
samples private, and only publishing the learned updates to the central server
using homomorphic encryption. Federated learning allows for personalization,
scaled deployment of models, lower latency, and less power consumption, all
while ensuring data privacy and security. One popular success example of
federated learning is the “Gboard on Android” (the Google Keyboard). When the
Gboard shows a suggested query, it is using federated learning on the history
on-device and updating it based on whether you clicked the suggestion or not
[25].

Currently, there are a few frameworks like PySyft [26] and HE Transformer [27]
that allow the users to perform homomorphic learning with Neural Network
models on encrypted data. These frameworks decouple private data from model
training using Federated Learning, Differential Privacy, and Multi-Party
computation (MPC) within the main deep learning frameworks like PyTorch and
TensorFlow.

One of the influential people who is taking the responsibility of developing
opensource tools for integrating fully homomorphic encryption (FHE) and ML
libraries is Andrew Trask. He is a researcher pursuing a Doctorate at Oxford
University, where he focuses on Deep Learning with an emphasis on human
language. Dowlin et al. [28] were the first to train a neural network model on
encrypted MNIST data with high throughput and accuracy using the SEAL [18]
library for homomorphic encryption. Hesamifard et al. [29] trained a deep
neural network over encrypted MNIST and CIFAR data with high efficiency and
accuracy. Badawi [30] et al. trained the first homomorphic convolution neural
network (HCNN) on encrypted data with Graphics Processing Unit (GPU)s. All
previous approaches before HCNN ran only on the CPU. HCNN is truly remarkable,
as it achieved the high-security level and great classification accuracy for
MNIST and CIFAR.

For the machine learning enthusiasts and practitioners, homomorphic learning
provides an exciting opportunity to democratize AI, and a privacy-focused way
to solve large-scale ML problems. Homomorphic learning is a nascent field with
lots of hope and promises, eagerly waiting for next Craig Gentry to
revolutionize the field.

## CONCLUSION

This article described a brief history on the development of homomorphic
encryption schemes, highlighting the collective contributions of a cohort of
brilliant minds. It took more than thirty years of communal effort to find a
theoretical answer to the question “Can we compute upon encrypted data?” posed
by Rivest et al [1]. It took another ten years to develop efficient
homomorphic encryption frameworks that could be coupled with other machine
learning libraries. Multi-party computation and federated learning aided with
homomorphic encryption have already started making a powerful impact on
privacy-focused machine learning communities. It might still take a few years
before homomorphic learning is ubiquitous.

## ACKNOWLEDGMENT

I would like to thank Dr. Sean Warnick for giving us this opportunity to work
on this project for CS611 course. Also, I would like to thank Connor Anderson,
Michael DeBuse, and Aatish Neupane for their constructive feedback and
suggestions to make this paper better.

## References

  * [1] R. L. Rivest, L. Adleman, M. L. Dertouzos, et al., “On data banks and privacy homomorphisms,” Foundations of secure computation, vol. 4, no. 11, pp. 169–180, 1978.
  * [2] T. Verheyden, D. Baert, L. V. Hee, and R. V. D. Heuvel, “Google employees are eavesdropping,” 2019-06-10.
  * [3] M. Minelli, Fully Homomorphic Encryption for Machine Learning.  PhD thesis, 2018.
  * [4] D. Kahn, The Codebreakers: The comprehensive history of secret communication from ancient times to the internet.  Simon and Schuster, 1996.
  * [5] W. Diffie and M. Hellman, “New directions in cryptography,” IEEE transactions on Information Theory, vol. 22, no. 6, pp. 644–654, 1976.
  * [6] R. L. Rivest, A. Shamir, and L. Adleman, “A method for obtaining digital signatures and public-key cryptosystems,” Communications of the ACM, vol. 21, no. 2, pp. 120–126, 1978.
  * [7] R. L. Rivest, “Analysis of associative retrieval algorithms.,” 1974.
  * [8] S. Goldwasser and S. Micali, “Probabilistic encryption,” Journal of computer and system sciences, vol. 28, no. 2, pp. 270–299, 1984.
  * [9] S. Goldwasser, S. Micali, and C. Rackoff, “The knowledge complexity of interactive proof systems,” SIAM Journal on computing, vol. 18, no. 1, pp. 186–208, 1989.
  * [10] O. Goldreich, S. Goldwasser, and S. Micali, “How to construct random functions,” Journal of the ACM (JACM), vol. 33, no. 4, pp. 792–807, 1986\.
  * [11] S. Goldwasser and J. Kilian, “Almost all primes can be quickly certified,” 1986\.
  * [12] J. D. C. Benaloh, “Verifiable secret-ballot elections.,” 1989.
  * [13] T. Sander, A. Young, and M. Yung, “Non-interactive cryptocomputing for nc/sup 1,” in 40th Annual Symposium on Foundations of Computer Science (Cat. No. 99CB37039), pp. 554–566, IEEE, 1999.
  * [14] D. Beaver, “Minimal-latency secure function evaluation,” in International Conference on the Theory and Applications of Cryptographic Techniques, pp. 335–350, Springer, 2000.
  * [15] C. Gentry and D. Boneh, A fully homomorphic encryption scheme, vol. 20.  Stanford University Stanford, 2009.
  * [16] M. Van Dijk, C. Gentry, S. Halevi, and V. Vaikuntanathan, “Fully homomorphic encryption over the integers,” in Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 24–43, Springer, 2010.
  * [17] S. Garg, C. Gentry, S. Halevi, and M. Zhandry, “Fully secure functional encryption without obfuscation.,” IACR Cryptology ePrint Archive, vol. 2014, p. 666, 2014.
  * [18] K. Laine and R. Player, “Simple encrypted arithmetic library-seal (v2. 0),” Technical report, Technical report, 2016.
  * [19] R. A. Hallman, K. Laine, W. Dai, N. Gama, A. J. Malozemoff, Y. Polyakov, and S. Carpov, “Building applications with homomorphic encryption,” in Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, pp. 2160–2162, ACM, 2018.
  * [20] S. Halevi and V. Shoup, “Algorithms in helib,” in Annual Cryptology Conference, pp. 554–571, Springer, 2014.
  * [21] S. Goldwasser, Y. T. Kalai, and G. N. Rothblum, “Delegating computation: interactive proofs for muggles,” Journal of the ACM (JACM), vol. 62, no. 4, p. 27, 2015.
  * [22] C. Dwork, A. Roth, et al., “The algorithmic foundations of differential privacy,” Foundations and Trends® in Theoretical Computer Science, vol. 9, no. 3–4, pp. 211–407, 2014.
  * [23] X. Tang, L. Zhu, M. Shen, and X. Du, “When homomorphic cryptosystem meets differential privacy: Training machine learning classifier with privacy protection,” arXiv preprint arXiv:1812.02292, 2018.
  * [24] D. Dua and C. Graff, “UCI machine learning repository,” 2017.
  * [25] B. McMahan and D. Ramage, “Federated learning: Collaborative machine learning without centralized training data.”
  * [26] T. Ryffel, A. Trask, M. Dahl, B. Wagner, J. Mancuso, D. Rueckert, and J. Passerat-Palmbach, “A generic framework for privacy preserving deep learning,” arXiv preprint arXiv:1811.04017, 2018.
  * [27] F. Boemer, A. Costache, R. Cammarota, and C. Wierzynski, “ngraph-he2: A high-throughput framework for neural network inference on encrypted data,” in Proceedings of the 7th ACM Workshop on Encrypted Computing & Applied Homomorphic Cryptography, pp. 45–56, ACM, 2019.
  * [28] R. Gilad-Bachrach, N. Dowlin, K. Laine, K. Lauter, M. Naehrig, and J. Wernsing, “Cryptonets: Applying neural networks to encrypted data with high throughput and accuracy,” in International Conference on Machine Learning, pp. 201–210, 2016.
  * [29] E. Hesamifard, H. Takabi, and M. Ghasemi, “Cryptodl: Deep neural networks over encrypted data,” arXiv preprint arXiv:1711.05189, 2017.
  * [30] A. A. Badawi, J. Chao, J. Lin, C. F. Mun, S. J. Jie, B. H. M. Tan, X. Nan, K. M. M. Aung, and V. R. Chandrasekhar, “The alexnet moment for homomorphic encryption: Hcnn, the first homomorphic cnn on encrypted data with gpus,” arXiv preprint arXiv:1811.00778, 2018.


1.5GNN | $95.90_{\pm 3.01}$ | $94.10_{\pm 4.57}$ | $73.08_{\pm 2.59}$ | $\bm{\underline{61.44}}_{\pm 0.30}$ | $\bm{\underline{61.77}}_{\pm 0.35}$ | $\bm{66.01}_{\pm 1.88}$ | $\bm{90.57}_{\pm 0.71}$ | $\bm{\underline{97.38}}_{\pm 0.43}$ | $\bm{\underline{97.76}}_{\pm 0.86}$
2.0GNN | $\bm{98.37}_{\pm 0.78}$ | $\bm{\underline{96.32}}_{\pm 1.50}$ | $\bm{84.93}_{\pm 0.39}$ | $61.13_{\pm 0.51}$ | $\bm{\underline{61.79}}_{\pm 0.34}$ | $63.55_{\pm 1.73}$ | $88.55_{\pm 1.05}$ | $\bm{97.56}_{\pm 0.16}$ | $\bm{\underline{97.94}}_{\pm 0.39}$
2.5GNN | $97.74_{\pm 0.99}$ | $\bm{96.78}_{\pm 0.44}$ | $83.21_{\pm 2.12}$ | $\bm{\underline{61.30}}_{\pm 0.41}$ | $\bm{\underline{61.74}}_{\pm 0.34}$ | $62.88_{\pm 2.31}$ | $79.64_{\pm 2.15}$ | $95.71_{\pm 0.34}$ | $97.25_{\pm 0.58}$
Table 5: Results on cSBM with dense splitting setting. Average accuracy (%) for 20 runs. Best results are outlined in bold and the results within $95\%$ confidence interval of the best results are outlined in underlined bold. Method | $\phi=-1$ | $\phi=-0.75$ | $\phi=-0.5$ | $\phi=-0.25$ | $\phi=0$ | $\phi=0.25$ | $\phi=0.5$ | $\phi=0.75$ | $\phi=1$
---|---|---|---|---|---|---|---|---|---
MLP | $50.37_{\pm 0.60}$ | $65.22_{\pm 0.92}$ | $75.82_{\pm 0.65}$ | $81.18_{\pm 0.55}$ | $79.86_{\pm 0.69}$ | $79.97_{\pm 0.57}$ | $75.03_{\pm 0.89}$ | $67.53_{\pm 0.68}$ | $51.96_{\pm 0.69}$
GCN | $83.14_{\pm 0.49}$ | $82.59_{\pm 0.48}$ | $77.17_{\pm 0.59}$ | $58.58_{\pm 0.41}$ | $61.18_{\pm 1.06}$ | $82.59_{\pm 0.50}$ | $92.20_{\pm 0.27}$ | $97.21_{\pm 0.27}$ | $97.10_{\pm 0.12}$
SGC | $78.35_{\pm 0.36}$ | $82.13_{\pm 0.09}$ | $77.76_{\pm 0.12}$ | $59.14_{\pm 0.57}$ | $60.31_{\pm 0.63}$ | $81.96_{\pm 0.34}$ | $91.68_{\pm 0.13}$ | $96.56_{\pm 0.09}$ | $96.87_{\pm 0.05}$
GAT | $92.99_{\pm 0.86}$ | $90.89_{\pm 0.60}$ | $87.02_{\pm 0.80}$ | $68.40_{\pm 1.60}$ | $61.98_{\pm 1.16}$ | $82.92_{\pm 0.51}$ | $92.05_{\pm 0.73}$ | $97.28_{\pm 0.25}$ | $98.04_{\pm 0.46}$
JKNet | $68.95_{\pm 9.05}$ | $79.21_{\pm 7.67}$ | $67.97_{\pm 5.22}$ | $56.12_{\pm 4.10}$ | $58.33_{\pm 1.70}$ | $80.15_{\pm 0.80}$ | $91.21_{\pm 0.50}$ | $\bm{\underline{97.62}}_{\pm 0.25}$ | $\bm{\underline{98.32}}_{\pm 0.21}$
APPNP | $49.86_{\pm 0.39}$ | $50.47_{\pm 0.89}$ | $65.28_{\pm 0.68}$ | $73.98_{\pm 0.64}$ | $79.37_{\pm 0.66}$ | $86.60_{\pm 0.73}$ | $\bm{92.45}_{\pm 0.39}$ | $\bm{97.67}_{\pm 0.14}$ | $97.65_{\pm 0.49}$
GPRGNN | $\bm{\underline{99.06}}_{\pm 0.25}$ | $\bm{97.14}_{\pm 0.31}$ | $\bm{94.59}_{\pm 0.32}$ | $\bm{83.84}_{\pm 0.69}$ | $78.81_{\pm 1.30}$ | $85.85_{\pm 1.01}$ | $92.08_{\pm 0.81}$ | $\bm{\underline{97.49}}_{\pm 0.22}$ | $\bm{98.46}_{\pm 0.15}$
1.0GNN | $98.19_{\pm 0.28}$ | $94.38_{\pm 0.44}$ | $86.40_{\pm 1.00}$ | $80.57_{\pm 0.43}$ | $\bm{\underline{80.21}}_{\pm 0.42}$ | $\bm{87.32}_{\pm 0.47}$ | $\bm{\underline{92.42}}_{\pm 0.62}$ | $\bm{\underline{97.52}}_{\pm 0.33}$ | $\bm{\underline{98.37}}_{\pm 0.26}$
1.5GNN | $\bm{\underline{98.88}}_{\pm 0.16}$ | $95.62_{\pm 0.21}$ | $86.87_{\pm 1.22}$ | $80.70_{\pm 0.71}$ | $\bm{80.28}_{\pm 0.31}$ | $86.29_{\pm 0.43}$ | $\bm{\underline{92.40}}_{\pm 0.24}$ | $\bm{\underline{97.56}}_{\pm 0.25}$ | $\bm{\underline{98.24}}_{\pm 0.32}$
2.0GNN | $\bm{99.21}_{\pm 0.09}$ | $\bm{\underline{96.91}}_{\pm 0.16}$ | $92.96_{\pm 0.31}$ | $80.83_{\pm 0.61}$ | $\bm{\underline{80.04}}_{\pm 0.49}$ | $84.96_{\pm 0.60}$ | $91.18_{\pm 0.27}$ | $\bm{\underline{97.41}}_{\pm 0.14}$ | $\bm{\underline{98.45}}_{\pm 0.14}$
2.5GNN | $\bm{99.21}_{\pm 0.14}$ | $\bm{\underline{96.94}}_{\pm 0.16}$ | $93.28_{\pm 0.37}$ | $80.93_{\pm 0.44}$ | $\bm{80.28}_{\pm 0.38}$ | $83.83_{\pm 0.70}$ | $86.10_{\pm 0.39}$ | $96.28_{\pm 0.43}$ | $97.76_{\pm 0.18}$

Table 5 shows that pGNNs obtain the best performance on weak homophilic graphs
($\phi=0,0.25$) while competitive performance against GPRGNN on strong
heterophilic graphs ($\phi=-0.75,-1$) and competitive performance with state-
of-the-art GNNs on strong homophilic graphs ($\phi=0.75,1$). We also observe
that GPRGNN is slightly better than pGNNs on weak heterophilic graphs
($\phi=-0.25,-0.5$), which suggests that GPRGNN could work very well using
strong supervised information ($60\%$ training rate and $20\%$ validation
rate). However, as shown in Table 4, pGNNs work better than GPRGNN under weak
supervised information ($2.5\%$ training rate and $2.5\%$) on all heterophilic
graphs. The result is reasonable, as discussed in Remark 3 in Sec. 3.2, GPRGNN
can adaptively learn the generalized PageRank (GPR) weights and it works
similarly to 2.0GNN on both homophilic and heterophilic graphs. However, it
needs more supervised information in order to learn optimal GPR weights. On
the contrary, pGNNs need less supervised information to obtain similar results
because $\Theta^{(2)}$ acts like a hyperplane for classification. Therefore,
pGNNs can work better under weak supervised information.

###  F.4 Experimental Results on Graphs with Noisy Edges

Here we present more experimental results on graph with noisy edges. Table 6
reports the results on homophilic graphs (Computers, Photo, CS, Physics) and
Table 7 reports the results on heterophilic graphs (Wisconsin Texas). We
observe from Tables 6 and 7 that pGNNs dominate all baselines. Moreover, pGNNs
even slightly better than MLP when the graph topologies are completely random,
i.e. the noisy edge rate $r=1$. We also observe that the performance of GCN,
SGC, JKNet on homophilic graphs dramatically degrades as the noisy edge rate
$r$ increases while they do not change a lot for the cases on heterophilic
graphs. It is reasonable since the original graph topological information is
very helpful for label prediction on these homophilic graphs. Adding noisy
edges and remove the same number of original edges could significantly degrade
the performance of ordinary GNNs. On the other hand, since we find that the
original graph topological information in Wisconsin and Texas is not helpful
for label prediction. Therefore, adding noisy edges and removing original
edges on these heterophilic graphs would not affect too much their
performance.

Table 6: Results on homophilic graphs with random edges. Average accuracy (%) for 20 runs. Best results are outlined in bold and the results within $95\%$ confidence interval of the best results are outlined in underlined bold. OOM denotes out of memory. Method | Computers | Photo
---|---|---
$r=0.25$ | $r=0.5$ | $r=1$ | $r=0.25$ | $r=0.5$ | $r=1$
MLP | $66.11_{\pm 2.70}$ | $66.11_{\pm 2.70}$ | $66.11_{\pm 2.70}$ | $76.44_{\pm 2.83}$ | $76.44_{\pm 2.83}$ | $76.44_{\pm 2.83}$
GCN | $74.70_{\pm 1.72}$ | $62.16_{\pm 2.76}$ | $8.95_{\pm 6.90}$ | $81.43_{\pm 0.76}$ | $75.52_{\pm 3.59}$ | $12.78_{\pm 5.20}$
SGC | $75.15_{\pm 1.08}$ | $66.96_{\pm 1.05}$ | $15.79_{\pm 7.47}$ | $82.22_{\pm 0.36}$ | $77.80_{\pm 0.49}$ | $13.57_{\pm 3.63}$
GAT | $76.44_{\pm 1.81}$ | $68.34_{\pm 2.61}$ | $11.58_{\pm 7.70}$ | $82.70_{\pm 1.31}$ | $77.20_{\pm 2.10}$ | $13.74_{\pm 5.14}$
JKNet | $56.74_{\pm 6.48}$ | $46.11_{\pm 8.43}$ | $12.50_{\pm 6.56}$ | $73.46_{\pm 6.74}$ | $64.18_{\pm 4.06}$ | $15.66_{\pm 6.10}$
APPNP | $78.23_{\pm 1.84}$ | $74.57_{\pm 2.25}$ | $66.67_{\pm 2.68}$ | $87.63_{\pm 1.05}$ | $86.22_{\pm 1.73}$ | $75.55_{\pm 1.72}$
GPRGNN | $77.30_{\pm 2.24}$ | $77.11_{\pm 1.80}$ | $66.85_{\pm 1.65}$ | $85.95_{\pm 1.05}$ | $85.64_{\pm 1.22}$ | $\bm{77.46}_{\pm 1.44}$
1.0GNN | $75.14_{\pm 14.95}$ | $63.26_{\pm 20.67}$ | $41.60_{\pm 16.17}$ | $\bm{\underline{87.97}}_{\pm 0.70}$ | $84.47_{\pm 3.05}$ | $41.17_{\pm 18.15}$
1.5GNN | $\bm{81.79}_{\pm 1.33}$ | $\bm{78.12}_{\pm 2.08}$ | $66.04_{\pm 2.73}$ | $\bm{88.09}_{\pm 1.18}$ | $86.20_{\pm 1.61}$ | $68.78_{\pm 8.97}$
2.0GNN | $80.34_{\pm 1.07}$ | $76.90_{\pm 1.93}$ | $\bm{67.17}_{\pm 1.63}$ | $87.65_{\pm 0.94}$ | $\bm{87.06}_{\pm 1.50}$ | $\bm{\underline{77.07}}_{\pm 1.83}$
2.5GNN | $79.14_{\pm 1.51}$ | $75.49_{\pm 1.25}$ | $64.95_{\pm 2.27}$ | $87.38_{\pm 0.85}$ | $86.11_{\pm 1.10}$ | $76.65_{\pm 1.46}$
Method | CS | Physics
$r=0.25$ | $r=0.5$ | $r=1$ | $r=0.25$ | $r=0.5$ | $r=1$
MLP | $86.24_{\pm 1.43}$ | $86.24_{\pm 1.43}$ | $\bm{\underline{86.24}}_{\pm 1.43}$ | $92.58_{\pm 0.83}$ | $92.58_{\pm 0.83}$ | $92.58_{\pm 0.83}$
GCN | $81.05_{\pm 0.59}$ | $68.37_{\pm 0.85}$ | $7.72_{\pm 2.39}$ | $89.02_{\pm 0.16}$ | $80.45_{\pm 0.34}$ | $19.78_{\pm 3.94}$
SGC | $83.41_{\pm 0.01}$ | $71.98_{\pm 0.12}$ | $8.00_{\pm 1.43}$ | OOM | OOM | OOM
GAT | $80.11_{\pm 0.67}$ | $68.66_{\pm 1.42}$ | $8.49_{\pm 2.39}$ | $88.72_{\pm 0.61}$ | $82.05_{\pm 1.86}$ | $22.39_{\pm 5.04}$
JKNet | $81.35_{\pm 0.74}$ | $71.30_{\pm 2.14}$ | $11.43_{\pm 1.18}$ | $87.98_{\pm 0.97}$ | $81.90_{\pm 2.27}$ | $26.38_{\pm 5.80}$
APPNP | $88.63_{\pm 0.68}$ | $87.56_{\pm 0.51}$ | $76.90_{\pm 0.96}$ | $93.46_{\pm 0.12}$ | $92.81_{\pm 0.24}$ | $90.49_{\pm 0.33}$
GPRGNN | $85.77_{\pm 0.81}$ | $83.89_{\pm 1.54}$ | $72.79_{\pm 2.24}$ | $92.18_{\pm 0.29}$ | $90.96_{\pm 0.48}$ | $91.77_{\pm 0.41}$
1.0GNN | $90.27_{\pm 0.86}$ | $89.56_{\pm 0.81}$ | $\bm{86.60}_{\pm 1.22}$ | $\bm{94.35}_{\pm 0.39}$ | $\bm{94.23}_{\pm 0.27}$ | $\bm{92.97}_{\pm 0.36}$
1.5GNN | $\bm{91.27}_{\pm 0.40}$ | $\bm{90.50}_{\pm 0.71}$ | $84.40_{\pm 1.84}$ | $\bm{\underline{94.34}}_{\pm 0.21}$ | $93.77_{\pm 0.29}$ | $92.51_{\pm 0.35}$
2.0GNN | $90.97_{\pm 0.49}$ | $89.98_{\pm 0.50}$ | $80.84_{\pm 1.48}$ | $\bm{\underline{94.14}}_{\pm 0.18}$ | $93.30_{\pm 0.31}$ | $91.72_{\pm 0.44}$
2.5GNN | $89.90_{\pm 0.45}$ | $89.00_{\pm 0.59}$ | $76.82_{\pm 2.11}$ | $93.61_{\pm 0.30}$ | $92.77_{\pm 0.26}$ | $91.16_{\pm 0.47}$
Table 7: Results on heterophilic graphs with random edges. Average accuracy (%) for 20 runs. Best results are outlined in bold and the results within $95\%$ confidence interval of the best results are outlined in underlined bold. Method | Wisconsin | Texas
---|---|---
$r=0.25$ | $r=0.5$ | $r=1$ | $r=0.25$ | $r=0.5$ | $r=1$
MLP | $93.56_{\pm 3.14}$ | $93.56_{\pm 3.14}$ | $93.56_{\pm 3.14}$ | $79.50_{\pm 10.62}$ | $79.50_{\pm 10.62}$ | $79.50_{\pm 10.62}$
GCN | $62.31_{\pm 8.12}$ | $59.44_{\pm 5.76}$ | $64.21_{\pm 4.49}$ | $41.56_{\pm 8.89}$ | $44.69_{\pm 23.05}$ | $40.31_{\pm 18.26}$
SGC | $64.68_{\pm 7.34}$ | $62.36_{\pm 2.64}$ | $51.81_{\pm 2.63}$ | $42.50_{\pm 5.49}$ | $40.94_{\pm 18.34}$ | $23.81_{\pm 14.54}$
GAT | $65.37_{\pm 9.04}$ | $60.05_{\pm 9.12}$ | $60.05_{\pm 7.46}$ | $39.50_{\pm 9.29}$ | $34.88_{\pm 21.59}$ | $29.38_{\pm 11.53}$
JKNet | $64.91_{\pm 13.07}$ | $51.39_{\pm 10.36}$ | $57.41_{\pm 2.57}$ | $47.75_{\pm 7.30}$ | $46.62_{\pm 23.23}$ | $40.69_{\pm 13.57}$
APPNP | $70.19_{\pm 9.04}$ | $60.32_{\pm 4.70}$ | $72.64_{\pm 4.73}$ | $66.69_{\pm 13.46}$ | $63.25_{\pm 9.87}$ | $69.81_{\pm 7.76}$
GPRGNN | $90.97_{\pm 3.83}$ | $87.50_{\pm 3.86}$ | $87.55_{\pm 2.97}$ | $74.25_{\pm 7.25}$ | $76.75_{\pm 14.05}$ | $80.69_{\pm 5.87}$
1.0GNN | $\bm{94.91}_{\pm 2.73}$ | $\bm{95.97}_{\pm 2.00}$ | $\bm{95.97}_{\pm 2.27}$ | $81.50_{\pm 9.24}$ | $\bm{82.12}_{\pm 11.09}$ | $\bm{81.81}_{\pm 5.67}$
1.5GNN | $\bm{\underline{94.58}}_{\pm 1.25}$ | $95.19_{\pm 2.18}$ | $94.95_{\pm 2.79}$ | $82.50_{\pm 6.39}$ | $78.12_{\pm 5.30}$ | $78.50_{\pm 7.98}$
2.0GNN | $90.46_{\pm 2.79}$ | $90.97_{\pm 4.22}$ | $91.44_{\pm 2.27}$ | $\bm{86.06}_{\pm 5.17}$ | $69.38_{\pm 11.47}$ | $63.50_{\pm 8.90}$
2.5GNN | $82.45_{\pm 3.93}$ | $88.24_{\pm 2.79}$ | $84.40_{\pm 1.98}$ | $80.00_{\pm 10.83}$ | $56.62_{\pm 10.01}$ | $52.31_{\pm 10.58}$

###  F.5 Experimental Results of Intergrating pGNNs with GCN and JKNet

Here we further conduct experiments to study whether pGNNs can be intergrated
into existing GNN architectures and improve their performance on heterophilic
graphs. We use two popular GNN architectures: GCN (Kipf & Welling, 2017) and
JKNet (Xu et al., 2018).

To incorporate pGNNs with GCN, we use the pGNN layers as the first layer of
the combined models, termed as pGNN + GCN, and GCN layer as the second layer.
Specifically, we use the aggregation weights
$\bm{\alpha}{\mathbf{D}}^{-1/2}{\mathbf{M}}{\mathbf{D}}^{-1/2}$ learned by the
pGNN in the first layer as the input edge weights of GCN layer in the second
layer. To combine pGNN with JKNet, we use the pGNN layer as the GNN layers in
the JKNet framework, termed as pGNN + JKNet. Tables 8 and 9 report the
experimental results on homophilic and heterophilic benchmark datasets,
respectively.

Table 8: The results of pGNNs + GCN and pGNNs + JKNet on homophilic benchmark dataset. Averaged accuracy (%) for 20 runs. Best results are outlined in bold and the results within $95\%$ confidence interval of the best results are outlined in underlined bold. Method | Cora | CiteSeer | PubMed | Computers | Photo | CS | Physics
---|---|---|---|---|---|---|---
GCN | $\bm{76.23}_{\pm 0.79}$ | $\bm{62.43}_{\pm 0.81}$ | $\bm{83.72}_{\pm 0.27}$ | $\bm{84.17}_{\pm 0.59}$ | $\bm{90.46}_{\pm 0.48}$ | $\bm{90.33}_{\pm 0.36}$ | $94.46_{\pm 0.08}$
1.0GNN + GCN | $72.37_{\pm 1.35}$ | $60.56_{\pm 1.59}$ | $82.14_{\pm 0.31}$ | $83.75_{\pm 1.05}$ | $\bm{\underline{90.24}}_{\pm 1.12}$ | $89.60_{\pm 0.46}$ | $\bm{\underline{94.59}}_{\pm 0.33}$
1.5GNN + GCN | $72.72_{\pm 1.39}$ | $60.23_{\pm 1.80}$ | $82.21_{\pm 0.22}$ | $\bm{\underline{83.89}}_{\pm 0.74}$ | $90.00_{\pm 0.68}$ | $89.48_{\pm 0.45}$ | $\bm{94.70}_{\pm 0.18}$
2.0GNN + GCN | $72.39_{\pm 1.55}$ | $60.19_{\pm 1.60}$ | $82.24_{\pm 0.23}$ | $\bm{\underline{83.92}}_{\pm 1.09}$ | $\bm{\underline{90.17}}_{\pm 0.83}$ | $89.60_{\pm 0.71}$ | $94.51_{\pm 0.39}$
2.5GNN + GCN | $72.85_{\pm 1.19}$ | $59.68_{\pm 1.85}$ | $82.23_{\pm 0.34}$ | $83.69_{\pm 0.92}$ | $90.02_{\pm 1.09}$ | $89.53_{\pm 0.68}$ | $\bm{\underline{94.58}}_{\pm 0.31}$
JKNet | $\bm{77.19}_{\pm 0.98}$ | $\bm{63.32}_{\pm 0.95}$ | $\bm{\underline{82.54}}_{\pm 0.43}$ | $79.94_{\pm 2.47}$ | $88.29_{\pm 1.64}$ | $89.69_{\pm 0.66}$ | $93.92_{\pm 0.32}$
1.0GNN+JKNet | $75.67_{\pm 1.54}$ | $60.38_{\pm 1.65}$ | $81.68_{\pm 0.44}$ | $\bm{83.19}_{\pm 1.36}$ | $89.71_{\pm 1.05}$ | $90.26_{\pm 0.72}$ | $94.27_{\pm 0.69}$
1.5GNN+JKNet | $76.40_{\pm 1.59}$ | $60.67_{\pm 1.93}$ | $\bm{\underline{82.42}}_{\pm 0.35}$ | $82.78_{\pm 2.09}$ | $\bm{90.25}_{\pm 1.03}$ | $\bm{90.76}_{\pm 0.75}$ | $\bm{94.82}_{\pm 0.34}$
2.0GNN+JKNet | $76.75_{\pm 1.26}$ | $61.05_{\pm 1.48}$ | $\bm{\underline{82.50}}_{\pm 0.53}$ | $82.36_{\pm 2.39}$ | $89.31_{\pm 1.39}$ | $90.33_{\pm 0.63}$ | $\bm{\underline{94.70}}_{\pm 0.33}$
2.5GNN+JKNet | $76.48_{\pm 1.28}$ | $60.97_{\pm 0.97}$ | $82.56_{\pm 1.04}$ | $81.45_{\pm 1.55}$ | $89.21_{\pm 1.10}$ | $89.66_{\pm 0.68}$ | $94.29_{\pm 0.59}$
Table 9: The results of pGNNs + GCN and pGNNs + JKNet on heterophilic benchmark dataset. Averaged accuracy (%) for 20 runs. Best results are outlined in bold and the results within $95\%$ confidence interval of the best results are outlined in underlined bold. Method | Chameleon | Squirrel | Actor | Wisconsin | Texas | Cornell
---|---|---|---|---|---|---
GCN | $34.54_{\pm 2.78}$ | $25.28_{\pm 1.55}$ | $31.28_{\pm 2.04}$ | $61.93_{\pm 3.00}$ | $56.54_{\pm 17.02}$ | $51.36_{\pm 4.59}$
1.0GNN + GCN | $48.52_{\pm 1.89}$ | $\bm{\underline{34.78}}_{\pm 1.11}$ | $32.37_{\pm 3.12}$ | $\bm{68.52}_{\pm 3.75}$ | $\bm{\underline{67.94}}_{\pm 12.60}$ | $\bm{\underline{67.81}}_{\pm 7.61}$
1.5GNN + GCN | $48.85_{\pm 2.13}$ | $34.61_{\pm 1.11}$ | $32.37_{\pm 2.48}$ | $66.25_{\pm 3.95}$ | $65.62_{\pm 11.99}$ | $64.88_{\pm 9.19}$
2.0GNN + GCN | $48.71_{\pm 2.24}$ | $\bm{35.06}_{\pm 1.18}$ | $\bm{32.72}_{\pm 2.02}$ | $66.34_{\pm 4.51}$ | $65.94_{\pm 7.63}$ | $\bm{68.62}_{\pm 6.55}$
2.5GNN + GCN | $\bm{49.53}_{\pm 2.19}$ | $34.40_{\pm 1.60}$ | $32.40_{\pm 3.23}$ | $67.18_{\pm 3.50}$ | $\bm{68.31}_{\pm 9.18}$ | $66.06_{\pm 9.56}$
JKNet | $33.28_{\pm 3.59}$ | $25.82_{\pm 1.58}$ | $29.77_{\pm 2.61}$ | $61.08_{\pm 3.71}$ | $59.65_{\pm 12.62}$ | $55.34_{\pm 4.43}$
1.0GNN + JKNet | $\bm{\underline{49.00}}_{\pm 2.09}$ | $35.56_{\pm 1.34}$ | $\bm{40.74}_{\pm 0.98}$ | $\bm{95.23}_{\pm 2.43}$ | $80.25_{\pm 6.87}$ | $\bm{78.38}_{\pm 8.14}$
1.5GNN + JKNet | $48.77_{\pm 2.22}$ | $\bm{35.98}_{\pm 0.93}$ | $40.22_{\pm 1.27}$ | $94.86_{\pm 2.00}$ | $80.38_{\pm 9.79}$ | $72.25_{\pm 9.83}$
2.0GNN + JKNet | $48.88_{\pm 1.63}$ | $35.77_{\pm 1.73}$ | $40.16_{\pm 1.31}$ | $88.84_{\pm 2.78}$ | $\bm{86.12}_{\pm 5.59}$ | $74.75_{\pm 7.81}$
2.5GNN + JKNet | $\bm{49.04}_{\pm 1.95}$ | $35.78_{\pm 1.87}$ | $40.00_{\pm 1.12}$ | $85.42_{\pm 3.86}$ | $79.06_{\pm 7.60}$ | $76.81_{\pm 7.66}$

We observe from Table 8 that intergrating pGNNs with GCN and JKNet does not
improve their performance on homophilic graphs. The performance of GCN
slightly degrade after incorporating pGNNs. The performance of JKNet also
slightly degrade on Cora, CiteSeer, and PubMed but is improved on Computers,
Photo, CS, Physics. It is reasonable since GCN and JKNet can predict well on
these homophilic benchmark datasets based on their original graph topology.

However, for heterophilic benchmark datasets, Table 9 shows that there are
significant improvements over GCN, and JKNet after intergrating with pGNNs.
Moreover, pGNNs + JKNet obtain advanced performance on all heterophilic
benchmark datasets and even better than pGNNs on Squirrel. The results of
Table 9 demonstrate that intergrating pGNNs with GCN and JKNet can
sigificantly improve their performance on heterophilic graphs.

###  F.6 Experimental Results of pGNNs on PPI Dataset for Inductive Learning

Additionally, we conduct comparison experiments of pGNNs against GAT on PPI
dataset (Zitnik & Leskovec, 2017) using the inductive learning settings as in
Velickovic et al. (2018) (20 graphs for training, 2 graphs for validation, 2
graphs for testing). We use three layers of GAT architecture with 256 hidden
units, use 1 attention head for GAT (1 head) and 4 attention heads for GAT (4
heads). We use three pGNN layers and a MLP layer as the first layer for pGNNs,
set $\mu=0.01$, $K=1$, and use 256 hidden units for pGNN-256 and 512 hidden
units for pGNN-512. The experimental results are reported in Table 10.

Table 10: Results on PPI datasets. Averaged micro-F1 scores for 10 runs. Best results are outlined in bold. Method | PPI
---|---
GAT (1 head) | $0.917\pm 0.041$
GAT (4 heads) | $0.972\pm 0.002$
1.0GNN-256 | $0.961\pm 0.003$
1.5GNN-256 | $0.967\pm 0.008$
2.0GNN-256 | $0.968\pm 0.006$
2.5GNN-256 | $0.973\pm 0.002$
1.0GNN-512 | $0.978\pm 0.005$
1.5GNN-512 | $0.977\pm 0.008$
2.0GNN-512 | $\bm{0.981}\pm 0.006$
2.5GNN-512 | $0.978\pm 0.005$

From Sec. F.6 we observe that the results of 2.5GNN on PPI slightly better
than GAT with 4 attention heads and other pGNNs are very close to it.
Moreover, all results of pGNNs significantly outperform GAT with one attention
head. The results of pGNNs on PPI is impressive. pGNNs have much less
parameters than GAT with 4 attention heads while obtain very completitive
performance on PPI. When we use more hidden units, 512 hidden units, pGNNs-512
significantly outperform GAT, while pGNNs-512 still have less parameters. It
illustrates the superior potential of applying pGNNs to inducting learning on
graphs.

###  F.7 Experimental Results of pGNNs on OGBN arXiv Dataset

Table 11: Results on OGBN arXiv dataset. Average accuracy (%) for 10 runs. Best results are outlined in bold. Method | OGBN arXiv
---|---
MLP | $55.50\pm 0.23$
GCN | $71.74\pm 0.29$
JKNet (GCN-based) | $72.19\pm 0.21$
DeepGCN | $71.92\pm 0.16$
GCN + residual (6 layers) | $72.86\pm 0.16$
GCN + residual (8 layers) + C&S | $72.97\pm 0.22$
GCN + residual (8 layers) + C&S v2 | $73.13\pm 0.17$
1GNN | $72.40\pm 0.19$
2GNN | $72.45\pm 0.20$
3GNN | $72.58\pm 0.23$
1GNN + residual (6 layers) + C&S | $72.96\pm 0.22$
2GNN + residual (6 layers) + C&S | $73.13\pm 0.20$
3GNN + residual (6 layers) + C&S | $\bm{73.23}\pm 0.16$

Here we present the experimental of pGNNs on OGBN arXiv dataset (Hu et al.,
2020). We use the official data split setting of OGBN arXiv. We use three
layers pGNN architecture and 256 hidden units with $\mu=0.5$, $K=2$. We also
combine pGNNs with correct and smooth model (C&S) (Huang et al., 2021) and
introduce residual units. The results of MLP, GCN, JKNet, DeepGCN (Li et al.,
2019), GCN with residual units, C&S model are extracted from the leaderboard
for OGBN arXiv. dataset555https://ogb.stanford.edu/docs/leader_nodeprop/#ogbn-
arxiv. Table 11 summaries the results of pGNNs against the baselines.

We observe from Table 11 that pGNNs outperform MLP, GCN, JKNet, and DeepGCN.
The performance of pGNNs can be further improved by combining it with C&S
model and residual units and 3GNN + residual (6 layers) + C&S obtains the best
performance against the baselines.

###  F.8 Running Time of pGNNs

Tables 12 and 13 report the averaged running time of pGNNs and baselines on
homophilic and heterophilic benchmark datasets, respectively.

Table 12: Efficiency on homophilic benchmark datasests. Averaged running time per epoch (ms) / averaged total running time (s). OOM denotes out of memory. Method | Cora | CiteSeer | PubMed | Computers | Photo | CS | Physics
---|---|---|---|---|---|---|---
MLP |  $7.7$ ms / $5.27$s |  $8.1$ ms / $5.37$s |  $7.8$ ms / $5.52$s |  $8.8$ ms / $5.45$s |  $8.4$ ms / $5.34$s |  $10.5$ ms / $8.18$s |  $14.6$ ms / $12.78$s
GCN |  $82.2$ ms / $6.1$s |  $84.2$ ms / $6.1$s |  $85$ ms / $6.13$s |  $85.2$ ms / $7.07$s |  $83.6$ ms / $6.08$s |  $85$ ms / $9.68$s |  $90$ ms / $13.8$s
SGC |  $89.5$ ms / $4.96$s |  $74.7$ ms / $4.86$s |  $80.6$ ms / $5.28$s |  $109$ ms / $5.21$s |  $85.9$ ms / $4.96$s |  $213.6$ ms / $8.01$s | OOM
GAT |  $534.8$ ms / $13.06$s |  $313.6$ ms / $13.36$s |  $314.6$ ms / $13.97$s |  $441.3$ ms / $24.62$s |  $309.8$ ms / $15.96$s |  $454$ ms / $21.87$s |  $436.9$ ms / $40.9$s
JKNet |  $95.4$ ms / $20.07$s |  $101.1$ ms / $19.58$s |  $105.4$ ms / $20.8$s |  $106.1$ ms / $29.72$s |  $97.9$ ms / $21.18$s |  $102.7$ ms / $24.94$s |  $119.2$ ms / $40.83$s
APPNP |  $86.7$ ms / $11.6$s |  $86.3$ ms / $11.98$s |  $85.5$ ms / $11.97$s |  $92.1$ ms / $15.75$s |  $86$ ms / $12.19$s |  $90.5$ ms / $17.36$s |  $99.6$ ms / $25.89$s
GPRGNN |  $86.5$ ms / $12.42$s |  $195.8$ ms / $12.6$s |  $88.6$ ms / $12.59$s |  $93.3$ ms / $15.98$s |  $86.7$ ms / $12.65$s |  $92$ ms / $17.8$s |  $217.1$ ms / $26.33$s
1.0GNN |  $96$ ms / $20.12$s |  $98.1$ ms / $19.81$s |  $100.2$ ms / $21.74$s |  $151.4$ ms / $64.08$s |  $121.3$ ms / $34.07$s |  $109.7$ ms / $25.03$s |  $122.9$ ms / $49.59$s
1.5GNN |  $98.2$ ms / $20.19$s |  $97$ ms / $20.26$s |  $100.2$ ms / $22.6$s |  $140.3$ ms / $64.08$s |  $120$ ms / $34.22$s |  $112.3$ ms / $25.11$s |  $127.9$ ms / $49.54$s
2.0GNN |  $98.1$ ms / $20.11$s |  $96.3$ ms / $19.97$s |  $99.3$ ms / $22.17$s |  $141$ ms / $64.04$s |  $129.3$ ms / $34.14$s |  $104.7$ ms / $24.93$s |  $124.6$ ms / $49.35$s
2.5GNN |  $96.6$ ms / $20.12$s |  $92.9$ ms / $20.16$s |  $103$ ms / $22.17$s |  $141.6$ ms / $64.01$s |  $128.1$ ms / $34.22$s |  $110.8$ ms / $25.07$s |  $124$ ms / $49.39$s
Table 13: Efficiency on heterophilic benchmark datasests. Averaged running time per epoch (ms) / averaged total running time (s). Method | Chameleon | Squirrel | Actor | Wisconsin | Texas | Cornell
---|---|---|---|---|---|---
MLP |  $7.7$ ms / $5.29$s |  $8$ ms / $5.44$s |  $8.6$ ms / $5.4$s |  $7.7$ ms / $5.16$s |  $7.9$ ms / $5.22$s |  $7.6$ ms / $5.19$s
GCN |  $83.4$ ms / $6.1$s |  $83.2$ ms / $6.2$s |  $90.7$ ms / $6.07$s |  $83.5$ ms / $5.94$s |  $80.7$ ms / $5.96$s |  $87.1$ ms / $5.92$s
SGC |  $78.1$ ms / $4.93$s |  $110.9$ ms / $5.21$s |  $77.1$ ms / $4.71$s |  $73.2$ ms / $4.52$s |  $74.2$ ms / $4.79$s |  $71.3$ ms / $4.8$s
GAT |  $374.9$ ms / $13.49$s |  $324.2$ ms / $17.15$s |  $420$ ms / $13.82$s |  $317.5$ ms / $12.68$s |  $357.9$ ms / $12.38$s |  $383.3$ ms / $12.45$s
JKNet |  $102.4$ ms / $21.15$s |  $101$ ms / $22.84$s |  $97.2$ ms / $21.24$s |  $98.5$ ms / $21.07$s |  $103.6$ ms / $20.92$s |  $102.2$ ms / $20.79$s
APPNP |  $87.1$ ms / $12.12$s |  $98.8$ ms / $12.41$s |  $87.2$ ms / $11.81$s |  $84.2$ ms / $11.83$s |  $86$ ms / $11.9$s |  $83.1$ ms / $11.94$s
GPRGNN |  $93$ ms / $12.98$s |  $86.1$ ms / $13.01$s |  $94.2$ ms / $13.01$s |  $84.3$ ms / $12.66$s |  $92$ ms / $12.64$s |  $89.1$ ms / $12.6$s
1.0GNN |  $107.3$ ms / $22.43$s |  $116.3$ ms / $30.92$s |  $117.8$ ms / $23.6$s |  $94.5$ ms / $18.47$s |  $92$ ms / $18.83$s |  $92.7$ ms / $18.97$s
1.5GNN |  $97.2$ ms / $22.54$s |  $115$ ms / $31.04$s |  $119.2$ ms / $23.47$s |  $93.3$ ms / $18.64$s |  $90.8$ ms / $19.09$s |  $94.9$ ms / $18.88$s
2.0GNN |  $98.7$ ms / $22.37$s |  $114.8$ ms / $31.14$s |  $100.8$ ms / $23.73$s |  $92.2$ ms / $19.09$s |  $92.5$ ms / $18.72$s |  $98$ ms / $18.64$s
2.5GNN |  $97.9$ ms / $22.38$s |  $115.9$ ms / $31.09$s |  $97.3$ ms / $23.77$s |  $92.8$ ms / $19.03$s |  $91$ ms / $18.84$s |  $90.7$ ms / $18.83$s

###  F.9 Experimental Results on Benchmark Datasets for 64 Hidden Units

Table 14: Results on heterophilic benchmark datasets for 64 hidden units. Averaged accuracy (%) for 20 runs. Best results outlined in bold and the results within $95\%$ confidence interval of the best results are outlined in underlined bold. Method | Chameleon | Squirrel | Actor | Wisconsin | Texas | Cornell
---|---|---|---|---|---|---
MLP | $46.55_{\pm 0.90}$ | $\bm{33.83}_{\pm 0.59}$ | $38.40_{\pm 0.76}$ | $93.91_{\pm 2.47}$ | $\bm{\underline{87.51}}_{\pm 8.53}$ | $\bm{\underline{86.75}}_{\pm 8.22}$
GCN | $34.74_{\pm 2.62}$ | $25.68_{\pm 1.17}$ | $30.86_{\pm 1.51}$ | $65.93_{\pm 5.47}$ | $58.56_{\pm 13.28}$ | $46.81_{\pm 4.28}$
SGC | $34.57_{\pm 4.71}$ | $24.39_{\pm 1.54}$ | $35.50_{\pm 2.09}$ | $62.87_{\pm 8.92}$ | $50.62_{\pm 5.60}$ | $29.44_{\pm 14.83}$
GAT | $43.33_{\pm 1.53}$ | $30.07_{\pm 0.99}$ | $33.44_{\pm 2.45}$ | $66.57_{\pm 4.69}$ | $50.69_{\pm 12.89}$ | $42.62_{\pm 13.37}$
JKNet | $32.69_{\pm 4.47}$ | $27.18_{\pm 0.76}$ | $25.72_{\pm 2.75}$ | $66.57_{\pm 10.53}$ | $43.88_{\pm 17.10}$ | $47.69_{\pm 3.25}$
APPNP | $35.09_{\pm 3.18}$ | $28.15_{\pm 0.93}$ | $32.28_{\pm 1.75}$ | $66.30_{\pm 1.60}$ | $69.00_{\pm 4.53}$ | $54.88_{\pm 3.85}$
GPRGNN | $34.65_{\pm 2.86}$ | $28.56_{\pm 1.35}$ | $34.58_{\pm 1.45}$ | $93.70_{\pm 3.12}$ | $86.50_{\pm 6.04}$ | $84.75_{\pm 8.38}$
1.0GNN | $\bm{\underline{49.51}}_{\pm 1.32}$ | $32.67_{\pm 1.00}$ | $\bm{40.70}_{\pm 0.88}$ | $\bm{95.23}_{\pm 1.60}$ | $84.12_{\pm 7.39}$ | $82.56_{\pm 6.97}$
1.5GNN | $\bm{49.52}_{\pm 1.15}$ | $33.14_{\pm 1.10}$ | $39.82_{\pm 1.54}$ | $94.03_{\pm 2.26}$ | $86.94_{\pm 6.99}$ | $\bm{86.89}_{\pm 6.63}$
2.0GNN | $49.19_{\pm 0.81}$ | $\bm{\underline{33.78}}_{\pm 0.87}$ | $39.75_{\pm 1.26}$ | $94.49_{\pm 1.81}$ | $\bm{87.62}_{\pm 6.64}$ | $85.56_{\pm 7.25}$
2.5GNN | $48.93_{\pm 0.74}$ | $33.31_{\pm 1.27}$ | $39.47_{\pm 1.20}$ | $92.13_{\pm 2.16}$ | $\bm{\underline{87.25}}_{\pm 5.57}$ | $80.56_{\pm 5.28}$

Table 15: Results on homophilic benchmark datasets for 64 hidden units. Averaged accuracy (%) for 20 runs. Best results are outlined in bold and the results within $95\%$ confidence interval of the best results are outlined in underlined bold. OOM denotes out of memory. Method | Cora | CiteSeer | PubMed | Computers | Photo | CS | Physics
---|---|---|---|---|---|---|---
MLP | $49.05_{\pm 0.82}$ | $50.67_{\pm 1.25}$ | $80.32_{\pm 0.40}$ | $70.58_{\pm 0.82}$ | $79.44_{\pm 0.79}$ | $89.48_{\pm 0.50}$ | $92.84_{\pm 0.62}$
GCN | $77.65_{\pm 0.42}$ | $64.72_{\pm 0.52}$ | $84.13_{\pm 0.12}$ | $\bm{\underline{84.56}}_{\pm 0.79}$ | $90.16_{\pm 0.88}$ | $91.14_{\pm 0.10}$ | $94.75_{\pm 0.04}$
SGC | $70.32_{\pm 1.87}$ | $\bm{65.77}_{\pm 0.99}$ | $76.27_{\pm 0.94}$ | $83.24_{\pm 0.81}$ | $89.43_{\pm 1.03}$ | $91.11_{\pm 0.10}$ | OOM
GAT | $76.97_{\pm 1.18}$ | $61.28_{\pm 1.62}$ | $83.57_{\pm 0.23}$ | $83.84_{\pm 1.93}$ | $\bm{\underline{90.54}}_{\pm 0.56}$ | $89.68_{\pm 0.42}$ | $93.91_{\pm 0.20}$
JKNet | $78.77_{\pm 0.79}$ | $64.62_{\pm 0.80}$ | $82.82_{\pm 0.16}$ | $82.22_{\pm 1.32}$ | $88.43_{\pm 0.53}$ | $90.48_{\pm 0.13}$ | $93.75_{\pm 0.32}$
APPNP | $\bm{79.95}_{\pm 0.72}$ | $\bm{\underline{65.56}}_{\pm 0.64}$ | $84.00_{\pm 0.22}$ | $83.83_{\pm 0.78}$ | $\bm{\underline{90.50}}_{\pm 0.59}$ | $91.90_{\pm 0.12}$ | $\bm{\underline{94.84}}_{\pm 0.08}$
GPRGNN | $78.17_{\pm 1.31}$ | $61.26_{\pm 2.14}$ | $84.54_{\pm 0.24}$ | $83.77_{\pm 1.06}$ | $89.86_{\pm 0.63}$ | $91.34_{\pm 0.25}$ | $94.63_{\pm 0.26}$
1.0GNN | $77.11_{\pm 0.39}$ | $63.17_{\pm 0.89}$ | $83.14_{\pm 0.46}$ | $82.64_{\pm 0.98}$ | $89.60_{\pm 0.69}$ | $92.53_{\pm 0.22}$ | $\bm{\underline{94.86}}_{\pm 0.24}$
1.5GNN | $78.69_{\pm 0.43}$ | $63.14_{\pm 0.93}$ | $83.97_{\pm 0.04}$ | $\bm{84.64}_{\pm 1.42}$ | $\bm{90.67}_{\pm 0.67}$ | $\bm{92.93}_{\pm 0.14}$ | $\bm{\underline{94.93}}_{\pm 0.12}$
2.0GNN | $79.06_{\pm 0.41}$ | $63.92_{\pm 1.14}$ | $84.24_{\pm 0.27}$ | $\bm{\underline{84.57}}_{\pm 0.96}$ | $90.17_{\pm 0.88}$ | $\bm{\underline{92.74}}_{\pm 0.26}$ | $\bm{95.05}_{\pm 0.09}$
2.5GNN | $79.15_{\pm 0.39}$ | $63.16_{\pm 1.25}$ | $\bm{84.88}_{\pm 0.09}$ | $83.84_{\pm 0.71}$ | $89.05_{\pm 0.85}$ | $92.31_{\pm 0.19}$ | $94.92_{\pm 0.10}$

###  F.10 Training Curves for $p=1$

Figure 7: The curves of training loss and testing accuracy for $p=1$.

###  F.11 Visualization Results of Node Embeddings

(a) 1.0GNN.

(b) 1.5GNN.

(c) 2.0GNN.

(d) 2.5GNN.

(e) GCN.

Figure 8: Visualization of node embeddings for Cora dataset using t-SNE (van
der Maaten & Hinton, 2008)

(a) 1.0GNN.

(b) 1.5GNN.

(c) 2.0GNN.

(d) 2.5GNN.

(e) GCN.

Figure 9: Visualization of node embeddings for Computers dataset using t-SNE.

(a) 1.0GNN.

(b) 1.5GNN.

(c) 2.0GNN.

(d) 2.5GNN.

(e) GCN.

Figure 10: Visualization of node embeddings for Chameleon dataset using t-SNE.

(a) 1.0GNN.

(b) 1.5GNN.

(c) 2.0GNN.

(d) 2.5GNN.

(e) GCN.

Figure 11: Visualization of node embeddings for Wisconsin Dataset using t-SNE.