# Robust Graph Representation Learning for Local Corruption Recovery

Bingxin Zhou  Shanghai Jiao Tong
UniversityShanghaiChina The University of SydneyNSWAustralia ,  Yuanhong Jiang
Shanghai Jiao Tong
UniversityShanghaiChina ,  Yu Guang Wang  Shanghai Jiao Tong
UniversityShanghaiChina ,  Jingwei Liang  Shanghai Jiao Tong
UniversityShanghaiChina ,  Junbin Gao  The University of SydneyNSWAustralia ,
Shirui Pan  Griffith UniversityQLDAustralia and  Xiaoqun Zhang  Shanghai Jiao
Tong UniversityShanghaiChina

(2023)

###### Abstract.

The performance of graph representation learning is affected by the quality of
graph input. While existing research usually pursues a globally smoothed graph
embedding, we believe the rarely observed anomalies are as well harmful to an
accurate prediction. This work establishes a graph learning scheme that
automatically detects (locally) corrupted feature attributes and recovers
robust embedding for prediction tasks. The detection operation leverages a
graph autoencoder, which does not make any assumptions about the distribution
of the local corruptions. It pinpoints the positions of the anomalous node
attributes in an unbiased mask matrix, where robust estimations are recovered
with sparsity promoting regularizer. The optimizer approaches a new embedding
that is sparse in the framelet domain and conditionally close to input
observations. Extensive experiments are provided to validate our proposed
model can recover a robust graph representation from black-box poisoning and
achieve excellent performance.

graph neural networks, constrained optimization, spectral transforms, graph
denoising

††copyright: acmcopyright††journalyear: 2023††copyright:
acmlicensed††conference: Proceedings of the ACM Web Conference 2023; May 1–5,
2023; Austin, TX, USA††booktitle: Proceedings of the ACM Web Conference 2023
(WWW ’23), May 1–5, 2023, Austin, TX, USA††price: 15.00††doi:
10.1145/3543507.3583399††isbn: 978-1-4503-9416-1/23/04††ccs: Computing
methodologies Artificial intelligence††ccs: Computing methodologies Neural
networks

##  1\. Introduction

Graph neural networks (GNNs) have received tremendous success in the past few
years (Bronstein et al., 2017; Wu et al., 2020a; Zhang et al., 2020; Zhou et
al., 2020). Graphs, as the input of GNNs, record useful features and
structural information. They exist widely in many fields, such as biomedical
science (Ahmedt-Aristizabal et al., 2021), social networks (Fan et al., 2019),
and recommender systems (Wu et al., 2020b).

Similar to other types of real-world data, inaccurate observations are
ubiquitous in graphs with a noticeable side-effect for graph representation
learning. For instance, fraudulent users in social media tend to fake user
avatars or online activities. A recommender might be dysfunctional by
mislabeled items or users. Such disruptive observations hinder the model
fitting and prediction. The feature aggregation in graph representation
learning accentuates the negative influence of irregular entities on their
neighborhoods, resulting in a misleading latent feature representation for the
predictor.

Figure 1. Illustrative architecture of the proposed MAGnet. Input feature
attributes (gray) are assumed locally corrupted. The first module constructs a
mask matrix (red) as the indices of locally-corrupted input feature attributes
(gray). They are sent to an inertia ADMM optimizer (yellow) to iterate a
robust feature representation, which is functioned as hidden embeddings by
typical graph convolutional layers. It can be encoded by other convolutions or
sent to a predictor (blue).

Existing works are aware of the harmful graph anomalies. i) Graph anomaly
detection (Ding et al., 2019; Ma et al., 2021; Peng et al., 2020; Zhu et al.,
2020) identifies the small portion of problematic nodes, such as fraudulent
users in a social network graph; ii) graph defense(Dai et al., 2018; Xu et
al., 2020; Zügner and Günnemann, 2019) refines the learning manner of a
classifier to provide promising predictions against potential misleading
entities that hurt the model training; iii) optimization-based graph
convolutions smooth out global noise, e.g., observation errors in data
collection, by special regularization designs (Chen et al., 2021; Liu et al.,
2021b; Zhou et al., 2021; Zhu et al., 2021). However, the first approach
detects the whole irregular node rather than individual node attributes, and
it does not amend the flawed representation of the identified outlier. The
second approach provides an adequate solution to protect the prediction
performance, but most researches focus on graph rewiring, as edges are
believed more vulnerable to adversarial attacks. The third choice, although
operates on node attributes, only makes implicit optimization against local
corruptions. They usually assume that feature corruptions are normally
observed in all inputs.

In this paper, we propose an alternative approach by developing a ‘detect-and-
then-recover’ strategy to protect graph representation learning from a small
portion of hidden corruptions in the input node attributes. In particular, an
unsupervised encoder module first detects suspicious attributes and assigns a
mask matrix to expose their positions. The detector requires no prior
knowledge of the distribution of the anomalous attributes. The constructed
mask guides a robust reconstruction of the initial input with sparsity
promoting regularizers. To guarantee an expressive representation that
simultaneously reconstructs irregular attributes, preserves small-energy
patterns, and eliminates global noise, the regularization is operated on
multi-scale framelet coefficients (Dong, 2017; Zheng et al., 2021). Meanwhile,
the posterior mask guarantees that the signal recovery is predominantly
conducted at the essential (anomalous) spots. The optimized embedding is
updated iteratively, which acts similarly to a graph convolutional layer that
constantly smooths the hidden feature representation for GNN prediction tasks.

Combining the three key ingredients of Mask, ADMM, and Graph, we name our
model as MAGnet. Figure 1 illustrates the three components of unsupervised
mask construction, localized robust optimization, and graph representation
learning. MAGnet detects local corruptions in an unsupervised manner and
approximates a robust graph representation. As indicated above, the
alternating direction method of multipliers (ADMM) algorithm (Gabay and
Mercier, 1976) is adopted in our optimization procedure.

##  2\. Problem Formulation

We use ${\mathcal{G}}=({\mathcal{V}},{\mathcal{E}},{\bm{X}})$ to denote an
undirected attributed graph with $n=|{\mathcal{V}}|$ nodes and
$|{\mathcal{E}}|$ edges, where the latter is usually described by an adjacency
matrix ${\bm{A}}\in\mathbb{R}^{n\times n}$. The observed $d$-dimensional node
features ${\bm{X}}\in\mathbb{R}^{n\times d}$ is a noised version of the ground
truth signal $\bar{{\bm{U}}}$, which reads
${\bm{X}}=\bar{{\bm{U}}}+{\bm{E}}_{1}+{\bm{E}}_{2}$ We call ${\bm{E}}_{1}$
global noise and ${\bm{E}}_{2}$ outliers or local corruptions. The main
difference between ${\bm{E}}_{1}$ and ${\bm{E}}_{2}$ is that the former might
universally exist on the entire graph, and the latter generally takes a small
chance of existence so it would not be observed from a large set of nodes or
node attributes. We hereby make the following assumptions on the properties of
$\bar{{\bm{U}}},{\bm{E}}_{1}$ and ${\bm{E}}_{2}$:

  1. (a)

The global noise ${\bm{E}}_{1}$ follows some distribution ${\mathcal{D}}$ with
an expectation of $0$;

  2. (b)

The outliers take a small portion of the entire graph, or the ${\bm{E}}_{2}$
is a sparse matrix; and

  3. (c)

The observations ${\bm{X}}$ are close to $\bar{{\bm{U}}}$ at regular
locations.

The associated objective function to estimate $\bar{{\bm{U}}}$ reads

(1) $\displaystyle\min_{{\bm{U}}}~{}\alpha{\rm Reg}({\bm{U}})+{\rm
Loss}({\bm{E}}_{2})\quad\mathrm{s.t.}\quad~{}{\bm{X}}|_{{\bm{M}}}=({\bm{U}}+{\bm{E}}_{1}+{\bm{E}}_{2})|_{{\bm{M}}},$

where $\alpha$ is tunable, and ${\bm{M}}$ is a mask matrix of outliers
indices. The ${\rm Reg}(\cdot)$ and ${\rm Loss}(\cdot)$ denote the regularizer
and loss function satisfying assumptions (a) and (b), respectively.

  * •

Choice of ${\rm Loss}({\bm{E}}_{2})$:  The loss function (1) finds a robust
approximation ${\bm{U}}$ from the input feature ${\bm{X}}$. As required by
assumption (b), a measure with respect to the sparsity of ${\bm{E}}_{2}$ has
to be optimized. The best choice for sparsity, in theory, is $\ell_{0}$-norm
which counts the number of nonzero entries in ${\bm{E}}_{2}$. Unfortunately,
the $\ell_{0}$ constrained problem is NP-hard. In substitute, the
$\ell_{1}$-norm allows feasible solution for (1) that promotes a good sparsity
measure for ${\bm{E}}_{2}$ (Chen et al., 2015). Also (Li et al., 2017; Peng et
al., 2018) implemented residual analysis-based _anomaly detection_ methods for
labeling suspicious outliers.

  * •

Choice of ${\rm Reg}({\bm{U}})$:  The regularization on ${\bm{U}}$ is a
penalty complementary to the loss function, which controls the noise level of
${\bm{X}}$ by the smoothness of ${\bm{U}}$, and it is usually quantified by
some energy measurements. For instance, GCN (Kipf and Welling, 2017) utilizes
normalized Dirichlet energy of ${\bm{U}}$ by ${\rm
tr}({\bm{U}}^{\top}\tilde{{\bm{L}}}{\bm{U}})$, where $\tilde{{\bm{L}}}$
denotes the normalized graph Laplacian from
$\tilde{{\bm{L}}}={\bm{I}}-{\bm{D}}^{-\frac{1}{2}}{\bm{A}}{\bm{D}}^{-\frac{1}{2}}$
with the adjacency matrix ${\bm{A}}$ and its degree matrix ${\bm{D}}$.
Minimizing such energy encourages message transmissions among connected nodes.
By extracting the summary of neighborhood space, unnoticeable noise is likely
to be smoothed out. In addition, minimizing the Dirichlet energy implies a
low-rank smooth solution to ${\bm{U}}$ (Monti et al., 2017). Such a _graph
smoothing effect_ (Chen et al., 2021; Liu et al., 2021b; Zhu et al., 2021) has
been implemented in many spatial-based graph convolution designs (Klicpera et
al., 2018; Wu et al., 2019; Xu et al., 2018a). Alternatively, spectral-based
methods regularize the graph signal in a transformed domain by ${\bm{L}}$. For
example, Dong (Dong, 2017) and Zhou et al. (Zhou et al., 2021) minimized the
$\ell_{1}$-norm total variation of framelet coefficients, and Mahmood et al.
(Mahmood et al., 2018) considered a similar regularization in the wavelet
domain. As the total variation reflects redundant local fluctuations, a
solution to minimize it is believed to remove noise and preserve local
patterns at the same time.

  * •

Restriction on ${\bm{E}}_{1}+{\bm{E}}_{2}$:  Compared to the main ingredients
of the objective function, the treatment of the fidelity constraint is rather
trivial when the outliers ${\bm{E}}_{2}$ do not exist. Usually a regularizer
is adopted to minimize the difference between ${\bm{X}}$ and
$\bar{{\bm{U}}}+{\bm{E}}_{1}$, i.e., ${\bm{X}}-{\bm{U}}$. However, when
${\bm{E}}_{2}$ is assumed to exist at a small proportion, it is undesired to
force ${\bm{U}}$ to approximate ${\bm{X}}$ especially on anomalous locations.
Instead, a conditional approximation is placed with the index matrix
${\bm{M}}$, in which case only attributes at regular positions are required
aligned. The target is then $\min{\rm
Reg}\left({\bm{M}}\odot({\bm{X}}-{\bm{U}})\right)$ with some penalty ${\rm
Reg}(\cdot)$, and it can be appended to the main objective by

(2) $\min_{{\bm{U}}}\alpha{\rm Reg}({\bm{U}})+{\rm
Loss}\left({\bm{M}}\odot({\bm{X}}-{\bm{U}})\right).$

The above optimization for graph signal recovery is well-defined.
Nevertheless, it has three issues in practice. First, a direct minimization of
the Dirichlet energy in the spatial domain usually falls into the pitfall of
over-smoothing, where the recovered graph loses expressivity drastically
(Balcilar et al., 2020). On the other hand, spectral transforms can be
sophisticated and time-consuming, which is generally circumvented by the
majority of studies. Second, fixing the $\ell_{1}$ or $\ell_{2}$ norm can be
too restricted for an arbitrary dataset or application, which could recover a
less robust graph representation that affects the prediction task later on.
Last but not least, attaining the mask matrix ${\bm{M}}$ in (2) can be nasty
in practice, as the prior knowledge of ${\bm{M}}$ is generally inaccessible.

In order to best handle the identified problems, we propose an objective
function design that combines masked $\ell_{q}$ ($1\leq q\leq 2$)
reconstruction error term and $\ell_{p}$ ($0\leq p\leq 1$) regularization,
i.e.,

(3)
$\min_{{\bm{U}}}\|{\bm{\nu}}\bm{{\mathcal{W}}}{\bm{U}}\|_{p,G}+\frac{1}{2}\|{\bm{M}}\odot({\bm{U}}-{\bm{X}})\|^{q}_{q,G},$

which is convex at $p=1$ and non-convex when $0\leq p<1$, regardless of $q$.
Equation (3) enforces the sparse representation by a graph framelet system
(Dong, 2017; Wang and Zhuang, 2019; Zheng et al., 2021, 2022). Through
framelet transforms, an input graph signal is decomposed into a low-pass
coefficient matrix and multiple high-pass coefficient matrices. The former
includes general global information about the graph, and the latter portrays
the local properties of the graph at different degrees of detail.

Specifically, the decomposition is realized by a set of multi-scale and multi-
level framelet decomposition operators $\bm{{\mathcal{W}}}$ under the framelet
system, with each $\bm{{\mathcal{W}}}_{k,l}$ be an orthonormal basis at
$(k,l)\in\\{(0,J)\\}\cup\\{(1,1),\dots,(1,J),\dots(K,1),\dots,(K,J)\\}$. This
decomposition operator forms the spectral representation of ${\bm{U}}$, where
its global trend is reflected in the low-pass coefficients
$\bm{{\mathcal{W}}}_{0,J}{\bm{U}}$. Meanwhile, the high-pass coefficients
$\bm{{\mathcal{W}}}_{k,l}{\bm{U}}$ records detailed information at scale $k$
and level $l$ ($1\leq k\leq K,1\leq l\leq J$). They reflect local patterns or
noises of the signal. The coefficients at a higher level $l$ contain more
localized information with smaller energy.

In addition, we replace $\alpha$ in (2) with a set of hyper-parameters
${\bm{\nu}}$ to normalize the high-frequency framelet coefficients
$\bm{{\mathcal{W}}}{\bm{U}}$ of the approximated ${\bm{U}}$ in different
scales. For example, an initialization $\nu_{0}$ defines ${\bm{\nu}}_{0,J}=0$
for the low-pass coefficients and ${\bm{\nu}}_{k,l}=4^{-l-1}\nu_{0}$ for high-
pass coefficients.

The signal reconstruction error $\|{\bm{M}}\odot({\bm{U}}-{\bm{X}})\|_{q}$
guarantees the optimal representation ${\bm{U}}$ to be conditionally close to
the masked feature matrix ${\bm{X}}$ of the given graph. We generalize the
conventional $\ell_{2}$ error to a $\ell_{q}$ penalty ($1\leq q\leq 2$).
Meanwhile, the $\ell_{p}$ regularization measures the graph total variation
(Sandryhaila and Moura, 2014) in the framelet domain, where pursuing a small
total variation recovers the graph signal from corrupted attribute noises.
When $p$ approaches $1$ from $2$, the framelet representation
$\bm{{\mathcal{W}}}{\bm{U}}$ gains increasing sparsity.

We treat $p,q$ as tunable parameters to allow sufficient freedom in our design
for selecting the most qualified optimization model that fits the data and
training requirements. Furthermore, we replace the ordinary Euclidean
$\ell_{k}$-norm with a graph $\ell_{k}$-norm, denoted as $\ell_{k,G}$, to
assign higher penalties to influential high-degree nodes. For an arbitrary
node ${\bm{v}}_{i}$ of degree ${\bm{D}}_{ii}$,
$\|{\bm{v}}_{i}\|_{k,G}:=\left(\|{\bm{v}}_{i}\|^{k}\cdot{\bm{D}}_{ii}\right)^{\frac{1}{k}}$.

Compared to the initial design in (1), (3) made three adjustments to tackle
the identified issues. First, minimizing the first component smooths out
${\bm{E}}_{1}$ under the assumption (a) from high-pass framelet coefficients,
which avoids information loss by spatial Dirichlet energy minimization. In
other words, the global noise ${\bm{E}}_{1}$ is removed without sacrificing
small-energy features. Secondly, we adopt the values of $p,q$ to adaptively
restrict the sparsity of recovered graph with $p\in[1,2],q\in[0,1]$. As
introduced in Section 4, the optimization can be solved by an inertial version
of the alternating direction method of multipliers with promising convergence.

A potential solution to the unreachable mask matrix ${\bm{M}}$ is to add a
sub-problem of optimizing (3), which introduces a two-stage optimization
problem. However, this approach blows up the difficulty of solving the
existing problem and the mask region could be too complicated to reveal.
Instead, we consider an unsupervised GNN scheme to automate the discovery of
anomalous positions. We approximate the anomaly score of ${\bm{X}}$ with a
classic graph anomaly detection scheme that looks for the reconstruction error
between the observed and reconstructed matrices from neural networks.

##  3\. Mask Matrix Generation with Graph Anomaly Detection

Graph anomaly detection is an important subproblem of the general graph signal
recovery where outliers are assumed to exist in the input. A detector
identifies nodes with ${\bm{E}}_{2}$ as _community anomalies_ (Ma et al.,
2021), which are defined as nodes that have distinct attribute values compared
to their neighbors of the same community. The underlying assumption here is
that the outlier is sparse and their coefficients are antipathetic from the
smooth graph signal ${\bm{U}}$. We hereby consider GNN-based algorithms to
investigate the difference between each node from the representation of its
local community.

###  3.1. Graph Autoencoder

Autoencoder is a powerful tool for reconstructing corrupted objects (Aggarwal,
2017; Kovenko and Bogach, 2020). GAE (Kipf and Welling, 2016) is a GCN-based
autoencoder, which has become a frequent solution in graph anomaly detection
(Ding et al., 2019; Peng et al., 2020; Zhu et al., 2020). A GAE layer takes
the information of ${\mathcal{G}}$ to obtain an embedding
${\bm{Z}}\in\mathbb{R}^{n\times h}$ of a hidden size $h$ by ${\bm{Z}}={\rm
GCN}({\bm{X}},{\bm{A}})$. When recovering the graph attributes from its hidden
embedding, a feed-forward network is trained to find ${\bm{X}}^{\prime}={\rm
FFN}({\bm{Z}})$, a smoothed version of ${\bm{X}}$ that is believed to remove
essential noise or minor corruptions of the raw input ${\bm{X}}$. In (Ding et
al., 2019; Peng et al., 2018) for graph anomaly detection, the learning
objective of the neural network is to best reconstruct the graph attribute
${\bm{X}}^{\prime}$, which loss function is the weighted average of the
squared _approximation errors_ , i.e.,
${\mathcal{L}}=\|{\bm{X}}-{\bm{X}}^{\prime}\|_{2}$.

Once the graph is reconstructed, it is straightforward to find outliers by
comparing the input and output representation. For node entities, a corrupted
object has different patterns from its local community, so its initial
representation should be distinct from the smoothed representation. The
approximation error is thus an appropriate indicator for diagnosing such
divergence. For a particular node ${\bm{v}}_{i}$, we calculate ${\rm
score}({\bm{v}}_{i})=\|{\bm{x}}_{i}-{\bm{x}}_{i}^{\prime}\|_{2}$.

While the outliers exist rarely, we adopt $\ell_{2}$ penalty for approximating
the approximation error (and anomalous scores) for two reasons. First,
reconstructing the noisy signal by an autoencoder aims at finding an overall
optimal representation without extreme errors. In this sense, the MSE loss is
more sensitive to large errors than the MAE loss. Meanwhile, as we do not
assume prior knowledge of the distribution of data noise, Gaussian noise (in
alignment with $\ell_{2}$ penalty) is more general among other choices (such
as the Laplacian distribution with $\ell_{1}$ penalty). On the other hand, the
sparsity requirement is satisfied in the later stages of our implementation.
As introduced in the next section, the mask matrix construction is instructed
by an MAE-loss, which favors a sparse distribution of the local noise in the
attribute matrix.

Figure 2. The sparsity of GAE-approximated $1-{\bm{M}}$ is directly controlled
by the threshold $\tau$.

###  3.2. Mask Matrix Generation

Our primary focus is on graph recovery without explicitly considering the
disordered node connections or the adjacency matrix. Also, unlike conventional
anomaly detection tasks that locate the problematic nodes, we aim at
generating a mask matrix of size $n\times d$ that identifies the corrupted
node attributes, and it is defined as

(4) ${\bm{M}}=1-{\rm threshold}(\|{\bm{X}}-{\bm{X}}^{\prime}\|_{1},\tau).$

The established ${\bm{M}}$ approximates the element-wise errors by
differentiating the raw and the recovered feature matrices from a trained
graph autoencoder. Optionally, ${\bm{M}}$ can be binarized with a tunable
threshold $\tau\in(0,1)$. Consequently, ${\bm{M}}_{ij}=1$ suggests assigning a
new value to the $j$th feature of node $i$ to avoid potential corruption.

Under assumption (b) that ${\bm{E}}_{2}$ exists rarely in node attributes, the
majority of the mask matrix should be $1$, i.e., $1-{\bm{M}}$ is a sparse
matrix. This requirement is guaranteed by both the autoencoder algorithm and
the thresholding function. Because the encoder smoothes ${\bm{U}}$ to approach
${\bm{X}}$ and the magnitude of ${\bm{E}}_{1}$ is assumed smaller than
${\bm{E}}_{2}$’s, the difference between ${\bm{X}}$ and ${\bm{X}}^{\prime}$
mainly comes from ${\bm{E}}_{2}$. On top of that, the tunable $\tau$ controls
the sparsity of ${\bm{M}}$. Figure 2 provides an empirical example with three
citation networks that are locally perturbed by the attribute injection (Ding
et al., 2019). A large $\tau$ reduces the number of non-zero elements in
$1-{\bm{M}}$ from a considerably sparse level to a lower degree.

##  4\. Optimization algorithm

This section describes the optimization algorithm to solve (3). As described
in (6), it is an inertial version of the celebrated alternating direction
method of multipliers (ADMM) (Gabay and Mercier, 1976).

###  4.1. An inertial ADMM

Denote ${\bm{Z}}={\bm{\mathcal{W}}}{\bm{U}}$, then we can rewrite (3) as

(5) $\displaystyle\min_{{\bm{U}},{\bm{Z}}}$
$\displaystyle~{}\|{\bm{\nu}}{\bm{Z}}\|_{p,G}+\tfrac{1}{2}\|{\bm{M}}\odot({\bm{U}}-{\bm{X}})\|^{q}_{q,G},\quad\mathrm{s.t.}$
$\displaystyle{\bm{Z}}={\bm{\mathcal{W}}}{\bm{U}}.$

This forms a standard formulation of problems that can be solved by ADMM. The
associated augmented Lagrangian to (5) reads

$\displaystyle{\mathcal{L}}({\bm{U}},{\bm{Z}};{\bm{Y}}):=$
$\displaystyle\|{\bm{\nu}}{\bm{Z}}\|_{p,G}+\tfrac{1}{2}\|{\bm{M}}\odot({\bm{U}}-{\bm{X}})\|^{q}_{q,G}$
$\displaystyle+\langle{\bm{Y}},\,{\bm{\mathcal{W}}}{\bm{U}}-{\bm{Z}}\rangle+\tfrac{\gamma}{2}{|\kern-1.125pt|}{\bm{\mathcal{W}}}{\bm{U}}-{\bm{Z}}{|\kern-1.125pt|}^{2},$

where $\gamma>0$. We consider the inertial ADMM motivated by Alvarez & Attouch
(Alvarez and Attouch, 2001) to secure an efficient solver, which defines

(6) $\displaystyle{\bm{Z}}_{k+1}$
$\displaystyle=\operatorname*{arg\,min}_{{\bm{Z}}}~{}\|{\bm{\nu}}{\bm{Z}}\|_{p,G}+\tfrac{\gamma}{2}{|\kern-1.125pt|}{\bm{Z}}-(2{\bm{Y}}_{k}-\widetilde{\bm{{V}}}_{k})/\gamma{|\kern-1.125pt|}^{2},$
$\displaystyle{\bm{V}}_{k+1}$
$\displaystyle={\bm{Y}}_{k}-\gamma{\bm{Z}}_{k+1},$
$\displaystyle\widetilde{\bm{{V}}}_{k+1}$
$\displaystyle={\bm{V}}_{k+1}+a_{k}({\bm{V}}_{k+1}-{\bm{V}}_{k}),$
$\displaystyle{\bm{U}}_{k+1}$
$\displaystyle=\operatorname*{arg\,min}_{{\bm{U}}}~{}\tfrac{1}{2}\|{\bm{M}}\odot({\bm{U}}-{\bm{X}})\|^{q}_{q,G}+\tfrac{\gamma}{2}{|\kern-1.125pt|}{\bm{\mathcal{W}}}{\bm{U}}+\widetilde{\bm{{V}}}_{k+1}/\gamma{|\kern-1.125pt|}^{2},$
$\displaystyle{\bm{Y}}_{k+1}$
$\displaystyle=\widetilde{\bm{{V}}}_{k+1}+\gamma{\bm{\mathcal{W}}}{\bm{U}}_{k+1},$

where $\widetilde{\bm{{V}}}_{k+1}$ is the inertial term and $a_{k}$ is the
inertial parameter. We refer to (Boţ and Csetnek, 2016; Boţ et al., 2015), and
the references therein for the convergence analysis of the above inertial ADMM
scheme.

Table 1. Average performance for node classification over $10$ repetitions.

| attribute injection | meta attack
---|---|---
Module | Cora | Citeseer | PubMed | Coauthor-CS | Wiki-CS | Wisconsin | Texas | OGB-arxiv | Cora | Citeseer | PubMed
clean |  $81.26$$\pm 0.65$ |  $71.77$$\pm 0.29$ |  $79.01$$\pm 0.44$ |  $90.19$$\pm 0.48$ |  $77.62$$\pm 0.26$ |  $56.47$$\pm 5.26$ |  $65.14$$\pm 1.46$ |  $71.10$$\pm 0.21$ |  $81.26$$\pm 0.65$ |  $71.77$$\pm 0.29$ |  $79.01$$\pm 0.44$
GCN |  $69.06$$\pm 0.74$ |  $57.58$$\pm 0.71$ |  $67.69$$\pm 0.40$ |  $82.41$$\pm 0.23$ |  $65.44$$\pm 0.23$ |  $48.24$$\pm 3.19$ |  $58.92$$\pm 2.02$ |  $68.42$$\pm 0.15$ |  $75.07$$\pm 0.64$ |  $55.32$$\pm 2.22$ |  $72.88$$\pm 0.30$
APPNP |  $68.46$$\pm 0.81$ |  $60.04$$\pm 0.59$ |  $68.70$$\pm 0.47$ |  $71.14$$\pm 0.54$ |  $56.53$$\pm 0.72$ |  $61.76$$\pm 5.21$ |  $59.46$$\pm 0.43$ | OOM |  $73.49$$\pm 0.59$ |  $55.67$$\pm 0.28$ |  $70.63$$\pm 1.07$
GNNGuard |  $61.96$$\pm 0.30$ |  $54.94$$\pm 1.00$ |  $68.50$$\pm 0.38$ |  $80.67$$\pm 0.88$ |  $65.69$$\pm 0.32$ |  $46.86$$\pm 1.06$ |  $59.19$$\pm 0.81$ |  $65.75$$\pm 0.32$ |  $72.02$$\pm 0.61$ |  $57.64$$\pm 1.31$ |  $71.10$$\pm 0.32$
ElasticGNN |  $77.74$$\pm 0.79$ |  $64.61$$\pm 0.85$ |  $71.23$$\pm 0.21$ |  $79.91$$\pm 1.39$ |  $64.18$$\pm 0.53$ |  $53.33$$\pm 2.45$ |  $59.77$$\pm 3.24$ |  $41.34$$\pm 0.38$ |  $79.25$$\pm 0.50$ |  $67.29$$\pm 1.17$ |  $71.95$$\pm 0.52$
AirGNN |  $76.22$$\pm 3.75$ |  $62.14$$\pm 0.82$ |  $74.73$$\pm 0.43$ |  $80.18$$\pm 0.31$ |  $71.36$$\pm 0.20$ |  $61.56$$\pm 0.72$ |  $59.46$$\pm 1.24$ |  $52.32$$\pm 0.58$ |  $78.94$$\pm 0.45$ |  $65.58$$\pm 0.63$ |  $78.58$$\pm 0.71$
MAGnetone |  $75.88$$\pm 0.42$ |  $59.22$$\pm 0.34$ |  $68.97$$\pm 0.21$ |  $84.04$$\pm 0.56$ |  $70.83$$\pm 0.29$ |  $55.49$$\pm 1.53$ |  $60.27$$\pm 1.73$ |  $68.24$$\pm 0.30$ |  $77.11$$\pm 0.45$ |  $62.49$$\pm 1.70$ |  $75.83$$\pm 2.05$
MAGnetgae |  $79.07$$\pm 0.56$ |  $64.79$$\pm 0.73$ |  $75.41$$\pm 0.35$ |  $86.50$$\pm 0.37$ |  $72.40$$\pm 0.21$ |  $64.31$$\pm 2.60$ |  $60.81$$\pm 2.18$ |  $68.68$$\pm 0.03$ |  $79.04$$\pm 0.50$ |  $67.40$$\pm 0.73$ |  $78.63$$\pm 0.32$
MAGnettrue |  $78.48$$\pm 0.67$ |  $68.55$$\pm 0.74$ |  $75.63$$\pm 0.56$ |  $89.23$$\pm 0.40$ |  $75.50$$\pm 0.20$ |  $65.69$$\pm 1.57$ |  $60.54$$\pm 2.16$ |  $69.57$$\pm 0.23$ |  $80.88$$\pm 0.37$ |  $67.46$$\pm 0.95$ |  $79.16$$\pm 0.41$

1 0.38,1.54- $100\%$ 0.33,0.77- $50\%$ 0.28,0.01- $0\%$ 0.4,-0.76- $-50\%$
0.45,-1.515- $-100\%$

###  4.2. Subproblems

The solutions to the subproblems of ${\bm{Z}}_{k+1}$ and ${\bm{U}}_{k+1}$ in
(6) depend on $p$ and $q$, respectively. Here we enumerate the special cases
of $p=\\{0,1\\}$ and $q=\\{1,2\\}$. Other choices of $p$, such as
$p=\frac{1}{2}$, are discussed in (Xu et al., 2012) and the references
therein.

Different values of $p$ affects the thresholding operator in updating
${\bm{Z}}_{k+1}$. When $p=1$, $\|{\bm{\nu}}{\bm{Z}}\|_{p,G}$ becomes the
$\ell_{1}$-norm and its update requires a soft-thresholding, that is,

$S_{\alpha}(x)=\operatorname{sign}(x)\odot\max\big{\\{}|x|-\alpha,0\big{\\}}.$

When $p=0$, hard-thresholding is applied with
$H_{\alpha}(x)=\left\\{\begin{aligned} x~{}&~{}~{}|x|>\alpha\\\
0~{}&~{}~{}|x|\leq\alpha\end{aligned}\right.$.

Compared to ${\bm{Z}}_{k+1}$, the update of ${\bm{U}}_{k+1}$ in (6) is more
complicated as it involves more regularization terms. When $q=2$, the
objective is a quadratic problem. With
${\bm{\mathcal{W}}}^{\top}{\bm{\mathcal{W}}}=\mathrm{Id}$, we directly have

${\bm{U}}_{k+1}=\frac{{\bm{M}}\odot{\bm{X}}-{\bm{\mathcal{W}}}^{\top}\widetilde{\bm{{V}}}_{k+1}}{{\bm{M}}+\gamma},$

which requires an element-wise division. Since the fast approximation of
${\bm{\mathcal{W}}}$ is implemented by the Chebyshev approximation, it happens
when the approximation degree is considerably small that the approximation has
a noticeable error, i.e.,
${\bm{\mathcal{W}}}^{T}{\bm{\mathcal{W}}}\neq\mathrm{Id}$. Alternatively, the
descent type methods such as gradient descent, and conjugate gradient can be
applied to inexactly solve the sub-problem with $I$ steps of iteration. At the
$i$th ($i\leq I$) iteration,

$\displaystyle{\bm{U}}^{(i+1)}$
$\displaystyle={\bm{U}}^{(i)}-\alpha\big{(}{\bm{M}}\odot({\bm{U}}^{(i)}-{\bm{X}})+\gamma{\bm{\mathcal{W}}}^{\top}({\bm{\mathcal{W}}}{\bm{U}}^{(i)}+\widetilde{\bm{{V}}}_{k+1}/\gamma)\big{)}$

where $\alpha$ is the step-size. The solution is then
${\bm{U}}_{k+1}={\bm{U}}^{(I)}$.

In the case of $q=1$, let ${\bm{Q}}={\bm{U}}-{\bm{X}}$ and consider

$\tfrac{1}{2}\|{\bm{M}}\odot{\bm{Q}}\|_{1,G}+\tfrac{\gamma}{2}{|\kern-1.125pt|}{\bm{Q}}+{\bm{X}}+{\bm{\mathcal{W}}}^{\top}\widetilde{\bm{{V}}}_{k+1}/\gamma{|\kern-1.125pt|}^{2}.$

Let ${\bm{Q}}_{k+1}$ be the soft-thresholding of
$-{\bm{X}}-{\bm{\mathcal{W}}}^{\top}\widetilde{\bm{{V}}}_{k+1}/\gamma$ and we
have

(7) ${\bm{U}}_{k+1}={\bm{Q}}_{k+1}+{\bm{X}}.$

Table 2. Average performance with different choices on $p$ and $q$ for node
classification.

Module | attribute injection | meta attack
---|---|---
mask | reg ($p$) | loss ($q$) | Cora | Citeseer | PubMed | Coauthor-CS | Wiki-CS | Cora | Citeseer | PubMed
N/A | $L_{2}^{\star}$ | $L_{2}$ |  $69.06$$\pm 0.74$ |  $57.58$$\pm 0.71$ |  $67.69$$\pm 0.23$ |  $82.41$$\pm 0.40$ |  $65.44$$\pm 0.23$ |  $75.07$$\pm 0.64$ |  $55.32$$\pm 0.64$ |  $72.88$$\pm 0.30$
ONE | $L_{0}$ | $L_{1}$ |  $58.36$$\pm 0.89$ |  $57.30$$\pm 0.74$ |  $65.77$$\pm 1.03$ |  $82.17$$\pm 0.41$ |  $64.58$$\pm 0.21$ |  $71.21$$\pm 1.12$ |  $55.38$$\pm 2.12$ |  $71.52$$\pm 0.43$
$L_{2}$ |  $68.74$$\pm 0.22$ |  $54.07$$\pm 1.23$ |  $58.52$$\pm 1.02$ |  $80.63$$\pm 0.59$ |  $63.63$$\pm 0.27$ |  $74.46$$\pm 0.60$ |  $57.75$$\pm 2.23$ |  $59.76$$\pm 1.91$
$L_{1}$ | $L_{1}$ |  $69.12$$\pm 0.57$ |  $57.58$$\pm 0.71$ |  $67.69$$\pm 0.40$ |  $82.17$$\pm 0.41$ |  $64.63$$\pm 0.18$ |  $75.07$$\pm 0.64$ |  $55.32$$\pm 2.22$ |  $72.88$$\pm 0.65$
$L_{2}$ |  $75.88$$\pm 0.42$ |  $59.22$$\pm 0.34$ |  $68.97$$\pm 0.21$ |  $84.04$$\pm 0.56$ |  $70.83$$\pm 0.29$ |  $77.11$$\pm 0.45$ |  $62.49$$\pm 1.70$ |  $75.83$$\pm 0.35$
GAE | $L_{0}$ | $L_{1}$ |  $68.42$$\pm 1.15$ |  $54.38$$\pm 0.54$ |  $67.74$$\pm 0.71$ |  $83.95$$\pm 0.52$ |  $61.96$$\pm 0.16$ |  $77.42$$\pm 1.08$ |  $56.13$$\pm 0.47$ |  $78.42$$\pm 0.65$
$L_{2}$ |  $66.34$$\pm 0.81$ |  $56.29$$\pm 1.18$ |  $59.15$$\pm 0.85$ |  $83.88$$\pm 0.55$ |  $64.67$$\pm 0.29$ |  $77.03$$\pm 0.78$ |  $55.84$$\pm 1.37$ |  $70.82$$\pm 0.38$
$L_{1}$ | $L_{1}$ |  $72.76$$\pm 0.40$ |  $63.60$$\pm 0.66$ |  $75.41$$\pm 0.35$ |  $86.02$$\pm 0.59$ |  $72.40$$\pm 0.21$ |  $78.18$$\pm 0.56$ |  $63.22$$\pm 1.56$ |  $78.63$$\pm 0.32$
$L_{2}$ |  $76.81$$\pm 0.98$ |  $64.79$$\pm 0.14$ |  $71.13$$\pm 0.25$ |  $86.50$$\pm 0.37$ |  $60.08$$\pm 0.39$ |  $79.04$$\pm 0.50$ |  $67.40$$\pm 0.73$ |  $74.47$$\pm 0.30$
TRUE | $L_{0}$ | $L_{1}$ |  $77.15$$\pm 0.74$ |  $68.14$$\pm 0.85$ |  $74.40$$\pm 0.56$ |  $88.14$$\pm 0.46$ |  $72.42$$\pm 0.29$ |  $80.88$$\pm 0.37$ |  $67.46$$\pm 0.95$ |  $79.16$$\pm 0.41$
$L_{2}$ |  $76.44$$\pm 0.59$ |  $65.02$$\pm 0.97$ |  $68.12$$\pm 1.24$ |  $87.01$$\pm 0.24$ |  $71.51$$\pm 0.20$ |  $80.57$$\pm 0.51$ |  $67.21$$\pm 1.63$ |  $71.90$$\pm 0.41$
$L_{1}$ | $L_{1}$ |  $78.48$$\pm 0.67$ |  $68.55$$\pm 0.74$ |  $75.63$$\pm 0.56$ |  $89.23$$\pm 0.37$ |  $75.50$$\pm 0.20$ |  $79.99$$\pm 0.45$ |  $65.50$$\pm 0.81$ |  $79.14$$\pm 0.32$
$L_{2}$ |  $77.57$$\pm 0.92$ |  $64.29$$\pm 0.19$ |  $75.19$$\pm 0.18$ |  $86.72$$\pm 0.31$ |  $74.44$$\pm 0.23$ |  $77.16$$\pm 0.66$ |  $67.33$$\pm 0.49$ |  $75.04$$\pm 0.32$

##  5\. Numerical Experiments

This section validates MAGnet by a variety of experiments. We start by
comparing our methods to three denoising methods on node classification tasks
with two types of attribute corruptions. The next two ablation studies digest
the influence of regularizers in mask generation and ADMM denoising towards
the graph recovery and property prediction performance of the proposed model.
To establish an intuitive understanding of the two learning modules, i.e.,
mask matrix approximation and ADMM optimization, their effects are
demonstrated with visualizations. The implementations at
https://github.com/bzho3923/MAGnet are programmed with PyTorch-Geometric
(version 2.0.1) and PyTorch (version 1.7.0) and run on NVIDIA® Tesla A100 GPU
with $6,912$ CUDA cores and $80$GB HBM2 mounted on an HPC cluster.

###  5.1. Experimental Protocol

####  5.1.1. Benchmark Preparation

We examine MAGnet on eight publicly available benchmark datasets: Cora,
Citeseer and PubMed of the citation networks (Yang et al., 2016); Wiki-CS
(Mernyei and Cangea, 2020) that classifies articles from Wikipedia database;
Coauthor-CS (Shchur et al., 2018) that labels the most active field of
authors; OGB-arxiv from open graph benchmark (Hu et al., 2020) that represents
the citation network between all arXiv papers in Computer Science; and
Wisconsin and Texas (García-Plaza et al., 2016) that records the web pages
from computer science departments of different universities and their mutual
links. In particular, the first three datasets are the most classic citation
networks that are used for node-level property prediction tasks, Wiki-CS
employs dense edge connection, Coauthor-CS elaborates (relatively) high
dimension of feature attributes, OGB-arxiv is a large-scale dataset, and the
last two web-page datasets are heterophilic graphs.

While the given datasets do not provide ground truth of anomalies, we conduct
two types of black-box poisoning methods that have been used in graph anomaly
detection and graph defense:

  * •

An _attribute injection_ method perturbs attributes through swapping
attributes of the most distinct samples in a random subgraph. The noise is
added similarly to (Ding et al., 2019). A certain number of targeted nodes are
randomly selected from the input graph. For each selected node $v_{i}$, we
randomly pick another $k$ nodes from the graph and select the node $v_{j}$
whose attributes deviate the most from node $v_{i}$ among the $k$ nodes by
maximizing the Euclidean distance of node attributes, i.e.,
$\left\|x_{i}-x_{j}\right\|_{2}$. Then, we substitute the attributes $x_{i}$
of node $v_{i}$ with $x_{j}$. Specifically, we set the size of candidates
$k=100$ for small datasets, i.e., Cora and Citeseer, and $k=500$ for
relatively larger datasets, i.e., PubMed, Coauthor-CS and Wiki-CS.

  * •

Secondly, _meta attack_ perturbs node attributes leverages meta-learning in
graph adversarial attack to poison node attributes with the meta-gradient of
the loss function (Zügner and Günnemann, 2019) 111implemented by DeepRobust
(Li et al., 2021) at https://github.com/DSE-MSU/DeepRobust. We use the
technique to create local corruptions on the underlying graph by corrupting a
small portion of attributes in the graph’s feature matrix, where the specific
amount of perturbation varies for different datasets to obtain a noticeable
attack effect. Instead of unifying the preprocessing procedures (i.e., conduct
the same attack step for all the baseline methods), we unify the input graph
(i.e., use the same attacked graph input) for baseline methods by fixing the
surrogate model to a 2-layer GCN. The justification comes in two-fold. First,
we aim to demonstrate each model’s ability to recover a robust representation
from given corrupted inputs. For this purpose, it is not required to make
baseline-specific attacks to maximize the effect of an adversarial attack.
Meanwhile, as we do not assume prior knowledge such as ”where were the
perturbations from” or ”how were the corruptions designed”, pre-determining a
corrupted graph for all baseline models corresponds to a fair comparison.

####  5.1.2. Training Setup

We construct the mask matrix by binary approximation errors from a GCN-based
autoencoder constituting $2$ encoding layers following $2$ decoding layers.
During the optimization, an inertial ADMM is iterated for $15$ times to fastly
recover the corrupted graph. The first six datasets follow the standard public
split and processing rules in PyTorch-Geometric (Fey and Lenssen, 2019) or OGB
(Hu et al., 2020). For the two heterophilic datasets, we split the training,
validation, and test sets following (Pei et al., 2020). The reported average
test accuracy (or AUROC for OGB-arxiv) is evaluated over $10$ repetitions.

The models are fine-tuned within the hyper-parameter searching space defined
in Table 3, where the first five hyper-parameters are universally applicable
to all the models, and the last $\nu_{0}$ is exclusive to MAGnet. As for model
architecture, we construct two convolution layers for GCN (except for OGB-
arxiv, where we train a $3$-layer GCN), and three blocks for ElasticGNN and
APPNP where each block contains a fully-connected layer and a graph
convolution. For GNNGuard and MAGnet, we run the main layers to find the
denoised representation ${\bm{U}}$ and send it to a $2$-layer GCN for node
classification. The prediction results are activated by a softmax function for
label assignment.

Table 3. Hyperparameter searching space. Hyperparameters | Searching Space
---|---
learning rate |  $10^{-3}$, $5\times 10^{-3}$, $10^{-4}$
weight decay ($L_{2}$) |  $10^{-3}$, $5\times 10^{-3}$, $10^{-4}$
hidden size |  $64$, $128$
dropout ratio | $0.5$
epochs |  $200$, $500$
$\nu_{0}$ |  $10$, $100$, $500$
$\tau$ | $0.1$

####  5.1.3. Baseline Comparison

A complete investigation on MAGnet is conducted with three different types of
mask matrix: all-ones (MAGnetone), GAE-approximated (MAGnetgae), and ground
truth (MAGnettrue) matrices. The last case advises the upper limit of our
model with the ‘perfectly’ approximated mask matrix. We compare our model to
three popular graph smoothing models with different design philosophies: APPNP
(Klicpera et al., 2018) 222https://github.com/klicperajo/ppnp avoids global
smoothness with residual connections; GNNGuard (Zhang and Zitnik, 2020)
333https://github.com/mims-harvard/GNNGuard modifies the neighbor relevance in
message passing to mitigate local corruption; ElasticGNN (Liu et al., 2021b)
444https://github.com/lxiaorui/ElasticGNN and AirGNN (Liu et al., 2021a)
555https://github.com/lxiaorui/AirGNN pursues local smoothness with a mixture
of $\ell_{1}$ and $\ell_{2}$ regularizers. We also train a $2$-layer GCN (Kipf
and Welling, 2017) as the baseline method, which smooths graph signals by
minimizing the Dirichlet energy in the spatial domain.

Figure 3. The performance comparison of MAGnet to baseline GCN (corrupted)
with different levels of attribute injection to Cora (left) and Citeseer
(right).

Figure 4. $\ell_{1}$/$\ell_{2}$ approximation error in GAE affects the
prediction performance.

###  5.2. Node Classification with Graph Recovery

Table 1 compares model performance under two types of local corruptions, i.e.,
attribute injection and graph meta attack. We highlight each score in red or
green by their relative improvement or retrogression over GCN. The opacity is
determined by the relative percentage change.

We observe that MAGnetgae outperforms its competitors and recovers at most
$94\%$ test accuracy from the perturbed attributes for homophilic graphs and
over $180\%$ for heterophilic graphs. In particular, the results on Wisconsin
by MAGnet is even higher than on the non-corrupted clean graph. It implies the
potential of our learning scheme to handle heterophilic graphs. We will leave
further investigations to the future regarding our denoising model’s
representation power in handling heterophilic graphs.

On the other hand, the four baseline methods fail to recover a robust
embedding from the locally-corrupted input. In some cases, they are fooled to
make worse predictions, as they are not able to distinguish outliers from
regular patterns. APPNP leverages residual connections to avoid global
smoothness by reinforcing local anomalies; GNNGuard makes modifications on the
edge connection to indirectly influence node representations; ElasticGNN,
although realizing the importance of local smoothness, designs the
optimization with low-pass filters and restricts stringent consistency of the
new representation even on anomalous positions.

Not only the MAGnet achieves promising performance in graph recovery, but also
it requires comparable computational cost. Table 4 displays the performance
versus running time of the entire program on Cora (with $200$ epochs) and OGB-
arxiv (with $500$ epochs). We train GAE with $1,000$ epochs and $10,000$
epochs on the two datasets, respectively. On the small dataset Cora, the
running speed of GNNGuard is significantly faster (at $7.35$ seconds) than its
counterparts (at around $46$ seconds) at the cost of the lowest accuracy
score. Alternatively, MAGnetgae achieves the best performance with a
comparable speed of $45.65$ seconds. On the large-scale dataset OGB-arxiv, the
advantage of GNNGuard on the training speed is suppressed by ElasticGNN and
AirGNN, but it achieves a higher score than the two baselines. Still, it is
$6\%$’s lower than our MAGnetgae at the cost of a slightly longer training
time. As for APPNP, it unfortunately exceeds the memory limit of $100$GB, and
thus fails to present any results. In addition to directly making the
comparison of our method to baseline models, we also report the training time
for MAGnettrue, which is essentially the training cost for denoising the graph
with a given mask, i.e., exclude training GAE. Our MAGnet can be potentially
more efficient by employing a fast mask approximation tool. Otherwise, a
smaller number of training epochs in GAE could also accelerate the overall
speed.

Table 4. Comparison of the computational cost.

| Cora | OGB-arxiv
---|---|---
| score (%) | time (sec) | score (%) | time (min)
APPNP | $68.46$ | $47.15$ | OOM | OOM
GNNGuard | $61.96$ | $7.35$ | $65.75$ | $35.27$
ElasticGNN | $77.74$ | $45.22$ | $41.34$ | $21.13$
AirGNN | $76.22$ | $43.92$ | $52.32$ | $11.84$
MAGnetgae | $79.07$ | $45.65$ | $68.68$ | $36.30$
MAGnettrue | $78.48$ | $33.58$ | $69.57$ | $30.88$

###  5.3. Ablation 1: Reconstruction Error in GAE

The choices on the regularizers of the mask matrix approximation affect the
approximation results. We make comparisons to
${\mathcal{L}}=\|{\bm{X}}-{\bm{X}}^{\prime}\|_{1}$ (MAE loss) and
${\mathcal{L}}=\|{\bm{X}}-{\bm{X}}^{\prime}\|_{2}$ (MSE loss) in GAE. The
experiment is conducted on the seven datasets with injection perturbations,
with the prediction accuracy reported in Figure 4.

While the empirical performance disagrees with an arbitrary choice of one over
another, it supports our analysis in Section 3 that MSE loss is generally a
more safe choice. More specifically, we observe that $\ell_{2}$-norm is more
likely to outperform when the feature scale is relatively small (e.g., between
-1 and 1, which gives a higher punishment to considerably small errors than
$\ell_{1}$’s). As a reference, the attribute values are $\\{0,1\\}$ (discrete
values) for Cora, Citeseer, and Coauthor-CS, [0,1.226] (continuous values) for
PubMed, and [-3,3] (continuous values) for Wiki-CS. On the other hand,
$\ell_{1}$-norm tends to perform better in heterophilic graphs, such as
Wisconsin. In addition, $\ell_{1}$-norm is less sensitive to the choice of
threshold in (4). According to Figure 11, the true positive and false negative
rate for the $\ell_{1}$-based mask matrix does not change drastically among
different $\tau$s. In the contrast, tuning the threshold $\tau$ is critical
for the $\ell_{2}$-based scoring function to perform a higher true positive
rate and lower false negative rate. When the threshold is properly chosen, its
approximation is more reliable than the $\ell_{1}$-based counterparts.

###  5.4. Ablation 2: Regularizers in Graph Recovery

Table 2 delivers the individual accuracy score for a combination of
$p\in\\{0,1\\}$ and $q\in\\{1,2\\}$ with all-ones, GAE-oriented, and ground
truth mask matrices to digest the preference of $p,q$’s choice in different
scenarios for two types of corruptions, respectively. We also include the
baseline (GCN) at the top, which is equivalent to optimizing a $p=2$, $q=2$
regularization in the spatial domain.

Overall, $p=1$, $q=2$ is a robust choice when the quality of mask matrix
approximation is concerned. The next best choice is $p=1$, $q=1$, which is a
frequently-adopted choice in conventional denoising tasks. When the mask is
believed reliable, $p\in\\{0,1\\}$ and $q=1$ both achieve satisfactory
performance. Generally, $p=0$ fits better to concentrated perturbations in a
few entities, while $p=1$ fits the case when the corruptions are rather
diverse.

Figure 4 reports the effect of corruption level, i.e., the sparsity of the
ground truth mask, on the performance with Cora and Citeseer. We visualize the
results of MAGnetgae (orange) with the best-tuned $p,q$. The performance gain
of MAGnet over GCN on both datasets keeps rising along with an increasing
level of corruption.

1 -2.4,2.65sparsity=$0.936\%$ 2.4,2.65sparsity=$0.536\%$

Figure 5. Distribution of the ground truth mask (left) and conditional GAE-
approximated mask (right) at threshold $\tau=0.1$. A $200\times 200$ sub-
region is amplified in the middle.

###  5.5. Investigation on Mask Matrix and Local Regularization

The next experiment digests the effect of the GAE-oriented mask approximation
and ADMM optimization with visualizations.

The quality of GAE is verified by the recall of the mask approximation. Figure
5 pictures the conditional mask matrix from model reconstruction error on Cora
with attribute injection. The sparsity of both matrices can be identified
clearly in the amplified subfigures. The approximated mask matrix succeeds in
seizing $60\%$ of anomalies, which provides a reliable foundation for
subsequent recovering work.

Figure 6 visually exhibits the local effect of ADMM optimization with an
example of graph inpainting, where a raw picture is chosen from the BSD68
dataset with $480\times 320$ pixels. It is processed to a graph of $2,400$
nodes and $64$ feature attributes. Each node is transformed by a patch of
$8\times 8$ pixels. A lattice-like graph adjacency matrix is prepared with
patch neighbors connected with edges. We randomly select $9$ nodes to assign
white noise of ${\mathcal{N}}(0,1)$ on their attributes. We assume a given
mask matrix and focus on the performance of the ADMM optimizer. MAGnet
restricts major smoothing effects within the masked region. The rest ‘clean’
area maintains a sharp detail. In comparison, the classic denoising model BM3D
(Dabov et al., 2007) blurs the entire scale of the picture.

1 [red,thick] (-3.25,0.78)–++(0.4,0)–++(0,-0.4)–++(-0.4,0)–cycle;
-2.6,-2.2Original image -2.6,-2.5Noise in Red Box 0,-2.2Local PSNR=$17.43$
0,-2.5Global PSNR=$27.64$ 2.6,-2.2Local PSNR=$24.59$ 2.6,-2.5Global
PSNR=$33.81$

Figure 6. Image recovery with local additive white noise at $\sigma=50$. Three
images display the noisy raw input (left), and the inpainting result by BM3D
(middle) and MAGnet (right).

##  6\. Related Work

The last few years have witnessed a roaring success of graph neural networks,
the essential design of which is a graph convolution operation. Depending on
whether an adjacency matrix or a graph Laplacian is explicitly employed, a
convolution operation falls into two genres of either spectral (Bruna et al.,
2014; Defferrard et al., 2016; Xu et al., 2018b; Zheng et al., 2021) or
spatial-based (Kipf and Welling, 2017; Veličković et al., 2018; Hamilton et
al., 2017; Monti et al., 2017; Li et al., 2018) methods. The widespread
message passing scheme (Gilmer et al., 2017) encourages continuous development
on adjacency matrix-based feature aggregation rules (Hamilton et al., 2017;
Kipf and Welling, 2017; Li et al., 2018; Monti et al., 2017; Veličković et
al., 2018). These spatial methods pursue global feature smoothness by
minimizing Dirichlet energy, which establishes a low-pass filter that denoises
under $\ell_{2}$ penalty (Dong et al., 2021; Nt and Maehara, 2019; Zhu et al.,
2021). When multiple convolution layers are stacked in a neural network, it is
inevitable to lose small-energy patterns and learn an over-smoothing
representation. In contrast, residual connections (Chen et al., 2020a;
Klicpera et al., 2018; Rong et al., 2019; Xu et al., 2018a) maintain feature
proximity and concurrently keep odd examples, i.e., anomalies, that
potentially disturb pattern characterization.

The harmful graph anomalies are getting noticed in the literature. Robust
graph optimization refines the learning manner of a classifier to provide
promising predictions against potential threats (Dai et al., 2018; Xu et al.,
2020; Zügner and Günnemann, 2019). They are essentially designed to defend
against graph adversarial attacks, which usually influence model performance
by corrupting node connections. A robust node embedding is indirectly
approximated by a refined adjacency matrix (Chen et al., 2020b; Entezari et
al., 2020; Jin et al., 2020; Zhang and Zitnik, 2020). Graph anomaly detection
(Ding et al., 2019; Ma et al., 2021; Peng et al., 2020; Zhu et al., 2020)
identifies rare problematic nodes, but the related methods merely recover
robust representation of anomalies. On top of that, the justification is based
on node entities rather than feature values. A few existing works modify the
loss function to force local smoothness of the feature space (Chen et al.,
2021; Liu et al., 2021a, b), but they limit the regularization in the spatial
domain, and the penalties are restricted to $\ell_{1}$ or $\ell_{2}$.

##  7\. Conclusion

This research develops a GNN-based framework to recover robust graph data
representations from locally corrupted node attributes. We propose a multi-
scale sparse regularizer to optimize the hidden representation that guarantees
conditional closeness to the disrupted input. The outliers in graph node
attributes are explicitly positioned by a learnable mask matrix, which is
approximated by an unsupervised graph autoencoder that requires no prior
knowledge of the distribution of anomalies. We define the optimization problem
by adaptive $l_{p}$ and $l_{q}$ errors, where the tunable factors $p,q$
stimulate the maximum ability of the regularizer, and the corresponding
optimization can be solved by an efficient inertial ADMM. Incorporating
sparsity in multi-level framelet coefficients not only removes global noises
and regularizes local anomalous attributes at the same time but also preserves
local patterns. Our model achieves competitive performance in recovering a
robust graph embedding from local corruptions, whereas graph smoothing and
defense baseline methods fail to provide a decent solution.

###### Acknowledgements.

This work was supported by the National Natural Science Foundation of China
(No. 62172370) and Shanghai Artificial Intelligence Laboratory (No.
P22KN00524).

## References

  * (1)
  * Aggarwal (2017) Charu C Aggarwal. 2017\.  Linear models for outlier detection.  In _Outlier Analysis_. Springer, 65–110.
  * Ahmedt-Aristizabal et al. (2021) David Ahmedt-Aristizabal, Mohammad Ali Armin, Simon Denman, Clinton Fookes, and Lars Petersson. 2021\.  Graph-based deep learning for medical diagnosis and analysis: past, present and future.  _Sensors_ 21, 14 (2021), 4758.
  * Alvarez and Attouch (2001) Felipe Alvarez and Hedy Attouch. 2001.  An inertial proximal method for maximal monotone operators via discretization of a nonlinear oscillator with damping.  _Set-Valued Analysis_ 9, 1 (2001), 3–11.
  * Balcilar et al. (2020) Muhammet Balcilar, Guillaume Renton, Pierre Héroux, Benoit Gaüzère, Sébastien Adam, and Paul Honeine. 2020\.  Analyzing the expressive power of graph neural networks in a spectral perspective. In _ICLR_.
  * Boţ and Csetnek (2016) R. I. Boţ and E. R. Csetnek. 2016.  An inertial alternating direction method of multipliers.  _Minimax Theory and its Applications_ 1 (2016), 029–049.  Issue 1.
  * Boţ et al. (2015) R. I. Boţ, E. R. Csetnek, and C. Hendrich. 2015\.  Inertial Douglas–Rachford splitting for monotone inclusion problems.  _Appl. Math. Comput._ 256 (2015), 472–487.
  * Bronstein et al. (2017) Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. 2017.  Geometric deep learning: going beyond euclidean data.  _IEEE Signal Processing Magazine_ 34, 4 (2017), 18–42.
  * Bruna et al. (2014) Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. 2014.  Spectral networks and locally connected networks on graphs. In _ICLR_.
  * Chen et al. (2020a) Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. 2020a.  Simple and deep graph convolutional networks. In _ICML_. 1725–1735.
  * Chen et al. (2021) Siheng Chen, Yonina C Eldar, and Lingxiao Zhao. 2021\.  Graph unrolling networks: Interpretable neural networks for graph signal denoising.  _IEEE Transactions on Signal Processing_ 69 (2021), 3699–3713.
  * Chen et al. (2015) Siheng Chen, Aliaksei Sandryhaila, José MF Moura, and Jelena Kovačević. 2015\.  Signal recovery on graphs: Variation minimization.  _IEEE Transactions on Signal Processing_ 63, 17 (2015), 4609–4624.
  * Chen et al. (2020b) Yu Chen, Lingfei Wu, and Mohammed Zaki. 2020b.  Iterative deep graph learning for graph neural networks: Better and robust node embeddings. In _NeurIPS_.
  * Dabov et al. (2007) Kostadin Dabov, Alessandro Foi, Vladimir Katkovnik, and Karen Egiazarian. 2007.  Image denoising by sparse 3-D transform-domain collaborative filtering.  _IEEE Transactions on Image Processing_ 16, 8 (2007), 2080–2095.
  * Dai et al. (2018) Hanjun Dai, Hui Li, Tian Tian, Xin Huang, Lin Wang, Jun Zhu, and Le Song. 2018.  Adversarial attack on graph structured data. In _ICML_. 1115–1124.
  * Defferrard et al. (2016) Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. 2016.  Convolutional neural networks on graphs with fast localized spectral filtering. In _NeurIPS_.
  * Ding et al. (2019) Kaize Ding, Jundong Li, Rohit Bhanushali, and Huan Liu. 2019\.  Deep Anomaly Detection on Attributed Networks. In _SIAM International Conference on Data Mining (SDM)_.
  * Dong (2017) Bin Dong. 2017.  Sparse representation on graphs by tight wavelet frames and applications.  _Applied and Computational Harmonic Analysis_ 42, 3 (2017), 452–479.
  * Dong et al. (2021) Yushun Dong, Kaize Ding, Brian Jalaian, Shuiwang Ji, and Jundong Li. 2021.  AdaGNN: Graph Neural Networks with Adaptive Frequency Response Filter. In _Proceedings of the 30th ACM International Conference on Information & Knowledge Management_.
  * Entezari et al. (2020) Negin Entezari, Saba A Al-Sayouri, Amirali Darvishzadeh, and Evangelos E Papalexakis. 2020.  All you need is low (rank) defending against adversarial attacks on graphs. In _Proceedings of the 13th International Conference on Web Search and Data Mining_. 169–177.
  * Fan et al. (2019) Wenqi Fan, Yao Ma, Qing Li, Yuan He, Eric Zhao, Jiliang Tang, and Dawei Yin. 2019\.  Graph neural networks for social recommendation. In _WWW_. 417–426.
  * Fey and Lenssen (2019) Matthias Fey and Jan Eric Lenssen. 2019.  Fast graph representation learning with PyTorch Geometric. In _ICLR Workshop on Representation Learning on Graphs and Manifolds_.
  * Gabay and Mercier (1976) Daniel Gabay and Bertrand Mercier. 1976.  A dual algorithm for the solution of nonlinear variational problems via finite element approximation.  _Computers & Mathematics with Applications_ 2, 1 (1976), 17–40.
  * García-Plaza et al. (2016) Alberto P García-Plaza, Víctor Fresno, Raquel Martínez Unanue, and Arkaitz Zubiaga. 2016\.  Using fuzzy logic to leverage HTML markup for web page representation.  _IEEE Transactions on Fuzzy Systems_ 25, 4 (2016), 919–933.
  * Gilmer et al. (2017) Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. 2017\.  Neural message passing for quantum chemistry. In _ICML_.
  * Hamilton et al. (2017) William L Hamilton, Rex Ying, and Jure Leskovec. 2017\.  Inductive representation learning on large graphs. In _NeurIPS_.
  * Hu et al. (2020) Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. 2020\.  Open graph benchmark: Datasets for machine learning on graphs. In _NeurIPS_.
  * Jin et al. (2020) Wei Jin, Yao Ma, Xiaorui Liu, Xianfeng Tang, Suhang Wang, and Jiliang Tang. 2020\.  Graph structure learning for robust graph neural networks. In _KDD_. 66–74.
  * Kipf and Welling (2016) Thomas N Kipf and Max Welling. 2016.  Variational Graph Auto-Encoders. In _NeurIPS Workshop on Bayesian Deep Learning_.
  * Kipf and Welling (2017) Thomas N. Kipf and Max Welling. 2017.  Semi-Supervised Classification with Graph Convolutional Networks. In _ICLR_.
  * Klicpera et al. (2018) Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. 2018.  Predict then propagate: Graph Neural Networks meet Personalized PageRank. In _ICLR_.
  * Kovenko and Bogach (2020) Volodymyr Kovenko and Ilona Bogach. 2020.  A Comprehensive Study of Autoencoders’ Applications Related to Images.. In _IT &I Workshops_. 43–54.
  * Li et al. (2017) Jundong Li, Harsh Dani, Xia Hu, and Huan Liu. 2017\.  Radar: Residual Analysis for Anomaly Detection in Attributed Networks.. In _IJCAI_. 2152–2158.
  * Li et al. (2018) Qimai Li, Zhichao Han, and Xiao-Ming Wu. 2018.  Deeper insights into graph convolutional networks for semi-supervised learning. In _AAAI_.
  * Li et al. (2021) Yaxin Li, Wei Jin, Han Xu, and Jiliang Tang. 2021\.  DeepRobust: a Platform for Adversarial Attacks and Defenses. In _AAAI_ , Vol. 35.
  * Liu et al. (2021a) Xiaorui Liu, Jiayuan Ding, Wei Jin, Han Xu, Yao Ma, Zitao Liu, and Jiliang Tang. 2021a.  Graph Neural Networks with Adaptive Residual. In _NeurIPS_.
  * Liu et al. (2021b) Xiaorui Liu, Wei Jin, Yao Ma, Yaxin Li, Hua Liu, Yiqi Wang, Ming Yan, and Jiliang Tang. 2021b.  Elastic graph neural networks. In _ICML_.
  * Ma et al. (2021) Xiaoxiao Ma, Jia Wu, Shan Xue, Jian Yang, Chuan Zhou, Quan Z Sheng, Hui Xiong, and Leman Akoglu. 2021\.  A comprehensive survey on graph anomaly detection with deep learning.  _IEEE Transactions on Knowledge and Data Engineering_ (2021).
  * Mahmood et al. (2018) Faisal Mahmood, Nauman Shahid, Ulf Skoglund, and Pierre Vandergheynst. 2018.  Adaptive graph-based total variation for tomographic reconstructions.  _IEEE Signal Processing Letters_ 25, 5 (2018), 700–704.
  * Mernyei and Cangea (2020) Péter Mernyei and Cǎtǎlina Cangea. 2020.  Wiki-cs: a wikipedia-based benchmark for graph neural networks. In _ICML Workshop on Graph Representation Learning and Beyond_.
  * Monti et al. (2017) Federico Monti, Michael M Bronstein, and Xavier Bresson. 2017\.  Geometric Matrix Completion with Recurrent Multi-Graph Neural Networks. In _NeurIPS_.
  * Nt and Maehara (2019) Hoang Nt and Takanori Maehara. 2019.  Revisiting graph neural networks: All we have is low-pass filters.  _arXiv:1905.09550_ (2019).
  * Pei et al. (2020) Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. 2020.  Geom-GCN: Geometric Graph Convolutional Networks. In _ICLR_.
  * Peng et al. (2018) Zhen Peng, Minnan Luo, Jundong Li, Huan Liu, and Qinghua Zheng. 2018.  ANOMALOUS: A Joint Modeling Approach for Anomaly Detection on Attributed Networks.. In _IJCAI_. 3513–3519.
  * Peng et al. (2020) Zhen Peng, Minnan Luo, Jundong Li, Luguo Xue, and Qinghua Zheng. 2020.  A Deep Multi-View Framework for Anomaly Detection on Attributed Networks.  _IEEE Transactions on Knowledge and Data Engineering_ (2020).
  * Rong et al. (2019) Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. 2019\.  DropEdge: Towards Deep Graph Convolutional Networks on Node Classification. In _ICLR_.
  * Sandryhaila and Moura (2014) Aliaksei Sandryhaila and Jose MF Moura. 2014.  Discrete signal processing on graphs: Frequency analysis.  _IEEE Transactions on Signal Processing_ 62, 12 (2014), 3042–3054.
  * Shchur et al. (2018) Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. 2018\.  Pitfalls of Graph Neural Network Evaluation. In _NeurIPS Workshop on Relational Representation Learning Workshop_.
  * Veličković et al. (2018) Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. 2018.  Graph attention networks. In _ICLR_.
  * Wang and Zhuang (2019) Yu Guang Wang and Xiaosheng Zhuang. 2019.  Tight framelets on graphs for multiscale data analysis. In _Wavelets and Sparsity XVIII_ , Vol. 11138. International Society for Optics and Photonics, 111380B.
  * Wu et al. (2019) Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. 2019\.  Simplifying graph convolutional networks. In _ICML_.
  * Wu et al. (2020b) Shiwen Wu, Fei Sun, Wentao Zhang, Xu Xie, and Bin Cui. 2020b.  Graph neural networks in recommender systems: a survey.  _ACM Computing Surveys (CSUR)_ (2020).
  * Wu et al. (2020a) Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. 2020a.  A comprehensive survey on graph neural networks.  _IEEE Transactions on Neural Networks and Learning Systems_ 32, 1 (2020), 4–24.
  * Xu et al. (2018b) Bingbing Xu, Huawei Shen, Qi Cao, Yunqi Qiu, and Xueqi Cheng. 2018b.  Graph Wavelet Neural Network. In _ICLR_.
  * Xu et al. (2020) Han Xu, Yao Ma, Hao-Chen Liu, Debayan Deb, Hui Liu, Ji-Liang Tang, and Anil K Jain. 2020.  Adversarial attacks and defenses in images, graphs and text: A review.  _International Journal of Automation and Computing_ 17, 2 (2020), 151–178.
  * Xu et al. (2018a) Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. 2018a.  Representation learning on graphs with jumping knowledge networks. In _ICML_.
  * Xu et al. (2012) Zongben Xu, Xiangyu Chang, Fengmin Xu, and Hai Zhang. 2012\.  L1/2 regularization: A thresholding representation theory and a fast solver.  _IEEE Transactions on Neural Networks and Learning Systems_ 23, 7 (2012), 1013–1027.
  * Yang et al. (2016) Zhilin Yang, William Cohen, and Ruslan Salakhudinov. 2016\.  Revisiting semi-supervised learning with graph embeddings. In _ICML_.
  * Zhang and Zitnik (2020) Xiang Zhang and Marinka Zitnik. 2020.  GNNGuard: Defending Graph Neural Networks against Adversarial Attacks. In _NeurIPS_ , Vol. 33.
  * Zhang et al. (2020) Ziwei Zhang, Peng Cui, and Wenwu Zhu. 2020.  Deep learning on graphs: a survey.  _IEEE Transactions on Knowledge and Data Engineering_ (2020).
  * Zheng et al. (2021) Xuebin Zheng, Bingxin Zhou, Junbin Gao, Yu Guang Wang, Pietro Lio, Ming Li, and Guido Montúfar. 2021.  How framelets enhance graph neural networks. In _ICML_.
  * Zheng et al. (2022) Xuebin Zheng, Bingxin Zhou, Yu Guang Wang, and Xiaosheng Zhuang. 2022.  Decimated framelet system on graphs and fast G-framelet transforms.  _Journal of Machine Learning Research_ 23, 18 (2022), 1–68.
  * Zhou et al. (2021) Bingxin Zhou, Ruikun Li, Xuebin Zheng, Yu Guang Wang, and Junbin Gao. 2021.  Graph Denoising with Framelet Regularizer.  _arXiv:2111.03264_ (2021).
  * Zhou et al. (2020) Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. 2020.  Graph neural networks: a review of methods and applications.  _AI Open_ 1 (2020), 57–81.
  * Zhu et al. (2020) Dali Zhu, Yuchen Ma, and Yinlong Liu. 2020.  Anomaly Detection with Deep Graph Autoencoders on Attributed Networks. In _2020 IEEE Symposium on Computers and Communications (ISCC)_. 1–6.
  * Zhu et al. (2021) Meiqi Zhu, Xiao Wang, Chuan Shi, Houye Ji, and Peng Cui. 2021.  Interpreting and unifying graph neural networks with an optimization framework. In _WWW_.
  * Zügner and Günnemann (2019) Daniel Zügner and Stephan Günnemann. 2019.  Adversarial attacks on graph neural networks via meta learning. In _ICLR_.

##  Appendix A Graph Framelet Transform

This section briefs the fast computation of undecimated framelet transform on
graphs. The initial idea was proposed by Dong (Dong, 2017), which is then
developed into a graph convolution (Zheng et al., 2021). Here we give a brief
introduction to the wavelet frame (framelet) system for a graph signal, using
the fast approximation on the framelet decomposition and reconstruction
operators by Chebyshev approximation, which is the key to an efficient graph
convolution.

###  A.1. Framelet System

A framelet is defined by two key elements: a _filter bank_
$\bm{\eta}:=\\{a;b^{(1)},\dots,b^{(K)}\\}$ and a set of _scaling functions_
$\Psi=\\{\alpha;\beta^{(1)},\dots,\beta^{(K)}\\}$. We name $a$ the low-pass
filter and $b^{(k)}$ the $k$th high-pass filter with $k=1,\dots,K$. The two
sets of filters respectively extract the approximated and detailed information
of the input graph signal in a transformed domain, i.e., the framelet domain.

There are different choices of filter masks, which results in different tight
framelet systems (See (Dong, 2017) for some examples). In general, the
selected filter bank and its associated scaling function satisfy the
relationship that

(8)
$\widehat{\alpha}(2\xi)=\widehat{a}(\xi)\widehat{\alpha}(\xi),\quad\widehat{\beta^{(k)}}(2\xi)=\widehat{b^{k}}(\xi)\widehat{\alpha}(\xi),$

for $k=1,\ldots,K$ and $\xi\in\mathbb{R}$. We implement the _Haar-type_ filter
with one high pass, i.e., $K=1$. For $x\in\mathbb{R}$, it defines

$\widehat{\alpha}(x)=\cos(x/2)\mbox{~{}~{}and~{}~{}}\widehat{\beta^{(1)}}(x)=\sin(x/2).$

With the defined filter bank and the scaling functions, the undecimated
framelet basis can be defined for a graph signal with the eigenpairs
$\\{(\lambda_{\ell},{\bm{u}}_{\ell})\\}_{\ell=1}^{n}$ of the graph Laplacian
${\mathcal{L}}$. At level $l=1,\dots,J$, we define the undecimated framelets
for node $p$ by

(9)
$\begin{array}[]{l}\bm{\varphi}_{l,p}(v):=\sum_{\ell=1}^{n}\widehat{\alpha}\left(\frac{\lambda_{\ell}}{2^{l}}\right)\overline{{\bm{u}}_{\ell}(p)}{\bm{u}}_{\ell}(v),\\\\[5.69054pt]
\bm{\psi}_{l,p}^{(k)}(v):=\sum_{\ell=1}^{n}\widehat{\beta^{(k)}}\left(\frac{\lambda_{\ell}}{2^{l}}\right)\overline{{\bm{u}}_{\ell}(p)}{\bm{u}}_{\ell}(v),\quad
k=1,\ldots,K.\end{array}$

We name $\bm{\varphi}_{l,p}(v),\bm{\psi}_{l,p}^{(k)}(v)$ with
$v\in{\mathcal{V}}$ the low-pass and the $k$th high-pass framelet basis,
respectively. These bases are called the _undecimated tight framelets_ on
${\mathcal{G}}$. They define an _undecimated framelet system_
$\operatorname{UFS}_{J_{1}}^{J}(\Psi,\bm{\eta})$ ($J>J_{1}$) for
$l_{2}({\mathcal{G}})$ from $J_{1}$, which reads

$\displaystyle\operatorname{UFS}_{J_{1}}^{J}(\Psi,\bm{\eta})$
$\displaystyle:=\operatorname{UFS}_{J_{1}}^{J}(\Psi,\bm{\eta};{\mathcal{G}})$
$\displaystyle:=\left\\{\varphi_{J_{1},p}:p\in{\mathcal{V}}\right\\}\cup\\{\psi_{l,p}^{(k)}:p\in{\mathcal{V}},l=J_{1},\dots,J\\}_{k=1}^{K}.$

###  A.2. Framelet Decomposition

We now introduce the _framelet decomposition operator_ of the defined tight
framelet system, i.e., $\bm{{\mathcal{W}}}$ that we used in equation 3 to
construct the spectral coefficients in the framelet domain.

The framelet decomposition operator $\bm{{\mathcal{W}}}_{k,l}$ contains a set
of orthonormal bases at
$(k,l)\in\\{(0,J)\\}\cup\\{(1,1),\dots,(1,J),\dots,(K,J)\\}$. It transforms a
given graph signal ${\bm{X}}$ to a set of multi-scale and multi-level
_framelet coefficients_ , i.e., the spectral representation of the graph
signal ${\bm{X}}$ in the transformed domain. In particular,
$\bm{{\mathcal{W}}}_{0,J}$ contains $\bm{\varphi}_{J,p},p\in{\mathcal{V}}$
that constructs the low-pass framelet coefficients
$\bm{{\mathcal{W}}}_{0,J}{\bm{X}}$ that preserve approximate information in
${\bm{X}}$. They are the smooth representation that reflects the global trend
of ${\bm{X}}$. Meanwhile, the high-pass coefficients
$\bm{{\mathcal{W}}}_{k,l}{\bm{X}}$ with
$\bm{{\mathcal{W}}}_{k,l}=\\{\bm{\psi}_{l,p}^{(k)},p\in{\mathcal{V}}\\}$
records detailed information at scale $k$ and level $l$. They reflect local
patterns or noises of the signal. A larger scale $k$ contains more localized
information with smaller energy.

The framelet coefficients can be directly projected by
$\langle\bm{\varphi}_{l,p},{\bm{X}}\rangle$ and
$\langle\bm{\psi}_{l,p}^{(k)},{\bm{X}}\rangle$ for node $p$ at scale level
$l$. For instance, we take eigendecomposition on a graph Laplacian
${\mathcal{L}}$ and obtain
${\bm{U}}=[{\bm{u}}_{1},\dots,{\bm{u}}_{n}]\in\mathbb{R}^{n\times n}$ be the
eigenvectors and $\Lambda=\operatorname{diag}(\lambda_{1},\dots,\lambda_{n})$
be the eigenvalues. According to the definition above, the respective filtered
diagonal matrices with low-pass and high-pass filters are

$\displaystyle\widehat{\alpha}\left(\frac{\Lambda}{2}\right)$
$\displaystyle=\operatorname{diag}\left(\widehat{\alpha}\left(\frac{\lambda_{1}}{2}\right),\dots,\widehat{\alpha}\left(\frac{\lambda_{n}}{2}\right)\right),$
$\displaystyle\widehat{\beta^{(k)}}\left(\frac{\Lambda}{2^{l}}\right)$
$\displaystyle=\operatorname{diag}\left(\widehat{\beta^{(k)}}\left(\frac{\lambda_{1}}{2^{l}}\right),\dots,\widehat{\beta^{(k)}}\left(\frac{\lambda_{n}}{2^{l}}\right)\right).$

The associated framelet coefficients at the low pass and the $k$th high pass
are

(10)
$\displaystyle\bm{{\mathcal{W}}}_{0,J}{\bm{X}}={\bm{U}}\widehat{\alpha}\left(\frac{\Lambda}{2}\right){\bm{U}}^{\top}{\bm{X}},$
$\displaystyle\bm{{\mathcal{W}}}_{k,l}{\bm{X}}={\bm{U}}\widehat{\beta^{(k)}}\left(\frac{\Lambda}{2^{l+1}}\right){\bm{U}}^{\top}{\bm{X}}\quad\forall
l=0,\dots,J.$

###  A.3. Fast Tight Framelet Transform

To formulate an efficient framelet decomposition, two strategies are
considered, including a recursive formulation on filter matrices, and
Chebyshev-approximated eigenvectors.

With a filter bank that satisfies (8), the above decomposition can be
implemented recursively by

$\displaystyle\bm{{\mathcal{W}}}_{k,1}{\bm{X}}={\bm{U}}\widehat{\beta^{(k)}}\left(2^{-R}\Lambda\right){\bm{U}}^{\top}{\bm{X}}$

for the first level ($l=1$), and

$\displaystyle\bm{{\mathcal{W}}}_{k,l}{\bm{X}}$
$\displaystyle={\bm{U}}\widehat{\beta^{(k)}}\left(2^{R+l-1}\Lambda\right)\widehat{\alpha}\left(2^{R+l-2}\Lambda\right)\dots\widehat{\alpha}\left(2^{-R}\Lambda\right){\bm{U}}^{\top}{\bm{X}}$
$\displaystyle\forall l=2,\dots,J,$

where the real-value dilation scale $R$ satisfies $\lambda_{\max}\leq
2^{R}\pi$.

Furthermore, we employ an $m$-order Chebyshev polynomials approximation for
efficient framelet decomposition. It avoids eigendecomposition on graph
Laplacian, which can be considerably slow on a large graph.

Denote the $m$-order approximation of $\alpha$ and
$\\{\beta^{(k)}\\}_{k=1}^{K}$ by ${\mathcal{T}}_{0}$ and
$\\{{\mathcal{T}}_{k}\\}_{k=1}^{K}$, respectively. The framelet decomposition
operator $\bm{{\mathcal{W}}}_{r,j}$ is approximated by

$\bm{{\mathcal{W}}}_{k,l}=\begin{cases}{\mathcal{T}}_{0}\left(2^{-R}{\mathcal{L}}\right),&l=1,\\\\[2.84526pt]
{\mathcal{T}}_{r}\left(2^{R+l-1}{\mathcal{L}}\right){\mathcal{T}}_{0}\left(2^{R+l-2}{\mathcal{L}}\right)\dots\mathcal{T}_{0}\left(2^{-R}{\mathcal{L}}\right),&l=2,\dots,J.\end{cases}$

We apply the fast-approximated $\bm{{\mathcal{W}}}$ in the $l_{p}$ penalty
term of the objective function equation 3 formulated in Section 2.

##  Appendix B Inertial ADMM algorithm

This section provides essential details for the inertial ADMM to understand
the update rules defined in Section 4 of the main text.

###  B.1. Inertial ADMM

We denote ${\bm{Z}}={\bm{\mathcal{W}}}{\bm{U}}$ and rewrite equation 3 as

$\min_{{\bm{U}},{\bm{Z}}}~{}\|{\bm{\nu}}{\bm{Z}}\|_{p,G}+\tfrac{1}{2}\|{\bm{M}}\odot({\bm{U}}-{\bm{X}})\|^{q}_{q,G},~{}~{}\mathrm{such~{}that}~{}{\bm{Z}}={\bm{\mathcal{W}}}{\bm{U}}.$

This forms a standard formulation of problems that can be solved by
Alternating Direction Method of Multipliers (ADMM (Gabay and Mercier, 1976)).
The associated augmented Lagrangian reads

$\displaystyle{\mathcal{L}}({\bm{U}},{\bm{Z}};{\bm{Y}}):=$
$\displaystyle\|{\bm{\nu}}{\bm{Z}}\|_{p,G}+\tfrac{1}{2}\|{\bm{M}}\odot({\bm{U}}-{\bm{X}})\|^{q}_{q,G}$
$\displaystyle+\langle{\bm{Y}},\,{\bm{\mathcal{W}}}{\bm{U}}-{\bm{Z}}\rangle+\tfrac{\gamma}{2}{|\kern-1.125pt|}{\bm{\mathcal{W}}}{\bm{U}}-{\bm{Z}}{|\kern-1.125pt|}^{2}.$

To find a saddle-point of ${\mathcal{L}}({\bm{U}},{\bm{Z}};{\bm{Y}})$, ADMM
applies the following iteration

$\displaystyle{\bm{Z}}_{k+1}=$
$\displaystyle\operatorname*{arg\,min}_{{\bm{Z}}}~{}\|{\bm{\nu}}{\bm{Z}}\|_{p,G}+\tfrac{\gamma}{2}{|\kern-1.125pt|}{\bm{\mathcal{W}}}{\bm{U}}_{k}-{\bm{Z}}{|\kern-1.125pt|}^{2}+\langle{\bm{Y}}_{k},\,{\bm{\mathcal{W}}}{\bm{U}}_{k}-{\bm{Z}}\rangle,$
$\displaystyle{\bm{U}}_{k+1}=$
$\displaystyle\operatorname*{arg\,min}_{{\bm{U}}}~{}\tfrac{1}{2}\|{\bm{M}}\odot({\bm{U}}-{\bm{X}})\|^{q}_{q,G}$
$\displaystyle+\tfrac{\gamma}{2}{|\kern-1.125pt|}{\bm{\mathcal{W}}}{\bm{U}}-{\bm{Z}}_{k+1}{|\kern-1.125pt|}^{2}+\langle{\bm{Y}}_{k},\,{\bm{\mathcal{W}}}{\bm{U}}-{\bm{Z}}_{k+1}\rangle,$
$\displaystyle{\bm{Y}}_{k+1}=$
$\displaystyle{\bm{Y}}_{k}+\gamma\big{(}{\bm{\mathcal{W}}}{\bm{U}}_{k+1}-{\bm{Z}}_{k+1}).$

The above iteration can be equivalently written as

$\displaystyle{\bm{Z}}_{k+1}$
$\displaystyle=\operatorname*{arg\,min}_{{\bm{Z}}}~{}\|{\bm{\nu}}{\bm{Z}}\|_{p,G}+\tfrac{\gamma}{2}{|\kern-1.125pt|}{\bm{\mathcal{W}}}{\bm{U}}_{k}-{\bm{Z}}+{\bm{Y}}_{k}/\gamma{|\kern-1.125pt|}^{2},$
$\displaystyle{\bm{U}}_{k+1}$
$\displaystyle=\operatorname*{arg\,min}_{{\bm{U}}}~{}\tfrac{1}{2}\|{\bm{M}}\odot({\bm{U}}-{\bm{X}})\|^{q}_{q,G}+\tfrac{\gamma}{2}{|\kern-1.125pt|}{\bm{\mathcal{W}}}{\bm{U}}-{\bm{Z}}_{k+1}+{\bm{Y}}_{k}/\gamma{|\kern-1.125pt|}^{2},$
$\displaystyle{\bm{Y}}_{k+1}$
$\displaystyle={\bm{Y}}_{k}+\gamma\big{(}{\bm{\mathcal{W}}}{\bm{U}}_{k+1}-{\bm{Z}}_{k+1}).$

If we further define

${\bm{V}}_{k+1}={\bm{Y}}_{k}-\gamma{\bm{Z}}_{k+1},$

the above iteration can be reformulated as

$\displaystyle{\bm{Z}}_{k+1}$
$\displaystyle=\operatorname*{arg\,min}_{{\bm{Z}}}~{}\|{\bm{\nu}}{\bm{Z}}\|_{p,G}+\tfrac{\gamma}{2}{|\kern-1.125pt|}{\bm{Z}}-{\bm{\mathcal{W}}}{\bm{U}}_{k}-{\bm{Y}}_{k}/\gamma{|\kern-1.125pt|}^{2},$
$\displaystyle=\operatorname*{arg\,min}_{{\bm{Z}}}~{}\|{\bm{\nu}}{\bm{Z}}\|_{p,G}+\tfrac{\gamma}{2}{|\kern-1.125pt|}{\bm{Z}}-(2{\bm{Y}}_{k}-{\bm{V}}_{k})/\gamma{|\kern-1.125pt|}^{2},$
$\displaystyle{\bm{V}}_{k+1}$
$\displaystyle={\bm{Y}}_{k}-\gamma{\bm{Z}}_{k+1},$
$\displaystyle{\bm{U}}_{k+1}$
$\displaystyle=\operatorname*{arg\,min}_{{\bm{U}}}~{}\tfrac{1}{2}\|{\bm{M}}\odot({\bm{U}}-{\bm{X}})\|^{q}_{q,G}+\tfrac{\gamma}{2}{|\kern-1.125pt|}{\bm{\mathcal{W}}}{\bm{U}}+{\bm{V}}_{k+1}/\gamma{|\kern-1.125pt|}^{2},$
$\displaystyle{\bm{Y}}_{k+1}$
$\displaystyle={\bm{Y}}_{k}+\gamma\big{(}{\bm{\mathcal{W}}}{\bm{U}}_{k+1}-{\bm{Z}}_{k+1})$
$\displaystyle={\bm{V}}_{k+1}+\gamma{\bm{\mathcal{W}}}{\bm{U}}_{k+1}.$

In this paper, we consider the inertial ADMM motivated by (Alvarez and
Attouch, 2001), whose iteration is provided below:

$\displaystyle{\bm{Z}}_{k+1}$
$\displaystyle=\operatorname*{arg\,min}_{{\bm{Z}}}~{}\|{\bm{\nu}}{\bm{Z}}\|_{p,G}+\tfrac{\gamma}{2}{|\kern-1.125pt|}{\bm{Z}}-(2{\bm{Y}}_{k}-\widetilde{\bm{{V}}}_{k})/\gamma{|\kern-1.125pt|}^{2},$
$\displaystyle{\bm{V}}_{k+1}$
$\displaystyle={\bm{Y}}_{k}-\gamma{\bm{Z}}_{k+1},$
$\displaystyle\widetilde{\bm{{V}}}_{k+1}$
$\displaystyle={\bm{V}}_{k+1}+a_{k}({\bm{V}}_{k+1}-{\bm{V}}_{k}),$
$\displaystyle{\bm{U}}_{k+1}$
$\displaystyle=\operatorname*{arg\,min}_{{\bm{U}}}~{}\tfrac{1}{2}\|{\bm{M}}\odot({\bm{U}}-{\bm{X}})\|^{q}_{q,G}+\tfrac{\gamma}{2}{|\kern-1.125pt|}{\bm{\mathcal{W}}}{\bm{U}}+\widetilde{\bm{{V}}}_{k+1}/\gamma{|\kern-1.125pt|}^{2},$
$\displaystyle{\bm{Y}}_{k+1}$
$\displaystyle={\bm{Y}}_{k}+\gamma\big{(}{\bm{\mathcal{W}}}{\bm{U}}_{k+1}-{\bm{Z}}_{k+1})$
$\displaystyle=\widetilde{\bm{{V}}}_{k+1}+\gamma{\bm{\mathcal{W}}}{\bm{U}}_{k+1}.$

In general, we have $a_{k}\in[0,1]$. When the problem is convex, the
convergence can be guaranteed by choosing $a_{k}\in[0,1/3]$ (Boţ and Csetnek,
2016; Boţ et al., 2015).

###  B.2. Solution to Subproblem of $q=1$

When $q=1$, let ${\bm{Q}}={\bm{U}}-{\bm{X}}$, and consider

$\min_{{\bm{Y}}}~{}\tfrac{1}{2}\|{\bm{M}}\odot{\bm{Y}}\|_{1,G}+\tfrac{\gamma}{2}{|\kern-1.125pt|}{\bm{\mathcal{W}}}{\bm{Y}}+{\bm{\mathcal{W}}}{\bm{X}}+\widetilde{\bm{{V}}}_{k+1}/\gamma{|\kern-1.125pt|}^{2}.$

The optimality condition yields

$\displaystyle\frac{1}{2}{\bm{M}}\odot\partial\|{\bm{M}}\odot{\bm{Q}}\|_{1,G}+\gamma{\bm{\mathcal{W}}}^{T}({\bm{\mathcal{W}}}{\bm{Q}}+{\bm{\mathcal{W}}}{\bm{X}}+\widetilde{\bm{{V}}}_{k+1}/\gamma)$
$\displaystyle\Longleftrightarrow$
$\displaystyle~{}\frac{1}{2}{\bm{M}}\odot\partial\|{\bm{M}}\odot{\bm{Q}}\|_{1,G}+\gamma({\bm{Q}}+{\bm{X}}+{\bm{\mathcal{W}}}^{T}\widetilde{\bm{{V}}}_{k+1}/\gamma)$
$\displaystyle\Longleftrightarrow$
$\displaystyle~{}\tfrac{1}{2}\|{\bm{M}}\odot{\bm{Q}}\|_{1,G}+\tfrac{\gamma}{2}{|\kern-1.125pt|}{\bm{Q}}+{\bm{X}}+{\bm{\mathcal{W}}}^{T}\widetilde{\bm{{V}}}_{k+1}/\gamma{|\kern-1.125pt|}^{2}.$

From above we have that ${\bm{Q}}_{k+1}$ is the soft-thresholding of
$-{\bm{X}}-{\bm{\mathcal{W}}}^{T}\widetilde{\bm{{V}}}_{k+1}/\gamma$ and

${\bm{U}}_{k+1}={\bm{Q}}_{k+1}+{\bm{X}}.$

##  Appendix C Supplementary Material

We prepare additional experimental results, including data description,
details for percentage improvements we colored in Table 1, as well as
additional visualizations for the mask approximation at
https://github.com/bzho3923/MAGnet/blob/main/sm.pdf.

Table 5. Summary of the datasets for node classification tasks.

| Cora | Citeseer | PubMed | Wiki-CS | Coauthor-CS | Wisconsin | Texas | OGB-arxiv
---|---|---|---|---|---|---|---|---
# Nodes | $2,708$ | $3,327$ | $19,717$ | $11,701$ | $18,333$ | $251$ | $183$ | $169,343$
# Edges | $5,429$ | $4,732$ | $44,338$ | $216,123$ | $100,227$ | $499$ | $309$ | $1,166,243$
# Features | $1,433$ | $3,703$ | $500$ | $300$ | $6,805$ | $1,7033$ | $1,703$ | $128$
# Classes | $7$ | $6$ | $3$ | $10$ | $15$ | $5$ | $5$ | $40$
# Training Nodes | $140$ | $120$ | $60$ | $580$ | $300$ | $120$ | $87$ | $90,941$
# Validation Nodes | $500$ | $500$ | $500$ | $1769$ | $200$ | $80$ | $59$ | $29,799$
# Test Nodes | $1,000$ | $1,000$ | $1,000$ | $5847$ | $1000$ | $51$ | $37$ | $48,603$
Label Rate | $0.052$ | $0.036$ | $0.003$ | $0.050$ | $0.016$ | $0.478$ | $0.475$ | $0.537$
Feature Scale | $\\{0,1\\}$ | $\\{0,1\\}$ | $[0,1.263]$ | $[-3,3]$ | $\\{0,1\\}$ | $\\{0,1\\}$ | $\\{0,1\\}$ | $[-1.389,1.639]$

Table 6. Improvement percentage of average performance for node classification
with injection.

| Cora | Citeseer | PubMed | Coauthor-CS | Wiki-CS | Wisconsin | Texas | OGB-arxiv
---|---|---|---|---|---|---|---|---
Module | absolute | relative | absolute | relative | absolute | relative | absolute | relative | absolute | relative | absolute | relative | absolute | relative | absolute | relative
APPNP | $-0.95\%$ | $-5.44\%$ | $4.27\%$ | $17.34\%$ | $1.49\%$ | $8.92\%$ | $-13.68\%$ | $-148.29\%$ | $-13.62\%$ | $-73.15\%$ | $28.03\%$ | $159.06\%$ | $0.92\%$ | $8.68\%$ | - | -
GNNGuard | $-10.36\%$ | $-58.98\%$ | $-4.58\%$ | $-17.38\%$ | $-1.20\%$ | $7.16\%$ | $-2.11\%$ | $-22.37\%$ | $0.00\%$ | $0.00\%$ | $-2.86\%$ | $-16.24\%$ | $0.46\%$ | $4.34\%$ | $-3.90\%$ | $-78.07\%$
ElasticGNN | $12.47\%$ | $71.00\%$ | $12.21\%$ | $49.54\%$ | $5.23\%$ | $31.27\%$ | $-3.03\%$ | $-32.89\%$ | $-1.93\%$ | $-10.34\%$ | $10.55\%$ | $59.88\%$ | $1.44\%$ | $13.67\%$ | $-39.58\%$ | $-791.81\%$
AirGNN | $10.37\%$ | $58.69\%$ | $7.92\%$ | $32.14\%$ | $10.40\%$ | $62.19\%$ | $-2.71\%$ | $-28.66\%$ | $9.05\%$ | $48.60\%$ | $27.61\%$ | $161.85\%$ | $0.92\%$ | $8.68\%$ | $-23.53\%$ | $-600.75\%$
MAGnet-one | $9.78\%$ | $55.68\%$ | $2.85\%$ | $11.31\%$ | $1.89\%$ | $10.80\%$ | $1.98\%$ | $20.95\%$ | $8.24\%$ | $44.25\%$ | $15.03\%$ | $85.29\%$ | $2.29\%$ | $21.70\%$ | $-0.26\%$ | $-5.26\%$
MAGnet-gae | $14.49\%$ | $82.05\%$ | $12.52\%$ | $50.81\%$ | $11.40\%$ | $68.20\%$ | $4.96\%$ | $52.57\%$ | $10.64\%$ | $57.14\%$ | $33.31\%$ | $189.06\%$ | $3.21\%$ | $30.39\%$ | $0.38\%$ | $7.60\%$
MAGnet-true | $13.50\%$ | $76.85\%$ | $19.05\%$ | $72.22\%$ | $11.73\%$ | $70.14\%$ | $8.28\%$ | $87.66\%$ | $15.37\%$ | $82.59\%$ | $36.17\%$ | $205.29\%$ | $2.75\%$ | $26.05\%$ | $1.68\%$ | $33.63\%$

Table 7. Improvement percentage of average performance for node classification
with meta-attack.

| Cora | Citeseer | PubMed
---|---|---|---
Module | absolute | relative | absolute | relative | absolute | relative
APPNP | $-2.10\%$ | $-25.53\%$ | $0.63\%$ | $2.13\%$ | $-3.09\%$ | $-36.70\%$
GNNGuard | $-4.06\%$ | $-49.27\%$ | $4.19\%$ | $14.10\%$ | $-2.44\%$ | $-29.04\%$
ElasticGNN | $5.57\%$ | $67.53\%$ | $21.64\%$ | $72.77\%$ | $-1.28\%$ | $-15.17\%$
AirGNN | $5.16\%$ | $62.52\%$ | $18.55\%$ | $62.37\%$ | $7.82\%$ | $92.99\%$
MAGnetone (ours) | $2.72\%$ | $32.96\%$ | $12.96\%$ | $43.59\%$ | $4.05\%$ | $48.12\%$
MAGnetgae (ours) | $5.29\%$ | $64.14\%$ | $21.84\%$ | $73.43\%$ | $7.89\%$ | $93.80\%$
MAGnettrue | $7.74\%$ | $93.86\%$ | $21.95\%$ | $73.80\%$ | $8.62\%$ | $102.45\%$

##  Appendix D Dataset Descriptions

Table 5 documents key descriptive statistics of the eight datasets for the
node classification tasks. The first five datasets are downloaded from
PyTorch-Gometric (Fey and Lenssen, 2019) 666https://pytorch-
geometric.readthedocs.io/en/latest/modules/datasets.html, the two heterophilic
graphs are from Geom-GCN (Pei et al., 2020) 777https://github.com/graphdml-
uiuc-jlu/geom-gcn, and OGB-arxiv is from open graph benchmarks (Hu et al.,
2020) 888https://ogb.stanford.edu/docs/nodeprop/#ogbn-arxiv. All the
preprocessing, data split, and evaluation are guided by the source codes or
standard routines.

##  Appendix E Percentage Performance Improvement in Node Classification

In the main paper, we use the relative scores of improvements to color the
performance in Table 1, which is calculated by

$\text{Relative
Score}=\frac{S-S_{\text{corrupted}}}{S_{\text{clean}}-S_{\text{corrupted}}},$

where $S$ denotes the current score of the performed model, and
$S_{\text{clean}}$ and $S_{\text{corrupted}}$ are the accuracy score of GCN on
the clean dataset and corrupted dataset, respectively. We also report the
absolute score of improvement for a clear comparison, which is defined by

$\text{Absolute Score}=\frac{S-S_{\text{corrupted}}}{S_{\text{corrupted}}}.$

Both scores are reported in Table 6 below. In Table 1, we color the model
performance by red for positive relative scores, and by green for negative
relative scores. If the absolute value of the relative score is large, the
color would be darker.

##  Appendix F GAE visualization

Figure 7-Figure 9 visualize the sparse mask matrix of the five datasets with
anomaly injection. We are interested in the recall of the mask matrix that
exposes the quality of the mask matrix approximation. As a result, we print
the conditional mask matrix that marks the positions of approximated index
that are at the true anomalous spots. Note that we did not visualize the mask
matrix from the datasets under meta attack perturbation, as such attack
focuses major poisonings on a minority of node entities. When making
visualizations on such matrices, they are nothing more than a few horizontal
lines. For PubMed, Coauthor-CS and Wiki-CS, we only visualize a subset of the
full node attribute matrix, as the full matrix is too large to display. For
instance, the size of Coauthor-CS’s node attribute matrix is about $\approx
18000\times 7000$. Different from the other three datasets, the attributes in
PubMed and Wiki-CS has non-binary values. Consequently, we report the mask
matrix with a threshold. In other words, in Cora, Citeseer, and Coauthor-CS,
$M_{ij}$=1 if the $i,j$th value in the ground truth matrix and the perturbed
matrix are different. In PubMed, $M_{ij}$=1 if the difference of the $j$th
feature of the $i$th node in the ground truth matrix and the perturbed matrix
are larger than $0.005$. The justification is similar to Wiki-CS, where the
difference threshold is increased to $0.05$.

1 -2.5,1.8ground truth, sparsity=$0.638\%$ 2.5,1.8approximation,
sparsity=$0.362\%$

Figure 7. Mask matrix visualization for Citeseer.

1 -2.5,1.9ground truth, sparsity=$0.656\%$ 2.5,1.9approximation,
sparsity=$0.419\%$

Figure 8. Mask matrix visualization for Coauthor-CS with the first $3000$
nodes and $3000$ features. Figure 9. Mask matrix visualization for PubMed with
the first $3000$ nodes and $500$ features at threshold=$0.005$. Figure 10.
Mask matrix visualization for Wiki-CS with the first $3000$ nodes and $300$
features at threshold=$0.05$.

##  Appendix G Reliability of Mask Approximation

We investigate the different choices on the regularizes of the mask matrix
approximated by the GAE module. In the first ablation study of the main paper
we compare the approximation results by $\ell_{1}$ and $\ell_{2}$
normalization in the loss function. Here we visualize the count of true
positive and false negative predictions in Figure 11 for the seven
(relatively) small datasets. We are more interested in identifying the non-
zero positions, or positive approximations, as the majority of the mask matrix
is filled with $0$.

It turns out that the $\ell_{1}$-based mask matrix does not change drastically
among different threshold $\tau$s. In the contrast, tuning the threshold
$\tau$ is critical for the $\ell_{2}$-based scoring function to perform a
higher true positive rate and lower false negative rate. When the threshold is
properly chosen, its approximation is more reliable than the $\ell_{1}$-based
counterparts.

1 0.2,2.2True Positive-Cora

1 0.2,2.2True Positive-CiteSeer

1 0.2,2.2True Positive-PubMed

1 0.2,2.2False Negative-Cora

1 0.2,2.2False Negative-CiteSeer

1 0.2,2.2False Negative-PubMed

1 0.2,2.3True Positive-WikiCS

1 0.2,2.2True Positive-CoauthorCS

1 0.2,2.2True Positive-Wisconsin

1 0.2,2.2False Negative-WikiCS

1 0.2,2.2False Negative-CoauthorCS

1 0.2,2.2False Negative-Wisconsin

1 0.2,2.2True Positive-Texas

1 0.2,2.2False Negative-Texas

Figure 11. Comparison on the True Positive and False Negative of $\ell_{1}$
and $\ell_{2}$-based mask matrix generator on the seven datasets. The
$\ell_{1}$-based results are named in the legend by MAE, and $\ell_{2}$-based
results are denoted as MSE.