VEM-GCN: Topology Optimization with Variational EM for Graph Convolutional Networks
Authors: Rui Yang
Wenrui Dai
Chenglin Li
Junni Zou
Hongkai Xiong
Venue:  (2021)
Keywords: Graph Convolutional Networks
Over-smoothing
Topology Optimization
Stochastic Block Model
Variational EM

Abstract: Over-smoothing has emerged as a severe problem for node classification with graph convolutional networks (GCNs). In the view of message passing, the over-smoothing issue is caused by the observed noisy graph topology that would propagate information along inter-class edges, and consequently, over-mix the features of nodes in different classes. In this paper, we propose a novel architecture, namely VEM-GCN, to address this problem by employing the variational EM algorithm to jointly optimize the graph topology and learn desirable node representations for classification. Specifically, variational EM approaches a latent adjacency matrix parameterized by the assortative-constrained stochastic block model (SBM) to enhance intra-class connection and suppress inter-class interaction of the observed noisy graph. In the variational E-step, graph topology is optimized by approximating the posterior probability distribution of the latent adjacency matrix with a neural network learned from node embeddings. In the M-step, node representations are learned using the graph convolutional network based on the refined graph topology for the downstream task of classification. VEM-GCN is demonstrated to outperform existing strategies for tackling over-smoothing and optimizing graph topology in node classification on seven benchmark datasets.

Under review as a conference paper at ICLR 2021
VEM-GCN: TOPOLOGY OPTIMIZATION WITH VARIATIONAL EM FOR GRAPH CONVOLUTIONAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
Over-smoothing has emerged a severe problem for node classification with graph convolutional networks (GCNs). In the view of message passing, the over- smoothing issue is caused by the observed noisy graph topology that would prop- agate information along inter-class edges, and consequently, over-mix the fea- tures of nodes in different classes. In this paper, we propose novel architecture, namely VEM-GCN, to address this problem by employing the variational EM algorithm to jointly optimize the graph topology and learn desirable node repre- sentations for classification. Specifically, variational EM approaches a latent adja- cency matrix parameterized by the assortative-constraine stochastic block model (SBM) to enhance intra-class connection and suppress inter-class interaction of the observed noisy graph. In the variational E-step, graph topology is optimized by approximating the posterior probability distribution of the latent adjacency ma- trix with a neural network learned from node embeddings. In the M-step, node representations are learned using the graph convolutional network based on the refined graph topology for the downstream task of classification. VEM-GCN is demonstrated to outperform existing strategies for tackling over-smoothing and optimizing graph topology in node classification on seven benchmark datasets.
INTRODUCTION
Complex graph-structured data are ubiquitous in the real world, ranging from social networks to chemical molecules. Inspired by the remarkable performance of convolutional neural networks (CNNs) in processing data with regular grid structures (e.g., images), myriad of studies on GCNs have emerged execute "convolution"
the graph domain (Niepert et al. 2016 Kipf & Welling
2017 Gilmer et al. 2017 Hamilton et al. 2017 Monti et al. 20177 Gao et al. 2018). Many of
these approaches follow neighborhood aggregation mechanism (a.k.a., message passing scheme)
that updates the representation of each node by iteratively aggregating the transformed messages sent from its neighboring nodes. Commencing with the pioncering works (Kipf & Welling [017] Gilmer al., 2017), numerous strategies have been developed improve the vanilla message pass- ing scheme such as introducing self-attention mechanism (Veličković et al. 2018 /hang et al, 2020 incorporating local structural information (Zhang
2020 Jin et al.) 2019; Ye et al. and leveraging the link attributes (Gong & Cheng 2019 Li et al. 2019 Jiang et al. 2019).
2020
Despite significant success in many fundamental tasks of graph-based machine learning. message passing-based GCNs almost all process the observed graph structure as ground truth and might suffer from the over-smoothing problem (Li al. 2018). which would seriously affect the node classifi- cation performance. Given the observed noisy graph topology (i.e.. excessive inter-class edges are linked while many intra-class edges are missing), when multiple message passing layers are stacked to enlarge the receptive field (the maximum hop of neighborhoods). features of neighboring nodes in different classes would be dominant in message passing. Thus, node representations would be corrupted by the harmful noise and affect the discrimination of graph nodes. The over-smoothing phenomenon in GCNs has already been studied from different aspects. Li et al. (2018) first inter- preted over-smoothing from the perspective of Laplacian smoothing, while Xu et al. 2018 and Klicpera et al. (2019a) associated with the limit distribution of random walk. Furthermore, Chen al. (2020a) developed quantitative metrics measure the over-smoothness from the topological

---

Under review as a conference paper at ICLR 2021
view. They argued that the key factor leading over-smoo is the noise passing between nodes of different categories and the classification performance of GCNs is positively correlated with the proportion of intra-class node pairs in all edges.
In this paper, we propose VEM-GCN, a novel architecture to address the over-smoothing problem with topology optimization for uncertain graphs. Considering that "clearer" graph with more intra-class edges and fewer inter-class edges would improve the node classification performance of GCNs (Yang et al. 2019; Chen et al. 2020a), VEM-GCN approaches a latent adjacency matrix parameterized by the assortative-constriine
stochastic block model (SBM) where nodes share the same label are linked and inter-class edges should be cut off. To jointly refine the latent graph structure and learn desirable node representations for classification, variational EM algorithm (Neal & Hinton 1998) is adopted to optimize the evidence lower bound (ELBO) of the likelihood function. In the inference procedure (E-step). graph topology is optimized by approximating the posterior probability distribution of the latent adjacency matrix with a neural network learned from node embeddings. In the learning procedure (M-step), a conventional GCN is trained to maximize the log-likelihood of the observed node labels based on the learned latent graph structure. The E-step and M-step optimize the graph topology and improve the classification of unlabeled nodes in an alternating fashion.
The proposed VEM-GCN architecture is flexible and general. In the E-step, the neural network can support arbitrary desirable node embeddings generated by algorithms such as node2vec (Grover & Leskoved| 2016), struc2vec (Ribeiro al. 2017), and GCNs, or the node attributes. The GCN in the M-step can also be substituted with arbitrary graph models, Furthermore, recent strategies for relieving the over-smoothing issue, i.e., AdaEdge (Chen al.. 2020a) and DropEdge (Rong) iet al. 2020)) are shown to be the specific cases of VEM-GCN under certain conditions. For em- pirical evaluation, we conduct extensive experiments on seven benchmarks for node classification, including four citation networks, two Amazon сo- co-purchase graphs, and one Microsoft Academic graph. Experimental results demonstrate the effectiveness of the proposed VEM-GCN -CN architecture in optimizing graph topology and mitigating the over-smoothing problem for GCNs.
2 BACKGROUND AND RELATED WORKS
Problem Setting. This paper focuses on the task of graph-based transductive node classification. A simple attributed graph is defined
tuple Gubs (V. Aubs, X), where V { is the node set, Aab. [ggge {0, 1 N is the observed adjacency matrix, and X E Nxf represents the collection of attributes with each row corresponding to the features of an individual node. Given the labels Y₁- = [yte] E {0, 1 for a subset of graph nodes Vi2 C V assigned to C' classes, the task is to infer the classes Y. = [wje] E {0, 13 IV. for the unlabeled nodes V. = VAVV based on Gabs-
Graph Convolutional Networks (GCNs). The core of most GCNs is message passing scheme, where each node updates its representation by iteratively aggregating features from its neighbor- hoods. Denote with (!)) the learnable weights the 1-th layer, (i) the set of neighboring node indices for node us and (() the nonlinear activation function. A basic message passing layer takes the following form:
h h(t))= =a (ESerron og (wwn.)
Here, h is the input features of node By in the 1-th layer, w (1) message, and a. is the aggregation weight for the message passing from node 2 to node 2/2 Ex-
h is the corresponding transformed
isting GCNs mainly differ in the mechanism for computing (1)
a (Kipf & Welling 2017 Veličkovid
et al. 2018 Ye et al. 2020. Hamilton et al. 2017 /Zhng et al. 2020).
Stochastic Block Model (SBM). SBM (Holland et al. 1983) is generative model for producing
graphs with community structures. It parameterizes the edge probability between each node pair by
Bernoulli (po), if = = Bernoulli (pi), if A
a.yly..
(2)
where ā.j is an indicator variable for the edge linking nodes eú and Ey. y: and y, denote their corresponding communities (classes), Po and pı are termed community link strength and cross-
2

---

Under review as a conference paper at ICLR 2021
community link probability, respectively. The case where po P1 is called assortative model, while the case Po < P1 is called disassortative. In this paper, we leverage an constrrrieed SBM (Gribel et al. 2020) with po = 1 and p1 = O to model the latent graph for a clear topology.
Over-smoothing. Real-world graphs often possess high sparsity and are corrupted by certain noise that leads inter-class misconnection and missing intra-class edges. Over-smoothing is mainly caused by the indistinguishable features of nodes in different classes produced by the message pass- ing along inter-class edges. Various strategies have been developed to alleviate this problem. JK-Net (Xu et al. 2018) utilizes skip connection for adaptive feature aggregation and DNA (Fey) 2019) fur- ther makes improvements based on the attention mechanism. PPNP and APPNP (Klicpera et al. 2019a) modify the message passing scheme by personalized PageRank (PPR) to avoid reaching the limit distribution of random walk. CGNN (Xhonneux et al.) (020) addresses over-smoothing in a similar manner as PPR. Zhao & Akoglu (2020) introduced a graph layer normalization scheme termed PairNorm to maintain the total pairwise distance between nodes unchanged across layers. GCNII (Chen et al.) 2020b) extends GCN with Initial residual and Identity mapping. However, these methods cannot fundamentally address the over-smoothing issue, as they all view the ob- served graph as ground truth and the features of nodes in different classes would still be over-mixed along the inter-class edges. AdaEdge (Chen et al. 2020a) constantly refines the graph topology by adjusting the edges in telf-training-like fashion. However, AdaEdge only adjusts the edges linking nodes classified with high confidence, which leads to limited improvement or degradation in classi- fication performance due the incorrect operations for misclassified nodes. DropEdge (Rong et al., 2020) randomly removes a certain fraction of edges to reduce message passing. Despite enhanced robustness, DropEdge does not essentially optimize the graph topology. BBGDC (Hasanzadeh al.) 2020 generalizes Dropout (Srivastava et al., 2014) and DropEdge by adaptive connection sampling.
Uncertain Graphs and Topology Optimization. Learning with uncertain graphs is another related research area, where the observed graph structure is supposed to be derived from noisy data rather than ground truth. Bayesian approaches are typical methods that introduce uncertainty to network analysis. ZZang et al. (2019) developed BGCN that considers the observed graph as sample from a parametric family of random graphs and makes maximum a posteriori (MAP) estimate of the graph parameters. Tiao et al. (0119) also viewed graph edges Bernoulli random variables and used vari- ational inference to optimize the posterior distribution of the adjacency matrix by approximating the pre- ref-nef graph priors. Some other Bayesian methods have also been developed to combine GCNs with probabilistic models (Ng et al. (2088: [Ma et al., 2019). However, without explicit optimization for the graph structure, they only improve the robustness under certain conditions such as incom- plete edges, active learning, and adversarial attacks. For explicit topology optimization, |Fanceschi] al. (2019) presented LDS to parameterize edges as independent Bernoulli random variables and learn discrete structures for GCNs by solving a bilevel programming. However, LDS requires an extra validation set for training and suffers from limited scalability. TO-GCN (Yang et al., 2019) only adds the intra-class edges derived from the labeled nodes, which causes topology imbalance between Vu, and V/. GDC (Klicpera et al., 2019b) refines the adjacency matrix with graph diffusion to consider the links between high-order neighborhoods. However, the added edges might still be noisy to hamper the classification. GRCN (Yu et al. (0200) modifies the original adjacency matrix by adding residual matrix with each element measuring the similarity between two corresponding node embeddings, and IDGL (Chen et al.) (020c) iteratively Iearns the graph structure in a similar manner. Pro-GNN (Jin al. 2020) introduces low rank and sparsity constraints to recover a clean graph in defending adversarial attacks. NeuralSparse (Zheng et al.) (020) uses the Gumbel Softmax trick (Jang al.) (017) to sample neighbors from the original neighborhoods for each node but does not consider recovering missing intra-class edges. Different from the aforementioned meth- ods, VEM-GCN aims at relieving the over-smoothing issue. We introduce learned latent graph based on the issortativ-conntrainnn SBM to explicitly enhance intra-class connection and suppress inter-class interaction with the variational EM algorithm.
3 METHODOLOGGY
In this section, we develop the VEM-GCN architecture for transductive node classification. VEM- GCN leverages the variational EM algorithm achieve topology optimization, and consequently, address the over-smoothing issue by reducing noisy interactions between nodes in different classes. Specifically, E-step approximates the posterior probability distribution of the latent adjacency ma-
3

---

Under review as a conference paper at ICLR 2021
trix to optimize the graph structure, and M-step maximizes the evidence lower bound of the log- likelihood function based on the refined graph. We first introduce our motivation and provide an overview of the proposed VEM-GCN architecture. Subsequently, elaborate the mechanisms of the variational E-step and M-step, respectively.
3.1 MOTIVATION AND OVERVIEW
Motivation. As mentioned above, graph with its nodes densely connected within their own com- munities (classes) has lower risk of over- smoothng, Under this consideration. the optimal adjacency matrix for GCN is A YY (Yang et al. Chen Chen et al. 2020a), where Y E R xC is the ma- trix of one-hot-encoded ground-truth labels. However, since we have to infer Y, for the unlabeled nodes Vus their true labels are not available for calculating A. Thus, we introduce a latent graph Aatent learned from Gabs through another neural network to help generate a topology clearer than Asbs for GCNs. It is obvious that A is equivalent to SBM with po 1 and pa O, and therefore we base the posterior probability distribution of the latent graph on this assumption.
Overview. The basic principle behind our proposed VEM-GCN architecture is maximum likelihood estimation (MLE) in latent variable model, i.e., to maximize the log- lggliike function of the observed node labels Ey (Atsoon ) [log Ps Yo/Gos))) based on the approximate posterior distribution qo (A (A Gobs) of the latent graph Alatent- According to variational inference, the evidence lower bound (ELBO) is optimized instead:
log po (Y Y1lgots) 2 LELBO o: Gobs) -ggo ( (ew) [log po (Y,, A (otss) ) log do Intent (obs));
(3)
where the equality holds when go (Atatem Gotrs) po( latent] Y,, Gohx). Note that qa can be arbitrary desirable distributions on Ajaent and we use a neural network to parameterize it in this work. To jointly optimize the latent graph topology Ajarent and the ELBO (E, i. Gobs), we adopt the variational EM algorithm to solve it (refer to Appendix A for the full algorithm).
3.2 E-STEP
In the inference procedure (F-step), is fixed and the goal is to optimze go (ateet 9onc) to approx- imate the true posterior distribution (Attatt Y Gots). Under the condition of SBM, we assume each edge of the latent graph to be independent. Thus, go (Aaatten can be factorized by:
g (aJaatt Goba)
II go (alyy (ooss). (Gots)
(4)
Unlike LDS (Franceschi et al. 2019) using O(N2) Bernoulli random variables to characterize the optimized graph with N nodes, we parameterize qo an(an (alasem Gohx) through neural network shared by all the possible node pairs (i.e., amortized variational inference (Gershman & Goodman) 20144), as shown in Eq. 5 Hence, method shows scalability for large-scale graphs and is casier train.
2, = NN(e),, (a
latent = 1 sigmoid(2,2,.)
(5)
where e; is the node embedding of node us, which can be derived from any desirable network embedding methods (e.g., node2vec (Grover & Leskoved 2016), struc2vec (Ribeiro et al.) 2017). and GCNs) the raw node attributes x; (the i-th row of X), and 2, is the transformed features of node uy NN(-) denotes a neural network and we use a Multi-Layer Perceptron (MLP) in this work. The probability for linking a node pair defined as the inner-product of their transformed features activated by sigmoid function.
To approximate the posterior probability distribution of Agatents we rewrite po Po(Ajaten Y,, Gots) as:
pa Allaent Yi, Gobs))
= Σ Po Opp(Alatont Y., Yi, Gobs)
Y
Eyo Yr, [po (Aatent Yr, Y., Gots)].
Here, Po (Ajatent Y,, Y,, Goba.) is parameterized by the aforementioned assortative- SBM (i.e., Po latcnt 1 (yy,,y) y.y] for the one-hot-encoded node label y), po (Y,, YY, Gons) is the
4

---

Under review as a conference paper at ICLR 2021
predicted categorical distributions for the unlabeled nodes derived in the previous M-step. Conse- quently, we can sample Y.. po Po (Y/lY,YY. Gobs) estimate the expectation in Eq. 6 and leverage stochastic gradient descent (SGD) to minimize the reverse KI--divergence between the approximate posterior distribution 4s [Attten Goss) and the target pal [ Y,, Gobs). ). Under appropriate assump- tions, do will converge to pel [Atatent] Y,, Gots) as the iteration step of SGD & + oo (Bottou) 2010) Thus, can obtain the following objective function in the variational E-step for optimizing @:
LE - Σ
Maa
latent
)a (aij
latent yy.y;) log go (ab)) Intent (obs);
MEE ((0.))
where y is the ground truth label for node in labeled set Vi, otherwise sampled from pe Po Gobs) for the nodes without given labels in each training step, and X(a (aagaaa) is the weighting hyperparam- eter alleviate class imbalance between the inter-class edges and the intra-class edges.
3.3 M-STEP
In the learning procedure (M-step), o is fixed and θ is updated to maximize the ELBO in Eq, 3 By factorizing po( Yi, A Intent Goba) = po, ( (Y/ Amtent Gors )po, (Alatent Gons) with (01, 02). we have:
CELBO Eg Go..) [logge pe, (Y |Y Gobs]] KL (a Gotss)) Ilpo, (A Gots)].
(8)
Here, pe; (Y Aaaeent Gobs) in the first term can be parameterized by arbitrary GCN models described
by Eq. 1 that infer the node labels from Aatent and X. We use the vanilla GCN (Kipf & Welling
2017) this work (see Eq. [3 in Appendix [A). 'he second term is the KI--divergence between lo A Aatent/9bbss and the prior Pa, (A (ots): which can be optimized by setting 0₂ = é to force
Actually, pe, (Alatemn is of little interest to the final node classification task and we just need to maximize Eg (Aumnn (e..) (lo.) Po, (Yı) A Gobs) in the
(L
(AAlatont (oobs) pp (Alatent [oobs]]
M-step.
Considering the fact that the observed graph structure Aots should not be fully discarded and the approximation go (Aiient (otas derived in the previous E-step is sometimes not very accurate, we use 2 A latem (obs) to refine Aobs, and substitute 9s with the following Is in practice:
{
p. 0,
if ys E1
latent = 1|9obs) To (a
if go < otherwise
=
p a-a
where p E (0, 1]. E1 is close to one (commonly 0.999), and Eg is close to zero (commonly 0.01). Eq. 9 implies that, for edges predicted by qo to be linked with high confidence (the value after sigmoid or the maximum value after softmax), they should be added to the observed graph with probability p. Edges predicted by qs be cut off with high confidence should be removed from the observed graph. Otherwise, we maintain the original graph structure with probability
Similar to the E-step, we can sample the latent adjacency matrix Ajanet ~ qo (Atsemt Goos) (note that we pre-train pe, using Aobs) and leverage SGD to minimize the cross-entropy error between the GCN's predictions po, (Yr) [Yi|Alaeom: Gobs) and the ground-truth labels Y; for optimizing 0:
C
CM= = Σ
Σ WEE, c=1
Ysc log po, Auee/Aaaeeu Goos).
(10)
In the test procedure, the final predictions for Y,, are (Auaaa Gee Ipo, (Y, Gons)), which can be approximated by Monte-Carlo sampling:
5
Po Y,,
(Y YI, Gabs) S
PY, (Y A Gots); with A Aatonn ~ go( Iatemt Gots))
po,
(11)
where the number of samples S and the probability p in Ts are tuned hyperparameters.
The two neural networks 4s and pe are trained an alternating fashion to reinforce each other. Topology optimization in the E-step improves the performance of the GCN in the M-step, and with more unlabeled nodes being correctly classified, do will better approximate the optimal graph A.
5

---

VEM-GCN vs. AdaEdge. AdaEdge also constantly adjusts the graph topology in the training procedure. It adds the edge between two nodes which are predicted by the GCN as the same class Under review as a conference paper at ICLR 2021
3.4 DISCUSSIONS
In this subsection, we discuss the relationship between VEM-GCN and two recent works for tackling over-smoothing, i.e., DropEdge (Rong et al., 2020) and AdaEdge (Chen al. 2020a). We show that these two methods are specific cases of VEM- under certain conditions. More detailed comparisons with other related works (e.g., SBM-related GCNs) are discussed Appendix
VEM-GCN vs. DropEdge. DropEdge randomly removes a certain fraction of edges in each training step. The authors proved that this strategy can retard the convergence speed of wverssmothinng. However, it does not address the over werrssoothing issue at the core, since the graph topology is not fundamentally optimized and noisy messages still pass along inter-class edges. Considering the scenario where node has few interactions with its community but many cross-community links, DropEdge cannot improve the discrimination of this stray node, since does not recover the missing intra-class edges. We find that VEM-GCN degenerates to DropEdge, if we skip the E-step and just maximize Egg (Aueellss)))) [log pe, (Yi)Alntent Gobs)] with To (a.j
lutent = 1| = p a.
with high confidence, and removes edges in similar manner. If we skip the E-step and set go as VEM-GCN and AdaEdge can be equivalent.
Eq. 12
{
d.
I,
if = y' and conf(y)), conf(y/) > TI ify + y and conf(y,), conf(y) (y)) 12 otherwise
Intent = 1[9obs) = (0
(12)
where y' is the prediction made by GCN, c.nf(.) denotes the corresponding confidence, T1 and 72 two thresholds. Eq. immples that, this self-training like fashion only adjusts the edges whose interacting nodes have already been classified with high confidence. Therefore, the performance improvement is limited and would even get worse for some misclassified nodes, it might wrongly add inter-class edges to the observed graph Aobs and remove helpful intra-class connections.
4 EXPERIMENTS
To evaluate our VEM-GCN architecture, we conduct extensive experiments on seven benchmark datasets. Under the same setting as DropEdge (Rong et al., 2020) and a label-scarce setting (i.e., low label rate), we compare the performance of VEM-GCN against variety of state of the arts for tackling over-smoothing, uncertain graphs and topology optimization in GCNs. We further give the visualization results of topology optimization and quantitative analysis to verify the effectiveness of VEM-GCN in relieving the over-smoothing issue (complexity analysis is provided in Appendix E..
4.1 EXPERIMENTAL SETUP
Datasets and Baselines. We adopt seven well-known benchmark datasets validate the proposed method. Cora (Sen et al. 2008), Cora-ML (McCallum et al.) 2000 Bojchevski & Günnemann, 2018). Citeseer (Sen et al., 2008), and Pubmed (Namata et al. 2012) are four citation network benchmarks, where nodes represent documents and edges are citations between documents. Amazon Photo and Amazon Computers are two segments from the Amazon co-purchase graph (McAuley al. 2015). in which nodes represent goods and edges indicate that two goods are frequently bought together. In the Microsoft Academic graph (Shchur et al.] 20188,, nodes are authors and edges represent their co-authorship. All graphs use bag-of-words encoded representations as node attributes. An overview of the dataset statistics is summarized in Appendix C
Since VEM-GCN aims at addressing the over-smoothing problem with topology optimization, evaluate the node classification performance of our method against various strategies for tackling over-smoothing. uncertain graphs and topology optimization in GCNs. For addressing the over- smoothing issue, five methods are considered: DropEdge (Rong et al. 22020), DropICE, AdaEdge (Chen al. 2020a), PairNorm (Zhao & Akoglu| 2020). and BBGDC (Hasanzadeh et al. 2020), in which DropICE is implemented by removing the inter-class edges derived from V.. For tackling uncertain graphs, we compare against several Bayesian approaches including BGCN (Zhang al. 2019), VGCN (Tiao et al. 2019), and GO (Ma et al. 2019). For topology optimization, LDS

---

Under review as a conference paper at ICLR 2021
Table 1: Average test accuracy (%) for all models (a two-layer vanilla GCN as the backbone) and all datasets under the supervieee setting. OOM: Out-of-memory error
Method
Cora
Citeseer Pubmed Cora-MI Amazon Photo
Amazon Computers
MS Academic
Vanilla GCN
87.5
78.6
88.4
90.6
93.6
88.5
93.5
AdaFdge
87.6
78.9
88.2
90.8
93.8
88.4
93.7
DropEdge
87.8
79.0
88.4
90.7
93.9
88.6
93.8
DropICE
86.8
78.3
87.2
90.5
93.5
PairNorm
85.2
77.2
87.6
88.8
94.4
89.9
91.7
BBGDC
87.0
77.2
OOM
90.4
91.2
OOM
0OM
LDS
87.4
79.6
OOM
91.0
94.1
OOM
0OM
TO-GCN
86.3
77.5
88.1
89.0
92.7
87.3
92.3
GDC
86.2
77.1
87.2
90.2
93,9
92.2
93.8
GRCN
87.8
76.7
86.9
90.2
91.6
77.1
92.8
IDGL
88.2
79.0
88.1
91.3
94.2
87.9
00M
BGCN
87.9
78.7
88.0
91.1
93.1
87.8
92.8
VGCN
87.3
78.4
87.8
90.5
93.5
88.1
93.3
G
87.5
77.6
88.7
90.7
94,8
90.1
94.0
GMNN
87.2
78.7
88.3
90.4
93.8
90.5
93.5
VEM-GCN
88.7
80.6
90.1
91.6
95.7
91.8
95.5
Franceschi et al. 2019), GDC (Klicpera et al., 2019b). TO-GCN Yang et al.
2019). GRCN Yu
al. 2020), and IDGL (Chen et al. (020c) are the baselines. GMNN (Qu et al. 2019) also taken as baseline, it also employs variational EM for transductive node classification.
We conduct node classification under two experimental settings, i.e., full-supervised and label-scarce settings. The full-supervised setting follows DropEdge (Rong et al. 2020), where each dataset is split into 500 nodes for validation, 1000 nodes for test and the rest for training. The label-scarce setting assigns labels to only a few nodes and selects 500 nodes for validation, while the rest are used for test. Under the label-scarce setting, we compare VEM-GCN with the baselines except for LDS, LDS always uses the validation set for training, which is unfair for learning with limited training samples. DropICE is also omitted since the number of the removed inter-class edges derived from Vi very small in the label-scarce setting and thus DropICE only obtains similar performance as the vanilla GCN. Considering that the classification performance is highly influenced by the split of the dataset (Shchur al., 2018), we run all the models with the same 5 random data splits for each evaluation. To further ensure the credibility of the results, we perform 10 random weight initializations for each data split and report the average test accuracy for both experimental settings.
Model Configurations. For fair comparison, we evaluate all the methods under the same GCN backbone and the same training procedure. To be concrete, the graph model used in all baselines and our VEM-GCN (pe, in the M-step) is vanilla GCN (Kipf & Welling 2017) with the number of hidden units set as 32, Besides, we train the GCN backbone of the methods for each dataset with the same dropout rate of 0.5, the same weight decay, the same learning rate of 0.01, the same optimizer (Adam (Kingma & Ba 2015)), the same maximum training epoch of 1500, and the same early stopping strategy based on the validation loss with patienee of 50 epochs (for deeper models with more than layers, we set the patience as 100 epochs). Note that IDGL empirically needs more training epochs to converge and set its maximum training epoch 10000 with patience of 1000 epochs. As for do in the E-step, the input node embeddings are the attributes averaged over the neighborhood of each node and the network architecture is four-layer MLP with hidden units of size 128, 64, 64, and 32, respectively. Please refer to Appendix D for more details of the implementations and hyperparameter settings for each dataset.
4.2 RESULTS AND ANALYSIS
Full-supervised Setting, Table summarrzzess the classification results. The highest accuracy in each column is highlighted in bold. Note that the results of BBGDC and LDS on three large graphs (i.e., Pubmed, Amazon Computers, and MS Academic) and IDGL on MS Academic graph missing due to the out-of-memory error. Table demonstrates that none the baselines outperform the vanilla GCN in all cases, while VEM-GCN consistently improves the test accuracy of the GCN

---

Under review as a conference paper at ICLR 2021
Table Average test accuracy (%) and over-smoothness under the label-scarce setting (10 labels per class) with varying layers. For both metries, the larger the better. A: Accuracy. S: Over-smoothness.
Dataset
Method
2 layers
4 layers
layers
8 layers
10 layers
Vanilla GCN [A/S] S]
74.5 / 2.39
7..2/2.09
68.8 / 2.04
66.7 / 2.01
46.9 1.73
DropFdge [A SS]
75.0
75.5
58.1 2.10
42.7 / 1.84
32.1 / 1.46
Cora
AdaEdge [A S]
74.9
7.40 7
68.9 2.05
54.6 1.86
VEM-GCN [A
/2.1
78.0/3.57
78.4/ 2.51
78.1/3.11
78.1 2.94
Vanilla GCN [A
61.0/1.5 1.82
56.7/1.83
1.77
44.9 1.66
26.7 /1.11
DropEdge [A S]
60.3 /183
56.5/1995
50.1/ 1.52
35.5/ 1.24
23.7 23.7 /1.13
Citeseer
AdaEdge [A S]
61.5 1.84
58.7/183
53.1/1887 1.87
49.1 1.72
43.5 1.62
VEM-GCN [A (A/S)
64.2 1.89
6..2/2001
63.7 / 1.85
63.8 / 1.93
63.7 / 1.83
Vanilla GCN [A / S]
8..4/2.87
81.3/3.15
66.4/2.11
44.9 1.73
DropEdge [A SS]
83.1 2.855
81.4/3.17
43.4/2.59 7..6
37.1 22339
Cora-ML
AdaEdge [A S]
83.3 2.998
81.0/3.21
70.2/ 78.1 2..89
53.5 13.5//.44
VEM-GCN [A S]
84.4 /377
84.4/
64.4/3..0
84.4/ 4.45
84.3 4.12
Table Average test accuracy (%) under different label rates on the Amazon Photo dataset.
3.0
# labels per class
5
10
20
30
Accuracy improvement (%)
Camputes
Acatienic
Vanilla GCN
86.7
88.8
90.6
91.8
AdaEdge
86.5
88.9
90.5
91.8
DropEdge
86.5
88.8
90.5
91.6
PairNorm
78.6
83.7
86.2
88.1
1.5
BBGDC
87.3
88.4
90.1
90.4
TO-GCN
83.2
85.4
86.7
88.2
1.0
GDC
85.4
88.1
90.2
91.0
GRCN
84.1
88.3
90.4
91.9
IDGL
86.8
89.2
91.0
91.4
BGCN
85.1
87.1
89.1
91.1
VGCN
85.9
88.5
90.5
91.3
G'NN
86.3
88.8
90.6
90.8
EM Iterations
GMNN
87.9
89.4
91.2
92.3
Figure I: Convergence analysis.
VEM-GCN
89.2
90.5
91.8
92.8
backbone by noticeable margins. Specifically, find the following facts under the full-supervised setting: (1) For tackling over-smoothing, AdaEdge, DropEdge and PairNorm demonstrate limited improvement on several datasets, while BBGDC and DropICE almost collapse for all cases. (2) LDS, TO-GCN, GDC, GRCN and IDGL cannot guarantee that their topology optimization could achieve performance gains for the GCN backbone. (3) Only adding intra-class edges (TO-GCN) or removing inter-class edges (DropICE) derived from Vi might cause topology imbalance between V, and V, The GCN trained Vi with enhanced graph topology would fail V,, with the original graph topology. (4) Bayesian approaches and GMNN can only achieve comparable performance with the vanilla GCN in almost all cases. Overall, these facts imply that VEM-GCN significantly benefits from the large labeled data to generate clearer topology and achieve better performance.
Label-scarce Setting. We randomly select 10 labeled nodes per class as the training set and evaluate the performance of VEM-GCN with varying layers. Table shows the test accuracy and the over- smoothness measurements of the learned node embeddings (input node features of the last layer). The metric to measure the over-smoothness is defined in Appendix D.3 supplementary results of VEM-GCN on additional datasets are shown Appendix [. As can be seen in Table the vanilla GCN severely suffers from the over-smoothing issue, while VEM-GCN can achieve performance gains even with deeper layers (e.g., on the Cora dataset). DropEdge and AdaEdge can relieve the over-smoothing issue to some extent, but the performance still decreases drastically when stacking more GCN layers. The results over-smoothness measurements indicate that VEM-GCN indeed produces more separable node embeddings across different classes to address the over-smoothing
8

---

Under review as a conference paper at ICLR 2021
0.4
0.6
06
0.6
0.03
-04
0.02
0.2
0.00
(a)
(b)
(c)
(d)
Figure 2: Visualization results of topology optimization on the Cora-ML dataset under the full- supervised setting, We plot an induced subgraph (node indices from 450 to 850) for a better view. (a) The observed graph Aobs: (b) The optimal graph A; (c) The approximate posterior distribution 9s on A (d) The refined graph qg.
problem. We further take Amazon Photo example dataset validate VEM-GCN under differ- ent label rates. Similar trend as Table[can be found in Table
Convergence Analysis and Visualization Results. VEM-GCN leverages the variational EM al- gorithm for optimization. In this subsection, we analyze the convergence of VEM-GCN. Figure depicts the accuracy improvement curve of pø; during the EM iterations under the full-supervised setting. We find that VEM-GCN requires only few iterations to converge. We further take Cora- ML an example to give the corresponding visualization results of graph topology optimization. Figure show that the observed graph is very sparse and contains a few intra-class edges, while the optimized graph recover many missing intra-class edges relieve the over-smoothing problem. Note that, although the refined graph is much denser than the observed graph, the hyperparameter (0.05 here) Zo helps maintain the sparsity of the latent adjacency matrix the training procedure. Thus, the M-step can still be implemented efficiently using sparse-dense matrix multiplications.
CONCLUSION
In this paper, we present novel architecture termed VEM-GCN for addressing the over-smoothing problem in GCNs with graph topology optimization. By introducing a latent graph parameterized by the assortatie-constraaneed stochastic block model and utilizing the variational EM algorithm to jointly optimize the graph structure and the likelihood function, VEM-GCN outperforms variety of sfate-of-the-att methods for tackling sro-shnot uncertain graphs, and topology optimization in GCNs. For future work, expect further improvements for the VEM-GCN architecture to deal with more complex graphs such as hypergraphs and heterogeneous graphs.
REFERENCES
Aleksandar Bojchevski and Stephan Günnemann. Deep Gaussian embedding of graphs: Unsuper- vised inductive learning via ranking. In 6th International Conference on Learning Representa- fions, 2018.
Léon Bottou. Large-scale machine learning with stochastic gradient descent. In Proceedings of COMPSTAT pp. 177-186, 2010.
Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, and Xu Sun. Measuring and relieving the over- smoothing problem for graph neural networks from the topological view. In Proceedings of the 34th AAAI Conference on Artificial Intelligence, 2020a.
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph con- volutional networks. In Proceedings of the 37th International Conference Machine Learning, 2020b.
Yu Chen, Lingfei Wu, and Mohammed J Zaki. Iterative deep graph learning for graph neural net- works: Better and robust node embeddings. In Proceedings of the 34th Conference on Neural Information Processing Systems, 2020c.

---

Under review as a conference paper at ICLR 2021
Matthias Fey. Just jump: Dynamic neighborhood aggregation in graph neural networks. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
Luca Franceschi, Mathias Niepert, Massimiliano Pontil, and Xiao He. Learning discrete structures for graph neural networks. In Proceedings of the 36th International Conference on Machine Learning. pp. 1972-1982, 2019.
Hongyang Gao, Zhengyang Wang, and Shuiwang Ji. Large-scale learnable graph convolutional networks. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1414-1426, 2018
Samuel Gershman and Noah Goodman. Amortized inference in probabilistic reasoning. In Pro- ceedings of the Annual Meeting of the Cognitive Science Society, pp. 517-522, 2014.
Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning, pp. 1263-1272, 2017.
Liyu Gong and Qiang Cheng. Exploiting edge features for graph neural networks. In 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2019.
Daniel Gribel, Thibaut Vidal, and Michel Gendreau. Assortative--onstrainde stochastic block mod-
els. arXiv preprint 10ti:::2004111890 2020.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 864, 2016.
William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems 30, pp. 1024-1034, 2017.
Arman Hasanzadeh, Ehsan Hajiramezanali, Shahin Boluki, Nick Duffield, Mingyuan Zhou, Krishna Narayanan, and Xiaoning Qian. Bayesian graph neural networks with adaptive connection sam- pling. Proceedings of the 37th International Conference on Machine Learning. 2020.
Paul W. Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First
steps. Social Networks, 109): 1983.
Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterizattio with gumbel-softmax. In 5th International Conference on Learning Representations, 2017.
Xiaodong Jiang, Pengsheng Ji, and Sheng Li. CensNet: Convolution with edge-node switching in graph neural networks. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, pp. 2656-266666 16662266,112 2019.
Wei Jin, Yao Ma, Xiaorui Liu, Xianfeng Tang, Suhang Wang, and Jiliang Tang. Graph structure learning for robust graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2020.
Yilun Jin, Guojie Song, and Chuan Shi. GraLSP: terns. In Proceedings of the 34th AAAI Conference on Artificial Intelligence, 2019.
Graph neural networks with local structural pat-
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In 3rd Interna- tional Conference on Learning Representations, 2015.
Diederik P. Kingma and Max Welling. Auto-encoding variational bayes. In 2nd International Conference on Learning Representations, 2014.
Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In 5th International Conference on Learning Representations, 2017.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized PageRank. In 7th International Conference on Leam- ing Representations, 2019a.
10

---

Under review as a conference paper at ICLR 2021
Johannes Kliepera, Stefan Weißenberger, and Stephan Günnemann. Diffusion improves graph learn- ing. In Advances in Neural Information Processing Systems 32, pp. 1935--13666 2019b.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Proceedings of the 32nd AAAI Conference on Artificial Intelligence, pp. 3538-3545, 2018.
Ziyao Li, Liang Zhang, and Guojie Song. GCN-LASE: towards adequately incorporating link tributes in graph convolutional networks. In Proceedings of the 28th International Joint Confer- ence on Artificial Intelligence, pp. 2959-2965, 2019.
Jiaqi Ma, Weijing Tang, Ji Zhu, and Qiaozhu Mei. A flexible generative framework for graph- based semi-supervised learning. In Advances in Neural Information Processing Systems 32, pp- 3281-3290, 2019.
Laurens van der Maaten and Geoffrey Hinton. Visualizing data using t-SNE. Journal of Machine Learning Research, 9NNvv) 2605, 2008.
Julian McAuley, Christopher Targett, Qinfeng Shi, and Anton Van Den Hengel. Image-based rec- ommendations on styles and substitutes. In Proceedings of the 38th International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 43-52, 2015.
Andrew Kachites McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. Automating the construction of internet portals with machine learning. Information Retrieval, 3(2):127-163, 2000.
Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodolà, Jan Svoboda, and Michael M. Bronstein. Geometric deep learning on graphs and manifolds using mixture model CNNs. In 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 5425-5434, 2017.
Galileo Namata, Ben London, Lise Getoor, and Bert Huang. Query-driven active surveying for collective classification. In 10th International Workshop on Mining and Learning with Graphs, volume 8, 2012.
Radford Neal and Geoffrey E Hinton. A view of the em algorithm that justifies incremental, sparse, and other variants. In Learning in graphical models, pp. 355-368. Springer, 1998.
Yin Cheng Ng, Nicolò Colombo, and Ricardo Silva. Bayesian semi-supervised learning with graph Gaussian processes. In Advances Neural Information Processing Systems 31, 2018.
Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. Learning convolutional neural net- works for graphs. In Proceedings of the 33rd International Conference Machine Learning, pp. 2014-2023, 2016.
Meng Qu, Yoshua Bengio, and Jian Tang. GMNN: Graph Markov neural networks. In Proceedings of the 36th International Conference on Machine Learning, pp. 5241-5250, 2019.
Leonardo F. R. Ribeiro, Pedro H. P. Saverese, and Daniel R. Figueiredo. struc2vee: Learning node representations from structural identity. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2017.
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. DropEdge: Towards deep graph convolutional networks on node classification. 8th International Conference on Learning Rep- resentations, 2020.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad Collective classification in network data. Al Magazine, 29(3):93-106, 2008.
Oleksandr Shehur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. In Relational Representation Learning Workshop 2011.2018), NeurlPS, 2018.
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: A simple way to prevent neural networks from overfitting. Journal of Machine Learning 2014.
Research,
11

---

Under review as a conference paper at ICLR 2021
Louis Tiao, Pantelis Elinas, Harrison Nguyen, and Edwin V. Bonilla. Variational graph convolutional networks. In Graph Representation Learning Workshop (NeurIPS 2019), 2019.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In 6th International Conference on Learning Representations, 2018.
Louis-Pascal Xhonneux, Meng Qu, and Jian Tang. Continuous graph neural networks. In Proceed- ings of the 37th International Conference on Machine Learning, 2020.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In Proceedings of the 35th International Conference on Machine Learning, pp. 5453-5462, 2018.
Liang Yang, Zesheng Kang, Xiaochun Cao, Di Jin, Bo Yang, and Yuanfang Guo. Topology op- timization based graph convolutional network. Proceedings of the 28th International Joint Conference on Artificial Intelligence, pp. 4054 4061, 2019.
Ze Ye. Kin Sum Liu, Tengfei Ma. Jie Gao, and Chao Chen. Curvature graph network. In 8th International Conference on Learning Representations, 2020.
Donghan Yu, Ruohong Zhang, Zhengbao Jiang, Yuexin Wu, and Yiming Yang. Graph-revised convolutional network. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, 2020.
Kai Zhang, Yaokang Zhu, Jun Wang, and Jie Zhang. Adaptive structural fingerprints for graph attention networks. In 8th International Conference on Learning Representations, 2020.
Yingxue Zhang, Soumyasundar Pal, Mark Coates, and Deniz Ustebay. Bayesian graph convolutional neural networks for semi-supervised classification. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence, pp. 5829-5836, 2019.
Lingxiao Zhao and Leman Akoglu. PairNorm: Tackling oversmoothing in GNNs. In 8th Interna- tional Conference on Learning Representations, 2020.
Cheng Zheng, Bo Zong, Wei Cheng, Dongjin Song, Jingchao Ni, Wenchao Yu, Haifeng Chen, and Wei Wang. Robust graph representation learning via neural sparsification. In Proceedings of the 37th International Conference on Machine Learning, 2020.
A ALGORITHM
For fair comparison, we adopt the vanilla GCN (Kipt & Welling 2017 the backbone for all baselines and our proposed VEM-GCN architecture. A two-layer GCN is in the following form:
pa, (Y = softmax (D- ADD & ReLU (D- ADD & xx(() e()),
(13)
where is the input node attribute matrix, IN is the identity matrix, Á A + IN is the adjacency matrix with added self self- D is its corresponding diagonal degree matrix, and 0, (o O()) are the learnable weight parameters. Algorithm describes the proposed VEM-GCN architecture.
B FURTHER DISCUSSIONS
In addition to recent strategies for tackling over-smoothing issues, further distinguish VEM-GCN from the SBM-related GCNs and VGCN and GMNN (that introduce variational inference).
Comparison with SBM-related GCNs. Stochastic block model (SBM) has been combined with GCNs several recent works (i.e., BGCN (Zhang et al. 2019) and N (Ma et al. 2019)) How- these architectures are totally different from VEM-GCN in motivations, objective functions and training methods. BGCN (Zhang et al.) (219)) jointly infers the node labels and the parame- ters of SBM using only A which ignores the dependence of the graph X and Y,. Then the
12

---

Under review as a conference paper at ICLR 2021
Algorithm 1 VEM-GCN
Input: Observed graph Gobs and labels Y; for the labeled nodes V/. & in the E-step and 0 in the M-step. Output: Predicted labels Y, for the unlabeled nodes Vu.
Parameter:
1: Pre-train Pe with Abs and Y to get initial pa (Y,) Y Goba).
2: for EM iteration = 1, I...., T do
3: E-step:
4: for training step 51 1, ..... S1 do
5: Sample Y, po (Y,,. Yi, Gohs) for the unlabeled nodes Vu-
6:
Set (Atteen (Y, Gobs) = (Aaaee Yr, Y... 9ots) according to Eq. Update ds to optimize the objective function in Eq. wwth SGD.
7:
8:
end for
9:
M-step:
10:
Obtain To( (Asteut (obbs) according to Eq.
11: for training step $2 = 1,.... S2 do
12:
Sample Atatent go( imee (oors) for the latent adjacency matrix.
13: Update po to maximize the log-likelihood log pe | Gobs) with SGD,
14: end for
15: Predict categorical distributions pe Pe(Y,, (Y Y1, Gobs) according to Eq.
16: end for
17:
return Final predicted labels for Vn based on po Y Y1, Gobs).
adjacency matrices sampled from the inferred SBM are used to train the GCN. Different from VEM- GCN, BGCN neither explicitly promotes intra-class connection only achieves robustness under certain conditions such as adversarial attacks, benefiting from the uncertainty brought by the inferred SBM. NN is a flexible generative model, where the graph generated by SBM is based the predictions of additional MLP learned from only X and Yi. The predictions for the unlabeled nodes are still based on Gob. (i.e., the input adjacency matrix of the GCN is still Abts). ). By contrast, VEM-GCN aims at addressing the over-smoothing issue with topol- ogy optimization. In VEM-GCN, the M-step trains a GCN to obtain the predictions of the unlabeled nodes based on Atatent X, and Yr. We then estimate the posterior distribution on Atatent based on Y; and the predictions for the unlabeled nodes under the SBM assumption. Subsequently, the E-step optimizes the graph topology by training another auxiliary neural network with node embeddings as input to approximate the posterior distribution of Ajatet- The E-step and M-step are optimized in an alternating fashion to improve each other.
demotes inter-class interaction.
VEM-GCN vs. VGCN. VGCN (Tiao et al., 2019) also introduces a latent graph A and op- timizes LELOO in Eq. 3 However, directly optimizes the ELBO in VAE (Kingma & Welling 2014) fashion and the posterior distribution of Aattett is set to approximate the pre-defined graph
priors p(a,) prior = 1) pia + p2(1 11--.gh oghe) with 0 < P1, P2 < 1 using the re- ce-parameterization trick.
VGCN is to achieve robustness under fake link attacks and only shows comparable performance with GCN under the standard transductive learning setting (i.e., inferring Y,, based the original Gatx). By contrast, VEM-GCN does not introduce priors over graphs. We optimize the graph topology by explicitly enhancing intra-class connection and suppressing inter-class interaction using SBM and variational EM to relieve the over-smoothing issue.
VEM-GCN vs. GMNN. Graph Markov Neural Network (GMNN) (Qu et al. 2019) also employs variational EM for node classification, but it is totally different from our method in motivations and objective functions. GMNN focuses on modeling the joint distribution of object (node) labels.
Therefore, GMNN views Y, as latent variables and optimizes the following ELBO:
log Y X) > Ey, [lo pa YY, Y, X) log 2o Y X)]-
(14)
In the E-step, GMNN parameterizes go (., a. (X) with GCN and qs (Y, X) is optimized to ap- proximate the posterior distribution pa (Y, Y X). In the M-step, GMNN utilizes another GCN to model the conditional distribution (NB X) for each node v, E V (NB(i) is the neighbor set node 2;) with a conditional random field and maximizes the corresponding likelihood. On
the contrary, VEM-GCN is proposed to relieve the over-smoothing issue. VEM-GCN optimizes the
13

---

Under review as a conference paper at ICLR 2021
Table 4: Summary of dataset statistics
Undirected graph
Directed graph
Dataset
Cora
Citeseer
Pubmed
Cora-ML
Amazon Photo
Amazon Computers
MS Academic
Nodes
2708
3312
19717
2995
7650
13752
18333
Edges
5278
4536
44324
8416
143662
287209
163788
Features
1433
3703
500
2879
745
767
6805
Classes
6
10
15
latent graph to approximate its posterior distribution based on SBM in the E-step, and trains GCN based on the latent graph in the M-step.
C DATASET STATISTICS
We utilize seven node classification benchmarks this paper, including four citation networks (i.e.. Citeseer, Pubmed, Cora, and Cora-ML), two Amazon co-purchase graphs (i.e., Amazon Photo and Amazon Computers), and one Microsoft Academic graph, as summarized below.
Citation Networks. Cora, Citeseer, Pubmed can be downloaded from the official source code of GCN (Kipf Welling 2017) publicly available at [tttps:///
com/ tkipf/gen/ ree htt////atttttcc//eeee// datt ta and Cora-ML can be downloaded from the source code of (A)PPNP (Kliepera et al. 2019a) publicly available at https://
Amazon Co-purchase Graph. The Amazon Photo and Amazon Computers datasets from the Amazon co-purchase graph can be publicly downloaded from |at tutpps: /itthub. (Shchur et al. 2018).
wtt.:reeeemaateeeeeeeaeeeeeeeeee com/ http://ggnnnnnnnnnn/neeeeeaeee
Microsoft Academic Graph. The MS Academic graph can be downloaded from the source code of (A)PPNP (Klicpera et 2019a) publicly available at/ttps: com/ data
klicpera [Llccetaao//ppnp/treee///tttttt/
overview of the dataset statistics listed in Table Note that for these open datasets, three (Cora, Citeseer, Pubmed) are given in the form of undirected graphs, while four (Cora-MI. Amazon Photo, Amazon Computers, MS Academic) are directed graphs. GCN treats all these datasets as undirected graphs (i.e., dls = (aij + ajz > 0j. where [-] denotes Iverson bracket).
D FURTHER EXPERIMENTA DETAILS
D.1 IMPLEMENTATIONS
The implementation of VEM-GCN consists of two alternating steps in each iteration, including a variational E-step and an M-step. In the variational E-step, a simple four-layer MLP is implemented for Tor where the numbers of neuron units of each layer are 128, 64, 64, and 32, respectively. We use tanh the nonlinear activation function for the hidden layers. In the M-step, pa, is vanilla GCN with the number of hidden units set as 32, and we use the official source code from gt/gtt/n/eeeeeeeeeeeeeeee mwwsta///////////aammmaaamamaaaa gon All the basclines and our VEM- GCN architecture are trained on a single NVIDIA GTX 1080 GPU with 11GB memory.
sttps://githu:
We just utilize the node attributes X as the input qa- Note that we also support any other desirable network embedding method and these experiments is left for the future work. Considering the fact that the bag-of-words representations of X is often noisy, we average the features of each node over its neighborhoods smooth the input signal. Let Arow denote the "self-enhanced" adjacency matrix with row normalization (we use = 1.5 in this paper), and [A [ be the concatenation of matrices A and B along the last dimension. Consequently, we summarize the specific input to 4s for all the datasets as below.
(D - + 7Iv)
For Cora, Citeseer, and MS Academic,
X' Ánm X the input of go-
14

---

Under review as a conference paper at ICLR 2021
For Pubmed and Amazon Photo, we use X'
| A Tow X
as the imput of qs-
For Cora-ML and Amazon Computers, we use X'
X A as the input of gø.
For the sampling in the E-step, find that it is not always stable draw the sampled labels Y Pe (Y,, Y, (obs) To alleviate this problem, we maintain Y argmax, (Pe (Y (obs) with probability Pe. and sample Y, ~ (Y Y, Gobs) with probability (1-Pe) to improve the performance practice. For training of the E-step, we utilize SGD with momentum (of 0.99).
In the test procedure, we perform inference in two ways: (1) keep p in Eq. Sq.9i the same the training procedure (commonly p 1), sample S (5 > 1) adjacency matrices, and predict the classes for the unlabeled nodes according to Eq. [1 (2) set deterministic) and methods on each dataset and find that (2) almost always performs better.
(i.e., the latent adjacency matrix is now We report the best test accuracy obtained using these two sampling
D.2 HYPERPARAMETER SETTINGS
summarisss the hyperparameters adopted for the full-supervised setting on the seven bench- mark datasets. For the label-scared setting, the hyperparameters are the same, except for E1 and E2 that need to be carefully tuned the search space: E1 E (0.95, 0.99, 0.995, 0.999, 0.9995, 0.9999), E2 {0.001, 0.005, 0.01, 0.05, 0.1}.
Table 5: Hyperparameter setting for the results in Table Ir denotes learning rate. An exponential decay schedule is adopted for Ir (E) with decay rate d, and decay step d, tuned: d, E {0.96, 0.97, 0.98, 0.99). d, (2500, 3000, 3500, 4000). Batch size of the M-step is set to 96 (i.e., we randomly select 96 nodes for each step of optimizing Eq. 7 is tuned the search space: p E {0.001, 0.002, ..., 0.01, 0. 0.10..1.....
M(a 0) and Maa = =) A.
.....
Datasets
weight decay
Ir (M)
Ir (E)
Pe
E1
E2
À
S
Cora
0.0001
0.01
0.001
0.6
0.99
0.01
20
0.25
10
Citeseer
0.0001
0.01
0.002
0.6
0.95
0.1
20
0,25
10
Pubmed
0,0001
0.01
0.002
0.8
0.99
0.01
20
0.1
10
Cora-MI.
0.0001
0.01
0.001
0.85
0.9999
0.01
20
0.05
10
Amazon Photo
0.0001
0.01
0.001
0.85
0.999
0.01
25
0.25
Amazon Computers
0.002
0.8
0.999
0.01
25
0.15
10
MS Academic
0.01
0.002
0.8
0.999
0.005
25
0.002
10
D.3 METRIC FOR MEASURING OVER-SMOOTIINESS
To address the over-smoothing issue, one would prefer to reduce the intra-class distance to make node features in the same class similar, and increase the inter-class distance to produce distinguish- able representations distance to average intra-class distance (Euclidean distance of input node features in the last layer) to measure the svor-smoothsess. Formally, given the learned node embeddings
nodes in different classes. Hence, we use ratio of average inter-class
[h, (the
input node features of the last layer), we first calculate the distance matrix = [dy]] E R X with each entry defined as
h,
h;
dij
(15)
h
h,
where ||
la denotes Euclidean norm. Next, define the inter-class mask matrix and intra-class mask matrix as follows:
Minter - + INNN
(16)
iintm
- IN=
(17)
where À T is the optimal graph and 1 NNN matrix of size N with all entries set to 1. Then we can obtain the inter-class distance matrix Dinter [digttr]] E NNN and the intra- class distance matrix intra
[di N by element-wise multiplication D with the mask
15

---

Under review as a conference paper at ICLR 2021
matrices:
D iiterr D Minter
(18)
D intra = D a M
(19)
where o denotes element-wise multiplication. Next we get the average inter-class distance ADinter and the average intra-class distance A ADima,, with which measure the over-smoothness as their
ratio Rt:
Eis digter
A
(20)
Eis (ddigtor)
Eis dintra
ADimm
(21)
Eis (ddigtra)
ADinter
(22)
ADintra
where (xx) 1 if 0 otherwise O.
E FURTHER EXPERIMENTAL RESULTS
E.I CLASSIFICATION RESULTS UNDER THE LABEL-SCARCE SETTING
Supplementary experiments for Table D are shown in Table O
Table 6: Average test accuracy (%) and over-smoothness under the label-scarce setting (10 labels per class) with varying layers. For both metries, the larger the better. A: Accuracy. S: Over-smoothness.
Dataset
Method
2 layers
4 layers
layers
layers
10 layers
Vanilla GCN [A S] VEM-GCN [A / S]
70.5 / 2.06
70.1 2.00
70.2 1.94
69.3 1.82
67.9 1.75 72.4 / 2.08
Pubmed
72.6 / 2.14
2.10
7
72.6 2.12
Amazon
Vanilla GCN [A VEM-GCN [A S]
89.5 4.04
8..4/3.21 3,87
78.5 3.10
54.8 / 2.88
Photo
90.8/ 5.41
90.4/
90.5 4.89
90.2 4.67
4.46
Amazon
Vanilla GCN [A/
80.2 2.68
76.8
71.2 2.89
60.6 3.55
50.2 / 2.71
Computers
VEM-GCN [A S]
82.6
82.2 4.59
82.4 4.31
82.6 4.20
82.1 3.99
MS
Vanilla GCN [A VEM-GCN [A S]
89.6
8
82.1 6.61
80.1
73.7 6.28
Academic
91.2/ 11.7
90.9 / 11.3
91.1 11.9
91.1/
91.0 11.1
E.2
VISUALIZATION RESULTS
Figure demonstrates the topology optimization results on the Cora-ML dataset under the full- supervised setting. For the lable-scarce setting, the visualization results shown in Figure 3
We further take Cora-MI. as an example dataset to provide t-SNE (Maaten Hinton 2008) visu- alizations of the learned node embeddings (input node features of the last layer) extracted by the vanilla GCN and our proposed VEM-GCN with varying layers under the label-scarce setting (10 labeled nodes per class). The results are shown in Figures and [5] As can be seen, VEM-GCN indeed generates more separable node embeddings for nodes in different classes (colors) for classi- fication. In particular, lan-r vanilla GCN severely suffers from the over-smoothing issue where node features in different classes are over-mixed and thus indistinguishable, while our VEM-GCN architecture with a ten-layer GCN as the backbone still achieves comparable performance with two-layer model.
E.3 COMPLEXITY ANALYSIS
VEM-GCN is very flexible and general. There no constraint on the design of the two neural networks 4s and po. Therefore, the architecture can be combined with arbitrary GCN models and
16

---

Under review as a conference paper at ICLR 2021
0.8 0.04
0.6
06
0.03
0.4
0.02
9.2
0.00
(b)
(c)
(d)
Figure 3: Visualization results of topology optimization on the Cora-ML dataset under the label- scarce setting (10 labels per class). We plot an induced subgraph (node indices from 450 to 850) for a better view. (a) The observed graph Aobs; (b) The optimal graph A; (c) The approximate posterior distribution qs on Aasent (d) The refined graph 9s-
Table 7: Average test accuracy (%) of GCNII and VEM-GCNII on the three citation networks under the label-scarce setting (10 labels per class). The number in parentheses denotes the number of layers.
Method
Cora
Citeseer
Pubmed
GCNII
78.6 (64)
64.3 (32)
70.6 (16)
VEM-GCNII 79.8 (64)
66.2 (32)
72.7 (16)
node embedding methods. Moreover, we generalize some existing state-of-the-art strategies for tackling the over-smoothing problem (i.e., DropEdge and AdaEdge). In comparison to the vanilla GCN, VEM-GCN achieves these benefits with topology optimization at the cost of efficiency. As illustrated Sections 3.2 and [.3] the M-step is traditional training procedure for optimizing the GCNs. Although Atatent recovers more intra-class edges than Auhs: the parameter in Eq. Eq.Dhee heepps maintain the sparsity of the latent graph in each step of the training procedure. Thus the M-step shares almost the same complexity as GCN. The E-step introduces MLP for graph structure optimization. However, to address the over-smoothing issue at the core, argue that topology optimization is necessary. Actually, efficiency issue is a common problem for some Bayesian approaches and topology optimization methods. Despite decreased efficiency compared with the vanilla GCN. YEM-GCN optimizes Ajatent with amortized variational inference (i.e., training MLP shared by all the node pairs with mini-batch SGD in the E-step), which is faster than BGCN (Zhang al.] (2019) (Bayesian method) and LDS (Franceschi et al. (019) (topology optimization) and is scalable for large-scale graphs For training the Amazon Photo dataset with a NVIDIA GTX 1080 Ti GPU, VEM-GCN is about 3x faster than LDS and 4x faster than BGCN.
extra procedure that trains
E.4 VEM-GCNII
As mentioned above, our VEM-GCN architecture is flexible and general. In the E-step, the neural network can support arbitrary desirable node embeddings and the GCN in the M-step can be sub- stituted with any graph models. This subsection further verifies the effectiveness of our proposed method by trying different models for pe, (Y, A Gobs). We also apply the same node embed- dings as illustrated in Appendix D Trying more effective node embeddings is not the focus of this paper and is left for the future work.
Recently, Chen et al. (2020b) proposed a simple and deep GCN model termed GCNII to address the over-smoothing issue. GCNII improves the vanilla GCN via Initial residual and Identity mapping:
H =o =(+)==((1-00) (11 HO) (1-5(0) + 300 s(w.))
(23)
where (0)) (0) is the output of the first layer (a fully connected layer), P --DAD is
the normalized adjaceney matrix, ( and (()) are two hyperparameters.
We utilize GCNII as the backbone that results in the VEM-GCNII architecture. We use the official source code from https : http:thwwww.cccccccecceeeet//eet and employ the hyperparameter
17

---

Under review as a conference paper at ICLR 2021
settings reported in (Chen et al., 2020b) that achieve the best performance the three citation net- works (i.e., Cora, Citeseer, and Pubmed) under the label-scarce setting. For the other four datasets, roughly tuned the hyperparameters but found that GCNII does not outperform the vanilla GCN. Thus, we only evaluate GCNII and VEM-GCNII on Cora, Citeseer, and Pubmed with 10 laheled nodes per class the training set. Experimental results shown in Table As can be seen, VEM-GCNII consistently boosts the performance of GCNII, further verifying the effectiveness and flexibility of our proposed architecture.
(a) layers
(b) layers
(c) 6 layers
(d) layers
(c) 10 layers
Figure 4: t-SNE plots of learned node embeddings extracted by vanilla GCN with varying layers on the Cora-ML dataset. Different colors denote different classes.
(a) layers
(b) layers
(c) layers
(d) layers
(c) layers
Figure 5: t-SNE plots of learned node embeddings extracted by VEM-GCN with varying layers on the Cora-ML dataset. Different colors denote different classes.
18


Reviews:
[{"review_id": "y2mFAXttNp", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\nIn this work the authors start from the following basic observation, that I will state in terms of binary classification.  In an ideal setting where there exist two labels, the graph structure should be two distinct connected components, and according to the author(s) the most natural choice is that the each component is a clique. However, when one performs semi-supervised learning, edges going across communities over smooth the labels, and especially in the absence of many labeled points this causes big issues in node classification. For this reason the authors assume that the graph is actually a noisy version of some latent graph. They incorporate a variational approach to GCNs, as a novel architecture that iteratively refines the node labels and the graph. Figure 2 nicely summarizes how  the proposed architecture enhances the community structure. Some comments to the authors follow. \n\n\n- Could the authors discuss alternative choices to l2 minimization such as the paper Algorithms for Lipschitz Learning on Graphs by Rasmus Kyng et al. at uses Lp-norm minimization as means to avoid over smoothing in a different but super relevant context of label propagation? \n- The authors discuss drop edge. While this is an issue of the DropEdge method, wouldn't it make sense to remove edges that have higher effective resistance instead of random sampling? The latter is more likely to kill intra-edges, instead of the inter-edges that cause the oversmoothing? It would be nice to include such a baseline in the experiments. \n- What happens when instead of having in the ideal setting two connected components that are cliques, there are two bipartite cliques instead?  This would capture a notion of 'heterophily' instead of 'homophile' that naturally creates a clique. Can your method be extended to this case? \n- Can you prove that when the input graph is stochastic block model your method provably results in the right classification? It seems such a claim could be plausible to prove analytically, at least when the gap of intra- vs inter-community edges is large enough. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "wPuAbd0iJJE", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a method to alleviate the over-smoothing problem of GNNs. The key idea is to generate a latent graph structure via leveraging stochastic block model to approximate the observed graph structure and label information. The learned latent graph is expected to have a clear community structure with dense intra-class edges and sparse inter-class edges, so that labels of unlabeled nodes are better predicted based on the latent structure. The whole framework is well designed as an MLE problem, with EBLO solved by an alternate EM style algorithm. Both E-step and M-step are assumed to enhance each other's performance, but this point is not clearly validated in the experiments. Also, it is good to see some discussions on the relationship between the proposed framework and dropedge and adaedge methods. Overall, the idea makes sense in terms of joint topology optimization (via SBM) and node classification. The methodology is designed well as an MLE problem. The paper writes well and the experimental results demonstrate effectiveness to some extent.\n\nThe following are some weak points regarding the paper.\n1. The method is designed to only handle semi-supervised node classification problem, which may not be flexible enough to be associated with various GNNs for different downstream tasks.\n2. The idea of joint topology optimization and node classification is not new. For example, the following work\nZheng et al. Robust Graph Representation Learning via Neural Sparsification. ICML 2020.\ndeals with a similar problem, and is flexible to different tasks. It is better to compare with it in the experiments. Thus the novelty of the proposed method lies in its incorporation of SBM and community optimization, which is good but not very substantial.\n3. Because of the pairwise node link generation via SBM, the complexity of the method may be high. From the paper and the appendix, this point seems not discussed in detail. It is better to provide a clearer comparison between the complexity of the proposed method and some other recent topology optimization methods.\n4. It seems the proposed method has many hyperparameters, such as p, epsilon in Eq. (9), S in Eq. (11). It is better to provide a summary about these parameters and how to select them in the experiments.\n5. From experimental results table 1, the performance gain of the proposed method is around 1-2% accuracy compared to vanilla GCN. This seems not very significant, especially considering the practice whether it is necessary to cost more computations to achieve such a performance gain. Meanwhile, how much extra time to run the proposed method compared to pure GCN is not clear. Also, it is better to show variance to help understand the statistical significance.\n6. From table 2, the accuracy improvement is slightly better than table 1 in the scarce-label setting. But table 3 tells if adding a small amount of labels, the difference between GCN and the proposed method becomes small again, which draws a similar question as toward the results in table 1.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "GiZkWDn54Ux", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nThe authors present a method for tackling the problem of over-smoothing in graph convolutional networks. Specifically, this is achieved by explicitly modelling a latent graph which, ideally, would be a graph which connects an observation to all other observations of the same class and no observations of a different class. In practice, there is only an uncertain picture of this latent graph as in many applications the labels must be estimated for unlabelled observations. The authors present an EM variational algorithm for approximating both this latent graph and using it to improve the estimation of a GCN. The authors demonstrate that the proposed method performs favourably on a battery of test against an array of existing methods for solving the node classification problem. \n\nStrengths:\n\nThe paper tackles an important question in the GCN literature, which is how to deal with situations in which the graph is unobserved or the observed graph structure is only a fraction of the true graph. The method proposed, modelling and optimising a latent graph, makes sense and is well justified.  The authors position the paper well in terms of its contributions in relation to previous work. This includes empirical comparisons to a wide array of existing competing methods. The paper is well written and clearly describes the proposed method. \n\nWeaknesses:\nThe main weakness of the paper is in the empirical section. Specifically, I would like to seen an expanded Table 2 to include more comparisons with existing methods. From Table 1, I am convinced that VEM-GCN achieves similar performance to existing methods, even if the magnitude of the performance increase is not very large. However, I think the main contribution of the paper in the empirical section is Table 2 and should be the main focus. It clearly demonstrates that the proposed method reduces over-smoothing relative to a vanilla GCN as expected, especially as the depth of the model increases, but I wonder what a similar comparison to the other models in Table 1 would show. Could the authors provide the results of a similar analysis, at least for the models for which this is possible?\n\nReasons for score:\n\nI vote for accepting the paper. It is a solid, clear, and novel contribution to the literature on GCNs that directly addresses an important consideration in these models that is often overlooked. \n\nQuestions for the rebuttal period:\n\nPlease refer to the questions in the weaknesses section. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "BMeR3d-vMb5", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "A brief summary of the paper.\nThis paper proposed a novel architecture termed VEM-GCN to address the over-smoothing problem of GNNs in the node classification task. The main idea is to optimize the graph topology by removing the inter-class edges as well as adding the intra-class edges, and then the noise information would not pass between nodes with different categories. The framework learns with two alternating steps: E-step optimizes the topology while M-step improves the performance of GCN. The experimental results show that the proposed VEM-GCN achieves higher classification accuracy than baseline methods.\n\nMain contributions of the paper.\n1.\tThis paper proposes a joint learning framework for GNN classification model and graph topology, which leverages variational EM as a learning framework.\n2.\tThis paper presents a graph topology learning algorithm based on SBM and neural networks, which employs the node embedding and labels to optimize the topology.\n3.\tExtensive experiments to demonstrate the performance superior of the proposed method.\n\nStrengths\nThe strengths of this paper are summarized below,\n1.\tThe proposed method is clearly introduced. Concretely, the theoretical background and the algorithm details are both well defined and written in a clear way. \n2.\tThe paper is well-organised and well-written.\n3.\tExtensive experiments are conducted and results analysis are given. The visualization result is intuitive to demonstrate the property of the proposed method.\n\nWeaknesses\nThe weaknesses of this paper are summarized below,\n1.\tThe main hesitation with this paper is the novelty of the proposed method. Actually, optimizing the graph topology is a hot research direction, and a variety of works are presented about this topic recently. In addition to the AdaEdge, LDS and TO-GCN mentioned in the paper, other works, e.g., \"Graph-Revised Convolutional Network\" (ECML-PKDD 2020, arxiv: 1911.07123), \"Deep Iterative and Adaptive Learning for Graph Neural Networks\" (arxiv: 1912.07832), and \"Graph Structure Learning for Robust Graph Neural Networks\" (arxiv: 2005.10203), also study the same problem. Among them, DIAL-GNN also leverages an iterative and alternating framework to learn GNN and topology, which is similar to this paper. The differences between LDS/AdaEdge and this work are also minor. GRCN and TO-GCN optimize topology and GNN simultaneously in an end-to-end way, which seems more efficient than this work. In summary, the novelty of the presented VEM-GNN is a little bit minor.\n2.\tA minor concern is about the motivation of this paper. The authors claim that \"over-smoothing is caused by \"indistinguishable features of nodes in different classes produced by the message passing along inter-class edges\", so \"adding intra-class edges and removing inter-class edges are helpful to suppress over-smoothing\". However, I have a different understanding about the over-smoothing problem. A more common definition (by Li et al., 2018) about over-smoothing is \"if a GCN is deep with many convolutional layers, the output features may be oversmoothed and vertices from different clusters may become indistinguishable.\" In my opinion, the over-smoothing is caused by the depth (or receptive field) of GNN and the message passing manner, but irrelevant to the graph topology. Assuming that we remove all the inter-class edges and connect all the intra-class edges in the graph. In such a situation, when the GNN goes deep, the output embeddings of each node with the same class still become indistinguishable (the embeddings of nodes in the same class will converge to an identical embedding). Maybe we can obtain a perfect classification model by this way, but the embeddings are still failed to represent the property of each node, and they are useless to be applied to other tasks (e.g., anomaly detection). In summary, I agree that topology optimization is beneficial to enhance the node classification performance, but its effect on surpassing over-smoothing is suspicious. \n3.\tThe impact of each module/design in the proposed framework is not clearly stated. Specifically, a probability matrix $\\bar{q}_{\\phi}$ is acquired by the learned adjacency matrix <${q}_{\\phi}$>, and then the adjacency matrix for GCN is sampled by <$\\bar{q}_{\\phi}$>. The question is: why don't we define $p=1$ directly to obtain a definite adjacency matrix? Such a design can be viewed as a \"DropEdge\", so is that the main contribution term for restraining over-smoothing? Authors should add more ablation study to demonstrate the impact of \"learned topology\" and \"probability matrix\" respectively.\n\nCorrectness and Clarity\nThe claims and method are well written without significant errors. The paper is well-organised and written in a logical way.\n\nAdditional Comments\nHere are some additional comments for the authors,\n1.\tMore baselines considering topology optimization should be included, such as GRCN, DIAL-GNN, Pro-GNN (the papers of these methods are mentioned in Weaknesses Section).\n2.\tIt is better to demonstrate how much edges are added/removed since sparsity is an important factor affecting the efficiency of GCN.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors propose a new approach to topology optimization to address over-smoothing in GCNs. This is a borderline paper. Topology optimization is clearly important and relevant and the approach tries to optimize the topology (add/delete edges) by viewing the problem as a latent variable model and aiming to optimize the graph together with the GCN parameters to maximize the likelihood of observed node labels. A number of related joint topology optimization approaches exist, however, as discussed in the reviews and the responses. The proposed methodology is termed variational EM but is a bit heuristic in the sense that E and M steps do not follow a consistent criterion (the direction of KL is flipped between the steps). A number of comparisons are provided with consistent gains though the gains appear relatively small. No error bars are provided despite request to add them to better assess the significance of these results. It remains unclear whether the gains are worth the added complexity. 

Decision: Reject