# Four Principles of Explainable AI as Applied to Biometrics and Facial
Forensic Algorithms

P. Jonathon Phillips Mark Przybocki

National Institute of Standards and Technology
100 Bureau Dr, Gaithersburg, MD 20899, USA
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Traditionally, researchers in automatic face recognition and biometric
technologies have focused on developing accurate algorithms. With this
technology being integrated into operational systems, engineers and scientists
are being asked, do these systems meet societal norms? The origin of this line
of inquiry is ‘trust’ of artificial intelligence (AI) systems. In this paper,
we concentrate on adapting explainable AI to face recognition and biometrics,
and we present four principles of explainable AI to face recognition and
biometrics. The principles are illustrated by _four_ case studies, which show
the challenges and issues in developing algorithms that can produce
explanations.

##  1 Introduction

In operational settings, face recognition and biometric systems answer
questions about a person’s identity. Typical questions include “Are the faces
in two images the same person?” and “Retrieve the top 10 candidates from a
search.” Based on the answer, a decision is made, and it influences a
resulting action by either a person or a machine. An example is unlocking a
biometric-enabled smartphone. The phone accepts that the biometric belongs to
an approved user and unlocks the phone. When the phone does not accept the
biometric verification attempt, the user has the option to enter a passcode.
The process for accessing the phone is simple and straightforward.

For high-stakes scenarios, identity decisions require a justification that
supports the AI finding. When facial forensic examiners testify in court, they
explain how they came to their conclusions. As face recognition systems
increase in accuracy, forensic analysis will include decisions by machines,
and in testimony, forensic examiners will need to explain how the algorithm
contributed to the conclusion.

As biometrics continue to assist humans in making high-stakes decisions,
society will view these systems in how they meet societal norms. For example,
one area of concern is the impact of bias in face recognition [10, 8, 1, 7].

Failure for a system to articulate the rationale for a negative answer will
affect the level of trust users will grant a system. It will sow suspicion
that the system is inherently biased or unfair. It will slow acceptance by
society and the adoption of the technology may ultimately fail. Humans often
accept or reject innovations and new technology based on their gut feeling.

Explainable AI is one of several properties that characterize ”trust” in AI
systems. These properties include fairness, bias, transparency, and
accountability among others. The definitions of these properties vary by
author. In most cases, these terms are not defined in isolation, but as a part
or set of principles or pillars. The focus of the principles is not
algorithmic methods, such as deep convolutions neural networks, but societal
norm of AI systems. While we acknowledge that a trade-off can exist between an
AI system’s accuracy and its explainability, this article focuses on
properties that AI systems should exhibit as functioning systems in society.
These principles may affect the methods in which algorithm operate so that
they meet explainable goals. These principles may form the foundation of
policy considerations, safety, acceptance by society, ethics, and other
aspects of AI technology.

There are many valid principles and concepts related to explainable AI. Some
of which are necessary to provide balance by domain, or provide special
consideration by certain AI interest groups (researcher, user, policy maker,
etc.).

Our approach is to focus on the core concepts of explainable AI. We treat
explainability as a distinct concept in AI, while at the same time
acknowledging that other AI concepts are necessary to enhance the
characterization of a functioning system in society. The result of adopting
these principles will assist in guiding research direction and helping to
define best practices for developers. Principles of explainable AI will form
one of the bases of addressing fairness, bias, transparency, security, safety
and ultimately trust in AI systems.

We characterize explainable AI as applied to face recognition and biometrics
by four principles. The face recognition case studies presented include
biometric, forensics and general applications. The four contributions of this
paper are

  * •

Articulate four principles of explainable AI applied to Biometrics and Facial
Forensic Algorithms.

  * •

Describe how the four principles apply.

  * •

Through four case studies, review challenges in implementing explainable AI.

  * •

Examine the relationship between explanations and response time to decisions.

After describing the four principles, we will illustrate the principles with
four case studies in face recognition and biometrics. The case studies will
cover challenges and the impact of adopting the principles.

##  2 Four Principles of Explainable AI

Our four principles of explainable AI for face recognition and biometrics are

Explanation:

Systems deliver accompanying evidence or reason for all decisions.

Interpretable:

Systems provide explanations that are understandable and meaningful to
individual users.

Explanation Accuracy:

Systems provide explanations that are understandable, meaningful, and
acceptable to individual users.

Knowledge Limits:

The system only produces decisions under the conditions it was designed and
tested.

###  2.1 Explanation

The Explanation principle obligates systems to supply evidence, support or
reasoning for each decision. By itself, this principle does not require that
the evidence be correct, informative, or even make sense; it merely states
that a system is capable of providing an explanation.

###  2.2 Interpretable

A system fulfills the Interpretable principle if the user understands the
system’s explanations and the explanation allows users to complete their
tasks. This principle does not expect a one-size fits all explanation. There
can be multiple groups of users for a system, and the Interpretable principle
dictates that explanations are tailored to each of the user groups. Thus, a
system may need to generate multiple explanations. We will refer to this as a
_multi-sided_ explanation.

The explanations should be generated when a decision is computed; however, the
explanations may not be consumed contemporaneous with a decision. For
corporate smartphones, face recognition unlocks the phone, and an explanation
is not provided to the user. The explanation is stored for subsequent security
audits by the company.

###  2.3 Explanation Accuracy

Together, the Explanation and Interpretable principles only obligate a system
to produce explanations that are understandable by a user community. These two
principles do not mandate that a system delivers accurate explanations. The
Explanation Accuracy principle imposes accuracy on a system’s explanations.

For over 25 years, researchers in face recognition and biometrics have
measured the accuracy of algorithms and systems decision on benchmark data
sets [11, 12, 9, 14, 16]. To avoid confusion, we will refer to this as
_decision accuracy_. Standard decision accuracy statistics include the
verification and false accept rates for an operating point and the rank one
retrieval rate for searching a gallery.

Decisions and explanation accuracies are independent. Regardless of whether
the system decision is ultimately correct or incorrect, an explanation must
describe how the system came to its conclusion.

An accurate explanation does not imply that a system provided the correct
answer. If the system decision is wrong, the explanation needs to articulate
how the system came to that wrong decision.

For correct answers, there are two reasons an explanation could be wrong. In
the first case, the explanation is not plausible. For example, the object on
the road is a car because it has two legs and three wings. In the second case,
the explanation is plausible but does not describe the reasoning the system
used. For example, the explanation provided states that is a car because it is
the right size and has four wheels. The correct logic is that the object looks
like a model of car in the training set.

While the community has established decision accuracy metrics, researchers
have not developed performance metrics for explanations.

###  2.4 Knowledge Limits

Given a pair of non-frontal face images, a face recognition system can provide
a judgment for the similarity between the two faces. If engineers designed the
system to process frontal faces, then the system should be prohibited from
comparing these two non-frontal images. The Knowledge Limits principle
commands systems to flag cases the algorithm was not designed or tested to
solve. The Knowledge Limits principle differs from the Explanation Accuracy
principle in that it doesn’t require evidence of truth, instead it provides a
mechanism for the system to punt on the answer. In the above example, the
algorithm should not compare the two non-frontal faces and alert the system
operators.

##  3 Related Work

Others have articulated the pillars of explainable AI [18], [2],[4]. These
pillars describe explainable AI’s relationship to transparency, trust,
fairness, and other properties. The focus of our principles was independent
from these other terms. Guidotti et al.[4] provide a detailed survey of
methods for explaining black-box algorithms.

The Defense Advanced Research Projects Agency (DARPA) runs the Explainable
Artificial Intelligence (XAI) Program which is designed to produce more
explainable models, while maintaining a high level of learning performance
(prediction accuracy); and to enable human users to understand, appropriately
trust, and effectively manage the emerging generation of artificially
intelligent partners111https://www.darpa.mil/program/explainable-artificial-
intelligence.

##  4 Dance Floor Perspective

We characterize interpretability along two axes, see Figure 1. In Figure 1,
the horizontal axis represents the time requirement a user has to respond to a
situation. The time requirement axis addresses situations from those that
require immediate responses to those that permit a long term view. The
vertical axis represents the user requirement for how the system information
will be used. The user requirement axis addresses situations related to the
level of detail the consumer or user will require, from little explanation
needed or required to much greater detail being required.

Figure 1: Dance floor that shows length of response time versus distance from
action.

What is interpretable depends on the consumer of the results. Ability to
explain depends on the technique or the domain. Consider how decisions from AI
systems might be used in the situations presented in the four quadrants of
Figure 1. The LAW OFFICER (lower-left quadrant) in the context of relying on
facial recognition in an active crime situation may use AI decisions to
determine if a suspect should be brought in for questioning. In this case, the
explanation need that is meaningful to her is minimal, and simply supports why
the system yields a match/unmatched decision. The DETECTIVE (lower-right
quadrant) in the context of building a case may require the AI ’match’
decision to include a greater explanation that will support arresting an
individual. The JURY (upper-left quadrant) may need the AI system to explain
greater details in possibly more layperson terms about the performance of the
system under similar and dissimilar situations. And the CONVICT (upper-right
quadrant) may want to dissect the most minute details of the system match
finding, as she prepares for her appeal.

##  5 Case Studies

This section presents four case studies that explore the challenges and
identify research directions of explainability in face recognition and
biometrics.

###  5.1 Explainable Methods for DCNN-based Algorithms

Our first case study looks at deep convolutional neural networks (DCNN)-based
algorithms for visual biometrics and highlights three of the challenges in
explainable AI. First, what is an explanation? Second, does a user understand
the explanation? Third, does the explanation accurately reflect the DCNN
decision process?

In daily human communications, the response to a request for an explanation is
usually spoken or written. Visual explanations are reserved for special
conditions, and they are often accompanied by verbal clarification. Two of the
most popular explanatory techniques, class activation mapping (CAM) [20] and
grad-CAM [17], provide pure visual explanations, see Figure 2. In Figure 2,
the classifier reports that there is a dog in the image and the explanation of
the decision is the highlighted region in the image. Since the output of the
gradCAM algorithm is the heatmap, further interpretation of the visual
explanation is left to the consumer of the image and its highlighted region.

Figure 2: Example of the gradCAM technique [17]. The top image is the input to
the gradCAM algorithm and the bottom images is a heatmap from analyzing the
original image. The highlighted regions in the bottom images shows the regions
that contributed to the objects being classifying as a dog.

The CAM and grad-CAM methods provide coarse localization of regions in an
image. In visual biometrics, explanations will require more precise
explanations, see the facial forensic case study in Section 5.4.

The technique in Hendricks et al. [5] provides a written explanation for the
decision of a bird species classifier. The algorithm learns explanations from
expert birders. The experiments in the study measure the explanation accuracy
by having human birders judge the algorithm’s explanations.

The CAM and grad-CAM methods demonstrate there are different styles for
providing explanations, from purely verbal or visual to a combination of both.
The evaluation protocol in Hendricks et al. measured explanation accuracy. The
existing literature gives insight to the first two questions raised at the
beginning of this case study. Unfortunately, the third question was not
explicitly addressed.

###  5.2 Speaker Recognition

Speaker recognition technology at its core compares two samples of speech and
determines the likelihood that the same speaker is speaking in each. If the
system-dependent internal score is above a predefined threshold, a match is
declared. Current systems are not required to explain the decision they
produce, although in NIST Speaker Recognition Evaluation 2018 some neural
network models incorporated ”attention” mechanisms to help explain which
features the model was focusing on to produce certain outputs [19]. Speaker
recognition technology is used as a biometric (e.g., for access to a room or a
bank account), for investigatory work (e.g., does a suspect’s voice match that
of a voice on a 911 call), or for search (e.g., to sift through voice mails
looking for a particular message).

Consider the situation of a person accessing his bank account using speaker
recognition technology. The system will compare the voice sample collected
over the phone to a signature file stored in its database and respond with
either TRUE or FALSE, depending on whether it decides the voice samples match.

Placing this example in the context of explainable AI, the Explanation
Principle requires the system to add reasoning to each decision. The principle
does not define the content or the quality of the reasoning and therefore
meeting this principle in practice should be straightforward. The reasoning or
evidence may take many forms. It could be a confidence score, a log-likelihood
score, or a data quality score; or it could take the form of a series of
technical statistics. Maybe there are internal system rules which predicate a
FALSE decision, such as having the number of attempts exceeded, the account is
locked, or the system is unavailable or failure to connect to the server.

The Interpretable Principle, on the other hand, does introduce challenges to
explainable AI in the context of speaker recognition technology. The first
challenge is in determining who the explanation is for. In our example, we
have two possible consumers of the AI decision - the account owner and the
bank owner. Once the consumer of the AI decision is identified, the second
challenge is in creating an explanation with the appropriate level of detail.
To demonstrate these challenges, we refer to the red dots in Figure 1 showing
that multiple consumers of the decision and explanation sit in various
quadrants of the dance floor, requiring different levels of detail in the
explanations. (1) Represents operation as expected from the account owner’s
point of view. Immediate correct response with very little explanation
required. (2) Represents the same situation from the bank owner’s point of
view. The bank owner would not be checking every login attempt as it happens
but may keep records to consult in case of reported fraudulent access. Here
the bank owner has less of a time requirement but a greater need for details
in the explanation. (3) Represents a system failure. The account owner will
want to understand why he was denied access to his account. He will expect the
same timely response but with much greater detail in the explanation. (4)
represents the same system failure from the bank owner’s point of view where
they may require additional information in the explanation to address the
failure, and the bank owner would like to resolve the issue promptly.

In terms of the Explanation Accuracy Principle the explanation must be proven
via measurement to represent the reasoning for the decision. For current
state-of-the-art systems the Explanation Accuracy Principle presents new
challenges to speaker recognition technology. It is not our goal to solve
these challenges, but rather to identify the area of research that will bring
explainable AI to speaker recognition technology. A single algorithm may have
multiple accuracy measures depending on the resulting AI decision, or method
employed to reach a decision. This is demonstrable by considering the
differences of measurements between a system defined no-match, and a system
that couldn’t connect to the server. The same type of results, would be
explained and measured with different techniques.

The concepts covered in the Knowledge Limits Principle are active in the
technology implementation today. The use of thresholds can be expanded to
include no-decision ranges to account for instances when the data quality is
not sound, the presence of speech samples are too few, or the expected speech
is replaced with yelling, crying, grunting, laughter, etc.

###  5.3 AI Superior to Humans

For an explanation to be accepted by users, it needs to align with their
knowledge, background, and intuition. What happens when an explanation does
not align with prior experience? With advances in AI technology, there are
numerous reasons this will occur. In this case study, we discuss four reasons
our intuition could not align with an algorithms explanation.

First, our intuition for how we come to decisions is not accurate. For
example, in face recognition, Rice et al. [15] showed that people do not know
which facial features are critical for recognizing individuals. The challenge
in this situation is developing techniques that enable humans to accept
counter-intuitive explanations.

Second, a system has capabilities superior to humans. There are several
avenues for superior capabilities. First, algorithms perform better than the
majority of humans; e.g., face recognition [13]. Second, algorithms combined
with humans yield a superior performance; e.g., face recognition [13] — the
source of these capabilities maybe new analysis paths.

Third, AI systems can find entirely novel solutions outside usual human
reasoning paths, experience, and intuition. For example, Chef Watson created
entirely novel recipes 222https://www.ibm.com/blogs/watson/2016/01/chef-
watson-has-arrived-and-is-ready-to-help-you-cook/. It is possible, that a
system could explain its reasoning process, but people will need time to
understand and comprehend the explanation.

Fourth, explaining decision in biometric Intelligent Infrastructure [6].
Intelligent infrastructure system performs AI functions on a large scale. Two
examples are determining identity in social media networks or nation-scale
mugshot and fingerprint systems. Whereas people can compare two face images,
they cannot process millions of samples in a multi-biometric search.

For these four scenarios, the user group that can understand the rationale for
a decision may be restricted to a specially trained group with access to a
customized set of tools. An additional responsibility for the specially
trained group could be to disseminate an explanation to the public and other
user groups.

###  5.4 Facial Forensics Examiners

Forensic facial examiners perform detailed analysis of face images. From their
analysis, they prepare comprehensive reports and testify in court if required.
Examiners prepare reports explicitly stating their conclusions following best
practices[3]. Ideally, AI systems would prepare reports to follow the same
best practices. Unfortunately, this is beyond current technology; however,
developing an AI system that collaborates with examiners to write reports
maybe within reach.

##  6 Conclusion

We introduced the principles of _Explanation_ , _Interpretable_ , _Explanation
Accuracy_ , and _Knowledge Limits_ , to provide a solid foundation for
explainability in face recognition and biometrics. Instead of focusing on
technology, the principles turn attention to systems meeting societal norms.
We illustrated this point of view with four case studies that provide lessons
and research directions.

First, explanations come in different varieties that include visualizations
for image-based biometrics, verbal description, and a combination for both.
Evaluation techniques need to be developed for these different explanation
modes.

Second, the authors failed to find a significant effort in the face
recognition and biometrics literature that addresses one of the principles,
let alone all four principles. Related work in computer vision could provide a
starting point for further research and point to paths for attacking all four
points.

Third, researchers need to tackle the challenge of creating explanations for
systems with extra-human capabilities. Extra-human capabilities include
systems that are more accurate than humans, systems that involve the fusing of
human and machine decisions using intelligent infrastructure. One solution is
to develop tools that assist specially trained experts in understanding the
reasoning behind systems’ decisions.

With the increase in complexity of face recognition and biometric systems, the
need for specialized tools and training should not be a surprise. For many
complex information processing systems, experts regularly educate the public,
senior manages and policy advisers on the details on how they are working.

The lessons learned by setting the foundations of explainability in face
recognition and biometrics will inform the broader AI community as it
addresses explainability, transparency, fairness, and trust.

## References

  * [1] J. Buolamwini and T. Gebru.  Gender shades: Intersectional accuracy disparities in commercial gender classification.  In Conference on Fairness, Accountability and Transparency, pages 77–91, 2018.
  * [2] V. Dignum.  Responsible autonomy.  arXiv preprint arXiv:1706.02513, 2017.
  * [3] Facial Identification Working Group.  Guidelines for facial comparison methods version 1.0.  Technical report, 2012.
  * [4] R. Guidotti, A. Monreale, S. Ruggieri, F. Turini, F. Giannotti, and D. Pedreschi.  A survey of methods for explaining black box models.  ACM computing surveys (CSUR), 51(5):93, 2018.
  * [5] L. A. Hendricks, Z. Akata, M. Rohrbach, J. Donahue, B. Schiele, and T. Darrell.  Generating visual explanations.  In European Conference on Computer Vision, pages 3–19. Springer, 2016.
  * [6] M. I. Jordan.  Artificial intelligence—the revolution hasn’t happened yet.  https://medium.com/@mijordan3/artificial-intelligence-the-revolution-hasnt-happened-yet-5e1d5812e1e7, 2018\.
  * [7] K. Krishnapriya, K. Vangara, M. C. King, V. Albiero, and K. Bowyer.  Characterizing the variability in face recognition accuracy relative to race.  In Bias Estimation in Face Analytics, CVPR workshops, 2019.
  * [8] Y. M. Lui, D. Bolme, B. A. Draper, J. R. Beveridge, G. Givens, and P. J. Phillips.  A meta-analysis of face recognition covariates.  In Proceedings Third IEEE International Conference on Biometrics: Theory, Applications, and Systems, 2009.
  * [9] P. Phillips, K. W. Bowyer, P. J. Flynn, X. Liu, and W. T. Scruggs.  The Iris Challenge Evaluation 2005.  In Second IEEE International Conference on Biometrics: Theory, Applications, and Systems, 2008.
  * [10] P. J. Phillips, F. Jiang, A. Narvekar, and A. J. O’Toole.  An other-race effect for face recognition algorithms.  ACM Trans. Applied Perception, 8(2), 2011.
  * [11] P. J. Phillips, H. Moon, S. Rizvi, and P. Rauss.  The FERET evaluation methodology for face-recognition algorithms.  IEEE Trans. PAMI, 22:1090–1104, October 2000.
  * [12] P. J. Phillips, W. T. Scruggs, A. J. O’Toole, P. J. Flynn, K. W. Bowyer, C. L. Schott, and M. Sharpe.  FRVT 2006 and ICE 2006 large-scale results.  IEEE Trans. PAMI, 32(5):831–846, 2010.
  * [13] P. J. Phillips, A. N. Yates, Y. Hu, C. A. Hahn, E. Noyes, K. Jackson, J. G. Cavazos, G. Jeckeln, R. Ranjan, S. Sankaranarayanan, et al.  Face recognition accuracy of forensic examiners, superrecognizers, and face recognition algorithms.  Proceedings of the National Academy of Sciences, 115(24):6171–6176, 2018.
  * [14] M. A. Przybocki, A. F. Martin, and A. N. Le.  Nist speaker recognition evaluations utilizing the mixer corpora—2004, 2005, 2006.  IEEE Transactions on Audio, Speech, and Language Processing, 15(7):1951–1959, 2007.
  * [15] A. Rice, P. J. Phillips, and A. J. O’Toole.  The role of the face and body in unfamiliar person identification.  Applied Cognitive Psychology, 27:761–768, 2013.
  * [16] S. O. Sadjadi, T. Kheyrkhah, A. Tong, C. S. Greenberg, D. A. Reynolds, E. Singer, L. P. Mason, and J. Hernandez-Cordero.  The 2016 nist speaker recognition evaluation.  In Interspeech, pages 1353–1357, 2017.
  * [17] R. R. Selvaraju, M. Cogswell, A. Das, R. Vedantam, D. Parikh, and D. Batra.  Grad-cam: Visual explanations from deep networks via gradient-based localization.  In Proceedings of the IEEE International Conference on Computer Vision, pages 618–626, 2017.
  * [18] A. Teredesai, M. A. Ahmad, C. Eckert, and V. Kumar.  Explainable models for healthcare ai.  ACM Learning Center Webinar Slides, 2018.
  * [19] Q. Wang, K. Okabe, K. A. Lee, H. Yamamoto, and T. Koshinaka.  Attention mechanism in speaker recognition: What does it learn in deep speaker embedding?  In in Proc. IEEE SLT Workshop. IEEE, December 2018.
  * [20] B. Zhou, A. Khosla, A. Lapedriza, A. Oliva, and A. Torralba.  Learning deep features for discriminative localization.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 2921–2929, 2016.


# Simple yet Effective Gradient-Free Graph Convolutional Networks

Yulin Zhu1 Xing Ai1 Qimai Li1 Xiao-Ming Wu1 Kai Zhou1 1The Hong Kong
Polytechnic University {yulinzhu, xiao-ming.wu<EMAIL_ADDRESS>{xing96.ai<EMAIL_ADDRESS>
###### Abstract

Linearized Graph Neural Networks (GNNs) have attracted great attention in
recent years for graph representation learning. Compared with nonlinear Graph
Neural Network (GNN) models, linearized GNNs are much more time-efficient and
can achieve comparable performances on typical downstream tasks such as node
classification. Although some linearized GNN variants are purposely crafted to
mitigate “over-smoothing”, empirical studies demonstrate that they still
somehow suffer from this issue. In this paper, we instead relate over-
smoothing with the vanishing gradient phenomenon and craft a gradient-free
training framework to achieve more efficient and effective linearized GNNs
which can significantly overcome over-smoothing and enhance the generalization
of the model. The experimental results demonstrate that our methods achieve
better and more stable performances on node classification tasks with varying
depths and cost much less training time.

##  1 Introduction

Graph Neural Networks (GNNs) are playing an increasingly important role in
mining relational data represented as graphs. They achieved state-of-the-art
performances on various tasks, including node classification Welling and Kipf
(2016); Veličković et al. (2018), link prediction Zhang and Chen (2018), graph
classification Xu et al. (2018a), and node clustering Tsitsulin et al. (2020).
A particularly successful type of GNNs is Graph Convolutional Networks (GCNs)
Welling and Kipf (2016). Recently, it is argued that unlike other deep
learning models such as Convolutional Neural Networks (CNNs) LeCun et al.
(1995) in the computer vision domain, the effectiveness of GCNs does not come
from the non-linear operations (e.g., the non-linear activation functions) but
is a result of the nature of the low pass filter that can locally smooth the
node features over the graph. Specifically, Wu et al. crafted a simplified GCN
by iteratively removing the non-linear activations and degenerating the multi-
layer GCN to logistic regression with one weight matrix. This simplified model
is termed Simplified Graph Convolutional Network (SGC). Empirically, it was
shown that SGC could achieve comparable performances as other nonlinear
competitors in most cases. But, SGC enjoys much less training time since
training SGC is a simple multiclass logistic regression problem. The benefits
of SGC are not limited to computational savings. Recently in the security
domain, SGC is commonly used as a surrogate model to simplify the attack
design Zügner et al. (2018); Zügner and Günnemann (2019); Zhu et al. (2022).
In addition, SGC could potentially reduce the computational complexity for
secure computation schemes Mohassel and Rindal (2018); Rathee et al. (2020),
for which dealing with nonlinear operations are notoriously expensive.

Thus, following SGC, a lot of research efforts have been devoted to studying
and further improving such linearized GCNs. Notably, Zhu and Koniusz; Wang et
al. have shown that SGC would suffer from the over-smoothing problem Li et al.
(2018) if more graph convolutional layers are stacked, which could cause a
severe downgrade in the node classification performance. The above works
tackle the over-smoothing problem from the perspective of the graph spectrum.
More specifically, they design a suitable graph filter to balance the local
and global information obtained from the propagation step to prevent the node
from paying unnecessarily more attention to its neighbors in the receptive
field and ignoring self-information. In this paper, we instead relate the
over-smoothing issue to the ineffective gradient-descent-based training
process, which further results in the downgrade in node classification
performance. Specifically, it has been shown that stacking more layers to CNN
or RNN Hochreiter and Schmidhuber (1997) will cause the _vanishing gradient_
problem Pascanu et al. (2013), meaning that the gradients used to update the
neural network’s weights will be minuscule during the training phase and lead
to insufficient training of the deep neural networks. Unfortunately, we
observe that the linearized GCNs also have this problem (see Fig. 1).

To address this issue, we propose a gradient-free solution for the training of
a series of linearized GCN models. In short, our method does not require
training the GCN model using gradient descent (thus gradient-free). Instead,
we directly calculate the optimal model parameters through closed-form
functions. Specifically, we replace and kernelize the original negative log-
likelihood (NLL) loss of the linearized GCNs to a dual formulation and map the
graph filters obtained from the linearized GCNs to a reproducing kernel
Hilbert space (RKHS) to train the node classifier. We transform the primal
classification problem into a regression problem on the RKHS. By setting the
first derivative of the dual form loss with respect to the Lagrange multiplier
to zero, we can obtain a closed-form solution for the model parameters with a
nice scale invariance property. That is, we can directly obtain the optimal
weights for linearized GCNs, avoiding the tedious gradient-descent-based
training and tuning various hyperparameters (e.g., learning rate, epoch
number, momentum, etc.). Importantly, since our method is gradient-free, it
can directly prevent the vanishing gradient problem when the number of layers
$K$ is large.

Overall, our methods can serve as a framework for refining linearized GCNs. We
use three representative linearized GCN models (i.e., SGC, SSGC, and DGC) as
examples, for which our methods lead to improved models termed gfSGC, gfSSGC,
and gfDGC, respectively. The experimental results show that our proposed
gradient-free linearized GCNs outperforms other baseline methods regardless of
the number of GCN layers. In addition, we also empirically show that our
methods have better performances in terms of computational efficiency and
stability.

###  1.1 Related Works

Graph convolutional networks Welling and Kipf (2016) are powerful tools to
mine non-Euclidean relational data. There are two typical analytical methods
for GCNs: spectrum-based and spatial-based. Spectrum-based GCNs Welling and
Kipf (2016); Yang et al. (2016) design the graph layer via localized first-
order approximation of spectral graph convolutions in the Fourier domain.
Spatial-based GCNs Hamilton et al. (2017); Danel et al. (2020) instead
propagate and update the node features based on the topology relationship
between the target node and its neighbors. Linearized GCNs simplify the
complex nonlinear GCNs to the multi-class logistic regressions (SGC Wu et al.
(2019)), which achieve comparable node classification performances to vanilla
GCNs. On the other hand, Simple Spectral Graph Convolution (SSGC) Zhu and
Koniusz (2020) and Decoupled Graph Convolution (DGC) Wang et al. (2021) tackle
the over-smoothing problem encountered by SGC via crafted tricks to prevent
the node features from paying too much attention to the neighbors’ information
when the depth $K$ increases.

##  2 Preliminaries

###  2.1 Notations

We denote $\mathcal{G}=\\{\mathbf{A},\mathbf{X}\\}$ as a unweighted attributed
graph, where $\mathbf{A}\in\mathbbm{R}^{N\times N}$ is the adjacency matrix
with binary entries and $\mathbf{X}$ is the attribute matrix, $N$ is the node
number. In this paper, we focus on the semi-supervised node classification
task Welling and Kipf (2016). Under this scenario, each node is assigned to a
label $y_{i}$ which represents a class $c_{i}$. We denote
$\mathbf{Y}=\\{y_{i}\\}_{i=1}^{N}$ and $C$ as the label set and class number.
The goal of the node classification task is to achieve a good performance on
predicting the nodes’ labels in the testing set.

###  2.2 Representative Linearized GCNs

####  2.2.1 Simplified Graph Convolution (SGC)

SGC is the first linearized GCN model for graph data. Intuitively, Wu et al.
argued that the powerful representation learning of the GCNs does not come
from the non-linear activations like $\text{ReLU}(\cdot)$. To address this
issue, it degenerates the vanilla GCN by repeatedly erasing the nonlinear
activations of each graph convolutional layer and then using a single weight
matrix to represent the stacked weight matrices for each layer. As a result,
SGC can be formulated as:

$\displaystyle\widehat{\mathbf{Y}}=\text{softmax}(\hat{\mathbf{A}}^{K}\mathbf{X}\mathbf{W}),$
(1a)
$\displaystyle\hat{\mathbf{A}}=\tilde{\mathbf{D}}^{-\frac{1}{2}}\tilde{\mathbf{A}}\tilde{\mathbf{D}}^{-\frac{1}{2}},\
\tilde{\mathbf{A}}=\mathbf{A}+\mathbf{I}.$ (1b)

Eqn. (1a) can be regarded as a multi-class logistic regression Menard (2002)
with the complex nodal features $\hat{\mathbf{A}}^{K}\mathbf{X}$ as the
inputs, where $K$ is the number of layers. Then, we can implement Adam
optimizer Kingma and Ba (2014) to train the multi-class logistic regression.

####  2.2.2 Simple Spectral Graph Convolution (SSGC)

To tackle the over-smoothing issue, SSGC goes a step further to augment the
modified Markov diffusion kernel Fouss et al. (2012) with SGC which can trade
off between low and high pass filter bands in the spectrum domain, which can
significantly alleviate the over-smoothing phenomenon. Then, the SSGC is
formulated as:

$\widehat{\mathbf{Y}}=\text{softmax}(\frac{1}{K}\sum_{k=1}^{K}((1-\tau)\hat{\mathbf{A}}^{k}\mathbf{X}+\tau\mathbf{X})\mathbf{W}),$
(2)

where $\hat{\mathbf{A}}$ is the normalized Laplacian matrix defined in Eqn.
(1b) and $\tau$ is a hyperparameter to trade off between the self-information
and consecutive neighbors’ information. Similarly, we can regard the complex
nodal features
$\frac{1}{K}\sum_{k=1}^{K}((1-\tau)\hat{\mathbf{A}}^{k}\mathbf{X}+\tau\mathbf{X})$
as the inputs to the multi-class logistic regression for the downstream semi-
supervised node classification task.

####  2.2.3 Decoupled Graph Convolution (DGC)

DGC regards the propagation of SGC as a numerical discretization of the graph
heat equation Chung (1997). Wang et al. utilize the Euler method with terminal
time to update the features to approximate the graph heat equation with $K$
forward steps. Then, Wang et al. decouples the terminal time $T$ and the depth
$K$ to get a more fine-grained approximation to the vanilla propagation steps
to mitigate the over-smoothing. It crafts the propagation step for each layer
as:

$\displaystyle\widehat{\mathbf{Y}}=softmax((1-\frac{T}{K})\mathbf{I}+\frac{T}{K}\hat{\mathbf{A}})^{K}\mathbf{X}$
(3a)

where $T$ is the terminal time to balance the under-smoothing and over-
smoothing. Then, the hybrid nodal features are fed into a logistic regression
for training.

##  3 Vanishing Gradient and Over-smoothing

Linearized GCNs suffer from the over-smoothing issue when $K$ increases. A
possible cause is that the vanishing gradient problem prevents the model from
being effectively trained through gradient descent. In this section, we
provide both theoretical and empirical analysis (Fig. 1) of the vanishing
gradient problem of linearized GCNs.

For convenience, we use $\mathcal{F}_{G}$ (Eqn. (10)) to represent the graph
filters obtained from the linearized GCNs. Recall that the feed-forward
function of linearized GCN
$\widehat{\mathbf{Y}}=\text{softmax}(\mathcal{F}_{G}\mathbf{W})$ is trained by
minimizing cross-entropy loss:
$\min_{\mathbf{W}}\mathcal{L}_{CE}{(\mathbf{Y},\widehat{\mathbf{Y}})}$. By the
chain rule, we have

$\frac{\partial\mathcal{L}_{CE}}{\partial\mathbf{W}}=\mathcal{F}_{G}^{\top}\frac{\partial\mathcal{L}_{CE}}{\partial\mathbf{H}},$
(4)

where $\mathbf{H}\overset{\Delta}{=}\mathcal{F}_{G}\mathbf{W}$. The gradient
of the model parameters $\mathbf{W}$ is significantly affected by the scale of
$\mathcal{F}_{G}$. The parameters $\mathbf{W}$ suffer from the vanishing
gradient problem if $\mathcal{F}_{G}$ is too small, which is true when $K$ is
large. Since the existence of bias parameters, logistic regression is
invariant to data point translation. Thus, we will focus on our discussion on
the scale of zero-centered $\mathcal{F}_{G}$ defined as follows:

$\mathcal{F}_{G}-\frac{1}{N}\mathbf{1}_{N}\mathbf{1}_{N}^{\top}\mathcal{F}_{G},$
(5)

where $\mathbf{1}_{N}\in\mathbbm{R}^{N}$ is an all-one vector, and
$\frac{1}{N}\mathbf{1}_{N}^{\top}\mathcal{F}_{G}$ is the center of data
points. Theorem 1 states the conditions for the vanishment of the scale of the
zero-centered $\mathcal{F}_{G}$ as $K$ increases.

######  Theorem 1.

For SGC, zero-centered $\mathcal{F}_{G}$ approximates a zero vector as $K$
approximates $+\infty$, if the graph is connected and not bipartite. That is,

$\lim_{K\to\infty}(\mathcal{F}_{G}-\frac{1}{N}\mathbf{1}_{N}\mathbf{1}_{N}^{\top}\mathcal{F}_{G})=\mathbf{0}.$
(6)

For SSGC, it approximates zero-centered $\tau\mathbf{X}$, which is small if
$\tau$ is small. That is,

$\lim_{K\to\infty}\left(\mathcal{F}_{G}-\frac{1}{N}\mathbf{1}_{N}\mathbf{1}_{N}^{\top}\mathcal{F}_{G}\right)=\tau\left(\mathbf{X}-\frac{1}{N}\mathbf{1}_{N}\mathbf{1}_{N}^{\top}\mathbf{X}\right).$

(7)

For DGC, let $\mathbf{A}_{rw}$ denote the row-normalized adjacency matrix. We
have

$\displaystyle\lim_{K\to\infty}$
$\displaystyle\left(\mathcal{F}_{G}-\tfrac{1}{N}\mathbf{1}_{N}\mathbf{1}_{N}^{\top}\mathcal{F}_{G}\right)$
(8)
$\displaystyle=(I-\tfrac{1}{N}\mathbf{1}_{N}\mathbf{1}_{N}^{\top})\exp(T(\mathbf{A}_{rw}-I))\mathbf{X},$
(9)

which is small, when $T$ is large.

The proof of Theorem 1 is presented in Sec. C of the supplement. We note that
the analysis in the proof applies to row-normalized adjacency matrix
$\mathbf{A}_{rw}$, while the most commonly adopted one is symmetrically
normalized $\hat{\mathbf{A}}$. However, for $\hat{\mathbf{A}}$ the left side
of Eqn. (6) converges to a small vector instead of zero. As a result, the
vanishing gradient problem still exists.

(a) SGC initial gradients

(b) SGC loss trace plot

(c) SSGC initial gradients

(d) SSGC loss trace plot

(e) DGC initial gradients

(f) DGC loss trace plot

Figure 1: Gradient density plot and the trace plot of training loss for SGC,
SSGC and DGC. SGC and SSGC encounter the vanishing gradient problem while DGC
with relatively small $T$ can mitigate this issue.

We also demonstrate the vanishing gradient problem empirically. Fig. 1(a),
1(c) and 1(e) present the density of the gradients with respect to the model
parameters at the initial iteration for the three linearized GCN models,
respectively. (We obtain the gradients of $\mathbf{W}$ at first iteration and
reshape it to one vector and curve the distribution of the vector with density
plot.) It is observed that the gradients of SGC and SSGC will indeed vanish as
we increase the number of layers $K$. Meanwhile, we also trace the training
losses (Fig. 1(b), 1(d), and 1(f)) for the three models with different values
of $K$. Fig. 1(b) and 1(d) reflect that the decrease in the gradients’
magnitudes will lead to the ineffective training of the models (thus leading
to the over-smoothing phenomenon in Tab. 2, 3, 4 and 5). For DGC, it is
observed that the density plots of gradients are almost the same when $K>4$.
The primary reason is that a small value of $T$ was chosen to achieve better
classification performance (Sec. E in the supplement provide the vanishing
gradient issue when $T$ increases). This demonstrates that DGC can mitigate
the vanishing gradient problem by properly choosing the parameter at the cost
of sacrificing the performance when $K$ is small (Tab. 2, 3, 4 and 5).
Nevertheless, we show that our gradient-free method could still slightly
improve DGC in some cases and improve the training efficiency.

##  4 Gradient-free GCNs

In this section, we elaborate on how to implement the gradient-free framework
with the three linearized GCNs (SGC, SSGC and DGC) as its graph filters for
the semi-supervised node classification task.

###  4.1 Graph Filters

Theoretically, we can split the framework into two modules: feature extraction
and kernelization. In the feature extraction module, we obtain different graph
filters based on the graph’s topological and semantic information:

$\mathcal{F}_{G}=\begin{cases}\hat{\mathbf{A}}^{K}\mathbf{X},&\mbox{for
SGC,}\\\
\frac{1}{K}\sum_{k=1}^{K}((1-\tau)\hat{\mathbf{A}}^{k}\mathbf{X}+\tau\mathbf{X}),&\mbox{for
SSGC,}\\\
\left((1-\frac{T}{K})\mathbf{I}+\frac{T}{K}\hat{\mathbf{A}}\right)^{K}\mathbf{X},&\mbox{for
DGC}.\end{cases}$ (10)

After that, we can generalize and formulate the linearized GCNs as:

$\widehat{\mathbf{Y}}=\text{softmax}(\mathcal{F}_{G}\mathbf{W}),$ (11)

where $\mathbf{W}$ is the single weight matrix to be trained.

###  4.2 Kernelization

After obtaining the corresponding graph filters, we endeavor to craft a
gradient-free GCN model to overcome the previously mentioned vanishing
gradient problem. Especially, the original objective function of the GCN model
is the negative log-likelihood (NLL) loss, i.e.,
$\mathcal{L}_{NLL}=-\sum_{i=1}^{N}\sum_{c=1}^{C}y_{ic}\log\hat{y}_{ic}$.
Unfortunately, it has been proven that the NLL loss does not have its closed-
form solution Jain and Kar (2017). Hence, a common way to optimize this
objective is to utilize the vanilla gradient descent method like Adam Kingma
and Ba (2014), which highly relies on gradient computation. To avoid the
vanishing gradient problem, it is natural to design a gradient-free method to
optimize the model weights $\mathbf{W}$. To this end, we elaborately replace
the NLL loss with the mean square loss augmented with the L2 penalty, i.e.,

$\begin{split}\mathcal{L}_{MSE}&\overset{\Delta}{=}\sum_{i=1}^{N}\sum_{c=1}^{C}\frac{1}{2}(y_{ic}-[\Phi(\mathcal{F}_{G})\mathbf{W}]_{ic})^{2}+\frac{\xi}{2}\operatorname{Tr}(\mathbf{W}^{\top}\mathbf{W})\\\
&=\frac{1}{2}\operatorname{Tr}((\mathbf{Y}-\Phi(\mathcal{F}_{G})\mathbf{W})^{\top}(\mathbf{Y}-\Phi(\mathcal{F}_{G})\mathbf{W}))\\\
&\quad+\frac{\xi}{2}\operatorname{Tr}(\mathbf{W}^{\top}\mathbf{W}),\end{split}$
(12)

where $\Phi(\mathcal{F}_{G})$ maps the graph filters to a new feature space,
$\xi$ is the L2 regularizer to control the sparsity of the model. Henceforth,
we attempt to find a closed-form solution $\mathbf{W}^{*}$ to optimize Eqn.
(12) without gradient computation. It is worth noting that in Eqn. (12) the
true label $\mathbf{Y}\in\mathbbm{R}^{N\times C}$ is a one-hot encoding
matrix. That is, we transform the traditional multi-class classification
problem to a multiple multivariate regression problem Menard (2002) by
substituting our objective from the NLL loss to Eqn. (12), and we aim to find
$\mathbf{W}^{*}$ which can push each entry of the prediction, i.e.,
$[\Phi(\mathcal{F}_{G})\mathbf{W}^{*}]_{ic}$ close to the binary entry
$\mathbf{Y}_{ic}$. However, it is natural that $\Phi(\cdot)$ is unknown to us,
we instead resort to the dual form of Eqn. (12) and kernelize the inputs
$\mathcal{F}_{G}$ to prevent the usage of $\Phi(\cdot)$. To tackle this issue,
we reformulate Eqn. (12) to:

$\begin{split}&\mathcal{L}_{MSE}=\frac{1}{2}\operatorname{Tr}(\mathbf{Z}^{\top}\mathbf{Z})+\frac{\xi}{2}\operatorname{Tr}(\mathbf{W}^{\top}\mathbf{W}),\\\
&\ \ \text{s.t.}\
\mathbf{Z}=\Phi(\mathcal{F}_{G})\mathbf{W}-\mathbf{Y}.\end{split}$ (13)

We then obtain its Lagrange function:

$\begin{split}\mathcal{L}_{\bm{\Lambda}}&=\frac{1}{2}\operatorname{Tr}(\mathbf{Z}^{\top}\mathbf{Z})+\frac{\xi}{2}\operatorname{Tr}(\mathbf{W}^{\top}\mathbf{W})\\\
&+\operatorname{Tr}(\bm{\Lambda}^{\top}(\mathbf{Z}-\Phi(\mathcal{F}_{G})\mathbf{W}+\mathbf{Y})),\end{split}$
(14)

where $\bm{\Lambda}\in\mathbbm{R}^{N\times C}$ is the Lagrange multiplier. We
then zero out the gradient
$\frac{\partial\mathcal{L}_{\bm{\Lambda}}}{\partial\mathbf{Z}}$ and
$\frac{\partial\mathcal{L}_{\bm{\Lambda}}}{\partial\mathbf{W}}$ and get:

$\begin{split}\mathbf{Z}^{*}=-\bm{\Lambda},\quad\mathbf{W}^{*}=\frac{1}{\xi}\Phi(\mathcal{F}_{G})^{\top}\bm{\Lambda}.\end{split}$
(15)

Next, by substituting $\mathbf{Z}$ and $\mathbf{W}$ in Eqn. (14) with Eqn.
(15) we obtain the dual form of Eqn. (12), i.e.,

$\begin{split}\mathcal{L}_{\bm{\Lambda}}&=-\frac{1}{2}\operatorname{Tr}(\bm{\Lambda}^{\top}\bm{\Lambda})-\frac{1}{2\xi}\operatorname{Tr}(\bm{\Lambda}^{\top}\mathbf{M}\bm{\Lambda})+\operatorname{Tr}(\bm{\Lambda}^{\top}\mathbf{Y}),\end{split}$
(16)

where $\mathbf{M}$ is the kernel matrix based on the inputs $\mathcal{F}_{G}$,
i.e., $\mathbf{M}_{uv}=m(\mathcal{F}_{Gu},\mathcal{F}_{Gv})$, $m(\cdot)$ is
the kernel function.

###  4.3 Closed-form Solution

Given the dual form loss function Eqn. (16), we aim to find an optimal
$\bm{\Lambda}^{*}$ to optimize this objective in a gradient-free manner. To
tackle this issue, we compute the gradient of
$\frac{\partial\mathcal{L}_{\bm{\Lambda}}}{\partial\bm{\Lambda}}$ and zeroize
it to explicitly represent $\bm{\Lambda}^{*}$ with the kernel matrix:

$\begin{split}\bm{\Lambda}^{*}&=(\frac{1}{\xi}\mathbf{M}+\mathbf{I})^{-1}\mathbf{Y}\overset{\Delta}{=}(\lambda\mathbf{M}+\mathbf{I})^{-1}\mathbf{Y},\end{split}$
(17)

After that, we can predict the node label in the testing set based on the
optimal solution $\bm{\Lambda}$:

$\begin{split}\bm{y}^{*}=\Phi(\mathcal{F}_{G})\mathbf{W}^{*}=\lambda\cdot
m(\mathcal{F}_{G}^{*},\mathcal{F}_{G}^{train})\bm{\Lambda}^{*},\end{split}$
(18)

where $\mathcal{F}_{G}^{*}$ is the graph filter of a new node computed based
on Eqn. (10), $\mathcal{F}_{G}^{train}$ is the graph filter of training set,
$\bm{y}^{*}\in\mathbbm{R}^{1\times C}$ is prediction of the new node. For
evaluation, we pick out the index of the largest entry of $\bm{y}^{*}$ as the
predicted label for the new node. In addition to that, if it is a binary
classification problem, we can still use Eqn. (18) for prediction. The only
difference between binary classification and multi-class classification is
that the binary classification does not utilize the one-hot encoding of the
true label $\mathbf{Y}$. It is worth noting that if the kernel function
$m(\cdot)$ is a linear kernel, we have the primal version of the closed-form
solution to the weight $\mathbf{W}$ in Eqn. 12, i.e.,
$\mathbf{W}^{*}=(\mathcal{F}_{G}^{\top}\mathcal{F}_{G}+\xi\mathbf{I})^{-1}\mathcal{F}_{G}^{\top}\mathbf{Y}$.

###  4.4 Scale Invariance of the Closed-form Solution

In the primal form, the optimization problem (12) has following closed-form
solution,

$\mathbf{W}^{*}=\left(\Phi(\mathcal{F}_{G})^{\top}\Phi(\mathcal{F}_{G})+\xi
I\right)^{-1}\Phi(\mathcal{F}_{G})^{\top}\mathbf{Y}.$ (19)

The optimal solution $\mathbf{W}^{*}$ results in an estimation
$\widehat{\mathbf{Y}}^{*}$,

$\begin{split}\widehat{\mathbf{Y}}^{*}&=\Phi(\mathcal{F}_{G})\mathbf{W}^{*}\\\
&=\Phi(\mathcal{F}_{G})\left(\Phi(\mathcal{F}_{G})^{\top}\Phi(\mathcal{F}_{G})+\xi
I\right)^{-1}\Phi(\mathcal{F}_{G})^{\top}\mathbf{Y}.\end{split}$ (20)

We consider $\widehat{\mathbf{Y}}^{*}$ as a function of
$\Phi(\mathcal{F}_{G})$ and $\xi$,

$\widehat{\mathbf{Y}}^{*}=\widehat{\mathbf{Y}}^{*}(\Phi(\mathcal{F}_{G}),\xi).$
(21)

If we scale $\Phi(\mathcal{F}_{G})$ by a constant $\beta$, and scale $\xi$ by
$\beta^{2}$, the estimation $\widehat{\mathbf{Y}}^{*}$ is invariant, i.e.,

$\widehat{\mathbf{Y}}^{*}(\Phi(\mathcal{F}_{G}),\xi)=\widehat{\mathbf{Y}}^{*}(\beta\Phi(\mathcal{F}_{G}),\beta^{2}\xi).$
(22)

In other words, the estimator resulting from the optimization problem (12) is
invariant to the scale of $\Phi(\mathcal{F}_{G})$, as long as hyper-parameter
$\xi$ is properly scaled correspondingly.

##  5 Experiments

###  5.1 Dataset Description

We consider the node classification task over four commonly used citation
networks: Cora, Cora-ML, Citeseer, and PubMed Sen et al. (2008). The nodes in
these datasets represent published papers, and the edges are citations among
papers. More details about the datasets are presented in Sec. A of the
supplement.

###  5.2 Baselines

To demonstrate the performance of the proposed model, we compare our models
with eight strong baselines, including GCN Welling and Kipf (2016), Graph
Attention Network (GAT) Veličković et al. (2018), Jumping Knowledge
Networks(JKNet) Xu et al. (2018b), APPNP Klicpera et al. (2019), Graph
Convolutional Network via Initial residual and Identity mapping (GCNII) Chen
et al. (2020), SGC Wu et al. (2019), SSGC Zhu and Koniusz (2020) and DGC Wang
et al. (2021). It is worth noting that GCN, GAT, JKNet, APPNP, GCNII are
nonlinear deep learning models; SGC, SSGC and DGC are linearized models.

###  5.3 Model Setting

For a fair comparison, each method is run on an Ubuntu 20.04 system with 16
Intel(R) Xeon(R) Platinum 8369B CPU @ 2.90GHz and a GeForce RTX 3090. The
computer codes and the parameters used for the GCN, GAT, SGC and SSGC are
available from the authors’ public links. We choose the default hyperparameter
settings for SSGC and DGC, i.e., we set the strength of identity mapping
$\tau=0.05$ for SSGC and the terminal time $T=5.27$ for DGC. For all the
models to be trained via gradient descent, we utilize the Adam Kingma and Ba
(2014) with the learning rate $0.01$ and epochs equal to $200$. For each of
the datasets, we split the dataset into a training, validation and testing set
with a proportion equal to $1:1:8$. We run all the models $20$ times with
different seeds and report the mean testing accuracy for evaluation. Without
loss of generality, we choose the kernel function $m(\cdot)$ as the linear
kernel for a fair comparison. We term our methods with three different graph
filters as: gfSGC, gfSSGC and gfDGC respectively.

###  5.4 Experiment Results

####  5.4.1 Overall Node Classification Performance

Our gradient-free method results in three refined linearized GCN models:
gfSGC, gfSSGC, and gfDGC. These models allow one to choose larger values of
$K$ to incorporate more information during the message-passing process. To
validate the effectiveness of our models, we compare them with eight baselines
(including both linearized and nonlinear models) on the node classification
task. We note that, for all models, we report their best performance among
different values of $K$, where $K\in\\{2,4,8,16,32,64,128\\}$. The results are
summarized in Tab. 1.

It is observed that our gradient-free methods gfSGC, gfSSGC, and gfDGC achieve
the best accuracies among the strong baselines in almost all cases, often with
a clear improvement over other GCNs. For instance, the best accuracies of our
models on Cora, Cora-ML, Citeseer, and PubMed are $86.5\%$, $87.5\%$,
$77.4\%$, and $87.0\%$ respectively. One exceptional case is on Pubmed, where
the best model APPNP is a nonlinear GNN model. However, we note that
linearized GCNs are much more efficient than nonlinear models in terms of
training. It is noteworthy that the gradient-free methods are always better
than the baseline models, i.e., SGC, SSGC and DGC. This observation directly
demonstrates the advantages and effectiveness of the gradient-free framework.

Table 1: Average test accuracy (%$\pm$ standard error) over $20$ runs on four
node classification datasets. The best and second-best results are highlighted
in bold and underlined.

Datasets | Cora | Cora-ML | Citeseer | Pubmed
---|---|---|---|---
GCN | $83.6\pm{0.6}$ | $85.7\pm{0.4}$ | $71.6\pm{0.4}$ | $85.0\pm{0.2}$
GAT | $83.7\pm{0.3}$ | $84.6\pm{0.5}$ | $73.1\pm{2.3}$ | $83.7\pm{0.5}$
JKNet | $85.0\pm{0.5}$ | $86.4\pm{0.3}$ | $72.4\pm{0.5}$ | $86.3\pm{0.1}$
APPNP | $85.5\pm{0.5}$ | $86.8\pm{0.7}$ | $71.8\pm{0.7}$ | $\bm{87.1\pm{0.3}}$
GCNII | $79.2\pm{0.4}$ | $82.7\pm{1.1}$ | $70.4\pm{0.4}$ | $86.9\pm{0.3}$
SGC | $85.3\pm{0.06}$ | $86.1\pm{0.03}$ | $74.1\pm{0.1}$ | $82.7\pm{0.03}$
SSGC | $85.9\pm{0.07}$ | $87.5\pm{0.05}$ | $75.2\pm{0.02}$ | $82.7\pm{0.03}$
DGC | $85.2\pm{0.03}$ | $86.2\pm{0.04}$ | $73.8\pm{0.06}$ | $81.2\pm{0.03}$
gfSGC | $86.4$ | $87.3$ | $\bm{77.4}$ | $86.7$
gfSSGC | $\bm{86.5}$ | $\bm{87.5}$ | $\bm{77.4}$ | $87.0$
gfDGC | $\underline{86.4}$ | $86.4$ | $\underline{76.8}$ | $84.7$

Table 2: Average test accuracy (%$\pm$ standard error) over $20$ runs on Cora
dataset.
The best and second-best results are highlighted in bold and underlined.

Model | $K=2$ | $K=4$ | $K=8$ | $K=16$ | $K=32$ | $K=64$ | $K=128$
---|---|---|---|---|---|---|---
GCN | $83.6\pm{0.6}$ | $81.2\pm{0.9}$ | $69.4\pm{3.7}$ | $39.3\pm{7.6}$ | $30.2\pm{3.1}$ | $29.2\pm{0.02}$ | $29.2\pm{0.02}$
GAT | $83.7\pm{0.3}$ | $82.4\pm{0.9}$ | $81.8\pm{1.0}$ | $56.9\pm{16.6}$ | $33.0\pm{8.9}$ | $29.2\pm{9.3}$ | $11.5\pm{0}$
GCNII | $79.1\pm{1.0}$ | $77.8\pm{1.2}$ | $78.9\pm{0.4}$ | $79.0\pm{0.5}$ | $79.2\pm{0.4}$ | $79.1\pm{0.5}$ | $79.1\pm{0.3}$
SGC | $84.9\pm{0.1}$ | $85.3\pm{0.06}$ | $84.5\pm{0.07}$ | $83.2\pm{0.6}$ | $80.7\pm{0.8}$ | $73.2\pm{0.2}$ | $61.3\pm{0.3}$
SSGC | $83.5\pm{0.1}$ | $85.5\pm{0.1}$ | $85.8\pm{0.08}$ | $85.9\pm{0.07}$ | $85.2\pm{0.08}$ | $84.7\pm{0.05}$ | $84.4\pm{0.09}$
DGC | $45.0\pm{0.3}$ | $84.6\pm{0.06}$ | $85.2\pm{0.07}$ | $85.2\pm{0.04}$ | $85.2\pm{0.04}$ | $85.2\pm{0.03}$ | $85.2\pm{0.05}$
gfSGC | $\bm{86.4}$ | $86.4$ | $84.9$ | $83.7$ | $82.0$ | $80.2$ | $77.6$
gfSSGC | $85.4$ | $86.5$ | $86.5$ | $86.4$ | $86.3$ | $86.2$ | $86.0$
gfDGC | $39.1$ | $84.9$ | $86.4$ | $86.4$ | $86.4$ | $86.3$ | $86.2$

Table 3: Average test accuracy (%$\pm$ standard error) over $20$ runs on Cora-
ML dataset.
The best and second-best results are highlighted in bold and underlined.

Model | $K=2$ | $K=4$ | $K=8$ | $K=16$ | $K=32$ | $K=64$ | $K=128$
---|---|---|---|---|---|---|---
GCN | $85.7\pm{0.4}$ | $82.3\pm{1.7}$ | $66.3\pm{10.5}$ | $55.8\pm{6.7}$ | $38.0\pm{7.1}$ | $32.9\pm{6.1}$ | $27.8\pm{0.4}$
GAT | $84.6\pm{0.5}$ | $83.1\pm{1.1}$ | $81.5\pm{5.3}$ | $54.9\pm{17.7}$ | $27.4\pm{3.9}$ | $17.4\pm{7.8}$ | $12.4\pm{0}$
GCNII | $82.7\pm{1.1}$ | $82.7\pm{1.2}$ | $79.2\pm{1.2}$ | $79.5\pm{1.3}$ | $80.6\pm{1.4}$ | $78.8\pm{1.5}$ | $79.1\pm{1.1}$
SGC | $86.0\pm{0.05}$ | $86.1\pm{0.03}$ | $84.6\pm{0.03}$ | $81.2\pm{0.06}$ | $73.5\pm{0.02}$ | $61.3\pm{0.02}$ | $38.1\pm{0.1}$
SSGC | $85.9\pm{0.08}$ | $86.6\pm{0.06}$ | $87.5\pm{0.05}$ | $86.6\pm{0.03}$ | $85.4\pm{0.07}$ | $83.0\pm{0.04}$ | $77.0\pm{0.05}$
DGC | $50.6\pm{0.07}$ | $85.4\pm{0.06}$ | $85.8\pm{0.04}$ | $86.1\pm{0.04}$ | $86.1\pm{0.06}$ | $86.2\pm{0.04}$ | $86.2\pm{0.03}$
gfSGC | $87.3$ | $86.4$ | $84.7$ | $84.3$ | $83.0$ | $80.5$ | $72.8$
gfSSGC | $86.2$ | $87.0$ | $87.5$ | $86.9$ | $86.3$ | $86.3$ | $86.4$
gfDGC | $41.4$ | $85.3$ | $86.1$ | $86.1$ | $86.2$ | $86.3$ | $86.4$

Table 4: Average test accuracy (%$\pm$ standard error) over $20$ runs on
Citeseer dataset.
The best and second-best results are highlighted in bold and underlined.

Model | $K=2$ | $K=4$ | $K=8$ | $K=16$ | $K=32$ | $K=64$ | $K=128$
---|---|---|---|---|---|---|---
GCN | $71.6\pm{0.4}$ | $69.2\pm{0.9}$ | $62.5\pm{3.4}$ | $54.3\pm{8.1}$ | $38.0\pm{13.2}$ | $26.6\pm{2.1}$ | $26.3\pm{2.7}$
GAT | $73.1\pm{2.3}$ | $70.4\pm{4.8}$ | $63.7\pm{13.4}$ | $57.4\pm{8.2}$ | $30.6\pm{14.5}$ | $8.3\pm{6.7}$ | $5.5\pm{0}$
GCNII | $67.7\pm{1.0}$ | $67.9\pm{0.9}$ | $68.9\pm{0.4}$ | $70.3\pm{0.6}$ | $70.4\pm{0.4}$ | $70.4\pm{0.4}$ | $70.3\pm{0.6}$
SGC | $74.1\pm{0.1}$ | $73.2\pm{0.06}$ | $72.7\pm{0.09}$ | $73.3\pm{0.07}$ | $72.0\pm{0.06}$ | $71.1\pm{0.02}$ | $72.0\pm{0.03}$
SSGC | $74.7\pm{0.1}$ | $74.7\pm{0.1}$ | $74.5\pm{0.09}$ | $75.2\pm{0.06}$ | $75.2\pm{0.08}$ | $75.2\pm{0.02}$ | $74.2\pm{0.05}$
DGC | $44.0\pm{0.3}$ | $73.8\pm{0.08}$ | $73.7\pm{0.07}$ | $73.8\pm{0.06}$ | $73.7\pm{0.05}$ | $73.7\pm{0.06}$ | $73.7\pm{0.06}$
gfSGC | $77.4$ | $76.7$ | $75.7$ | $75.1$ | $74.4$ | $73.1$ | $72.5$
gfSSGC | $77.4$ | $77.4$ | $77.3$ | $76.4$ | $76.1$ | $75.7$ | $75.4$
gfDGC | $46.0$ | $76.5$ | $76.7$ | $76.8$ | $76.7$ | $76.7$ | $76.6$

Table 5: Average test accuracy (%$\pm$ standard error) over $20$ runs on
PubMed dataset.
The best and second-best results are highlighted in bold and underlined.

Model | $K=2$ | $K=4$ | $K=8$ | $K=16$ | $K=32$ | $K=64$ | $K=128$
---|---|---|---|---|---|---|---
GCN | $85.0\pm{0.2}$ | $82.6\pm{0.4}$ | $72.4\pm{15.6}$ | $56.2\pm{15.8}$ | $44.0\pm{3.4}$ | $44.0\pm{2.8}$ | $45.4\pm{4.9}$
GAT | $83.7\pm{0.5}$ | $82.0\pm{0.9}$ | $81.0\pm{4.7}$ | $61.8\pm{19.1}$ | $41.4\pm{5.6}$ | $32.3\pm{9.3}$ | $21.7\pm{4.2}$
GCNII | $86.9\pm{0.3}$ | $85.9\pm{0.4}$ | $85.6\pm{0.4}$ | $85.3\pm{0.3}$ | $84.7\pm{0.3}$ | $84.4\pm{0.2}$ | $85.3\pm{0.2}$
SGC | $82.7\pm{0.03}$ | $81.2\pm{0.04}$ | $79.9\pm{0.04}$ | $78.1\pm{0.04}$ | $73.0\pm{0.1}$ | $64.1\pm{0.2}$ | $58.1\pm{0.1}$
SSGC | $82.7\pm{0.03}$ | $82.7\pm{0.03}$ | $82.0\pm{0.02}$ | $81.3\pm{0.03}$ | $80.2\pm{0.03}$ | $77.9\pm{0.07}$ | $72.9\pm{0.1}$
DGC | $68.8\pm{0.03}$ | $80.5\pm{0.04}$ | $81.0\pm{0.05}$ | $81.1\pm{0.03}$ | $81.1\pm{0.03}$ | $81.2\pm{0.03}$ | $81.2\pm{0.03}$
gfSGC | $86.7$ | $84.7$ | $83.3$ | $82.1$ | $81.0$ | $80.0$ | $77.6$
gfSSGC | $87.0$ | $87.0$ | $86.2$ | $85.8$ | $85.4$ | $85.3$ | $85.4$
gfDGC | $52.1$ | $82.6$ | $84.6$ | $84.7$ | $84.7$ | $84.6$ | $84.6$

####  5.4.2 Mitigating Over-smoothing

We further provide the node classification accuracies with varying depth
$K\in\\{2,4,8,16,32,64,128\\}$ in Tab. 2, 3, 4 and 5 to demonstrate the over-
smoothing issue as $K$ increases. Specifically, it is observed that the
accuracies of vanilla baselines such as GCN, GAT, and SGC decrease sharply
with the increases in depths. For instance, the accuracies of GCN and GAT on
Cora decrease to about $30\%$ when $K>16$. In some extreme cases, such as GAT
on Citeseer when $K=64$ and $128$ the accuracies are below $10\%$. In general,
those baselines (e.g., SSGC and DGC) specifically designed to overcome over-
smoothing perform much more stable as $K$ increases. In particular, the
accuracies of DGC are almost the same when $K>4$. This phenomenon is
consistent with the empirical results in Fig. 1(e) and 1(f). That is, DGC
mitigates the vanishing gradient issue to prevent over-smoothing.

In contrast to the baselines, our gradient-free models, i.e., gfSGC, gfSSGC
and gfDGC maintain almost invariant performance as $K$ increases. For example,
on Cora, the accuracy of gfSGC decreases from $86.4\%$ to $77.6\%$ when depth
$K$ increases from $2$ to $128$, while SGC greatly decreases from $84.9\%$ to
$61.3\%$. Even for DGC where over-smoothing is not quite obvious, our
counterpart gfDGC can achieve comparable or slightly better performance.
Similar cases can be found for other models on other datasets. An interesting
observation is that GCNII achieves the second-best performance on PubMed under
all layer numbers. One possible reason is that large-scale dataset such as
PubMed prefers the complex architecture of GCNII.

####  5.4.3 Gradient-free v.s. Linear Models

Our gradient-free models gfSGC, gfSSGC and gfDGC can be regarded as the
refinement of their counterparts SGC, SSGC, and DGC, respectively. To validate
the effectiveness of the gradient-free method, it is necessary to directly
compare gfSGC, gfSSGC, and gfDGC with the linear models with the corresponding
filters.

We note that SGC and gfSGC share the same feature extraction process and the
extracted graph filter of SGC is not specially designed to tackle over-
smoothing. Notably, the performance of SGC drastically decreases around
$27.7\%$ and $55.7\%$ for Cora and Cora-ML while gfSGC slightly decreases
around $10.2\%$ and $16.6\%$. This fact directly demonstrates the
effectiveness of the gradient-free method in mitigating vanishing gradients
and further over-smoothing. As for SSGC, although it crafts the graph filter
to balance the global and local context of each node to mitigate over-
smoothing, augmenting SSGC with the gradient-free method can further enhance
their performances and robustness with varying depths. For example, SSGC
drastically decreases around $10.4\%$ and $11.9\%$ for Cora-ML and PubMed
while gfSSGC slightly declines around $-0.7\%$ and $1.8\%$. These results are
consistent with the empirical results in Fig. 1(c) and 1(d). Since DGC itself
can mitigate the vanishing gradient issue quite well, gfDGC just slightly
improves the performance of DGC. In addition, we also observe that gfSSGC
(i.e., gradient-free built upon a different graph filter) outperforms DGC. For
example, the gaps between the best performance of gfSSGC and DGC for these
four datasets are $1.3\%$, $1.3\%$, $3.7\%$, and $5.8\%$, respectively. It
demonstrates that the gradient-free method could potentially be a better way
in tackling the vanishing gradient problem, thus leading to a better
linearized GCN model.

####  5.4.4 Ablation Study

(a) Cora

(b) Cora-ML

(c) Citeseer

(d) Pubmed

Figure 2: Gradient descent v.s. gradient-free with SGC filter.

We conduct the ablation study to validate the necessity of the gradient-free
method for the linearized GCNs. Specifically, we utilize the gradient descent
to optimize $\Lambda$ in Eqn. (17) and term it “Gradient descent”. The
experiment results are shown in Fig. 2. For each case, we set the same values
for the hyperparameter $\lambda$ for “Gradient free” and “Gradient descent”
and set sufficient epoch for “Gradient descent” to ensure convergence. Without
loss of generality, We use the Cora dataset as an example. The experiment
results demonstrate that “Gradient free” outperforms the gradient descent
method for all different depths especially when $K$ is large. On the other
hand, for Cora, Cora-ML and PubMed, there is a trend that the gap between
“Gradient free” and “Gradient descent” becomes larger with the decreasing of
the depth $K$. This indicates that our method indeed mitigates the over-
smoothing problem by preventing gradient computing during training.

###  5.5 Other Benefits of Gradient-Free

####  5.5.1 Comparison of Stability

The advantages of our methods also include stability. As shown in Tab. 2, 3,
4, 5, existing GCNs are unstable in some cases, which is reflected in high
standard errors. For example, on Cora-ml, the standard errors of GCNII are
more than $1.0$. Benefiting from the closed-form solution in Eqn. (17), the
closed-form solution is a deterministic mapping with the inputs as kernel
matrix, one-hot encoding label matrix and the hyperparameter $\lambda$ and is
regardless of the initial values of the weight matrix. Hence, setting
different random seeds will lead to the same classification results and the
standard error is zero.

####  5.5.2 Comparison of Efficiency

Table 6: Training time cost (s) on PubMed dataset.

Model | $K=2$ | $K=8$ | $K=32$ | $K=128$
---|---|---|---|---
GCN | $1.67$ | $1.96$ | $6.58$ | $24.89$
GCNII | $4.10$ | $6.30$ | $20.37$ | $77.57$
SGC | $0.24$ | $0.26$ | $0.30$ | $0.46$
SSGC | $0.24$ | $0.26$ | $0.30$ | $0.47$
DGC | $0.25$ | $0.26$ | $0.30$ | $0.50$
gfSGC | $0.02$ | $0.02$ | $0.02$ | $0.02$
gfSSGC | $0.02$ | $0.02$ | $0.02$ | $0.02$
gfDGC | $0.02$ | $0.02$ | $0.02$ | $0.02$

In this section, we evaluate the training efficiency of our methods compared
with other baselines. For gradient free methods, we report the time cost of
closed-form solution, while for other baselines we report the training time.
It is observed from Tab. 6 that the linearized GCNs are much more efficient
than the nonlinear models (GCN and GCNII). Comparing the gradient-free methods
and linear models, it is demonstrated that utilizing the closed-form solution
in a one-pipeline manner is more time-efficient than the vanilla gradient
descent.

##  6 Conclusions

In this paper, we propose a gradient-free training algorithm to provide
significant improvements over the linearized GCN models through kernelization
and closed-form solutions to the model weights. Sufficient experiments
demonstrate that our methods outperform other typical baselines with less time
cost. The intuition is that current linearized GCNs still perform not well
when the model depth is large under some scenarios. The theoretical and
empirical finding is that when the model depth is large, the gradients of the
model weights tend to be minuscule – “vanishing gradient”. We hope that this
finding will provide new insights to the community to propose alternative
views on tackling the “over-smoothing” problem and boost the performance of
the linearized GCNs.

## References

  * Chen et al. [2020] Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li.  Simple and deep graph convolutional networks.  In International Conference on Machine Learning, pages 1725–1735. PMLR, 2020.
  * Chung [1997] Fan RK Chung.  Spectral graph theory, volume 92.  American Mathematical Soc., 1997.
  * Danel et al. [2020] Tomasz Danel, Przemysław Spurek, Jacek Tabor, Marek Śmieja, Łukasz Struski, Agnieszka Słowik, and Łukasz Maziarka.  Spatial graph convolutional networks.  In International Conference on Neural Information Processing, pages 668–675. Springer, 2020.
  * Fouss et al. [2012] François Fouss, Kevin Francoisse, Luh Yen, Alain Pirotte, and Marco Saerens.  An experimental investigation of kernels on graphs for collaborative recommendation and semisupervised classification.  Neural networks, 31:53–72, 2012.
  * Hamilton et al. [2017] Will Hamilton, Zhitao Ying, and Jure Leskovec.  Inductive representation learning on large graphs.  Advances in neural information processing systems, 30, 2017.
  * Hochreiter and Schmidhuber [1997] Sepp Hochreiter and Jürgen Schmidhuber.  Long short-term memory.  Neural computation, 9(8):1735–1780, 1997.
  * Jain and Kar [2017] Prateek Jain and Purushottam Kar.  Non-convex optimization for machine learning.  Foundations and Trends® in Machine Learning, 10(3-4):142–336, 2017.
  * Kingma and Ba [2014] Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  arXiv preprint arXiv:1412.6980, 2014.
  * Klicpera et al. [2019] Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann.  Predict then propagate: Graph neural networks meet personalized pagerank.  In International Conference on Learning Representations (ICLR 2019), pages 6861–6871, 2019.
  * LeCun et al. [1995] Yann LeCun, Yoshua Bengio, et al.  Convolutional networks for images, speech, and time series.  The handbook of brain theory and neural networks, 3361(10):1995, 1995.
  * Li et al. [2018] Qimai Li, Zhichao Han, and Xiao-Ming Wu.  Deeper insights into graph convolutional networks for semi-supervised learning.  In Thirty-Second AAAI conference on artificial intelligence, 2018\.
  * Menard [2002] Scott Menard.  Applied logistic regression analysis.  Number 106. Sage, 2002.
  * Mohassel and Rindal [2018] Payman Mohassel and Peter Rindal.  Aby3: A mixed protocol framework for machine learning.  In Proceedings of the 2018 ACM SIGSAC conference on computer and communications security, pages 35–52, 2018.
  * Pascanu et al. [2013] Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio.  On the difficulty of training recurrent neural networks.  In International conference on machine learning, pages 1310–1318. PMLR, 2013.
  * Rathee et al. [2020] Deevashwer Rathee, Mayank Rathee, Nishant Kumar, Nishanth Chandran, Divya Gupta, Aseem Rastogi, and Rahul Sharma.  Cryptflow2: Practical 2-party secure inference.  In Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, pages 325–342, 2020.
  * Sen et al. [2008] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad.  Collective classification in network data.  AI magazine, 29(3):93–93, 2008.
  * Tsitsulin et al. [2020] Anton Tsitsulin, John Palowitch, Bryan Perozzi, and Emmanuel Müller.  Graph clustering with graph neural networks.  arXiv preprint arXiv:2006.16904, 2020.
  * Veličković et al. [2018] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio.  Graph attention networks.  In J. International Conference on Learning Representations (ICLR 2018), 2018.
  * Wang et al. [2021] Yifei Wang, Yisen Wang, Jiansheng Yang, and Zhouchen Lin.  Dissecting the diffusion process in linear graph convolutional networks.  Advances in Neural Information Processing Systems, 34:5758–5769, 2021.
  * Welling and Kipf [2016] Max Welling and Thomas N Kipf.  Semi-supervised classification with graph convolutional networks.  In J. International Conference on Learning Representations (ICLR 2017), 2016.
  * Wu et al. [2019] Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger.  Simplifying graph convolutional networks.  In International conference on machine learning, pages 6861–6871. PMLR, 2019.
  * Xu et al. [2018a] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka.  How powerful are graph neural networks?  arXiv preprint arXiv:1810.00826, 2018.
  * Xu et al. [2018b] Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka.  Representation learning on graphs with jumping knowledge networks.  In International conference on machine learning, pages 5453–5462. PMLR, 2018.
  * Yang et al. [2016] Zhilin Yang, William Cohen, and Ruslan Salakhudinov.  Revisiting semi-supervised learning with graph embeddings.  In International conference on machine learning, pages 40–48. PMLR, 2016.
  * Zhang and Chen [2018] Muhan Zhang and Yixin Chen.  Link prediction based on graph neural networks.  Advances in neural information processing systems, 31, 2018.
  * Zhu and Koniusz [2020] Hao Zhu and Piotr Koniusz.  Simple spectral graph convolution.  2020\.
  * Zhu et al. [2022] Yulin Zhu, Yuni Lai, Kaifa Zhao, Xiapu Luo, Mingquan Yuan, Jian Ren, and Kai Zhou.  Adversarial robustness of graph-based anomaly detection, 2022.
  * Zügner et al. [2018] Daniel Zügner, Amir Akbarnejad, and Stephan Günnemann.  Adversarial attacks on neural networks for graph data.  In SIGKDD, pages 2847–2856, 2018.
  * Zügner and Günnemann [2019] Daniel Zügner and Stephan Günnemann.  Adversarial attacks on graph neural networks via meta learning.  In International Conference on Learning Representations, 2019.