Year: 2020

Abstract:
Over-smoothing has emerged as a severe problem for node classification with graph convolutional networks (GCNs). In the view of message passing, the oversmoothing 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.

heading: 1 INTRODUCTION
text: 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), a myriad of studies on GCNs have emerged to execute “convolution” in the graph domain (Niepert et al., 2016; Kipf & Welling, 2017; Gilmer et al., 2017; Hamilton et al., 2017; Monti et al., 2017; Gao et al., 2018). Many of these approaches follow a 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 pioneering works (Kipf & Welling, 2017; Gilmer et al., 2017), numerous strategies have been developed to improve the vanilla message passing scheme such as introducing self-attention mechanism (Veličković et al., 2018; Zhang et al., 2020), incorporating local structural information (Zhang et al., 2020; Jin et al., 2019; Ye et al., 2020), and leveraging the link attributes (Gong & Cheng, 2019; Li et al., 2019; Jiang et al., 2019).
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 et al., 2018), which would seriously affect the node classification 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 interpreted over-smoothing from the perspective of Laplacian smoothing, while Xu et al. (2018) and Klicpera et al. (2019a) associated it with the limit distribution of random walk. Furthermore, Chen et al. (2020a) developed quantitative metrics to measure the over-smoothness from the topological
view. They argued that the key factor leading to over-smoothing 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 a “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-constrained 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 & Leskovec, 2016), struc2vec (Ribeiro et al., 2017), and GCNs, or the raw 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 et al., 2020a) and DropEdge (Rong et al., 2020), are shown to be the specific cases of VEM-GCN under certain conditions. For empirical evaluation, we conduct extensive experiments on seven benchmarks for node classification, including four citation networks, two Amazon co-purchase graphs, and one Microsoft Academic graph. Experimental results demonstrate the effectiveness of the proposed VEM-GCN architecture in optimizing graph topology and mitigating the over-smoothing problem for GCNs.

heading: 2 BACKGROUND AND RELATED WORKS
text: Problem Setting. This paper focuses on the task of graph-based transductive node classification. A simple attributed graph is defined as a tuple Gobs = (V,Aobs,X), where V = {vi}Ni=1 is the node set, Aobs = [ aobsij ] ∈ {0, 1}N×N is the observed adjacency matrix, and X ∈ RN×f represents the collection of attributes with each row corresponding to the features of an individual node. Given the labels Yl = [yic] ∈ {0, 1}|Vl|×C for a subset of graph nodes Vl ⊂ V assigned to C classes, the task is to infer the classes Yu = [yjc] ∈ {0, 1}|Vu|×C for the unlabeled nodes Vu = V\Vl based on Gobs. 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 neighborhoods. Denote with W(l) the learnable weights in the l-th layer, N (i) the set of neighboring node indices for node vi, and σ(·) the nonlinear activation function. A basic message passing layer takes the following form:
h (l+1) i = σ (∑ j∈N (i)∪{i} α (l) ij W (l)h (l) j ) . (1)
Here, h(l)j is the input features of node vj in the l-th layer, W (l)h (l) j is the corresponding transformed message, and α(l)ij is the aggregation weight for the message passing from node vj to node vi. Existing GCNs mainly differ in the mechanism for computing α(l)ij (Kipf & Welling, 2017; Veličković et al., 2018; Ye et al., 2020; Hamilton et al., 2017; Zhang et al., 2020).
Stochastic Block Model (SBM). SBM (Holland et al., 1983) is a generative model for producing graphs with community structures. It parameterizes the edge probability between each node pair by
āij |yi,yj ∼ {
Bernoulli (p0) , if yi = yj Bernoulli (p1) , if yi 6= yj , (2)
where āij is an indicator variable for the edge linking nodes vi and vj , yi and yj denote their corresponding communities (classes), p0 and p1 are termed community link strength and cross-
community link probability, respectively. The case where p0 > p1 is called an assortative model, while the case p0 < p1 is called disassortative. In this paper, we leverage an assortative-constrained SBM (Gribel et al., 2020) with p0 = 1 and p1 = 0 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 to 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 passing 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) further 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., 2020) 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 observed 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 a self-training-like fashion. However, AdaEdge only adjusts the edges linking nodes classified with high confidence, which leads to limited improvement or degradation in classification performance due to 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 et 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. Zhang et al. (2019) developed BGCN that considers the observed graph as a sample from a parametric family of random graphs and makes maximum a posteriori (MAP) estimate of the graph parameters. Tiao et al. (2019) also viewed graph edges as Bernoulli random variables and used variational inference to optimize the posterior distribution of the adjacency matrix by approximating the pre-defined graph priors. Some other Bayesian methods have also been developed to combine GCNs with probabilistic models (Ng et al., 2018; Ma et al., 2019). However, without explicit optimization for the graph structure, they only improve the robustness under certain conditions such as incomplete edges, active learning, and adversarial attacks. For explicit topology optimization, Franceschi et 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 Vl. 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., 2020) modifies the original adjacency matrix by adding a residual matrix with each element measuring the similarity between two corresponding node embeddings, and IDGL (Chen et al., 2020c) iteratively learns the graph structure in a similar manner. Pro-GNN (Jin et al., 2020) introduces low rank and sparsity constraints to recover a clean graph in defending adversarial attacks. NeuralSparse (Zheng et al., 2020) uses the Gumbel Softmax trick (Jang et al., 2017) to sample k neighbors from the original neighborhoods for each node but does not consider recovering missing intra-class edges. Different from the aforementioned methods, VEM-GCN aims at relieving the over-smoothing issue. We introduce a learned latent graph based on the assortative-constrained SBM to explicitly enhance intra-class connection and suppress inter-class interaction with the variational EM algorithm.

heading: 3 METHODOLOGY
text: In this section, we develop the VEM-GCN architecture for transductive node classification. VEMGCN leverages the variational EM algorithm to 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-
trix to optimize the graph structure, and M-step maximizes the evidence lower bound of the loglikelihood function based on the refined graph. We first introduce our motivation and provide an overview of the proposed VEM-GCN architecture. Subsequently, we elaborate the mechanisms of the variational E-step and M-step, respectively.

heading: 3.1 MOTIVATION AND OVERVIEW
text: Motivation. As mentioned above, a graph with its nodes densely connected within their own communities (classes) has lower risk of over-smoothing. Under this consideration, the optimal adjacency matrix for GCN is Ã = YY> (Yang et al., 2019; Chen et al., 2020a), where Y ∈ RN×C is the matrix of one-hot-encoded ground-truth labels. However, since we have to infer Yu for the unlabeled nodes Vu, their true labels are not available for calculating Ã. Thus, we introduce a latent graph Alatent learned from Gobs through another neural network to help generate a topology clearer than Aobs for GCNs. It is obvious that Ã is equivalent to a SBM with p0 = 1 and p1 = 0, 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 a latent variable model, i.e., to maximize the log-likelihood function of the observed node labels Eqφ(Alatent|Gobs)[log pθ(Yl|Gobs)] based on the approximate posterior distribution qφ(Alatent|Gobs) of the latent graph Alatent. According to variational inference, the evidence lower bound (ELBO) is optimized instead:
log pθ(Yl|Gobs) ≥ LELBO(θ, φ; Yl,Gobs) = Eqφ(Alatent|Gobs)[log pθ(Yl,Alatent|Gobs)− log qφ(Alatent|Gobs)], (3)
where the equality holds when qφ(Alatent|Gobs) = pθ(Alatent|Yl,Gobs). Note that qφ can be arbitrary desirable distributions on Alatent and we use a neural network to parameterize it in this work. To jointly optimize the latent graph topology Alatent and the ELBO LELBO(θ, φ; Yl,Gobs), we adopt the variational EM algorithm to solve it (refer to Appendix A for the full algorithm).

heading: 3.2 E-STEP
text: In the inference procedure (E-step), θ is fixed and the goal is to optimze qφ(Alatent|Gobs) to approximate the true posterior distribution pθ(Alatent|Yl,Gobs). Under the condition of SBM, we assume each edge of the latent graph to be independent. Thus, qφ(Alatent|Gobs) can be factorized by:
qφ(Alatent|Gobs) = ∏ i,j qφ(a latent ij |Gobs). (4)
Unlike LDS (Franceschi et al., 2019) using O(N2) Bernoulli random variables to characterize the optimized graph with N nodes, we parameterize qφ(alatentij |Gobs) through a neural network shared by all the possible node pairs (i.e., amortized variational inference (Gershman & Goodman, 2014)), as shown in Eq. 5. Hence, our method shows scalability for large-scale graphs and is easier to train.
zi = NN(ei), qφ(alatentij = 1|Gobs) = sigmoid(ziz>j ), (5) where ei is the node embedding of node vi, which can be derived from any desirable network embedding methods (e.g., node2vec (Grover & Leskovec, 2016), struc2vec (Ribeiro et al., 2017), and GCNs) or the raw node attributes xi (the i-th row of X), and zi is the transformed features of node vi. NN(·) denotes a neural network and we use a Multi-Layer Perceptron (MLP) in this work. The probability for linking a node pair is defined as the inner-product of their transformed features activated by a sigmoid function.
To approximate the posterior probability distribution of Alatent, we rewrite pθ(Alatent|Yl,Gobs) as: pθ(Alatent|Yl,Gobs) = ∑ Yu pθ(Alatent,Yu|Yl,Gobs)
= Epθ(Yu|Yl,Gobs)[pθ(Alatent|Yl,Yu,Gobs)]. (6)
Here, pθ(Alatent|Yl,Yu,Gobs) is parameterized by the aforementioned assortative-constrained SBM (i.e., pθ(alatentij = 1|yi,yj) = yiy>j for the one-hot-encoded node label y), pθ(Yu|Yl,Gobs) is the
predicted categorical distributions for the unlabeled nodes derived in the previous M-step. Consequently, we can sample Ŷu ∼ pθ(Yu|Yl,Gobs) to estimate the expectation in Eq. 6 and leverage stochastic gradient descent (SGD) to minimize the reverse KL-divergence between the approximate posterior distribution qφ(Alatent|Gobs) and the target pθ(Alatent|Yl,Gobs). Under appropriate assumptions, qφ will converge to pθ(Alatent|Yl,Gobs) as the iteration step of SGD t → ∞ (Bottou, 2010). Thus, we can obtain the following objective function in the variational E-step for optimizing φ:
LE = − ∑ i,j ∑ alatentij ∈{0,1} λ(alatentij )pθ(a latent ij |yi,yj) log qφ(alatentij |Gobs), (7)
where y is the ground truth label for node in labeled set Vl, otherwise sampled from pθ(Yu|Yl,Gobs) for the nodes without given labels in each training step, and λ(alatentij ) is the weighting hyperparameter to alleviate class imbalance between the inter-class edges and the intra-class edges.

heading: 3.3 M-STEP
text: In the learning procedure (M-step), φ is fixed and θ is updated to maximize the ELBO in Eq. 3. By factorizing pθ(Yl,Alatent|Gobs) = pθ1(Yl|Alatent,Gobs)pθ2(Alatent|Gobs) with θ = {θ1, θ2}, we have:
LELBO = Eqφ(Alatent|Gobs)[log pθ1(Yl|Alatent,Gobs)]−KL[qφ(Alatent|Gobs)‖pθ2(Alatent|Gobs)]. (8)
Here, pθ1(Yl|Alatent,Gobs) in the first term can be parameterized by arbitrary GCN models described by Eq. 1 that infer the node labels from Alatent and X. We use the vanilla GCN (Kipf & Welling, 2017) in this work (see Eq. 13 in Appendix A). The second term is the KL-divergence between qφ(Alatent|Gobs) and the prior pθ2(Alatent|Gobs), which can be optimized by setting θ2 = φ to force KL[qφ(Alatent|Gobs)‖pθ2(Alatent|Gobs)] = 0. Actually, pθ2(Alatent|Gobs) is of little interest to the final node classification task and we just need to maximize Eqφ(Alatent|Gobs)[log pθ1(Yl|Alatent,Gobs)] in the M-step.
Considering the fact that the observed graph structure Aobs should not be fully discarded and the approximation qφ(Alatent|Gobs) derived in the previous E-step is sometimes not very accurate, we use qφ(Alatent|Gobs) to refine Aobs, and substitute qφ with the following q̄φ in practice:
q̄φ(a latent ij = 1|Gobs) =  p, if qφ > ε10, if qφ < ε2p · aobsij , otherwise , (9) where p ∈ (0, 1], ε1 is close to one (commonly 0.999), and ε2 is close to zero (commonly 0.01). Eq. 9 implies that, for edges predicted by qφ 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 qφ to be cut off with high confidence should be removed from the observed graph. Otherwise, we maintain the original graph structure with probability p.
Similar to the E-step, we can sample the latent adjacency matrix Âlatent ∼ q̄φ(Alatent|Gobs) (note that we pre-train pθ1 using Aobs) and leverage SGD to minimize the cross-entropy error between the GCN’s predictions pθ1(Yl|Âlatent,Gobs) and the ground-truth labels Yl for optimizing θ:
LM = − ∑ vi∈Vl C∑ c=1 yic log pθ1(yic|Âlatent,Gobs). (10)
In the test procedure, the final predictions for Yu are Eq̄φ(Alatent|Gobs)[pθ1(Yu|Alatent,Gobs)], which can be approximated by Monte-Carlo sampling:
pθ(Yu|Yl,Gobs) = 1
S S∑ i=1 pθ1(Yu|Ailatent,Gobs), with Ailatent ∼ q̄φ(Alatent|Gobs), (11)
where the number of samples S and the probability p in q̄φ are tuned hyperparameters.
The two neural networks qφ and pθ are trained in 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, qφ will better approximate the optimal graph Ã.

heading: 3.4 DISCUSSIONS
text: 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 et al., 2020a). We show that these two methods are specific cases of VEM-GCN under certain conditions. More detailed comparisons with other related works (e.g., SBM-related GCNs) are discussed in Appendix B.
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 over-smoothing. However, it does not address the over-smoothing 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 a node has few interactions with its community but many cross-community links, DropEdge cannot improve the discrimination of this stray node, since it 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 Eq̄φ(Alatent|Gobs)[log pθ1(Yl|Alatent,Gobs)] with q̄φ(alatentij = 1|Gobs) = p · aobsij . 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 with high confidence, and removes edges in a similar manner. If we skip the E-step and set q̄φ as Eq. 12, VEM-GCN and AdaEdge can be equivalent.
q̄φ(a latent ij = 1|Gobs) =  1, if y′i = y ′ j and conf(y ′ i), conf(y ′ j) > τ1
0, if y′i 6= y′j and conf(y′i), conf(y′j) > τ2 aobsij , otherwise , (12)
where y′ is the prediction made by GCN, conf(·) denotes the corresponding confidence, τ1 and τ2 are two thresholds. Eq. 12 implies 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, as it might wrongly add inter-class edges to the observed graph Aobs and remove helpful intra-class connections.

heading: 4 EXPERIMENTS
text: 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 a 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.3).

heading: 4.1 EXPERIMENTAL SETUP
text: Datasets and Baselines. We adopt seven well-known benchmark datasets to validate the proposed method. Cora (Sen et al., 2008), Cora-ML (McCallum et al., 2000; Bojchevski & Gü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 et 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., 2018), 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, we 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 oversmoothing issue, five methods are considered: DropEdge (Rong et al., 2020), DropICE, AdaEdge (Chen et 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 Vl. For tackling uncertain graphs, we compare against several Bayesian approaches including BGCN (Zhang et al., 2019), VGCN (Tiao et al., 2019), and G3NN (Ma et al., 2019). For topology optimization, LDS
(Franceschi et al., 2019), GDC (Klicpera et al., 2019b), TO-GCN (Yang et al., 2019), GRCN (Yu et al., 2020), and IDGL (Chen et al., 2020c) are the baselines. GMNN (Qu et al., 2019) is also taken as a baseline, as 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, as 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 Vl is 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 et 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 a 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 (pθ1 in the M-step) is a vanilla GCN (Kipf & Welling, 2017) with the number of hidden units set as 32. Besides, we train the GCN backbone of all 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 a patience of 50 epochs (for deeper models with more than 2 layers, we set the patience as 100 epochs). Note that IDGL empirically needs more training epochs to converge and we set its maximum training epoch as 10000 with a patience of 1000 epochs. As for qφ in the E-step, the input node embeddings are the attributes averaged over the neighborhood of each node and the network architecture is a 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.

heading: 4.2 RESULTS AND ANALYSIS
text: Full-supervised Setting. Table 1 summarizes 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 are missing due to the out-of-memory error. Table 1 demonstrates that none of the baselines outperform the vanilla GCN in all cases, while VEM-GCN consistently improves the test accuracy of the GCN
Table 2: Average test accuracy (%) and over-smoothness under the label-scarce setting (10 labels per class) with varying layers. For both metrics, the larger the better. A: Accuracy. S: Over-smoothness.
Dataset Method 2 layers 4 layers 6 layers 8 layers 10 layers
Cora
Vanilla GCN [A / S] 74.5 / 2.39 73.2 / 2.09 68.8 / 2.04 66.7 / 2.01 46.9 / 1.73 DropEdge [A / S] 75.0 / 2.01 75.5 / 2.59 58.1 / 2.10 42.7 / 1.84 32.1 / 1.46 AdaEdge [A / S] 74.9 / 2.47 73.9 / 2.42 72.0 / 2.47 68.9 / 2.05 54.6 / 1.86 VEM-GCN [A / S] 77.7 / 2.51 78.0 / 3.57 78.4 / 2.51 78.1 / 3.11 78.1 / 2.94
Citeseer
Vanilla GCN [A / S] 61.0 / 1.82 56.7 / 1.83 53.7 / 1.75 44.9 / 1.66 26.7 / 1.51 DropEdge [A / S] 60.3 / 1.83 56.5 / 1.95 50.1 / 1.52 35.5 / 1.24 23.7 / 1.13 AdaEdge [A / S] 61.5 / 1.84 58.7 / 1.83 53.1 / 1.87 49.1 / 1.72 43.5 / 1.62 VEM-GCN [A / S] 64.2 / 1.89 64.2 / 2.01 63.7 / 1.85 63.8 / 1.93 63.7 / 1.83
Cora-ML Vanilla GCN [A / S] 83.4 / 2.87 81.3 / 3.15 77.7 / 2.46 66.4 / 2.11 44.9 / 1.73 DropEdge [A / S] 83.1 / 2.85 81.4 / 3.17 77.6 / 2.42 43.4 / 2.59 37.1 / 2.39 AdaEdge [A / S] 83.3 / 2.98 81.0 / 3.21 78.1 / 2.89 70.2 / 2.50 53.5 / 2.43 VEM-GCN [A / S] 84.4 / 3.78 84.4 / 3.88 84.4 / 3.70 84.4 / 4.45 84.3 / 4.12
Figure 1: Convergence analysis.
Table 3: Average test accuracy (%) under different label rates on the Amazon Photo dataset.
# labels per class 5 10 20 30
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 BBGDC 87.3 88.4 90.1 90.4 TO-GCN 83.2 85.4 86.7 88.2 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 G3NN 86.3 88.8 90.6 90.8 GMNN 87.9 89.4 91.2 92.3
VEM-GCN 89.2 90.5 91.8 92.8
backbone by noticeable margins. Specifically, we 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 Vl might cause topology imbalance between Vu and Vl. The GCN trained on Vl with enhanced graph topology would fail on Vu 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 a 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 2 shows the test accuracy and the oversmoothness 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 and supplementary results of VEM-GCN on additional datasets are shown in Appendix E.1. As can be seen in Table 2, 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 of over-smoothness measurements indicate that VEM-GCN indeed produces more separable node embeddings across different classes to address the over-smoothing
problem. We further take Amazon Photo as an example dataset to validate VEM-GCN under different label rates. Similar trend as Table 1 can be found in Table 3.
Convergence Analysis and Visualization Results. VEM-GCN leverages the variational EM algorithm for optimization. In this subsection, we analyze the convergence of VEM-GCN. Figure 1 depicts the accuracy improvement curve of pθ1 during the EM iterations under the full-supervised setting. We find that VEM-GCN requires only a few iterations to converge. We further take CoraML as an example to give the corresponding visualization results of graph topology optimization. Figure 2 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 to relieve the over-smoothing problem. Note that, although the refined graph is much denser than the observed graph, the hyperparameter p (0.05 here) in q̄φ helps maintain the sparsity of the latent adjacency matrix in the training procedure. Thus, the M-step can still be implemented efficiently using sparse-dense matrix multiplications.

heading: 5 CONCLUSION
text: In this paper, we present a 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 assortative-constrained stochastic block model and utilizing the variational EM algorithm to jointly optimize the graph structure and the likelihood function, VEM-GCN outperforms a variety of state-of-the-art methods for tackling over-smoothing, uncertain graphs, and topology optimization in GCNs. For future work, we expect further improvements for the VEM-GCN architecture to deal with more complex graphs such as hypergraphs and heterogeneous graphs.

heading: A ALGORITHM
text: For a fair comparison, we adopt the vanilla GCN (Kipf & Welling, 2017) as the backbone for all baselines and our proposed VEM-GCN architecture. A two-layer GCN is in the following form:
pθ1(Y|A,X) = softmax ( Ḋ− 1 2 ȦḊ− 1 2 ReLU ( Ḋ− 1 2 ȦḊ− 1 2 XΘ(0) ) Θ(1) ) , (13)
where X is the input node attribute matrix, IN is the identity matrix, Ȧ = A + IN is the adjacency matrix with added self-loops, Ḋ is its corresponding diagonal degree matrix, and θ1 = {Θ(0),Θ(1)} are the learnable weight parameters. Algorithm 1 describes the proposed VEM-GCN architecture.

heading: B FURTHER DISCUSSIONS
text: In addition to recent strategies for tackling over-smoothing issues, we 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 in several recent works (i.e., BGCN (Zhang et al., 2019) and G3NN (Ma et al., 2019)). However, these architectures are totally different from VEM-GCN in motivations, objective functions and training methods. BGCN (Zhang et al., 2019) jointly infers the node labels and the parameters of SBM using only Aobs, which ignores the dependence of the graph on X and Yl. Then the
Algorithm 1 VEM-GCN Input: Observed graph Gobs and labels Yl for the labeled nodes Vl. Parameter: φ in the E-step and θ in the M-step. Output: Predicted labels Yu for the unlabeled nodes Vu.
1: Pre-train pθ with Aobs and Yl to get initial pθ(Yu|Yl,Gobs). 2: for EM iteration t = 1, . . . , T do 3: E-step: 4: for training step s1 = 1, . . . , S1 do 5: Sample Ŷu ∼ pθ(Yu|Yl,Gobs) for the unlabeled nodes Vu. 6: Set pθ(Alatent |Yl,Gobs) = pθ(Alatent |Yl, Ŷu,Gobs) according to Eq. 6. 7: Update qφ to optimize the objective function in Eq. 7 with SGD. 8: end for 9: M-step:
10: Obtain q̄φ(Alatent |Gobs) according to Eq. 9. 11: for training step s2 = 1, . . . , S2 do 12: Sample Âlatent ∼ q̄φ(Alatent |Gobs) for the latent adjacency matrix. 13: Update pθ to maximize the log-likelihood log pθ(Yl|Âlatent ,Gobs) with SGD. 14: end for 15: Predict categorical distributions pθ(Yu|Yl,Gobs) according to Eq. 11. 16: end for 17: return Final predicted labels for Vu based on pθ(Yu|Yl,Gobs).
adjacency matrices sampled from the inferred SBM are used to train the GCN. Different from VEMGCN, BGCN neither explicitly promotes intra-class connection nor demotes inter-class interaction. It only achieves robustness under certain conditions such as adversarial attacks, benefiting from the uncertainty brought by the inferred SBM. G3NN is a flexible generative model, where the graph generated by SBM is based on the predictions of an additional MLP learned from only X and Yl. The predictions for the unlabeled nodes are still based on Gobs (i.e., the input adjacency matrix of the GCN is still Aobs). By contrast, VEM-GCN aims at addressing the over-smoothing issue with topology optimization. In VEM-GCN, the M-step trains a GCN to obtain the predictions of the unlabeled nodes based on Alatent, X, and Yl. We then estimate the posterior distribution on Alatent based on Yl 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 Alatent. The E-step and M-step are optimized in an alternating fashion to improve each other.
VEM-GCN vs. VGCN. VGCN (Tiao et al., 2019) also introduces a latent graph Alatent and optimizes LELBO in Eq. 3. However, it directly optimizes the ELBO in a VAE (Kingma & Welling, 2014) fashion and the posterior distribution of Alatent is set to approximate the pre-defined graph priors p(apriorij = 1) = ρ1a obs ij +ρ2(1−aobsij ) with 0 < ρ1, ρ2 < 1 using the re-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 Yu based on the original Gobs). 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 Yu as latent variables and optimizes the following ELBO:
log pθ(Yl|X) ≥ Eqφ(Yu|X)[log pθ(Yl,Yu|X)− log qφ(Yu|X)]. (14)
In the E-step, GMNN parameterizes qφ(Yu|X) with a GCN and qφ(Yu|X) is optimized to approximate the posterior distribution pθ(Yu|Yl,X). In the M-step, GMNN utilizes another GCN to model the conditional distribution pθ(yi|yNB(i),X) for each node vi ∈ V (NB(i) is the neighbor set of node vi) 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
latent graph to approximate its posterior distribution based on SBM in the E-step, and trains a GCN based on the latent graph in the M-step.

heading: C DATASET STATISTICS
text: We utilize seven node classification benchmarks in 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 https://github.com/ tkipf/gcn/tree/master/gcn/data, and Cora-ML can be downloaded from the source code of (A)PPNP (Klicpera et al., 2019a) publicly available at https:// github.com/klicperajo/ppnp/tree/master/ppnp/data.
• Amazon Co-purchase Graph. The Amazon Photo and Amazon Computers datasets from the Amazon co-purchase graph can be publicly downloaded from https://github. com/shchur/gnn-benchmark/tree/master/data (Shchur et al., 2018).
• Microsoft Academic Graph. The MS Academic graph can be downloaded from the source code of (A)PPNP (Klicpera et al., 2019a) publicly available at https://github.com/ klicperajo/ppnp/tree/master/ppnp/data.
An overview of the dataset statistics is listed in Table 4. Note that for these open datasets, three (Cora, Citeseer, Pubmed) are given in the form of undirected graphs, while four (Cora-ML, Amazon Photo, Amazon Computers, MS Academic) are directed graphs. GCN treats all these datasets as undirected graphs (i.e., a′ij = [aij + aji > 0], where [·] denotes Iverson bracket).

heading: D FURTHER EXPERIMENTAL DETAILS
text: 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 qφ, where the numbers of neuron units of each layer are 128, 64, 64, and 32, respectively. We use tanh as the nonlinear activation function for the hidden layers. In the M-step, pθ1 is a vanilla GCN with the number of hidden units set as 32, and we use the official source code from https://github.com/tkipf/gcn/tree/master/gcn. All the baselines and our VEMGCN architecture are trained on a single NVIDIA GTX 1080 Ti GPU with 11GB memory.
We just utilize the raw node attributes X as the input to qφ. Note that we can 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 to smooth the input signal. Let Ârow = (D + γIN )−1(A + γIN ) denote the “self-enhanced” adjacency matrix with row normalization (we use γ = 1.5 in this paper), and [A‖B] be the concatenation of matrices A and B along the last dimension. Consequently, we summarize the specific input to qφ for all the datasets as below.
• For Cora, Citeseer, and MS Academic, we use X′ = ÂrowX as the input of qφ.
• For Pubmed and Amazon Photo, we use X′ = [ X‖ÂrowX‖Â2rowX ] as the input of qφ.
• For Cora-ML and Amazon Computers, we use X′ = [ X‖ÂrowX ] as the input of qφ.
For the sampling in the E-step, we find that it is not always stable to draw the sampled labels Ŷu ∼ pθ (Yu|Yl,Gobs). To alleviate this problem, we maintain Ŷu ← argmaxy(pθ (Yu|Yl,Gobs)) with probability pe, and sample Ŷu ∼ pθ (Yu|Yl,Gobs) with probability (1 − pe) to improve the performance in 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. 9 the same as the training procedure (commonly p < 1), sample S (S > 1) adjacency matrices, and predict the classes for the unlabeled nodes according to Eq. 11; (2) set p = 1 (i.e., the latent adjacency matrix is now deterministic) and S = 1. We report the best test accuracy obtained using these two sampling methods on each dataset and find that (2) almost always performs better.
D.2 HYPERPARAMETER SETTINGS
Table 5 summarizes the hyperparameters adopted for the full-supervised setting on the seven benchmark datasets. For the label-scarce setting, the hyperparameters are the same, except for ε1 and ε2 that need to be carefully tuned in the search space: ε1 ∈ {0.95, 0.99, 0.995, 0.999, 0.9995, 0.9999}, ε2 ∈ {0.001, 0.005, 0.01, 0.05, 0.1}.
D.3 METRIC FOR MEASURING OVER-SMOOTHNESS
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 distinguishable representations for nodes in different classes. Hence, we use the ratio of average inter-class distance to average intra-class distance (Euclidean distance of input node features in the last layer) to measure the over-smoothness. Formally, given the learned node embeddings H = {hi}Ni=1 (the input node features of the last layer), we first calculate the distance matrix D = [dij ] ∈ RN×N with each entry defined as
dij = ∥∥∥∥ hi‖hi‖2 − hi‖hi‖2 ∥∥∥∥
2
, (15)
where ‖ · ‖2 denotes Euclidean norm. Next, we define the inter-class mask matrix and intra-class mask matrix as follows:
Minter = −Ã + 1N×N , (16) Mintra = Ã− IN , (17)
where Ã = YY> is the optimal graph and 1N×N is a matrix of size N × N with all entries set to 1. Then we can obtain the inter-class distance matrix Dinter = [dinterij ] ∈ RN×N and the intraclass distance matrix Dintra = [dintraij ] ∈ RN×N by element-wise multiplication D with the mask
matrices:
Dinter = D ◦Minter, (18) Dintra = D ◦Mintra, (19)
where ◦ denotes element-wise multiplication. Next we get the average inter-class distance ADinter and the average intra-class distance ADintra, with which we measure the over-smoothness as their ratio R:
ADinter =
∑ i,j d
inter ij∑
i,j 1(d inter ij )
, (20)
ADintra =
∑ i,j d
intra ij∑
i,j 1(d intra ij )
, (21)
R = ADinter
ADintra , (22)
where 1(x) = 1 if x > 0 otherwise 0.

heading: E FURTHER EXPERIMENTAL RESULTS
text: E.1 CLASSIFICATION RESULTS UNDER THE LABEL-SCARCE SETTING
Supplementary experiments for Table 2 are shown in Table 6.
E.2 VISUALIZATION RESULTS
Figure 2 demonstrates the topology optimization results on the Cora-ML dataset under the fullsupervised setting. For the lable-scarce setting, the visualization results are shown in Figure 3.
We further take Cora-ML as an example dataset to provide t-SNE (Maaten & Hinton, 2008) visualizations 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 4 and 5. As can be seen, VEM-GCN indeed generates more separable node embeddings for nodes in different classes (colors) for classification. In particular, a ten-layer 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 a two-layer model.
E.3 COMPLEXITY ANALYSIS
VEM-GCN is very flexible and general. There is no constraint on the design of the two neural networks qφ and pθ. Therefore, the architecture can be combined with arbitrary GCN models and
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 in Sections 3.2 and 3.3, the M-step is a traditional training procedure for optimizing the GCNs. Although Alatent recovers more intra-class edges than Aobs, the parameter p in Eq. 9 helps 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 an extra procedure that trains a MLP for graph structure optimization. However, to address the over-smoothing issue at the core, we 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, VEM-GCN optimizes Alatent with amortized variational inference (i.e., training a MLP shared by all the node pairs with mini-batch SGD in the E-step), which is faster than BGCN (Zhang et al., 2019) (Bayesian method) and LDS (Franceschi et al., 2019) (topology optimization) and is scalable for large-scale graphs. For training on the Amazon Photo dataset with a NVIDIA GTX 1080 Ti GPU, VEM-GCN is about 3× faster than LDS and 4× faster than BGCN.
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 substituted with any graph models. This subsection further verifies the effectiveness of our proposed method by trying different models for pθ1(Yl|Alatent,Gobs). We also apply the same node embeddings 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(l+1) = σ (( (1− α(l))P̃H(l) + α(l)H(0) )( (1− β(l))IN + β(l)W(l) )) , (23)
where H(0) = XW(0) is the output of the first layer (a fully connected layer), P̃ = Ḋ− 1 2 ȦḊ− 1 2 is the normalized adjacency matrix, α(l) and β(l) are two hyperparameters.
We utilize GCNII as the backbone that results in the VEM-GCNII architecture. We use the official source code from https://github.com/chennnM/GCNII and employ the hyperparameter
settings reported in (Chen et al., 2020b) that achieve the best performance on the three citation networks (i.e., Cora, Citeseer, and Pubmed) under the label-scarce setting. For the other four datasets, we 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 labeled nodes per class as the training set. Experimental results are shown in Table 7. As can be seen, VEM-GCNII consistently boosts the performance of GCNII, further verifying the effectiveness and flexibility of our proposed architecture.

Review summaries:
The 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. 

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.