# Learning to Drop: Robust Graph Neural Network via Topological Denoising

Dongsheng Luo1∗, Wei Cheng2∗, Wenchao Yu2, Bo Zong2, Jingchao Ni2 and  Haifeng
Chen2, Xiang Zhang1 1Pennsylvania State University, 2NEC Labs America
<EMAIL_ADDRESS><EMAIL_ADDRESS>
(2021)

###### Abstract.

Graph Neural Networks (GNNs) have shown to be powerful tools for graph
analytics. The key idea is to recursively propagate and aggregate information
along edges of the given graph. Despite their success, however, the existing
GNNs are usually sensitive to the quality of the input graph. Real-world
graphs are often noisy and contain task-irrelevant edges, which may lead to
suboptimal generalization performance in the learned GNN models. In this
paper, we propose PTDNet, a parameterized topological denoising network, to
improve the robustness and generalization performance of GNNs by learning to
drop task-irrelevant edges. PTDNet prunes task-irrelevant edges by penalizing
the number of edges in the sparsified graph with parameterized networks. To
take into consideration of the topology of the entire graph, the nuclear norm
regularization is applied to impose the low-rank constraint on the resulting
sparsified graph for better generalization. PTDNet can be used as a key
component in GNN models to improve their performances on various tasks, such
as node classification and link prediction. Experimental studies on both
synthetic and benchmark datasets show that PTDNet can improve the performance
of GNNs significantly and the performance gain becomes larger for more noisy
datasets.

*Equal Contribution

††copyright: acmcopyright††journalyear: 2021††doi:
10.1145/1122445.1122456††conference:  International Conference on Web Search
and Data Mining; March 08–12, 2021; Jerusalem, Israel††booktitle: WSDM
’21:International Conference on Web Search and Data Mining, March 08–12, 2021,
Jerusalem, Israel ††price: 15.00††isbn: 978-1-4503-XXXX-X/18/06

##  1\. Introduction

In recent years, we have witnessed a dramatic increase in our ability to
extract and collect data from the physical world. In many applications, data
with complex structures are connected for their interactions and are naturally
represented as graphs (Wang et al., 2017; Ni et al., 2018; Van Essen et al.,
2013). Graphs are powerful data representations but are challenging to work
with because they require modeling both node feature information as well as
rich relational information among nodes (Sen et al., 2008; Carlson et al.,
2010; Yang et al., 2016; Hamilton et al., 2017). To tackle this challenge,
various Graph Neural Networks (GNNs) have been proposed to aggregate
information from both graph topology and node features (Hamilton et al., 2017;
Kipf and Welling, 2016a; Veličković et al., 2017; Xu et al., 2018; Zhang et
al., 2020). GNNs model node features as messages and propagate them along the
edges of the input graph. During the process, GNNs compute the representation
vector of a node by recursively aggregating and transforming representation
vectors of its neighboring nodes. Such methods have achieved state-of-the-art
performances in various tasks, including node classification and link
prediction (Zhang et al., 2018; Zhou et al., 2018).

Despite their success, GNNs are vulnerable to the quality of the given graph
due to its recursively aggregating schema. It is natural to ask: is it
necessary to aggregate all neighboring nodes? If not, is there a principled
way to select which neighboring nodes are not needed to be included? In many
real-world applications, graph data exhibit complex topology patterns. Recent
works (Rong et al., 2020; Zhao and Akoglu, 2019) have shown that GNNs are
greatly over-smoothed as edges can be pruned without loss of accuracy.
Besides, GNNs are easily aggregating task-irrelevant information, leading to
over-fitting which weakens the generalization ability. Specifically, from the
local perspective, a node might be linked to nodes with task-specific “noisy”
edges. Aggregating information from these nodes would impair the quality of
the node embedding and lead to unwanted prediction in the downstream task.
From the global view, nodes located at the boundary of clusters are connected
to nodes from multiple communities. Overwhelming information collected from
their neighbors would dilute the true underlying patterns.

As a motivating example, we consider a benchmark dataset Cora (Sen et al.,
2008). We denote the edges connecting nodes with the same label as positive
edges, otherwise, as negative edges. Table 1 shows the statistics of different
edges. It is reasonable to consider that passing messages through positive
edges leads to high quality node representation, while information aggregated
along negative edges impair the performance of GNNs (Hou et al., 2020). We
adopt Graph Convolutional Network(GCN) (Kipf and Welling, 2016a), a
representative GNN, as an example to verify this intuition. We randomly delete
some positive and negative edges and conduct GCN on the resulting graphs. As
shown in Fig. 1, the performance of GCN increases with more negative edges
removed.

Figure 1. Performance of GCN w.r.t. removing positive and negative edges on Cora. Table 1. Statistics of positive and negative edges on Cora. Dataset | # Nodes | # Edges | # Pos. Edges | # Neg. Edges
---|---|---|---|---
Cora | 2,708 | 5,429 | 4,418 | 1,011

Topological denoising is a promising solution to address the above-mentioned
challenge by removing “noisy” edges (Entezari et al., 2020; Wang et al.,
2019b). By denoising the input graph, we can prune away task-irrelevant edges
to avoid aggregating unnecessary information in GNNs. Besides, it can also
help improve the robustness and alleviate the over-smoothing problem inherent
of GNNs (Rong et al., 2020). The idea of topological denoising is not new. In
fact, this line of thinking has motivated GAT (Veličković et al., 2017) that
aggregates neighboring nodes with weights from attention mechanism and thus to
some extent alleviate the problem. Other existing methods aim to extract
smaller subgraphs from the given graphs to preserve pre-defined properties or
randomly remove/sample edges during the training process to prevent GNNs from
over-smoothing (Shin et al., 2019; Rong et al., 2020; Hamilton et al., 2017;
Wang et al., 2020). However, within unsupervised settings, subgraphs sampled
from these approaches may be suboptimal for downstream tasks and also lack
persuasive rationales to explain the outcomes of the model for the task.
Instead, the task-irrelevant “noisy” edges should be specific to the
downstream objective. Besides, in real-life graphs, node contents and graph
topology provide complementary information to each other. Denoising process
should take both information into consideration, which is overlooked by
existing methods.

In this paper, we propose a Parameterized Topological Denoising network
(PTDNet) to enhance the performance of GNNs. We use deep neural networks,
considering both structural and content information as inputs, to learn to
drop task-irrelevant edges in a data-driven way. PTDNet prunes the graph edges
by penalizing the number of edges in the sparsified graph with parameterized
networks (Louizos et al., 2017; Xue and Xin, 2020). The denoised graphs are
then fed into GNNs for robust learning. The introduced sparsity in the
neighboring nodes aggregation has a variety of merits: 1) a sparse aggregation
is less complicated and hence generalizes well (Girosi, 1998); 2) it can
facilitate interpretability and help infer task-relevant neighbors.
Considering the combinatorial nature of the denoising process, we relax the
discrete constraint with continuous distributions that could be optimized
efficiently with backpropagation, enabling PTDNet to be compatible with
various GNNs in both transductive and inductive settings, including GCN (Kipf
and Welling, 2016a), Graph Attention Network (Veličković et al., 2017),
GraphSage (Hamilton et al., 2017), etc. In PTDNet, the denoising networks and
GNN are jointly optimized in an end-to-end fashion. Different from
conventional methods that remove edges randomly or based on pre-defined rules,
the denoising process of PTDNet is guided by the supervision of the downstream
objective in the training phase.

To further concern the global topology, the nuclear norm regularization is
applied to impose low-rank constraint on the resulting sparsified graph for
better generalization. Due to the discontinuous nature of the rank
minimization problem, PTDNet smooths the constraint with the nuclear norm,
which is the tightest convex envelope of the rank (Recht et al., 2010). This
regularization denoises the input graph from the global topology perspective
by removing edges connecting multiple communities to improve generalization
ability and robustness of GNNs (Entezari et al., 2020). Experimental results
on both synthetic and benchmark datasets demonstrate that PTDNet can
effectively enhance the performance and robustness of GNNs.

##  2\. Related Work

GNNs are powerful tools to investigate the graph data with node contents. GNN
models utilize the message passing mechanism to encode both graph structural
information and node features into vector representations. These vectors are
then used to node-level or graph-level downstream tasks. GNNs were initially
proposed in (Gori et al., 2005), and extended in (Scarselli et al., 2008).
These methods learn node representations by iteratively aggregating neighbor
information until reaching a static state. Inspired by the success of
convolutional neural networks (CNNs) in computer vision, graph convolutional
networks in the graph spectral domain were proposed based upon graph Fourier
transform (Bruna et al., 2013). Multiple extensions were further proposed
(Kipf and Welling, 2016a; Defferrard et al., 2016; Scarselli et al., 2008; Li
et al., 2018b; Veličković et al., 2017; Ma et al., 2019). The express power of
GNNs were analyzed in (Xu et al., 2018). DropEdge and PairNorm investigated
the over-smoothing problem of stacking multiple GNN layers (Rong et al., 2020;
Zhao and Akoglu, 2019).

Graph Sparsification and Sampling. Conventional graph sparsification
approximates the large input graph with a sparse subgraph to enable efficient
computation, and at the same time preserve certain properties. Different
notions have been extensively studied including pairwise distances betweenness
(Chew, 1989), sizes of all cuts (Benczúr and Karger, 1996), node degree
distributions (Eden et al., 2018), and spectral properties (Hermsdorff and
Gunderson, 2019; Arora and Upadhyay, 2019). These methods remove edges only
based upon the structural information, which limits their power when combining
with GNNs. Besides, without supervised feedback from the downstream task,
these approaches may generate subgraphs with suboptimal structural properties.
NeuralSparse (Zheng et al., 2020) learns $k$-neighbor subgraphs for robust
graph representation learning by selecting at most $k$ edges for each nodes.
The $k$-neighbor assumption however limits its learning power and may lead to
suboptimal performance in generalization.

Recently, graph sampling has been investigated in GNNs for fast computation
and better generalization capacity, including neighbor-level (Hamilton et al.,
2017), node-level (Chen et al., 2018; Huang et al., 2018; Zeng et al., 2020),
and edge-level sampling methods (Rong et al., 2020). Unlike these methods that
randomly sample edges in the training phase, PTDNet utilizes parametrized
networks to actively remove task-specific noisy edges. With supervised
guidance from downstream objective, the generated subgraphs benefit GNNs in
not only robustness but also accuracy and interpretability. Besides, PTDNet
has better generalization capacity as the parametrized networks can be used
for inductive inference.

##  3\. Notations and preliminaries

Notations. In general, we use lowercase, bold uppercase, and bold lowercase
letters for scalars, matrices, and vectors, respectively. For example, we use
$\mathbf{Z}$ to denote a matrix, whose $i,j$-th entry is denoted by $z_{ij}$,
a lowercase character with subscripts. Let $G=(\mathcal{V},\mathcal{E})$
represent the input graph with $n$ nodes, where $\mathcal{V},\mathcal{E}$
stand for its node/edge set, respectively. The adjacency matrix of $G$ is
denoted by $\mathbf{A}\in\mathbb{R}^{n\times n}$. Node features are denoted by
matrix $\mathbf{X}\in\mathbb{R}^{n\times m}$ with $m$ as the dimensionality of
node features. We use $\mathbf{Y}$ to denote the labels in the downstream
task. For instance, in the node classification task,
$\mathbf{Y}\in\mathbb{R}^{n\times c}$ represents node labels, where $c$ is the
number of classes.

GNN layer. Applying a GNN layer consists of the propagation step and the
output step (Zhou et al., 2018). At the propagation step, the aggregator first
computes the message for each edge. For an edge $(v_{i},v_{j})$, the
aggregator takes the representations of $v_{i}$ and $v_{j}$ in previous layer
as inputs, denoted by $\mathbf{h}_{i}^{t-1}$, and $\mathbf{h}_{j}^{t-1}$,
respectively. Then, the aggregator collects messages from local neighborhoods
for each node $v_{i}$. At the output step, the updater computes its new hidden
representation, denoted by $\mathbf{h}_{v}^{t}$.

GNN models adopt message passing mechanisms to propagate and aggregate
information along the input graph to learn node representations. The
performances can be heavily affected by the quality of the input graph.
Messages aggregated along “noisy” edges may decrease the quality of node
embeddings. Overwhelming information from multiple communities put GNNs at the
risk of over-smoothing, especially when multiple GNN layers are stacked (Zhao
and Akoglu, 2019; Rong et al., 2020; Loukas, 2020). Existing methods either
utilize graph sparsification strategies to extract subgraphs or randomly
sample graphs to enhance the robustness of GNNs. Basically, they are conducted
in an unsupervised way, limiting their ability to filter out task-specific
noisy edges.

The core idea of PTDNet is to actively filter out task-specific noisy edges in
the input graph with a parameterized network. It consists of the denoising
network and general GNNs. GNNs can be applied under both inductive and
transductive settings. We first give an overview of PTDNet in Sec. 4.1,
followed by details of the denoising network in Sec. 4.2. To enhance the
generalization ability of PTDNet, we further introduce the low-rank constraint
on resulting graphs and provide smoothing relaxation to achieve an end-to-end
model.

##  4\. The PTDNet

###  4.1. The overall architecture

The architecture of PTDNet is shown in Fig. 2(a). It consists of two major
components, the denoising networks and the GNNs. The denoising network is a
multi-layer network that samples a subgraph from a learned distribution of
edges. PTDNet is compatible with most existing GNNs, such as GCN (Kipf and
Welling, 2016a), GraphSage (Hamilton et al., 2017), GAT (Veličković et al.,
2017), GIN (Xu et al., 2018), etc. With relaxations, the denoising network is
differentiable and can be jointly optimized with GNNs guided by supervised
downstream signals.

###  4.2. The denoising network

####  4.2.1. Graph edge sparsification

The goal of the denoising network is to generate a subgraph filtering out
task-irrelevant edges for GNN layers. For the $l$-th GNN layer, we introduce a
binary matrix $\mathbf{Z}^{l}\in\\{0,1\\}^{|\mathcal{V}|\times|\mathcal{V}|}$,
with $z^{l}_{u,v}$ denoting whether the edge between node $u$ and $v$ is
present (0 indicates noisy edge).

Formally, the adjacency matrix of the resulting subgraph is
$\mathbf{A}^{l}=\mathbf{A}\odot\mathbf{Z}^{l}$ ,where $\odot$ is the element-
wise product. One way to reduce noisy edges with the least assumptions about
$\mathbf{A}^{l}$ is to directly penalize the number of non-zero entries in
$\mathbf{Z}^{l}$ of different layers.

(1)
$\small\sum_{l=1}^{L}||\mathbf{Z}^{l}||_{0}=\sum_{l=1}^{L}\sum_{(u,v)\in\mathcal{E}}\mathbb{I}[z^{l}_{u,v}\neq
0],$

where $\mathbb{I}[\cdot]$ is an indicator function, with $\mathbb{I}[True]=1$
and $\mathbb{I}[False]=0$, $||\cdot||_{0}$ is the $\ell_{0}$ norm. There are
$2^{|\mathcal{E}|}$ possible states of $\mathbf{Z}^{l}$. Because of its
nondifferentiability and combinatorial nature, optimizing this penalty is
computationally intractable. Therefore, we consider each binary number
$z^{l}_{u,v}$ to be drawn from a Bernoulli distribution parameterized by
$\pi^{l}_{u,v}$, i.e., $z^{l}_{u,v}\sim Bern(\pi^{l}_{u,v})$. The matrix of
$\pi_{u,v}^{l}$’s is denoted by $\Pi^{l}$. Then, penalizing the non-zero
entries in $\mathbf{Z}^{l}$, i.e., the number of edges being used, can be
reformulated as regularizing $\sum_{(u,v)\in\mathcal{E}}\pi^{l}_{u,v}$
(Louizos et al., 2017).

Since $\pi_{u,v}^{l}$ is optimized jointly with the downstream task, it
describes the task-specific quality of the edge $(u,v)$. A small value of
$\pi_{u,v}^{l}$ indicates the edge $(u,v)$ is more likely to be noise and
should be with small weight or even be removed in the following GNN. Although
the regularization of the reformulated form is continuous, the adjacency
matrix of the resulting graph is still generated by a binary matrix
$\mathbf{Z}^{l}$. The expected cost of downstream task could be modeled as
$L(\\{\Pi^{l}\\}^{L}_{l=1})=\mathbb{E}_{\mathbf{Z}^{1}\sim
p(\Pi^{1}),\cdots,\mathbf{Z}^{L}\sim
p(\Pi^{L})}f(\\{\mathbf{Z}^{l}\\}^{L}_{l=1},\mathbf{X})$. To minimize the
expected cost via gradient descent, we need to estimate the gradient
$\nabla_{\Pi^{l}}\mathbb{E}_{\mathbf{Z}^{1}\sim
p(\Pi^{1}),\cdots,\mathbf{Z}^{L}\sim
p(\Pi^{L})}f(\\{\mathbf{Z}^{l}\\}^{L}_{l=1},\mathbf{X})$,
$l\in[1,2,\cdots,L]$. Existing methods adopt various estimators to approximate
the gradient, including score function (Williams, 1992), straight-through
(Bengio et al., 2013), etc. However, these methods suffer from either high
variance or biased gradients (Mnih and Gregor, 2014). In addition, to make
PTDNet suitable for the inductive setting and enhance generalization ability,
a parameterized method for modeling $\mathbf{Z}^{l}$ should be adopted.

####  4.2.2. Continuous relaxation with parameterized networks

To efficiently optimize subgraphs with gradient methods, we adopt the
reparameterization trick (Jang et al., 2016) and relax the binary entries
$z_{u,v}^{l}$ from being drawn from a Bernoulli distribution to a
deterministic function $g$ of parameters $\alpha_{u,v}^{l}\in\mathbb{R}$ and
an independent random variable $\epsilon^{l}$. That is
$z_{u,v}^{l}=g(\alpha_{u,v}^{l},\epsilon^{l})$.

(2)
$\small\nabla_{\alpha_{u,v}^{l}}\mathbb{E}_{\epsilon^{1},...,\epsilon^{L}}f(\\{g,\mathbf{X}\\})=\nabla_{\alpha_{u,v}^{l}}\mathbb{E}_{\epsilon^{1},...,\epsilon^{L}}\left[\frac{\partial
f}{\partial g}\frac{\partial g}{\partial\alpha_{u,v}^{l}}\right].$

(a) Framework of PTDNet.

(b) Computation for low-rank constraint.

Figure 2. The PTDNet model.

To enable the inductive setting, we should not only figure out which edges but
also why they should be filtered out. To learn to drop, for each edge $(u,v)$,
we adopt parameterized networks to model the relationship between the task-
specific quality $\pi_{u,v}^{l}$ and the node information including node
contents and topological structure. In the training phase, we jointly optimize
denoising networks and GNNs. In the testing phase, the input graphs could also
be denoised with the learned denoising networks. Since we need to compute a
subgraph of the input graph, the time complexity of the denoising network in
the inference phase is linear to the number of edges $O(|\mathcal{E}|)$.

Following (Veličković et al., 2017), we adopt deep neural networks to learn
the parameter $\alpha_{u,v}^{l}$ that controls whether to remove the edge
($u,v$). Without loss of generality, we focus on a node $u$ in the training
graph. Let $\mathcal{N}_{u}$ be its neighbors. For the $l$-th GNN layer, we
calculate $\alpha_{u,v}^{l}$ for node $u$ and $v\in\mathcal{N}_{u}$ with
$\alpha^{l}_{uv}=f^{l}_{\theta^{l}}(\mathbf{h}^{l}_{u},\mathbf{h}^{l}_{v})$,
where $f_{\theta^{l}}^{l}$ is an MLP parameterized by $\theta^{l}$. To get
$z^{l}_{u,v}$, we utilize the concrete distribution along with hard sigmoid
function (Maddison et al., 2016; Louizos et al., 2017). First, we draw
$s_{u,v}^{l}$ from a binary concrete distribution with $\alpha^{l}_{uv}$
parameterizing the location (Maddison et al., 2016; Jang et al., 2016).
Formally,

(3) $\small\epsilon\sim\text{Uniform}(0,1),\>\quad
s_{u,v}^{l}=\sigma((\log\epsilon-\log(1-\epsilon)+\alpha^{l}_{uv})/\tau),$

where $\tau\in\mathcal{R}^{+}$ indicates the temperature and
$\sigma(x)=\frac{1}{1+e^{-x}}$ is the sigmoid function. With $\tau>0$, the
function is smoothed with a well-defined gradient $\frac{\partial
s_{u,v}^{l}}{\partial\alpha^{l}_{uv}}$, enabling efficient optimization of the
parameterized denoising network.

Since the binary concrete distribution has a range of (0,1), to encourage the
weights for task-specific noisy edges to be exactly zeros, we first extend the
range to $(\gamma,\zeta)$, with $\gamma<0$ and $\zeta>1$ (Louizos et al.,
2017). Then, we compute $z^{l}_{u,v}$ by clipping the negative values to 0 and
values larger than 1 to 1.

(4)
$\small\bar{s}_{u,v}^{l}=t(s_{u,v}^{l})=s_{u,v}^{l}(\zeta-\gamma)+\gamma,\quad
z^{l}_{u,v}=\text{min}(1,\text{max}(\bar{s}_{u,v}^{l},0)).$

Within the above formulation, the constraint on the number of non-zero entries
in $\mathbf{Z}^{l}$ in Eq.( 1) can be reformulated with

(5)
$\small\mathcal{R}_{c}=\sum_{l=1}^{L}\sum_{(u,v)\in\mathcal{E}}(1-\mathbb{P}_{\bar{s}^{l}_{u,v}}(0|\theta^{l})).$

$\mathbb{P}_{\bar{s}^{l}_{u,v}}(0|\theta^{l})$ is the cumulative distribution
function (CDF) of $\bar{s}^{l}_{u,v}$.

As shown in (Maddison et al., 2016), the density of $s^{l}_{u,v}$ is

(6)
$p_{s^{l}_{u,v}}({x})=\frac{\tau\alpha_{u,v}^{l}x^{-\tau-1}(1-x)^{-\tau-1}}{(\alpha_{u,v}^{l}x^{-\tau}+(1-x)^{-\tau})^{2}}.$

The CDF of variable $s^{l}_{u,v}$ is

(7) $\mathbb{P}_{s^{l}_{u,v}}(x)=\sigma((\log
x-\log(1-x))\tau-\alpha_{u,v}^{l}).$

Since the function $\bar{s}_{u,v}^{l}=t(s_{u,v}^{l})$ in Eq. (4) is monotonic.
The probability density function of $\bar{s}_{u,v}^{l}$ is

(8) $\displaystyle
p_{\bar{s}^{l}_{u,v}}(x)=p_{s^{l}_{u,v}}(t^{-1}(x))|\frac{\partial}{\partial
x}t^{-1}(x)|$
$\displaystyle=\frac{(\zeta-\gamma)\tau\alpha_{u,v}^{l}(x-\gamma)^{-\tau-1}(\zeta-x)^{-\tau-1}}{(\alpha_{u,v}^{l}(x-\gamma)^{-\tau}+(\zeta-x)^{-\tau})^{2}}.$

Similarly, we have the CDF of $\bar{s}^{l}_{u,v}$

(9)
$\displaystyle\mathbb{P}_{\bar{s}^{l}_{u,v}}(x)=\mathbb{P}_{s^{l}_{u,v}}(t^{-1}(x))$
$\displaystyle=\sigma((\log(x-\gamma)-\log(\zeta-x))\tau-\alpha_{u,v}^{l}).$

By setting $x=0$, we have the

(10)
$\mathbb{P}_{\bar{s}^{l}_{u,v}}(0|\theta^{l})=\sigma(\tau\log\frac{-\gamma}{\zeta}-\alpha_{u,v}^{l}).$

Algorithm 1 summarizes the overall training of PTDNet.

1: Input: Training Graph $G=(\mathcal{V},\mathcal{E})$, node features
$\mathbf{X}$, number of GNN layers $L$, labels $\mathbf{Y}$ for downstream
task.  2: Output: Predicted labels for downstream task  3: for each minibatch
do 4: for $l\leftarrow 1$ to $L$ do 5:
$G_{d}=(\mathcal{V},\mathcal{E}_{d})\leftarrow$ subgraph of $G$ sampled by
$l$-th denoising network.  6: Feed $G_{d}$ into the following GNN layer.  7:
$\mathbf{H}^{l}\leftarrow$ hidden representations updated by GNN layer.  8:
end for 9: $\\{\hat{\mathbf{y}}_{v}|v\in\mathcal{V}\\}\leftarrow$ prediction
with $\mathbf{H}^{L}$.  10: Compute $loss(\hat{\mathbf{Y}},\mathbf{Y})$ and
regularizors.  11: Update parameters of GNN and denoising networks.  12: end
for

Algorithm 1 PTDNet algorithm

1: Input: Adjacency $\mathbf{A}^{l}$, approximate hyper-parameter $K$ 2:
Output: nuclear norm loss $\tilde{\mathcal{R}}_{lr}$ 3: for $l\leftarrow 1$ to
$L$ do 4:
$(\mathbf{U}^{l})\Lambda^{l}(\mathbf{V}^{l})^{*}\leftarrow\text{SVD}(\mathbf{A}^{l})$
$\triangleright$ dismiss gradients at backpro.  5:
$\mathbf{B}\leftarrow(\mathbf{A}^{l})^{*}\mathbf{A}^{l}$ 6: for $i\leftarrow
1$ to $K$ do 7:
$\mathbf{v}^{l}_{i}\leftarrow$PI($\mathbf{B},\mathbf{v}_{i}^{l}$)  8:
$\tilde{\lambda}^{l}_{i}\leftarrow\sqrt{[(\mathbf{v}^{l}_{i})^{T}\mathbf{B}\mathbf{v}^{l}_{i}]/[(\mathbf{v}^{l}_{i})^{T}\mathbf{v}^{l}_{i}]}$
9:
$\mathbf{B}\leftarrow\mathbf{B}-\mathbf{B}\mathbf{v}^{l}_{i}(\mathbf{v}^{l}_{i})^{T}$
$\triangleright$ deflation 10: end for 11: end for 12:
$\tilde{\mathcal{R}}_{lr}\leftarrow\sum_{l=1}^{L}\sum_{i=1}^{K}|\tilde{\lambda}^{l}_{i}|$

Algorithm 2 Forward pass to compute nuclear norm

###  4.3. The low-rank constraint

In the previous section, we introduced parameterized networks to remove the
task-specific noisy edges from the local neighborhood perspective. In real-
life graph data, nodes from multiple classes can be divided into different
clusters. Intuitively, nodes from different topological communities are more
likely with different labels (Fortunato, 2009). Hence, edges connecting
multiple communities are highly possible noise for GNNs. Based upon this
intuition, we further introduce a low-rank constraint on the adjacency matrix
of the resulting subgraph to enhance the generalization capacity and
robustness, since the rank of the adjacency matrix reflects the number of
clusters. This regularization denoises the input graph from the global
topology perspective by encouraging the denoising networks to remove edges
connecting multiple communities such that the resulting subgraphs to have
dense connections within communities while sparse between them (Kanada et al.,
2018). Recent work also shows that graphs with low rank are more robust to
network attacks (Entezari et al., 2020; Jin et al., 2020).

Formally, the straightforward regularizer $\mathcal{R}_{lr}$ for low-rank
constraint of PTDNet is $\sum_{l=1}^{L}\text{Rank}(\mathbf{A}^{l})$, where
$\mathbf{A}^{l}$ is the adjacency matrix for the $l$-th GNN layer. It has been
shown in previous studies that the matrix rank minimization problem (RMP) is
NP-hard (David, 1995). We approximately relax the intractable problem with the
nuclear norm, which is the convex surrogate for RMP problem (Friedland and
Lim, 2018). The nuclear norm of a matrix is defined as the sum of its singular
values. It is a convex function that can be optimized efficiently. Besides,
previous studies have shown that in practice, nuclear norm constraints produce
very low-rank solutions (Entezari et al., 2020; Friedland and Lim, 2018; Recht
et al., 2010). With nuclear norm minimization, the regularizer is

(11)
$\small\mathcal{R}_{lr}=\sum_{l=1}^{L}||\mathbf{A}^{l}||_{*}=\sum_{l=1}^{L}\sum_{i=1}^{|\mathcal{V}|}|\lambda^{l}_{i}|,$

where $\lambda_{i}^{l}$ is the $i$-th largest singular values of graph
adjacency matrix $\mathbf{A}^{l}$.

Singular value decomposition (SVD) is required to optimize the nuclear norm
regularization. However, SVD may lead to unstable results during
backpropagation. As shown in (Ionescu et al., 2015), the partial derivatives
of the nuclear norm requires computing of a matrix $\mathbf{M}^{l}$ with
elements

(12) $\small
m^{l}_{ij}=\left\\{\begin{array}[]{ll}1/((\lambda^{l}_{i})^{2}-(\lambda^{l}_{j})^{2}),&i\neq
j\\\ 0,&i=j\end{array}.\right.$

When $(\lambda^{l}_{i})^{2}-(\lambda^{l}_{j})^{2}$ is small, the partial
derivatives become very large, leading to an arithmetic overflow. Besides, the
gradient-based optimization on SVD is time-consuming. The Power Iteration (PI)
method with deflation procedure is one way to solve this problem (Nakatsukasa
and Higham, 2013; Ortega, 1990; Wang et al., 2019a). PI approximately computes
the largest eigenvalue and the dominant eigenvector of the matrix
$(\mathbf{A}^{l})^{*}\mathbf{A}^{l}$with an iterative procedure from a
randomly initiated vector. $(\mathbf{A}^{l})^{*}$ stands for the transpose-
conjugate matrix of $\mathbf{A}^{l}$. The largest singular value of
$\mathbf{A}^{l}$ is then the square root of the largest eigenvalues. To
calculate other eigenvectors, the deflation procedure is involved to
iteratively remove the projection of the input matrix on this vector. However,
PI may output inaccurate approximations if two eigenvalues are close to each
other. The situation becomes worse when we consider eigenvalues near zero.
Besides, with randomly initiated vectors, PI may need more iterations to get a
precise approximation.

To address the problem, we combine SVD and PI (Wang et al., 2019a) and further
relax the nuclear norm to Ky Fan $K$-norm (Fan, 1951), which is the sum of top
$K$, $1\leq K\ll|\mathcal{V}|$, largest singular values. Fig. 2(b) shows the
forward pass and backpropagation of the nuclear norm. In the forward pass, as
shown in Algorithm 2, SVD is used to calculate singular values, left and right
singular vectors. Then we get the nuclear norm as the regularization loss. In
order to minimize the nuclear norm, we utilize the power iteration to compute
top $K$ singular values, denoted by
$\tilde{\lambda}^{l}_{1},...\tilde{\lambda}^{l}_{K}$. Note that the PI process
does not update the values in singular vectors and singular values. It only
serves to compute the gradients during backpropagation, which is shown with
red dot lines in Fig. 2(b). We estimate the nuclear norm with
$\tilde{\mathcal{R}}_{lr}=\sum_{l=1}^{L}\sum_{i=1}^{K}|\tilde{\lambda}^{l}_{i}|$.
$\tilde{\mathcal{R}}_{lr}$ is a lower bound function of $\mathcal{R}_{lr}$
with gap

(13)
$\displaystyle\mathcal{R}_{lr}-\tilde{\mathcal{R}}_{lr}=\sum_{l=1}^{L}\sum_{i=K+1}^{|\mathcal{V}|}|\tilde{\lambda}^{l}_{i}|=\sum_{l=1}^{L}\sum_{i=K+1}^{|\mathcal{V}|}|\lambda^{l}_{i}|\leq(|\mathcal{V}|-K)\sum_{l=1}^{L}|\lambda^{l}_{K+1}|.$

It is obvious that
$\lceil\frac{|\mathcal{V}|}{K}\rceil\tilde{\mathcal{R}}_{lr}$ is the upper
bound of $\mathcal{R}_{lr}$. We dismiss the constant coefficient and minimize
$\tilde{\mathcal{R}}_{lr}$ as the low-rank constraint.

##  5\. Experimental study

In this section, we empirically evaluate the robustness and effectiveness of
PTDNet with both synthetic and benchmark datasets. First, we apply PTDNet to
popular GNN models for node classification on benchmark datasets. Second, we
evaluate the robustness of PTDNet by injecting additional noise. Moreover, we
also provide insight into the denoising process by checking the edges removed
by PTDNet. We also conduct comprehensive experiments to uncover insights of
PTDNet, including empirically demonstrating the effects of regularizers,
parameter study, analyzing the over-smoothing problem inherent in GNNs, and
applying PTDNet to another downstream task, i.e., link prediction.

Table 2. Dataset statistics Dataset | Cora | Citeseer | Pubmed | PPI
---|---|---|---|---
Nodes | 2,708 | 3,327 | 19,717 | 56,944
Edge | 5,429 | 4,732 | 44,338 | 818,716
Fea. | 1,433 | 3,703 | 500 | 50
Classes | 7 | 6 | 3 | 121
Train. | 140 | 120 | 100 | 44,906
Val. | 500 | 500 | 500 | 6,514
Test. | 1,000 | 1,000 | 1,000 | 5,524

###  5.1. Experimental setup

Datasets. Four benchmark datasets are adopted in our experiments. Cora,
Citeseer, and Pubmed are citation graphs where each node is a document and
edges describe the citation relationship. A document is assigned with a unique
label based on its topic. Node features are bag-of-words representations of
the documents. We follow the standard train/val/test splits in (Kipf and
Welling, 2016a; Veličković et al., 2017) with very scarce labelled nodes,
which are different from the full-supervised setting in DropEdge (Rong et al.,
2020). PPI contains graphs describing protein-protein interaction in different
human tissues. Positional gene sets, motif gene sets, and immunological
signatures are used as node features. Gene ontology sets are used as labels.
The statistics of these datasets are listed in Table 2.

Implementations & metrics. We consider three representative GNNs as backbones,
including GCN (Kipf and Welling, 2016a), GraphSage (Hamilton et al., 2017),
GAT (Veličković et al., 2017). Note that our model is a general framework that
is compatible with diverse GNN models. Recent sophisticated models can also be
combined with our framework to improve their performances and robustness.
Achieving SOTA performances by using a complex architecture is not the main
research point of this paper. We compare with most recent state-of-the-art
sampling and sparsification methods, DropEdge (Rong et al., 2020) and
NeuralSparse (Zheng et al., 2020). For GraphSage, we use the mean aggregation.
We follow the experimental setting in (Rong et al., 2020) to perform a random
hyper-parameter search for each model. For each setting, we run 10 times and
report the average results. Parameters are tuned via cross-validation. We also
include a variant of PTDNet by removing the low-rank constraint as the
ablation study. For single-label classification datasets, including Cora,
Citeseer, and Pubmed, we evaluate the performance with accuracy (Kipf and
Welling, 2016a). For PPI, we evaluate with micro-F1 scores (Hamilton et al.,
2017).

All experiments are conducted on a Linux machine with 8 NVIDIA Tesla V100
GPUs, each with 32GB memory. CUDA version is 9.0 and Driver Version is
384.183. All methods are implemented with Tensorflow 1.12.

###  5.2. Effectiveness evaluation

Table 3. Node classification. Backbone | Method | Cora | Citeseer | Pubmed | PPI
---|---|---|---|---|---
GCN | Basic |  0.811 $\pm$ 0.015 |  0.703 $\pm$ 0.012 |  0.790 $\pm$ 0.020 |  0.660 $\pm$ 0.024
DropEdge |  0.809 $\pm$ 0.035 |  0.722 $\pm$ 0.032 |  0.785 $\pm$ 0.043 |  0.606 $\pm$ 0.041
NeuralSparse |  0.821 $\pm$ 0.014 |  0.715 $\pm$ 0.014 |  0.788 $\pm$ 0.018 |  0.651 $\pm$ 0.014
PTDNet-wl |  0.824 $\pm$ 0.018 |  0.717 $\pm$ 0.170 |  0.791 $\pm$ 0.012 |  0.752 $\pm$ 0.017
PTDNet |  0.828 $\pm$ 0.026 |  0.727 $\pm$ 0.018 |  0.798 $\pm$ 0.024 |  0.803 $\pm$ 0.008
GraghSage | Basic |  0.792 $\pm$ 0.027 |  0.676 $\pm$ 0.023 |  0.767 $\pm$ 0.020 |  0.618 $\pm$ 0.014
DropEdge |  0.787 $\pm$ 0.023 |  0.670 $\pm$ 0.031 |  0.748 $\pm$ 0.026 |  0.610 $\pm$ 0.035
NeuralSparse |  0.793 $\pm$ 0.021 |  0.674 $\pm$ 0.011 |  0.751 $\pm$ 0.021 |  0.626 $\pm$ 0.023
PTDNet-wl |  0.794 $\pm$ 0.026 |  0.678 $\pm$ 0.022 |  0.770 $\pm$ 0.024 |  0.645 $\pm$ 0.020
PTDNet |  0.803 $\pm$ 0.019 |  0.679 $\pm$ 0.018 |  0.771 $\pm$ 0.010 |  0.648 $\pm$ 0.025
GAT | Basic |  0.830 $\pm$ 0.007 |  0.721 $\pm$ 0.009 |  0.790 $\pm$ 0.008 |  0.973 $\pm$ 0.012
DropEdge |  0.832 $\pm$ 0.040 |  0.709 $\pm$ 0.020 |  0.779 $\pm$ 0.019 |  0.850 $\pm$ 0.038
NeuralSparse |  0.834 $\pm$ 0.015 |  0.724 $\pm$ 0.026 |  0.780 $\pm$ 0.017 |  0.921 $\pm$ 0.018
PTDNet-wl |  0.837 $\pm$ 0.022 |  0.723 $\pm$ 0.014 |  0.792 $\pm$ 0.014 |  0.978 $\pm$ 0.018
PTDNet |  0.844 $\pm$ 0.023 |  0.737 $\pm$ 0.031 |  0.793 $\pm$ 0.015 |  0.980 $\pm$ 0.022

Table 3 summarizes the results on different datasets. PTDNet-wl is the variant
of PTDNet by removing the low-rank constraint for ablation study. The
comparison results demonstrate that by including the denoising part, PTDNet
achieves the state-of-the-art or matched performance across different
benchmarks. Specifically, 1) comparing to basic GNNs, PTDNet-wl can improve
the performance and generalization capacity by including denoising process to
GNNs. 2) In PTDNet, we further include the low-rank constraint to denoise the
input graph from the global perspective. As discussed in Sec. 4.3, graphs with
low ranks are more robust to complex structures. It encourages to remove the
edges across different clusters and helps to alleviate the over-smoothing
problem. 3) PTDNet utilizes a parameterized method to actively remove task-
irrelevant edges or decrease their weights. The denoising networks can also be
used in the testing phase, which shows a better generalization capacity. While
DropEdge only works in the training phase to randomly remove edges. These
explain the reason why PTDNet outperforms DropEdge. 4) PTDNet outperforms
recent work – NeuralSparse because NeuralSparse constrains the extracted
subgraphs to be $k$-neighbor graphs. The $k$-neighbor assumption however
limits its learning power and may lead to suboptimal performance in
generalization. Moreover, NeuralSparse does not consider the low-rank
constraints on the resulting sparsified graph, thus achieves worse
generalization performance.

(a) GCN

(b) GraphSage

(c) GAT

Figure 3. Accuracy performance with noisy edges in Cora.

###  5.3. Robustness evaluation

In this part, we evaluate the robustness of PTDNet by manually including noisy
edges. We use the Cora dataset and randomly connect $N$ pairs of previously
unlinked nodes with $N$ ranging from 1000 to 20,000. We compare the proposed
method to baselines with all there backbones. Performances are shown in Fig.
3. We have the following observations. 1) PTDNet consistently outperforms
DropEdge, NeuralSparse and the basic backbones with various numbers of noisy
edges. The comparison demonstrates the robustness of PTDNet. 2) DropEdge
randomly samples a subgraph for GNN layers. In most cases, DropEdge reports
worse performances than the original backbones. The comparison demonstrates
that a random sampling strategy used in DropEdge is vulnerable to noisy edges.
3) NeuralSparse selects noise edges guided by task signals thus achieves
better results than basic backbones. However, it selects at most $k$ edges for
each nodes, which may lead to suboptimal performance. 4) The margins between
results of PTDNet and basic backbones become large when more noise are
injected. Specifically, PTDNet relatively improves the accuracy scores by
37.37% for GCN, 13.4% for GraphSage, and 16.1% for GAT with 20,000 noisy
edges.

###  5.4. On denoising process

In this section, we use controllable synthetic datasets to analyze the
denoising process of PTDNet, which has 5 labels and 30 features per node. We
first randomly sample five 30-dimensional vectors as the centroids, one for
each label. Then, for each label, we sample nodes from a Gaussian distribution
with the centroid as the mean. The variance, which controls the quality of
content information is set to 80. The number of nodes for each label is drawn
from another Gaussian distribution $\mathcal{N}(200,25)$.

To validate GNNs on fusing node content and topology, we build a graph
containing complementary information with node features. Specifically, we use
the distance between a node and the centroid node of its label as the metric
to evaluate the quality of the node feature. The probability that it connects
to another node with a different label is positively proportional to the
feature quality. The resulting graph contains 1,018 nodes and 4,945 edges. We
randomly select 60/20/20% nodes for training/validation/testing, respectively.

We use GCN as the backbone for example. The denoising process of the first
PTDNet layer is shown in Fig. 4. Red lines represent the mean weight, i.e.,
$z$ in Sec. 4, of positive edges (edges connected nodes with the same label),
and blue dotted lines are for negative edges. Fig. 4(a), 4(b) count the edges
linked with a training/testing node, respectively. We also show the results of
DropEdge to see the case of random selection. These figures demonstrate that
DropEdge, an unparameterized method, cannot actively drop the task-irrelevant
edges. While PTDNet can detect negative edges and remove or assign them with
lower weights. The denoising process of PTDNet leads to higher accuracy with
more iterations, which is shown in Fig. 4(c). In addition, the consistent
performance of PTDNet on testing nodes shows that our parameterized method can
still learn to drop negative edges in the testing phase, demonstrating the
generalization capacity of PTDNet. Besides, we plot the degree(volume)
distribution of the input graph, subgraph sampled by DropEdge and PTDNet in
Fig. 4(d). We observe that both PTDNet and DropEdge can keep the distribution
property of the input graph.

(a) Training edges

(b) Testing edges

(c) PTDNet accuracy

(d) Degree distribution

Figure 4. Denoising on a synthetic dataset.

###  5.5. Effects of regularizers

In this part, we adopt GCN as the backbone to analyze the effects of
regularizers. We first show the accuracy performance of PTDNet w.r.t
coefficients for regularizers in Fig. 5. For each choice, we fix that value
for the coefficient and use the genetic algorithm to search other hyper-
parameters. The best performances are reported here. In general, the
performance first increases and then drops as coefficients increase. Since the
benchmark datasets are relatively clean. To better show the effects of the
proposed two regularizers: $\mathcal{R}_{c}$ and $\mathcal{R}_{lw}$. We
synthesize datasets with controllable properties instead. We introduce two
hyper-parameters $\beta_{1}$ and $\beta_{2}$ for regularizers
$\mathcal{R}_{c}$, and $\mathcal{R}_{lw}$, respectively. These two hyper-
parameters affect the ratio of edges to be removed. We first dismiss the low-
rank constraint by setting $\beta_{2}=0$. With different choices of
$\beta_{1}$ (0, 0.05, 0.075, 0.9), we show mean weights (i.e., $z$) of edges
during iterations in Fig. 6(a). The figure shows that with a larger hyper-
parameter for $\mathcal{R}_{c}$, PTDNet achieves a more sparse subgraph.
Similar observations can be found in Fig. 6(b), where $\beta_{1}=0$ and only
the low-rank constraint is considered.

(a) Effect of $\mathcal{R}_{c}$

(b) Effect of $\mathcal{R}_{lw}$

Figure 5. Effects of $\mathcal{R}_{c}$ and $\mathcal{R}_{lw}$ on the accuracy.

(a) Effect of $\mathcal{R}_{c}$

(b) Effect of $\mathcal{R}_{lw}$

Figure 6. Effects of $\mathcal{R}_{c}$ and $\mathcal{R}_{lw}$ on the denoising
process.

To demonstrate the effects of including regularizers on the generalization
capacity of PTDNet. We synthesize four datasets with various topology
properties. The percentages of positive edges in these four datasets range
from 0.5 to 0.85. We tune the $\beta_{1}$ and $\beta_{2}$ separately by
setting the other one to 0. The best options of $\beta_{1}$ and $\beta_{2}$
for these four datasets are shown in Table 4. The table shows that for
datasets with poor topological qualities, regularizers should be assigned with
higher weights, such that PTDNet can denoise more task-irrelevant edges. On
the other hand, for datasets with good structure, i.e., the ratio of positive
edges is over 0.85, $\beta_{1}$ or $\beta_{2}$ should be with relatively small
values to keep more edges.

Table 4. The optimal hyper-parameters for graphs with different qualities. #pos edge/#all edges |  Best $\beta_{1}$ |  Best $\beta_{2}$
---|---|---
0.85 | 0.01 | 0.05
0.7 | 0.04 | 0.07
0.6 | 0.08 | 0.08
0.5 | 1.0 | 0.1
Table 5. Ratio of cross-community edges in the original graph and subgraphs generated by PTDNets with different settings. | original |  | $\beta_{1}=0.05$
---
$\beta_{2}=0$
| $\beta_{1}=0$
---
$\beta_{2}=0.05$
| $\beta_{1}=0.05$
---
$\beta_{2}=0.05$
$\frac{\text{\\#cross comm. eges}}{\text{\\#all edges}}$ | 0.211 | 0.206 | 0.189 | 0.190

Low-rank constraint $\mathcal{R}_{lw}$ is introduced to enhance the
generalization of PTDNet by setting a constraint on edges connecting nodes
from different communities. We use a synthetic dataset to show the influence
of $\mathcal{R}_{lw}$. We adopt the spectral clustering to group nodes into 5
communities. As shown in Table 5, the ratio of cross-community edges is 0.211
in the original graph. We fist adopt PTDNet with $\beta_{1}=0.05,\beta_{2}=0$
on the dataset. The ratio in the subgraph generated by the first layer is
0.206. By considering low-rank constraint and setting
$\beta_{1}=0,\beta_{2}=0.05$, the ratio drops to 0.189, showing the
effectiveness of low-rank constraint on removing cross-community edges.

###  5.6. Impacts of approximate factor $K$

In Sec. 4.3, $K$ is the approximate factor in the low-rank constraint. In this
part, we the synthetic dataset used in Sec. 5.4. We do not utilize the early
stop strategies and fix the number of epochs to 300. We range $K$ from 1 to 32
and adopt 2 layer GCN with 256 hidden units as the backbone. The accuracy and
running time are shown in Fig. 8.

From the figure, we can see that the accuracy performance increase with the
larger $K$, which is consistent with Eq. LABEL:eq:topk that larger $K$
indicates tighter bound. At the same time, it leads to more running time.
Besides, PTDNet can achieve a relatively high performance even when $K$ is
small.

###  5.7. On over-smoothing

The over-smoothing problem exists when multiple GNN layers are stacked (Li et
al., 2018a). DropEdge alleviates this problem by random drop edges during the
training phase. Removing certain edges makes the graph more sparse and reduces
messages passing along edges (Rong et al., 2020). However, As an
unparameterized method, DropEdge is not utilized during the testing phase,
which limits its power on preventing the over-smoothing problem, especially on
very dense graphs. On the other hand, our PTDNet is a parameterized method,
which learns to drop in both training and testing phases.

Figure 7. Impacts of $K$

Figure 8. On over-smoothing

In this part, we experimentally demonstrate the effectiveness of PTDNet on
alleviating the over-smoothing problem in GNN models with a very dense graph.
We adjust the synthetic datasets used in the above section by adding more
edges. With GCN as the backbone, we compare our PTDNet with DropEdge and the
basic backbone. Since stacking multiple GNN also involves the overfitting
problem, we include MLP as another baseline, which uses the identity matrix as
the adjacency matrix. For DropEdge, we choose three dropedge rates, 0.1, 0.8,
and 0.99. We range the number of GCN from 2 to 16 and show the results in Fig
8.

From the figure, we have the following observations. First, the performances
of MLP w.r.t the number of layers show that the overfitting problem appears
when 16 layers are stacked. Thus, for models with 8 or fewer layers, we can
dismiss the overfitting problem and focus on the over-smoothing merely.
Second, GCN models with 4 layers or more suffer from the over-smoothing
problem, which makes the basic GCN model performance even worse than MLP.
Third, DropEdge can only alleviate the over-smoothing problem to some degree
due to its limitation on the testing phase. Last but not least, our PTDNet
consistently outperforms all baselines. The reason is that our method is
parameterized and can learn to drop edges during the training phase. The
learned strategies can also be utilized in the testing phase to further reduce
the effects of the over-smoothing.

Table 6. Performances of Link Prediction Method | Cora | Citeseer | Pubmed
---|---|---|---
AUC | AP | AUC | AP | AUC | AP
GCN(GAE) | 0.910 | 0.920 | 0.895 | 0.899 | 0.964 | 0.965
DropEdge | 0.881 | 0.903 | 0.862 | 0.880 | 0.859 | 0.877
NeuralSparse | 0.901 | 0.917 | 0.899 | 0.910 | 0.926 | 0.953
PTDNet | 0.916 | 0.931 | 0.918 | 0.922 | 0.963 | 0.966

###  5.8. Link prediction

In this section, we apply our PTDNet to another downstream task, link
prediction. We adopt the Cora, Citeseer, and Pubmed datasets and follow the
same experimental settings in GAE, which applies GCN for link prediction (Kipf
and Welling, 2016b). PPI dataset is not used because it contains multiple
graphs and not suitable for link prediction. Specifically, we randomly remove
10% and 5% edges for positive samples in the testing and validation sets. The
left edges and all node features are used for training. We include the same
number of negative samples as positive edges by randomly sampling unconnected
nodes in validation and testing sets. We adopt area under the ROC curve,
denoted by AUC, and average precision, denoted by AP, scores to evaluate their
ability to correctly predict the removed edges. GCN is used as the backbone.
We compare our PTDNet with the basic GCN, DropEdge and NeuralSparse.
Performances are shown in Table 6.

The table shows that our PTDNet can also improve the accuracy performance of
link prediction. The denoising networks in PTDNet are optimized by the
downstream task loss and can remove task-irrelevant edges. On the other hand,
the performance between DropEdge and the original backbone shows that DropEdge
is suitable for the link prediction task.

##  6\. Conclusion

In this paper, we propose a Parameterized Topological Denoising Network
(PTDNet) to filter out task-specific noisy edges to enhance the robustness and
generalization power of GNNs. We directly limit the number of edges in the
input graph with parameterized networks. To further improve the generalization
capacity, we introduce the nuclear norm regularization to impose the low-rank
constraint on the resulting sparsified graphs. PTDNet is compatible with
various GNN models, such as GCN, GraphSage, and GAT to improve performance on
various tasks. Our experiments demonstrate the effectiveness of PTDNet on both
synthetic and benchmark datasets.

## ACKNOWLEDGMENTS

This project was partially supported by NSF projects IIS-1707548 and
CBET-1638320.

## References

  * (1)
  * Arora and Upadhyay (2019) Raman Arora and Jalaj Upadhyay. 2019.  On Differentially Private Graph Sparsification and Applications. In _NeurIPS_. 13378–13389.
  * Benczúr and Karger (1996) András A Benczúr and David R Karger. 1996.  Approximating st Minimum Cuts in Õ (n2) Time.. In _STOC_ , Vol. 96. Citeseer, 47–55.
  * Bengio et al. (2013) Yoshua Bengio, Nicholas Léonard, and Aaron Courville. 2013\.  Estimating or propagating gradients through stochastic neurons for conditional computation.  _arXiv preprint arXiv:1308.3432_ (2013).
  * Bruna et al. (2013) Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. 2013.  Spectral networks and locally connected networks on graphs.  _arXiv preprint arXiv:1312.6203_ (2013).
  * Carlson et al. (2010) Andrew Carlson, Justin Betteridge, Bryan Kisiel, Burr Settles, Estevam R Hruschka, and Tom M Mitchell. 2010.  Toward an architecture for never-ending language learning. In _AAAI_.
  * Chen et al. (2018) Jie Chen, Tengfei Ma, and Cao Xiao. 2018.  Fastgcn: fast learning with graph convolutional networks via importance sampling.  _arXiv preprint arXiv:1801.10247_ (2018).
  * Chew (1989) L Paul Chew. 1989\.  There are planar graphs almost as good as the complete graph.  _J. Comput. System Sci._ 39, 2 (1989), 205–219.
  * David (1995) JJ David. 1995.  Algorithms for analysis and design of robust controllers.  (1995).
  * Defferrard et al. (2016) Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. 2016.  Convolutional neural networks on graphs with fast localized spectral filtering. In _NIPS_. 3844–3852.
  * Eden et al. (2018) Talya Eden, Shweta Jain, Ali Pinar, Dana Ron, and C Seshadhri. 2018.  Provable and practical approximations for the degree distribution using sublinear graph samples. In _WWW_. 449–458.
  * Entezari et al. (2020) Negin Entezari, Saba Al-Sayouri, Amirali Darvishzadeh, and Evangelos Papalexakis. 2020.  All You Need is Low (Rank): Defending Against Adversarial Attacks on Graphs. In _WSDM_. ACM.
  * Fan (1951) Ky Fan. 1951.  Maximum properties and inequalities for the eigenvalues of completely continuous operators.  _PNAS_ 37, 11 (1951), 760.
  * Fortunato (2009) Santo Fortunato. 2009\.  Community detection in graphs.  _CoRR_ abs/0906.0612 (2009).
  * Friedland and Lim (2018) Shmuel Friedland and Lek-Heng Lim. 2018.  Nuclear norm of higher-order tensors.  _Math. Comp._ 87, 311 (2018), 1255–1281.
  * Girosi (1998) Federico Girosi. 1998\.  An Equivalence Between Sparse Approximation And Support Vector Machines.  _Neural Computation_ 10, 6 (1998), 1455–1480.
  * Gori et al. (2005) Marco Gori, Gabriele Monfardini, and Franco Scarselli. 2005\.  A new model for learning in graph domains. In _IJCNN_ , Vol. 2. IEEE, 729–734.
  * Hamilton et al. (2017) Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017\.  Inductive representation learning on large graphs. In _NIPS_. 1024–1034.
  * Hermsdorff and Gunderson (2019) Gecia Bravo Hermsdorff and Lee M Gunderson. 2019.  A Unifying Framework for Spectrum-Preserving Graph Sparsification and Coarsening.  _arXiv preprint arXiv:1902.09702_ (2019).
  * Hou et al. (2020) Yifan Hou, Jian Zhang, James Cheng, Kaili Ma, Richard T. B. Ma, Hongzhi Chen, and Ming-Chang Yang. 2020.  Measuring and Improving the Use of Graph Information in Graph Neural Networks. In _ICLR_.
  * Huang et al. (2018) Wenbing Huang, Tong Zhang, Yu Rong, and Junzhou Huang. 2018\.  Adaptive sampling towards fast graph representation learning. In _NeurIPS_. 4558–4567.
  * Ionescu et al. (2015) Catalin Ionescu, Orestis Vantzos, and Cristian Sminchisescu. 2015\.  Matrix backpropagation for deep networks with structured layers. In _ICCV_. 2965–2973.
  * Jang et al. (2016) Eric Jang, Shixiang Gu, and Ben Poole. 2016.  Categorical reparameterization with gumbel-softmax.  _arXiv preprint arXiv:1611.01144_ (2016).
  * 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.  _arXiv preprint arXiv:2005.10203_ (2020).
  * Kanada et al. (2018) Taiju Kanada, Masaki Onuki, and Yuichi Tanaka. 2018\.  Low-rank Sparse Decomposition of Graph Adjacency Matrices for Extracting Clean Clusters. In _APSIPA ASC_. IEEE, 1153–1159.
  * Kipf and Welling (2016a) Thomas N Kipf and Max Welling. 2016a.  Semi-supervised classification with graph convolutional networks.  _arXiv preprint arXiv:1609.02907_ (2016).
  * Kipf and Welling (2016b) Thomas N Kipf and Max Welling. 2016b.  Variational graph auto-encoders.  _arXiv preprint arXiv:1611.07308_ (2016).
  * Li et al. (2018a) Qimai Li, Zhichao Han, and Xiao-Ming Wu. 2018a.  Deeper insights into graph convolutional networks for semi-supervised learning. In _AAAI_.
  * Li et al. (2018b) Ruoyu Li, Sheng Wang, Feiyun Zhu, and Junzhou Huang. 2018b.  Adaptive graph convolutional neural networks. In _AAAI_.
  * Louizos et al. (2017) Christos Louizos, Max Welling, and Diederik P Kingma. 2017\.  Learning Sparse Neural Networks through $L\\_0$ Regularization.  _arXiv preprint arXiv:1712.01312_ (2017).
  * Loukas (2020) Andreas Loukas. 2020\.  What graph neural networks cannot learn: depth vs width. In _ICLR_.
  * Ma et al. (2019) Jianxin Ma, Peng Cui, Kun Kuang, Xin Wang, and Wenwu Zhu. 2019.  Disentangled Graph Convolutional Networks. In _ICML_. 4212–4221.
  * Maddison et al. (2016) Chris J Maddison, Andriy Mnih, and Yee Whye Teh. 2016\.  The concrete distribution: A continuous relaxation of discrete random variables.  _arXiv preprint arXiv:1611.00712_ (2016).
  * Mnih and Gregor (2014) Andriy Mnih and Karol Gregor. 2014.  Neural variational inference and learning in belief networks.  _arXiv preprint arXiv:1402.0030_ (2014).
  * Nakatsukasa and Higham (2013) Yuji Nakatsukasa and Nicholas J Higham. 2013.  Stable and efficient spectral divide and conquer algorithms for the symmetric eigenvalue decomposition and the SVD.  _SIAM Journal on Scientific Computing_ 35, 3 (2013), A1325–A1349.
  * Ni et al. (2018) Jingchao Ni, Shiyu Chang, Xiao Liu, Wei Cheng, Haifeng Chen, Dongkuan Xu, and Xiang Zhang. 2018.  Co-regularized deep multi-network embedding. In _WWW_.
  * Ortega (1990) James M Ortega. 1990\.  _Numerical analysis: a second course_.  SIAM.
  * Recht et al. (2010) Benjamin Recht, Maryam Fazel, and Pablo A Parrilo. 2010\.  Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization.  _SIAM review_ 52, 3 (2010), 471–501.
  * Rong et al. (2020) Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. 2020\.  DropEdge: Towards Deep Graph Convolutional Networks on Node Classification.  _ICLR_ (2020).
  * Scarselli et al. (2008) Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. 2008\.  The graph neural network model.  _IEEE TNN_ 20, 1 (2008), 61–80.
  * Sen et al. (2008) Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. 2008\.  Collective classification in network data.  _AI magazine_ 29, 3 (2008), 93–93.
  * Shin et al. (2019) Kijung Shin, Amol Ghoting, Myunghwan Kim, and Hema Raghavan. 2019.  Sweg: Lossless and lossy summarization of web-scale graphs. In _WWW_. ACM, 1679–1690.
  * Van Essen et al. (2013) David C Van Essen, Stephen M Smith, Deanna M Barch, Timothy EJ Behrens, Essa Yacoub, Kamil Ugurbil, Wu-Minn HCP Consortium, et al. 2013\.  The WU-Minn human connectome project: an overview.  _Neuroimage_ (2013).
  * Veličković et al. (2017) Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. 2017.  Graph attention networks.  _arXiv preprint arXiv:1710.10903_ (2017).
  * Wang et al. (2017) Chi-Jen Wang, Seokjoo Chae, Leonid A Bunimovich, and Benjamin Z Webb. 2017.  Uncovering Hierarchical Structure in Social Networks using Isospectral Reductions.  _arXiv preprint arXiv:1801.03385_ (2017).
  * Wang et al. (2019b) Lu Wang, Wenchao Yu, Wei Wang, Wei Cheng, Wei Zhang, Hongyuan Zha, Xiaofeng He, and Haifeng Chen. 2019b.  Learning Robust Representations with Graph Denoising Policy Network.  _IEEE ICDM_ (2019).
  * Wang et al. (2020) Lichen Wang, Bo Zong, Qianqian Ma, Wei Cheng, Jingchao Ni, Wenchao Yu, Yanchi Liu, Dongjin Dong, and Haifeng Chen. 2020.  Inductive and Unsupervised Representation Learning on Graph Structured Objects. In _ICLR_.
  * Wang et al. (2019a) Wei Wang, Zheng Dang, Yinlin Hu, Pascal Fua, and Mathieu Salzmann. 2019a.  Backpropagation-Friendly Eigendecomposition. In _NeurIPS_. 3156–3164.
  * Williams (1992) Ronald J Williams. 1992\.  Simple statistical gradient-following algorithms for connectionist reinforcement learning.  _Machine learning_ 8, 3-4 (1992), 229–256.
  * Xu et al. (2018) Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. 2018\.  How powerful are graph neural networks?  _arXiv preprint arXiv:1810.00826_ (2018).
  * Xue and Xin (2020) F Xue and J Xin. 2020\.  Learning Sparse Neural Networks via l0 and l1 by a Relaxed Variable Splitting Method with Application to Multi-scale Curve Classification. In _6th World Congress on Global Optimization_.
  * Yang et al. (2016) Zhilin Yang, William W Cohen, and Ruslan Salakhutdinov. 2016\.  Revisiting semi-supervised learning with graph embeddings.  _arXiv preprint arXiv:1603.08861_ (2016).
  * Zeng et al. (2020) Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. 2020\.  GraphSAINT: Graph Sampling Based Inductive Learning Method. In _ICLR_.
  * Zhang et al. (2020) Kai Zhang, Yaokang Zhu, Jun Wang, and Jie Zhang. 2020\.  Adaptive Structural Fingerprints For Graph Attention Networks.  _ICLR_ (2020).
  * Zhang et al. (2018) Ziwei Zhang, Peng Cui, and Wenwu Zhu. 2018.  Deep learning on graphs: A survey.  _arXiv preprint arXiv:1812.04202_ (2018).
  * Zhao and Akoglu (2019) Lingxiao Zhao and Leman Akoglu. 2019.  PairNorm: Tackling Oversmoothing in GNNs.  _arXiv preprint arXiv:1909.12223_ (2019).
  * Zheng et al. (2020) Cheng Zheng, Bo Zong, Wei Cheng, Dongjin Song, Jingchao Ni, Wenchao Yu, Haifeng Chen, and Wei Wang. 2020\.  Robust Graph Representation Learning via Neural Sparsification. In _ICML_.
  * Zhou et al. (2018) Jie Zhou, Ganqu Cui, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. 2018\.  Graph neural networks: A review of methods and applications.  _arXiv preprint arXiv:1812.08434_ (2018).