Interpretable Node Representation with Attribute Decoding
Authors: Xiaohui Chen
Xi Chen
Liping Liu
Venue: Accepted by TMLR ()

Abstract: Variational Graph Autoencoders (VGAEs) are powerful models for unsupervised learning of node representations from graph data. In this work, we make a systematic analysis of modeling node attributes in VGAEs and show that attribute decoding is important for node representation learning. We further propose a new learning model, interpretable NOde Representation with Attribute Decoding (NORAD). The model encodes node representations in an interpretable approach: node representations capture community structures in the graph and the relationship between communities and node attributes. We further propose a rectifying procedure to refine node representations of isolated notes, which improves the quality of the representations of these nodes. Our empirical results demonstrate the advantage of the proposed model when learning graph data in an interpretable approach.

Published in Transactions on Machine Learning Research (12/2022)
Interpretable Node Representation with Attribute Decoding
Xiaohui Chen"
aioohui. canobuui.cher@ttffssscoom
Deportment of Computer Science
Tufts University
Xi Chen'
vi w..cenn15@rugerr.com edu
Department of Computer Science Rutgers University
Li-Ping Liu
liping, linig.l edu
Deportment of Computer Science Tufts Universily
Reviewed OpenReview: https:
httpe:///penrrvveeu openr/view........ net/ forum? id= AM
Abstract
Variational Graph Autoencoders (VGAFs) are powerful models for unsupervised learning of node representations from graph data. In this work, we systematically analyze modeling node attributes in VGAEs and show that attribute decoding is important for node reprosentation learning. We further propose a new learning model, interpretable NOde Representation with Attribute Decoding (NORAD). The model encodes node representations in an inter- pretable approach: node representations capture community structures in the graph and the relationship between communities and node attributes. We further propose rectifying procedure to refine node representations of isolated notes, improving the quality of these nodes' representations. Our empirical results demonstrate the advantage of the proposed model when learning graph data in an interpretable approach.
1 Introduction
Graph data are ubiquitous in real-world applications. Graph data contain rich information about graph nodes. The community structure among graph nodes is particularly interesting. Such structures modeled by traditional models such as the stochastic blockmodel (SBM) (Wang & Wong 1987 1997) and its variants, which assign a node to one or multiple communities.
Snijders & Nowicki
Learning node representations are widely investigated in document networks. One typical branch is Relational Topic Model (RTM) (Chang Blei. 2009) and its variants (Panwar et al.] 2021 Bai al.) 2018). In such models, the links and node altributes are decoded from the node representations, which learned from documents with rich textual information. RTM-based models often provide interpretable representations due to their carefully-designed graphical models. However, the effectiveness of the RTM-based models highly relies on the text richness of the dataset.
On par with the RTM-based models, Variational Graph Autoencoder (VGAE) Kipf & Welling 2016 utilizes Graph Neural Networks (GNNs) to learn node vectors that encode information that can be used for reconstructing the graph structure. This model further improved in multiple aspects. [Meta et al. 2019
et al. ) Sarkar al.
2020)) adopt different priors to learn node representations for different applications. Hasanzadeh al. (0199 introduce hierarchical variational framework to VGAE and modify the link decoder.
Pan et al. (2018 2019]; Tian et al. (202bb) adopt the training scheme of generative adversarial networks
(GANs) [Goodfellww et al. 2014 to encode the node latent representations, Tian et al. (022a) employs
Equal contribution.

---

Published in Transactions on Machine Learning Research (12/2022)
masked autoencoder to learn node representations for heterogeneous graphs. Following VGAE, most of its variants only use node attributes in the encoder but do not decode node attributes. Though some other models (Mehta et al. 2019 Cheng et al.) (021) use separate decoder heads to generate graph edges and node attributes. There is no systematic approach to analyzing how node attributes should be used to learn representations the VGAE framework better.
In this work, we analyze VGAE using the cooomattoontheoretii framework by Alemi et al. (2018) and show the thcoretical strengths of different model constructions. The analysis indicates that appropriate modeling of node attributes benefits large class of link prediction tasks. Node attributes not only help to overcome the limitation of structure node representations by breaking symmetric structures in the graph (Srinivasan & Ribeiro 2019), but also provide rich information for link prediction.
We further devise a new representation learning model, interpretable Node Representation with Attribute Decoding (NORAD), which Iearns interpretable node representations from the graph data. To exploit node altributes, the model includes specially designed decoder for node attributes. The model learn good representations for nodes with low degrees. When there are isolated nodes in the graph, their representations are generally hard to learn. We show that their representations can be better learned by attribute decoding. We also propose rectification procedure to refine representations of isolated nodes.
We conduct extensive experiments to evaluate and diagnose our model. The results show that node representations learned by our model perform well link prediction and node clustering tasks, indicating the good quality of these representations. We also show that the learned node representations capture community structures in the graph and the relationship wetn communities and node attributes.
Our contributions can be summarized follows:
we systematically examine VGAE through an information-theoreer analysis; we propose a new model NORAD, which includes a specially designed attribute decoder and a refinement procedure for representations of isolated nodes; and we conduct extensive experiments to study the quality and interpretability of node representations learned by NORAD.
2 Preliminaries
Let G = XA denote an attributed graph with n nodes, A E Raxx is the binary adjacency matrix of the graph, and X = (x:) E RaxD denotes node attribules, with x, being the attribule vector of node i. We consider the problem of jointly modeling A and X. The goal is to learn interpretable node representations Z = (2.) E = that can better explain the data. Then provides essential information for downstream tasks such as node clustering.
Graph Neural Networks. GNN lype of neural network designed to extract information from graph data. It typically consists of multiple layers, each of which runs message-passingg passing procedure encode information into a node's vector representation. Let H gnn(A, denote the network function of an L-layer GNN, which is typically defined by ( X,
O ( 11 w + AH"-
1= 1,,,..,,4
and - H(), Here o(-) is the activation function. w( and v(O) are the network weights for the [-th layer. We denote all network weights with
Variational Graph Autocncoder. VGAE Kipf Welling 2016 learns node representations in an
unsupervised approach based on variational auto-encoder (VAE) (Kingna & Welling 2013). In VGAE, the prior distribution pZZ) over node presentations Z is standard Gaussian distribution. And the generative
2

---

Published in Transactions on Machine Learning Research (12/2022)
model p(A|Z) Z) is defined
70
P
2)
(( 24, 2j), p(Ai = 1|2,, 23) = sigmoid (z) 2z).
(1)
i=1j=1
VGAE is type of variational autoencoder (Kingma & Welling 2013 It defines its variational distribution
(2|AA,) X) to be Gaussian distribution Gaussian 14, o²), which is defined by GNN.
(v, = gnn(,, X).
(2)
The output of the GNN is split into μ and o, representing the mean and standard derivation, respectively. VGAE maximizes the Evidence Lower Bound (ELBO) of the marginal log- likelihood l(g)(A) to learn the encoder and the decoder:
Lg =
+ log log ( A, (Z),
(3)
After the encoder is learned, its mean f can be used as deterministic node representations. Note that node features X are not decoded in this model. Therefore, i mostly represents structural information of nodes but not attribute information, though the μ also computed from X.
3 An Information-Theoole
Analysis of Attribute Decoding
this section, we analyze VGAE from the perspective with the rate-distortion theory (Alemi et al. 2018 and consider the mutual information between the encoding and obscrvod data (A, X). Lot (. X) be the data distribution and H be its entropy, which is constant. Let. I, 7[AA, Z] denote the mutual information between (A,X) and Z. Note that Lg is defined from the encoder distribution (Z) X) and the data distribution. The maximization of the ELBO
Le X log pl X + log log (Z|A,
(4)
can be viewed as indirect maximizatioo of the mutual information /[AA, X); Z] under rate constraint
(Aemi
et al. 2018 We further decompose [[(A, X); Z] as follows:
I[ x); Z = /A; IX: 2 -
(5)
In this dccomposition, the last term ]|A is constant decided by the data. The first term is the information about A from Z, and the second is the information about X. The third term 7|A; X Z is the information between A and X that cannot be explained by Z. When is lossless encoding, [[A; X|Z| =
The docomposition above derived from the encoder distribution (Z X). Still, helps us to design the decoder p( A, X which approximates AA, X|Z) when maximizing the ELBO L.. One variant of VGAE Meeht et al, 2019 Cheng et al.) 2021 assumes p(A, p(X A Z). In this case, the conditional mutual information /[A; X /Z] tends to be zero. The conditional independence assumption may require Z to have extra bits so that Z can explain A and X separately. In this model choice, the lower bound becomes
Ca = E logp + log p( Z) + PZ) - log g (Z(A,
(6)
Other possible variants that do not have the assumption, the decoder p(A, XZ) can be decomposed as (XX)))p(A(X) Z), then is more flexible and should fit the data better. However, Z less capable of explaining because part of the information is encoded X. A similar issue happens the decomposition p(A,X/Z) =
Z).
Another variant, Graphite (rrover et al. 2019 takes totally different approach: it only lets Z encode A and conditions the entire model on X. Therefore, the ELBO is
L. Bx(z)A.)) log (A log log g (Z < [[AA,]].
(7)
3

---

Published in Transactions on Machine Learning Research (12/2022)
8
u
C
Cj
Zi
Lj
X
X
A ij
B
Figure The plate representation our framework. Here (6, u, 8) are the prior parameters.
In this case, the optimal encoding Z only encodes the part A that cannot explained by X. This results in Z only containing small portion of the information about A.
In the ELBO L, of the basic VGAE, there is decoding of X, which means that the encoder has no incentive to encode any information about X.
Our analysis shows that the simple formulation Ca with conditional independence assumption is better if we want Z to maximally encode information about X). Though we are not the first to discover this formulation, our analysis of different formulations helps deepen the understanding of VGAE variants.
Fix the bias of model fitting in link prediction. Node representations of VGAE are often used in link prediction tasks. Therefore, the given adjacency matrix Å, which is sparser than the true adjacency matrix A. In this case, we must do model fitting with Å instead of A.
Model training based on Å biased because actual edges missing from À are mixed with non-edges. This issue has been studied by Liang et al. (2016); Liu & Blei (2017) in different contexts. Specifically, the bias is due to the term Eg log pl (A[Z)), which leads Z to treat missing edges and non-edges equally. However, in some datasets, X and A are strongly correlated, and X is observed for all graph nodes. In this case, encoding information in X helps improve the link prediction performance, so we consider a modified ELBO:
L. B2(ZAA (ogz(A + a logpp(X()) + log,(Z) log g (Z[A,
(8)
In link prediction task, we the ratio factor so that model training can pay more attention to node features. Note that this modified ELBO still lower bound of T H when X is discrete and log p(X|Z) < 0. If we set a = 0, equivalent to VGAE. If À in a representation learning task, we still use the normal ELBO and set a 1.
4 Interpretable Node Representation with Attribute Decoding
In this section, we introduce our new model, NORAD, learn node representations. The proposed model has two goals. The primary goal to learn high-quality node representations that best preserve the information of the attributed graph, and the secondary goal is to make the learned representations interpretable.
4

---

Published in Transactions on Machine Learning Research (12/2022)
We will use the formulation La in Equation the encoder g(Z|A, X), the prior p(Z), the decoder p(A Z), and the decoder p(X We illustrate the graphical model of our framework in Figure]
(
construct our model. We need to specify four distributions:
4.1 The prior distribution
We assign a prior such that the representation 2; of node i is sparse vector. We use prior that separately decides the sparse pattern and non-zero values in z, Let C (c,) be the random binary vectors indicating the sparse pattern, and let V= (v,))=, 1 be the random real value vectors deciding non-zero entries Z. Both of them have the same dimension Z. Then
(9) Here = 0.5, u= 0, = 1, and C @ V with @ being the Hadamard product. The prior p(Z) in our framework is equivalent to pCC, V). We can view 2, i-th node's membership assignment in K communities. Each entry of z, is from spike and slab distribution: the spike indicates whether the i-th node belongs to the corresponding community, while the slab indicates the (positive negalive) strength of i-th node's membership in the community.
Cjks ~ (ernoulli
Vik Gaussian(u, s), where i = I,..., ni k 1,..., K
4.2 The conditional distribution of the adjacency
We then define the gencrative process of graph edges. We use the OSBM (Latouche et al. 2011 to define the decoder for A. In OSBM, two nodes' community memberships indicate how they interact. We use parameter B E R to indicate the interactions between different communities. A large value in the entry B& means node in community k has a higher chance of connecting with a node in community W, and vice versa. Formally, define the graph edge distribution as follows:
PB PB 1/2,, 2,) = sigmoid(z, Bz,), (B(A = IIII PB A,)l,,,2)) i=1j=1
(10)
Here B is learned together with other parameters.
The OSBM distribution is important for the NORAD model to encode meaningful community structures the graph into node representations. To explain the graph structure A, z: Bz, needs to be large for connections and small for non-edges. While the model can freoly decide the B matrix, later experiments indicate that the learned B has relatively large positive diagonal elements. It means that the nodes belonging to the same communities (having positive entries corresponding to these communities) tend to have connection in between.
4.3 The conditional distribution of attributes
We also define an interpretable decoder for node attributes. X; E (0, D) is a binary vector.
Here we first focus on binary attributes:
We assune that each z; independently generates x;: pX| = lev p(x./z,). Then we design an Attention- based Topic Network (ATN) to consider the community-attribne relation in p(x,/z,). We use to denote the network parameters in ATN.
Similar to topic models, ATN assumes that each community is represented as embedding vector. All such embedding vectors are in a matrix T E Kxd' Each attribute also has an embedding vector, and all attributes' vectors are denoted in a matrix U E gd'xD xD We compute attention weights from the two embodding matrices to docide the probabilitics of the node's attributes from the two embedding matrices. We first compule the aggregated community vector
g relu z.).
(11)
5

---

Published in Transactions on Machine Learning Research (12/2022)
Algorithm Variational EM for NORAD
network graph G (), initialized model and variational parameters (0, and blockmodel B, iteration steps 7 ratio factor regularization factor 7
Input:
Output: learned model and variational parameters (0, Ø) and blockmodel B. repeat
[Estep] Fix blockmodel B
for t= .... T do
Compute (17, p4 gnn(X, A: o).
Sample C ~ Bernoull(n)). V Gaussian o²) via reparameterizztiion tricks.
Compute Hadamard product Z = C V.
Compute loss L(0, a log pa (X + log Pn PBp (A + log V) - logg,(C, V). Update (ø, by maximizing [ 8) via SGD.
end for [M-step] Fix parameters (Ø)
for == .... m do
Compute (1. 0 gun X, A; 6).
Compute Hadamard product = 1) ( μ.
Compute loss L(B) = P [A] (Z) BB|-
Update B by maximizing (B) via SGD. end for until convergence of the ELBO L(0, 0,
Then we use the vector gi query compute attention weights against attribute vectors U.
Bi W.W.W
A sigmoid
(12)
d
Here the parameters Wg and Wi both have size (d' d"). We apply the sigmoid function, instead of softmax in standard attention calculation, get binary probabilities A;
We denote the procedure above as A; atn(z;; T, U. W), then we have
(x) I p zi), p(x 1/z,) Aid-
(13)
The calculation 11 and capture the interaction between communitics and "topics" X. The U matrix has shape such that d' much smaller than D, which means that it must capture correlations among node attribute entries, and each of U be viewed as topic. The three matrices T, W and Wi roughly decides how community components in activate these topics. Our experiment later does indicate the topic structure in U.
For node features that are not binary, we can devise appropriate distributions and parameterize them with A;-
4.4 The encoder
NORAD's encoder is designed for two purposes: computing node representations and model fitting through variational inference, which we will discuss right after this subsection.
The encoder 4 (Z|A, X) is computed by a GNN, whose parameters are collectively denoted by á. Since is computed from C and V, we use (C, V X) instead, this can be further represented as qz (Z A, X) do (VIA, X) A, X) by using mean-field distribution. In the variational distribution, V and C are

---

Published in Transactions on Machine Learning Research (12/2022)
respectively sampled from Bernoulli and Gaussian distributions, which are parameterized by GNN.
4s (C (n) 9o(V ~ Gaussian o²).
(14)
We use GNN to compute these distribution parameters from X and A.
(n. (4, = gnn A, Ø;
(15)
Here n, μ. and a are all matrices of size n x K. The output of the GNN has size n x (3K), then is split into the three matrices. All parameters of the two variational distributions are network parameters of the GNN.
Deterministic node representations Z are computed from and f directly.
z μ C (( > 0.5).
(16)
Here 1(1 0.5) gets binary matrix indicating which elements are greater than the threshold 0.5.
4.5 Model fitting through variational inference
In this section, we discuss the learning procedure of our model. Besides the ELBO we have discussed in the previous section, we also add regularization terms over the parameter B.
C(0.0. 0, B) E.s(Cc. Pm (A|C,, V) + a log ps (X|C, V) + logp((C V) log (o V/A, + BlI
(17)
The hyper-pane prrrm-err a controls the strength of the attribute decoder. We maximize the objective C(O, Φ, B) with respect to model paramcters (9 and B) and variational paramcters ø. The objective gradient is estimatod through Monte Carlo samples from the variational distribution. Note that the random variable C is binary, and we use the Gumbel-softmax trick (Jang al. 2016 then we can estimate the gradient of the objective efficiently through the reparameterizztion trick.
We find alternatively updating (0, d) and B in variational-EN, EM fashion gives better optimization performance. In our optimization procedure, we fix and update (0, σ) for a few iterations at E-step, and then fix model and variational parameters (0, Φ) and optimize B for a few iterations at M-step. The parameters are all optimized with SGD. The intuition behind this is that the training of B needs depend on somewhat clear relations between different communities. The training procedure is shown in Algorithm 1
4.6 Rectifying representations of isolated nodes
In the training process, the representations of isolated nodes are learned to predict zero connections from these nodes. As we have analyzed, representations learned in this approach are biased. Here we use the rectification strategy to post-process the learned representations of isolated nodes. For isolated node i, we first compute the deterministic node representation 2 from Equation (16) and then update 2 through ATN to improve the recovery of x, The update rule is shown as follows:
z
z + cV log2o(x;1z)),
(18)
where is the updated learning rate. We run the update for multiple iterations and obtain the final represen- tation. Empirically, 50 to 100 iterations usually give clear improvement of these nodes' representations.
5
Experiments
In this section, we study the proposed model with real datasets. The first aim of the study is to examine the quality node representations: whether the model learns node representations of high quality and how each component contributes to the learning. We examine our model through extensive ablation studics and sensitivity analysis. The second aim is to examine the interpretability of learned node representations, We look into the data and show how learned representations encode interpretable structures in the data.
7

---

Published in Transactions on Machine Learning Research (12/2022)
DecpWalk
VGAE
KernelGCN
DGLFRM
VGNAE
NORAD
AUC
84.6+0.01
92.6=0.01
93.1+0.06
93.4=0.23
94.9+L0.3
95.6
Cora
AP
88.520.00
93.3=0.01
93.240.07
93.8=0.22
94.940039
96.110.44
AUC
80.510.01
90.8=0.02
90.9110008
93.8=0.32
96.0:10.74
95.6:10.28
Citeseer
AP
85.0#1.00
92.0=0.02
91.840.04
94.4=0.73
96.1#0.89
96.540.19
AUC
84.2+10.02
94.2=0.76
94.5++0.03
94.0=0.08
95.0++0.26
97.1+0.25
Pubmed
AP
87.8+1.00
94.0=0.88
94.2110.01
95.0=0.35
94.7++0.36
97.310.28
AUC
80.4+00.55
90.8-0.37
93.6+H0222
93.7=0.41
91.8++0.44
96.3+-0.22
DBLP
AP
83.15
91.4=0.44
93.9
94.0=0.54
92.6+1.226
97.0110.88
AUC
OOM
87.2=1.37
OOM
91.2=0.38
92.3+5.03
94.5+0.22
OGBN-arxiv
AP
OOM
88.7
OOM
92.0=0.31
92.8+4.12
94.6++0.0
AUC
OOM
0.99
93.1+0.85
92.8=0.90
95.3++0.33
96.0+0.22
Wiki-cs
AP
OOM
0.94
93.0+1.22
93.0=1.07
94.5+L0.55
96.0+10.23
Table 1: Performance comparison of all models in the link prediction task: We use unpaired t-test. to compare
models' performance values. Not significantly worse than the best at the 5% significance level are bold.
DeepWalk
VGAE
KerneIGCN
DGLFRM
VGNAE
NORAD
NMI
40.0#1.26
42.6=2.64
44.2#1.07
48.0#2.02
51.120.84
50.313.72
Cora
ACC
56.5#1.71
56.7=4.49
60.912.43
63.114.11
67.512.29
66.515.89
NMI
13.2#1.55
15.5=2.83
25.612.56
28.811.63
35.613.76
38.911.18
Citeseer
ACC
38.8#2.12
36.1=2.38
52.8+4.36
51.942238
57.8+4.41
64.5+1.17
NMI
28.520.73
30.1=2.56
28.611.27
25.0
26.220.47
24.515.97
Pubmed
ACC
67.140.54
67.6-2.88
68.6
65.243.64
64.1
61.116636
NMI
19.7+1.76
23.6-2.70
30.5+
30.04:2.6
26.0+3340
DBLP
ACC
54.8
47.8=2.81
56.012.61
55.813.19
52.416.66
64.416.09
NMI
OOM
7.3+2.15
OOM
9.4+2.55
9.0+2.15
10.3#1.64
-GBN-arxiv
ACC
OOM
1013-1.15
OОM
11.24-0.89
10.4+0.97
11.1 0.69
NMI
OOM
21.2=5.66
34.1+5.20
20.41-6.99
24.6+1.10
34.1+1.57
Wiki-cs
ACC
OOM
29.9
39.113.86
30.4
33.7#1.01
39.4
Table 2: Performance comparison of all models in the node clustering task: We use unpaired t-lest to compare models' performance values. Not significantly worse than the best at the 5% significance level are bold.
Datasets. We use seven benchmark datasets, including Cora, Citeseer, Pubmed, DBLP, OGBL-collab,
OGBN-arxiv, and Wiki-cs (Morris et al. 2020 Hu et al. 2020 Mernyei & Cangea, 2020). The details of these datasets can be found in Table Appendix.
Baselines. We benchmark the performance of NORAD against existing models that share the same traits as ours. The experiment setups and the implementation details our model are shown in Appendix A.2 We consider five baseline methods. (1) DeepWalk (Perozzi et al. 2014) learns the latent node representations by trcating truncated random walks sampled within the network as sentences. (2) VGAE (Kipf Welling 2016 is the first variational auto-encoder based on GNN. (3) KernelGCN (Tian al. 2019 proposes a learnable dernel-based framework, which decouples the kernel function and feature mapping function in the propagation of GCN; (4) DGLFRM (Mehta et al. 2019) adopts IBP and Normal prior when encoding the node representations and adds a perceptron layer to the node representations before decoding the edges. (5) VGNAE (Ahn & Kim 20221 shows that T.2 normalization on node hidden vector in GCN improves the representation quality of isolated nodes.
5.1 Link prediction and node clustering
We consider the quality of node representations in link prediction and node clustering tasks. In particular, pay attention to the representations of isolated nodes in sparse graphs. In the link prediction task, all
8

---

Published in Transactions on Machine Learning Research (12/2022)
VGAE
KernelGCN
DGLFRM
VGNAE
NORAD
Hits@10f
26.18:10.12
0OM
28.75 +0.68
31.2440.19
3..5
Hits@501
44.76:10.98
00M
47.38+1.09 46.76=0.88 51.49+0.15
46.19=1.37
Hits@100f
51.44+0.770
0OM
51.39=0.42
51.40:0.225
Table 3: Performance comparison of all models on OGBL-collab dataset: We use unpaired t-test to compare models' performance values. Not. significantly worse than the best at the 5% significance level are bold.
models predict the missing edges of the graph based on the training data, including node attributes and links. We evaluate our model and the baselines regarding Area Under the ROC Curve (AUC) and Average Precision(AP) (AP) on six datasets. We follow the data splitting strategy Kipf & Welling (2016) and report the mean and standard deviation over 10 random data splits. For Wiki-cs, since all models yield high performance by following the data splitting stralegy in VGAE as mentioned in (Mernyei & Cangea 2020), we lower down the training ratio and use split ratio: train/val val/ttest: 0.6/0.1/0.3. The results are reported in Table [ Note that an "OOM" entry mcans that the corresponding model cannot run on that dataset because of the out-of-memory issue. Since the results on OGBL-collab use different metrics, we report the metric Hits@K, K=10, 50, 100 following (Hu et al. 2020 in Table 3 Given that KernelGCN requires transformation on the adjacency matrix, the computation memory cost is too high to scale it to large networks, e.g., OGBN-arxiv and OGBL-collab.
The table shows that NORAD significantly outperforms the baselines almost all datasets, illustrating the superior capability of our model in encoding graph information. The advantage is more obvious on DBLP, which has relatively rich node attributes and links.
In the node clustering task, we generate the node representations from different learning models and then use K-means to obtain the clustering results. We set the hyperparameter in K-means as the nunber of classes in each dataset. We compare the clustering performance with the node embeddings learned from the basclines above. We compare NORAD against the baselines in terms of Normalized Mutual Information (NMI) and Accuracy (ACC) on six datasets. Before calculating ACC, we use the Hungarian matching algorithm (Kuhn 1955 to match the K-means predicted cluster labels with true labels. We report the mean and standard derivation over 10 runs. The results can be found in Table 2
In the node clustcring task, NORAD works better on Cora, Citeseer, DBLP, OGBN-arxiv, and Wiki-es against almost all baselines. For Citeseer and DBLP, NORAD significantly outperforms all five baselines; this can be explained by the fact that these two datasets provide more node information or edge information than the other two. Our performance on Pubmed is not as competitive as on other datasets. One possible reason is that Pubmed has the least node information among all the six datasets, and node attributes not informative about node classes.
5.2 Ablation study
In this section, we do ablation studies to understand the benefit of each model's component in the link prediction task. Specifically, we investigate different variants of the decoder for A and X, respectively, and the benefits of employing representation rectification for isolated nodes. The results are tabulated in Table and implementation details can be found in Appendix A.2
We compare our edge decoder against two variants, whose results are shown in the second and third rows in Table 4 The first variant constructs the decoder by p(A, X p(X Z)p( A Z), that is, we first decode X from Z and then decode A from Z and decoded X. We find that this model is less capable of explaining the adjacency matrix because it mainly encodes information of node features. The decoding of the adjacency matrix depends on decoded features X, whose dimension is much higher than Z and likely to cause extra errors. The second variant uses the dot product decoder p(A from the VGAE model. It essentially uses an identity matrix as B. The dot product decoder in the second variant shows much worse performance than our decoder. This result shows the benefit of learning the block model B, which can control connection densities within/between the same/different. communities.
9

---

Published in Transactions on Machine Learning Research (12/2022)
Model Variants
Cora
Citesecr
NORAD
95.6++0.56
95.6+H0.28
construction w/ A(AAX,2
94.5+0.42
94.3+t0.6
VGAE decoder p( p(A[Z)
90.4+1.21
89.9
w w/o decoder pl (X|Z)
94.6++0.58
93.4+-0.99
NRTM decoder p(X[Z)
95.3++0.41
94.0=+0.22
TAN decoder p(X[Z)
95.0+t0.69
94.7++0.55
w/o rectification
95.0++0.2
95.0+0.29
Table AUC of link prediction on Cora and Citescer using different model variants.
We then investigate the power using different node decoders p p Z Specifically, we choose decoders proposed by Neural Relational Topic Model (NRTM) (Bai et al.) 2018) and Topic Attention Networks (TAN) (Panwar et al., 2021). In addition, the effect of the node decoder absence is also considered. We find that ATN decoder performs belter than the decoders in other works. Moreover, we see that using the node decoder significantly contributes to model performance. Interestingly, the richer the node attributes are, the more the model can benefit from utilizing node decoder.
Finally, we study how rectifying the representations of the isolated nodes brings additional performance rise to our model. Even though only a small portion of the nodes are isolated, we still observe a non-trial improvement in the performance, which indicates the effectiveness of rectification. We give more thorough analysis of it under the circumstance when graphs are sparse in the next section,
5.3 Attribute decoding for sparse graphs
Our experiments show strong evidence that decoding attribute benefits node representation learning when graphs are sparse. We create sparser graphs by masking out more edges during training. Specifically, we use different training ratios (TRs) and keep 20%, 40%, 60%, and 80% edges in the training set. For the remaining edges, 1/3 are used for validation, and 2/3 are used for testing. We again choose Cora and Citeseer datasets for analysis. Results reported in Table 5 This result shows that more benefit is gained from the node decoder ATN when graphs are sparser.
We then consider the case of strengthening the node decoder by using a values greater than 1. We run the same experiment as above but varying a values in Equation 117] and then report our obsorvations in Table We see that large a values slightly increase the performance for sparse graphs.
Suggesting links for isolated nodes is often considered as the cold-start problem (Schein et al., 2002). which is important in recommender systems. Here we examine the benefit of the rectification procedure proposed in Equation 18) by checking the isolated node representations. We consider datasets with different sparsily. A lower training ratio indicates more isolated nodes exist. The details of isolated nodes for each dataset can be found in Table g in Appendix. The results in Figure 2 show that our rectification procodure greatly improves the quality isolated nodes' representations.
5.4 Interpretability of node representations
We inspect node representations learned by model qualitatively and interpret them in the application context. Specifically, we focus on two questions: whether representations capture community structures in the data and whether representations explain node attributes from the perspective of community structures.
Alignment between community membership and node classes. We visualize a few example com- munities detected from the graph and correspond them to node labels. The visualization is through the following steps. (1) We first obtain node representations Z from a trained model and compress them into two-dimensional vectors by using t-SNE (Van der Maaten Hinton 2008). (2) Then we take 10% of the nodes and choose representative communities (corresponding to two entries a node vector). Note that we perform the dimension reduction in full data, then randomly take subset of the compressed data. (3) In the
10

---

Published in Transactions on Machine Learning Research (12/2022)
89
92
87
AUC
AUC
91
85
90
IR-20%
60%
IR=20%
TR-60%
40-40%
80%
TR-40%
TR-80%
20
40
20 40
60
80
100
Number iterations
Number of iterations
(a) Cora
(b) Citeseer
Figure 2: Rectifying representations of isolated nodes: for both (a) Cora and (b) Citescor datascts, we can find that the AUC of link prediction related isolated nodes increasing with the rectification iteration on all training ratios (TRs).
Cora
Citeseer
Cora
Citeseer
Ratio
w/o ATN
w/ ATN
w/o ATN
w/ ATN
20%
40%
20%
40%
20%
82.7=0.61
86.420.88
88.5
92.2::0.55
1.0
86.4
90.7
92.2
93.7
40%
88.520.71
90.7:0.44
91.7+0.51
93.7::0.99
1.5
86.5
90.8
92.6
93.9
60%
91.9-0.63
93.2+00.7
92.8:10.88
94.5+0.42
2.0
86.7
90.9
92.8
94.0
80%
94.0:10.75
95.2+1..66
93.9:10.62
95.6+10.48
2.5
86.8
91.1
92.9
94.1
3.0
86.9
91.4
93.1
94.3
Table 5: Benefits of using ATN versus different sparsity levels: The percentage(%) indicates the fraction of graph odges in the training set. We report the link prediction performance (AUC).
Table Link prediction performance (AUC) on Cora and Citeseer with different training ratios as increases.
last step, we set the threshold to 0.5 and compute the community membership for each selected node. There are three kinds of community assignments for each node community 1, community 2, and others.
We colors indicate node classes. Then we extract communities from Z. For community k, nodes with Zιk greater than threshold are considered to be in the community. We identify nodes in two communities and indicate them with markers in the figure. We see that nodes in the same community tend to be in the same node class. They also tend to clump together in the plot.
The visualization results are shown in Figure 3
Topics used by communities. Here, we inspect the relation between learned communities and node attributes by analyzing node representations learned from the Pubmed dataset. In this dataset, each node is a clinical article, the node attribute is a binary vector indicating words appearing in this article, and links represent their citation relations. The articles in Pubmed are categorized into three Diabetes Mellitus classes: (1) Experimental, (2) Type 1, and (3) Type 2. We examine whether nodes in the same community share similar topics. To determine which words are used by cach community k, we manually set c be a onc-hot. vector with C2 and Gaussian(O. I), then we get fake node vector z c o from community k. We sample 10,000 times, reconstruct via ATN, and get distribution of words ("topics") used by community k. These words do not include non-semantic words, which are removed by thresholding word frequency.
Our model learned 12 related subareas, which are highly related to their own corresponding high-frequency stemmed keywords. In the appendix, we show the full names the abbreviations in Table [0] We show each community's top eight stemmed keywords in Table 7 For each community, these keywords are coherently related to medical subarea, such as treatment, discase, etc. Here we manually assign each community a label according to the area. For example, by inspecting the keywords, the second community be labeled
11

---

Published in Transactions on Machine Learning Research (12/2022)
Community Community
Community 1
Community 2 Others
Others
(a) Cora
(b) Citeseer
The t-SNE visualization of node representations Cora and Citeseer: color indicates the node class, marker indicates the community assignment. We only choose two non-overlapping communities for visualization.
Figure 3:
Topic Label NAFLD DR
Top Eight Stemmed Keywords
liver, fat, resist, correl, hepat, befor, obes, degre retinopathi, complic, diagnosi, mortal, famili, cohort, predict, screen cholesterol, genotyp, polymorph, lipoprotein, heart, coronari, target, triglycerid exercis, postprandi, oral, presenc, region, metformin, reduct, agent intervent, intak, particip, promot, loss, individu, primari, dietari depress, chronic, approxim, dictari, socret, cpeptid, defect, vs period, pathogenesi, greater, continu, daili, meal, weight, dose receptor, alter, neuropathi, streptozotocin, oxid, inhibit, stimul, peripher antibodi, transplant, beta, pancreat, antigen, ica, immuu, tcell hypoglycaemia, hbalc, manag, symptom, life, glycaem, known, ii abnorm, metabol, children, nondiabet, durat, nerv, rat, sever caus, syndrom, evid, acid, diet, urinari, rat, insulindepend
CAD
Hypoglycemic agents
Diet intervention
Eating disorder
Obesity
AGEs
ICA
HbAlc
MS neuropathhy
MS uric acid
Table 7: Display of top eight words in twelve learned latent topics in Pubmed dataset. The topic labels are abbreviations clinical subareas related to Diabetes Mellitus. They are highly related to the top eight stemmed keywords. The details can be found in Table 10 in Appendix.
diabetic retinopathy (DR), which the most common complication of diabetes mellitus (Wang & Lo 2018); the third community can be labeled coronary artery disease (CAD), which is happened at higher risk in patients with type diabetes mellitus (T2DM) than non-T2DM patients Naito & Kasai (015 the ninth community can be labeled as Islet Cell Antibodies (ICA
It shows that the learned subareas of diabetes mellitus are all meaningful and interpretable after analyzing high-frequency stemmed keywords. Besides, We also find that each community often belongs to one node class in the dataset, which again proves that the detected community is coherent.
AAcordiing Narendran 2005 "the beta cell: ICA, the first islet (a pancreatic cell) 'autoantigen' be described. Antibodies to ICA present. in 90% type diabetes patients the time of diagnosis."
12

---

Published in Transactions on Machine Learning Research (12/2022)
6 Related Work
The stochastic blockmodel (Wang & Wong 1987 Snijders & Nowicki 1997] is frequently used for detecting
and modcling community structure within network data. Later variants of SBM make different assumptions
on the node-community relationships (Airoldi et al. 2008; Miller al. 2009 Latouche et al.] 2011). p. For
example, the mixed membership stochastic blockmodel (MMSB) (Airoldi et al. 2008) assumes each node
belongs to a mixture of communities. The overlapping stochastic blockmodel (OSBM) Latouche et al. 2011 assumes each node can belong to multiple communities with the same strength.
Variational framework [Biii et al.
2017] are frequently applicd in learning graph data (Kipf & Welling 2016
Chen et al.) 2021 The VGAE models [Kipf & Welling) 2016 Hasanzadeh et al., 2019 Mehta et al., 2019
Sarkar et al.
2020 Li et al.) 2020 Cheng et al., (021]] combine a VAE and a GNN to learn the representation
of graph data. DGLFRM (Mehta et al., 2019) replaces the Gaussian prior with Indian Buffet Process (TBP)
prior (Tch et al., 2007) to promote the interprotability of learned representations. LGVG (Sarkar et al., 2020 exlends the ladder VAE (Sonderby et al. 2016) lo modeling graph data and introduces the gamma distribution to enable the interpretability of the learned representation. But these models do not explain the relationship between communities and attributes. Other models improve the architectures of different components of VGAE. DGVAE (Li et al. 2020) instead uses the Dirichlet prior and shows its application in node clustering and balanced graph cut.
Cheng et al. 2021 devises a model that decodes multi-view node
attributes.
The RTM models (Nallapati et al. 2008
Chang & Blei 2009) focus on learning meaningful topics from the document content with the help of the relational information that resides in the document network. Various works [Wang et al. 2017 Bai et al.
2018 Xie et al.) 202 Panwar et al. 2021 are proposed based on this idea by either improving the graphical model or proposing a novel network architecture.
On combining the ideas of VGAEs and RTMs, our model can learn node representations that not only being useful for performing downstream tasks such as link prediction and node clustering but also provide high interpretability in both community-wise and topie-wise, where the former concerns the topological structure of the network and the latter concerns the content of the documents.
7 Conclusion
In this work, we have theoretically analyzed the role of node attribute decoder in representation learning with VGAEs. We show that the node attribute decoder helps the model encode information about the graph structure.
We further propose the NORAD model to learn interpretable node representations. We introduce the OSBM to the edge decoder with the aim of capturing communily structure. We carefully designed the ATN to decode node attributes, which improves the quality of node representations and makes them interpretable. We also design rectification procodure to refine representations of isolated nodes in the graph after model training.
However, our model has the following limitations: (1) It needs substantial work to extend our node attribute decoder for other types of features. (2) Although the block model improves the performance of edge decoding, the learned matrix B, which is desinged for capturing interactions between communities, still lacks enough interpretability.
Acknowledgments
We thank all reviewers and oditors for their insightful comments. Li-Ping Liu was supported by NSF 1908617. Xiaohui Chen was supported by Tufts RA support.
References
Scong Jin Ahn and MyoungHo Kim. Variational graph normalized autoencoders. In Proceedings of the 30th
ACM International Conference Information & Knowledge Management, pp. 2827-882222 2021.
13

---

Published in Transactions on Machine Learning Research (12/2022)
Edoardo Maria Airoldi, David M Blei, Stephen E Fienberg, and Eric P Xing. Mixed membership stochastic blockmodels. Journal of machine learnöng research, 2008.
Alexander Alemi, Ben Poole, Ian Fischer, Joshua Dillon, Rif A Saurous, and Kevin Murphy. Fixing a broken elbo. In International Conference on Machine Learning, pp. 159 168. PMLR, 2018.
Haoli Bai, Zhuangbin Chen, Michael R Lyu, Irwin King, and Zenglin Xu. Neural relational topic models for scientific article analysis. In Proceedings of the 27th ACM International Conference on Information and Knowledge Management, pp. 27 36, 2018.
David M Blei, Alp Kucukelbir, and Jon D McAuliffe. Variational inference: A review for statisticians. Journal of the American slatistioal Associalion, 112(518):859 877, 2017.
Jonathan Chang and David Blei. Relational topic models for document networks. In Artificial intelligence and statistics, pp. 81 88. PMLR, 2009.
Xiaohui Chen, Xu Han, Jiajing Hu, Francisco JR. Ruiz, and Liping Liu. Order matters: Probabilistic modeling of node sequence for graph gencration. arxiv preprint arxiv:2106. 06189, 2021.
Jiafeng Cheng, Qianqian Wang, Zhiqiang Tao, Deyan Xie, and Quanxue Gao. Multi-view attribute graph convolution networks for clustering. In Proceedings of the Twenty-Ninie Ninth International Conference International Joinl Conferences Artāficial Intelligence, pp. 2973 2979, 2021.
Ian Goodfellow, Jean Touget-Abadic Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. Advonces in neural information processing systems, 27, 2014.
Aditya Grover, Aaron Zweig, and Stefano Ermon. Graphite: Iterative generative modeling graphs. In International conference on machine learning, pp. 2434 2444. PMLR, 2019.
Arman Hasanzadeh, Ehsan Hajiramezanali, Nick Duffield, Krishna R Narayanan, Mingyuan Zhou, and Xiaoning Qian. Semi-implicit graph variational aulo-encoders. arXiv preprinl ar arXiv:1908. 1908.00708777 2019.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovee. Open graph benchmark: Datasets for machine learning on graphs. Advonces in neural information processing systems, 18:22118-22133 2020.
Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterization with gumbel-softmax. arXiv preprint arXiv:1611.01144, 2016.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1422.60 6980, 2014.
Diederik P Kingma and Max Welling, Auto-cncoding variational bayes. orXiv preprint arXiv.1312.6114, 2013.
Thomas N Kipf and Max Welling, Variational graph auto-encoders, arXiv preprint arXiv:1611.07990 2016.
Harold W Kuhn. The hungarian method for the assignment problem. Naval research logistics quarterly. 2 (1-2):83 97, 1955.
Pierre Latouche, Etienne Birmelé, and Christophe Ambroise. Overlapping stochastic block models with application to the french political blogosphere. The Annals of Applied Statistics, pp. 309 336, 2011.
Jia Li, Tomasyu Yu, Jiajin Li, Honglei Zhang, Kangfei Zhao, Yu Rong, Hong Cheng, and Junzhou Huang. Dirichlet graph variational autocncoder. arXiv preprint 2rXiv:2010.044. 0408 2020.
Dawen Liang, Laurent Charlin, James McInerncy, and David M Blei. Modeling user exposure rec- ommendation. In Proceedings of the 25th international conference on World Wide Web, pp. 951-961, 2016.
14

---

Published in Transactions on Machine Learning Research (12/2022)
Li-Ping Liu and David M Blei. Zero-inflated exponential family embeddings. In International Conference Machine Learning, pp. 2140-2148. PMLR, 2017.
Nikhil Mehta, Lawrence Carin Duke, and Piyush Rai. Stochastic blockmodels meet graph neural networks. In International Conference on Machine Learning, pp. 4466-4474. PMLR, 2019.
Péter Mernyei and Cätälina Cangea. Wiki-es: A wikipedia- based benchmark for graph neural networks arXiv preprint (0X::2007.02000 2020.
Kurt Miller, Michael Jordan, and Thomas Griffiths. Nonparametric latent feature models for link prediction. Advances in neural information processing systems, 22:1276-1281 2009.
Christopher Morris, Nils M Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. arXiv preprint orXiv:2007.08663, 2020.
Ryo Naito and Takatoshi Kasai. Coronary artery disease in type 2 diabetes mellitus: Recent treatment strategics and future perspectives. World journal of cardiology, 7 3:119-22 24, 2015.
Ramesh M Nallapati, Amr Ahmed, Eric P Xing, and William W Cohen. Joint latent topic models for text and citations. In Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 542-550, 2008.
P. Narendran, E. Estella, and S. Fourlanos. Immunology of type 1 diabetes. QJM: An International Journal of Medicine, 9888)5547-556 06 2005. ISSN 1460-2725. doi: 10. 10.1093/qjmed/ gjmed/hci088, URL https //doi org/10. 10. 109////mmmm/ccci088
Shirui Pan, Ruiqi Hu, Guodong Long, Jing Jiang, Lina Yao, and Chengqi Zhang. Adversarially regularized graph autoencoder for graph embedding. orXiv preprint ArXiv:1802.00 04404, 2018.
Shirui Pan, Ruiqi Hu, Sai-fu Fung, Guodong Long, Jing Jiang, and Chengqi Zhang. Learning graph embedding with adversarial training methods. IEEE transactions on cybernetics, 50(6):2475 2487, 2019.
Madhur Panwar, Shashank Shailabh, Milan Aggarwal, and Balaji Krishnamurthy: TAN-NTM:
Topic attention networks for neural topic modeling. In Proceedings of the 59th Annual Meeting of the Associalion for Computational Linguistics and the 11th International Joint Conference Natural Language Processing (Volume 1: Long Popers), pp. 3865-3880, Online, August 2021. Association for Computational Linguistics.
doi: 20.18633/v1/200 wwt.///ao......n........ 299. URL htttps:/aclaatthlleee http:////.ccaaooooooooo///////// wrt.://...//...-1oo.o..... 299
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and dala miningg pp. 701-710, 2014.
Arindam Sarkar, Nikhil Mehta, and Piyush Rai. Graph representation learning via ladder gamma variational autoencoders. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 5604 5611, 2020.
Andrew I Schein, Alexandrin Popescul, Lyle H. Ungar, and David M Pennock. Methods and metrics for cold-start recommendations. In Proceedings of the 25th anaual international ACM SIGIR conference 2002.
Research and development in information retrieval, pp.
Tom AB Snijders and Krzysztof Nowicki. Estimation and prediction for stochastic blockmodels for graphs with latent block structure. Journal of classification, 14(1):75 100, 1997.
Casper Kaac Sønderby, Tapani Raiko, Lars Maalec, Seren Kaac Sønderby, and Ole Winther. Ladder variational auloencoders. Advances in neural information processing systems, 29:3738 3746, 2016.
Balasubramaniam Srinivasan and Bruno Ribeiro. On the equivalence between positional node embeddings and structural graph representations. In International Conference on Learning Representations, 2019.
15

---

Published in Transactions on Machine Learning Research (12/2022)
Yee Whye Teh, Dilan Grür, and Zoubin Ghahramani. Stick-breaking construction for the indian buffet process. In Artificial Intelligence and Stalisties, pp. 556-563. PMLR, 2007.
Yijun Tian, Kaiwen Dong, Chumhui Zhang, Chuxu Zhang, and Nitesh V Chawla. Heterogeneous graph masked autoencoders. arXiv preprint arXiv:2208.0090 2022a.
Yijun Tian, Chuxu Zhang, Zhichun Guo, Xiangliang Zhang, and Nitesh V Chawla. Nosmog: Learning noise-robust and structure-aware mlps on graphs. arXiv preprint arXiv:2208. 10010, 2022b.
Yu Tian, Long Zhao, Xi Peng, and Dimitris Metaxas. Rethinking kernel methods for node representation learning on graphs. Advances in neural information processing systems, 32:11686 11697, 2019.
Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of machine learning research, 9(11), 2008.
Hao Wang, Xingjian Shi, and Dit-Yan Yeung. Relational deep learning: deep latent variable model for link prediction. In Thirty-firsl AAAI conference on artificial intelligence, 2017.
Wei Wang and Amy C. Y. Lo. Diabetic retinopathy: Pathophysiology and treatments. International Journal of Molecular Sciences, 19(6), 2018. ISSN 1422-0067. doi: 1..339//jmms11e 19061816. URL https
//www. mdpi com/ www.mm2m-000077777/0 14222-40000071////188
Yuchung J Wang and George Y Wong. Stochastic blockmodels for directed graphs. Journal of the American Statistical Association, 82(397):8-19) 1987.
Qianqian Xie, Yutao Zhu, Jimin Huang, Pan Du, and Jian- Yun Nie. Graph neural collaborative topic model for citation recommendation. ACM Transactions on Information Systems (TOIS), 40(3):1-30, 2021.
16

---

Published in Transactions on Machine Learning Research (12/2022)
Dataset
#Nodes
#Edges
#
# #Classes
Cora
2,708
5,429
1,433
7
Citeseer
3,312
4,732
3,703
6
Pubmed
19,717
44,338
500
DBLP
17,716
105,734
1,639
4
OGBL-collab
235,868
1,285,465
128
OGBN-arxiv
169,343
1,166,243
128
40
Wiki-cs
11,701
216,123
300
10
Table 8: Dataset statistics
A Appendix
A.1 Datasets details
Cora. Citation network consists of 2,708 documents from seven categories. The dataset contains bag-of- words feature vectors of length 1,433. The network has 5,278 links.
Citeseer. Citation network consists of 3,312 scientific publications from six categories. The dataset contains bag-of-words feature vectors of length 3,703. The network has 4,732 links.
Pubmed. Citation network consists of 19,717 scientific publications from three categories. The dataset contains bag-of-words feature vectors of length 500. The network has 44,338 links.
DBLP. Citation network consists of 17,716 papers from four categories. The dataset contains bag-of-words feature vectors of length 1,639. The network has 105,734 links.
OGBN-collab. Collaboration network consists of 235,868 authors. The dataset contains comes with a 128-dimensional feature vector obtained by averaging the word embeddings of papers published by the authors. The network has 1,285,465 links.
OGBN-arxiv. Citation network consists of 169,343 papers from fourty calegories. The dalaset contains comes with 128-dimensional feature vector obtained by averaging the embeddings of words in its title and abstract. The network has 1,166,234 links.
Wiki-cs. Wikipedia-based network consists of 11,701 subjects from ten categories. The dataset contains node feature vectors of length 300. The network has 216,123 links.
Isolated nodes in different training ratios. In Table calculate the numbers and percentages of isolated nodes in different training set split ratios, we also get the numbers and percentages of edges that contribute to generating the isolated nodes.
A.2 Model implementation and experimental details
In this section, introduce the NORAD implementation and experiments' detailed setups.
Hyperparameters setting. For the encoder of NORAD, choose 1-layer Graph Convolution Network (GCN) as our encoder. Since we need to output three sets of variational parameters, layers soparately. Each encoder shares the same output dimension. We search the number of cluster K over {32, 64, 128, 256} and find that our model is insensitive to K. When K becomes larger (usually 64 and above), the model gives a relatively stable performance. We choose K = 256 for all models in the reported experiments. For other VGAE baselines, we observe slight performance drop when increasing the dimension of the hidden layers of the encoder. Though node representations learned by NORAD are in higher dimension, argue that the actual number of effective entries is usually much smaller. For
three GCN
17

---

Published in Transactions on Machine Learning Research (12/2022)
Cora
Citeseer
Training ratio
20%
40%
60%
80%
20%
40%
60%
80%
# isolated nodes
1,370
702
336
120
2,045
1,275
737
341
% isolated nodes
50.6%
25.9%
12.4%
4.4%
61.8%
38.5%
22.3%
10.3%
#contributed edges
3,584
1,445
547
155
3,883
1,955
958
385
%contributed odges
66.0%
26.6%
10.1%
2.9%
82.1%
41.3%
20.3%
8.1%
Pubmed
DBLP
Training ratio
20%
40%
60%
80%
20%
40%
60%
80%
#isolated nodes
11,220
7,196
4,290
1,964
8,290
4,664
2,628
1102
%isolated nodes
56.9%
36.5%
21.8%
10.0%
46.8%
26.3%
14.8%
6.2%
#contributed edges
19,919
9,938
5,156
2,125
19,915
7,765
3,525
1249
%contributed edges
45.0%
22.4%
11.6%
4.8%
18.8%
7.3%
3.3%
1.2%
Table 9: Isolated nodes numbers and percentages in different training ratios.
Abbreviation
Full Name
NAFLD
Nonalcoholic Fatty Liver Disease
DR
Diabetic Retinopathy
CAD
Coronary Artery Disease
AGEs
Advanced Glycation End products
ICA
Islet Cell Antibodies
MS
Metabolic Syndrome
AIH
Autoimmune Hepatitis
DN
Diabetic Neuropathy
ED
Erectile Dysfunction
TyG
Triglyceride
BMT
Body index
UTI
Urinary Tract Infection
FSD
Female sexual dysfunction Hemoglobin
HGB
Table 10: Abbreviation and the full name of learned topics.
example, we only observe 12 effective entries in the Pubmed dataset. Detailed configurations of the encoders of the baselines and our models are shown in Table 11 For the node decoder ATN, search (d' d')) over {(128, 64), (64, 32 We set d' to 128 and d" to 64 in our experiment.
Training and prediction. We alternatively optimize (ø, and B. We first update (d, 0) for T steps, then update for T steps, and alternate until convergence. In the implementation, we set T 10 and 7 10. We use Adam optimizers Kingma & Ba (2014) with a learning rate of 0.001. Since we the Gumbel-softmax Jang et al. (2016) to relax the binary vector C, in the training process, annealing with 0.5 to be the minimum temperature. We use the relaxed binary vector for optimizing (ø, 0), and for optimizing B and prediction phase, we use the binary vector by truncating the Bernoulli parameters n. For isolated node rectification, we use the same learning rate to rectify the representation the isolated nodes. We optimize the representation for multiple iterations and choose the number of iterations to be when reporting the experiment results.
temperature
Hyperparameters
VGAE
KernelGCN
DGLFRM GCN
VGNAE
NORAD
Layer type
GCN
GCN
APPNP
GCN
Layers
2
2
1
Hidden dimension
(32, 16)
(32, 16)
(256, 50}
[128)
(256)
Prior
Gaussian
Ganssian
Gaussian-IBP
Gaussian
Gaussian Bernoulli B
Table 11: Encoder configuration of each model
18

---

Published in Transactions on Machine Learning Research (12/2022)
92
88
86
AUC
AUC
84
84
82
TR=20%
-0%
1R-20%
TR-60%
80
4R-40%
80%
TR-40%
TR-80%
w/o 0
60
80
100
w/o
40
100
Number of iterations
Number of iterations
(a) Cora
(b) Citeseer
Figure 4: Tsolated nodes link prediction and representation rectification: (a) For Cora, AUC of isolated nodes related link prediction is improved by adding ATN decoder (w/o + iteration 0) and increasing rectification iterations (iteration 100); (b) For Citeseer, the increase more obvious with lower training ratio.
Model diagnosis. Here we show the detailed implementation for each extra component mentioned in Section 5.2 For the probability construction (Z)p (X/Z)p( A|Z X), Z is used for two purposes: reconstructs X and reconstructs A with the help of X. For Z() we use the ATN as the node decoder. For P(A X), first use node encoder encode X into hidden vector R, which has the same dimension Z. Then concatenate Z with R and feed it into the edge decoder. We function for the node encoder. For the edge decoder in DGLFRM, two-layer MLP with ReLU activation linear layer along with the ReLU activation function. We set the dimension of the output Ž of the MLP to be half the nunber of the clusters K. We use Ž to reconstruct A via the imner product. And for reconstructing X, we still use Z. Isolated node rectification employed for all the model variants with node decoders.
A.3 Additional Experiments
Further result analysis of isolated nodes. Here we show how node decoder can greatly improve the link prediction performance for isolated nodes. Figure shows the superior capability of suggesting links for isolated nodes, especially Citeseer.
Normalization trick on NORAD. We also experiment with deploying normalization trick (Ahn & Kim 2021) on our model. We add L2 normalization on the encoded features in the GCN layer. We compare the performance of adding only the normalization trick or only our ATN on the Cora and Citeseer dataset with four different ratios. We also try adding the normalization trick and our ATN to study thoir effects thoroughly. We show the performances of four variants Table 12 We can find that our ATN decoder outperforms the normalization trick on both datasets with all training ratios. The difference more obvious the sparser graph datasct Citescer. We also find that the combination of these two operations yiclds trivial improvement Cora with some training ratios and even gets worse Citeseer compared with using only one of the operations.
t-SNE visualization of baselines. Figure 5 we visualize the node embeddings learned from NORAD, KernelGCN, DGLFRM, and VGNAE on Cora and Citeseer. Compared with other baselines, we can better interpret the community structure from the node embeddings learned by our model.
Topic analysis for DGLFRM. We perform the same topic analysis on the Pubmed dataset for the bascline DGLFRM. Table 13 shows the analyzed results. As we can observe, community topics learned by NORAD more interpretable than those by DGLFRM. From learned DGLFRM, see that communities
19

---

Published in Transactions on Machine Learning Research (12/2022)
KernelGCN
Cora
Citeseer
Pubmed
DBLP
DGLFRM
Cora
Cileseer
Pubmed
DBLP
VGNAE
Cora
Citeseer
Pubmed
DBLP
NORAD
Cora
Citeseer
Pubmed
DBLP
Figure Visualization of latent node embeddings learned by four models on four datascts.
often have overlapped topics. As a comparison, community topics learned by NORAD are more coherent and representative.
Downstream tasks on learned node representation. We train classification model for the Icarned node representation see if the model has informative encoding from the data. Specifically, the classifier we adopt here is SVM with RBF kernel. The classification results reported using Accuracy (ACC). Table 14
20

---

Published in Transactions on Machine Learning Research (12/2022)
Ratio
base
w/ norm
w/ ATN
w/ both
Cora
20%
82.710061
86.211.15
86.410.58
87.9.10.49
40%
88.5#0.71
89.8+0.52
90.7+0.44
91.2+0.51
60%
91.9=+0.63
91.8++0.1
93.2+0.37
92.6+0.71
80%
94.0:10.75
93.0+1..25
95.2+1..6
93.721.14
Citeseer
20%
88.520.76
85.9+1.34
92.2+0.55
91.2+0..7
40%
91.7=0.51
90. 10.14
93.7=0.39
93.3
60%
92.8+0.58
91.6+1.07
94.5=t0.2
94.1=0.66
80%
93.910.62
92.811.09
95.6110.88
94.8.10.70
Table 12: Performance comparison of normalization trick and ATN decoder: NORAD without ATN (denoted "base"), base with normalization trick (denoted as "norm"), NORAD (denoted ATN), NORAD with normalization trick (denoted both).
Topic Label
Top Eight Stemmed Keywords
AIH
vivo, liver, releas, defect, hepat, given, content, autoimmun affect, diagnos, defect, neuropathi, sex, diagnosi, drug, predict 50, dysfunct, primari, suscept, interv, new, sex affect, triglyccrid, adjust, women, bmi, autoimmun, particip, men
DN
ED
ByG+BMI
TyG+HGB
suscept, drug, longterm, autoimmun, hemoglobin, loss, triglycerid, primari play, particip, class, triglycerid, loss, outcom nerv, neuropathi, dysfumet, content, liver, chronic, vitro, defect vivo, excret, dysfunct, analys, urinari, play, support 50, support, particip, hypothesi, intervent, drug, singl, hemoglobin affect, sex, retinopathi, loss, vivo, vitro, diagnos, defect primari, play, intervent, defect, particip, vitro, hemoglobin, drug diagnos, play, dysfunct, vivo, loss, drug, particip, shown affect, triglycerid, hepat, suscept, outcom, autoimmun, need, fatti hemoglobin, adjust, triglycerid, dysfunct, drug, protect, women, sex
TyG
DN
UTI
Clinical Practice
DR
Clinical Practice
ED
NAFLD
HGB+FSD
Table 13: Display of top eight words in fourteen learned latent topies from DGLFRM in Pubmed dataset. The topic labels are abbreviations of clinical subareas related to Diabetes Mellitus. They highly related to the top eight stemmed keywords.
shows the classification performance. We can see that SVM trained with node representation learned by NOARD achieves higher accuracy than other basclines, thus demonstrating the offectiveness of our model on downstream node classification lask.
VGAE
KernelGCN
DGLFRM
VGNAE
NORAD
Cora
65.24=0.73
78.21 #1.53
83.70 +1.85
83.7440.92
84.79+1.12
Citesoer
57.09=0.25
64.99 #2.02
69.10
74.79+1.11
74.0410.98
Pubmed
85.57=0.41
80.20 +1.37
78.53+1.59
86.36+00.46
87.91+0.29
DBLP
77.85=1.19
80.1710.66
76.83+2.47
84.10+0.39
84.8710.46
Table 14: Performance comparison of all models in the downstream classification task: We used an unpaired t-test to compare models' performance values. Not significantly worse than the best at the 5% significance level are bold.
21


Reviews:
[{"review_id": "BeFr58semT", "reviewer": "Reviewer_CC4h", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The paper is well-written. The introduction to probabilistic factor models of graphs is informative.\n2. It is nice to see someone use the vast literature on Probabilistic Matrix Factorization to propose a graph model. There is a lot there that has not been properly explored in the context of graph representation learning.\n\nWeaknesses:\n1. The implication that the spike and slab distribution creates an \"interpretable\" distribution is not grounded in a clear notion of interpretation and how humans would interact with such model. The proposed node embedding Z_i is effectively a mixture model where a point (Z_i) can belong to multiple subpopulations (communities). For two nodes that belong to the same subpopulations (communities), the link is predicted based on the inner product between the embedding vectors, which is as interpretable as other matrix factorization methods. If i and j have overlapping communities and, say, we have K=100 communities (recall $v_{ik}$ is Gaussian). I am not sure how someone looking at the output of Eq (10) and the vectors $c_i, v_i$ and $c_j,v_j$ can categorically say \"I understand exactly why the link (i,j) was predicted\".  There are a few cases where I can see why the output would be interpretable. For instance, if i and j do not share any communities or just share one community. The argument that one can interpret the model would have been stronger had $v_{ik}$ being strictly positive.\n2. One of the more puzzling parts of the model comes at Eq (13). The gnn(A,X;\\phi) seems to be equivariant, such that two isomorphic nodes on the attributed graph (A,X) will get the same node embedding average and variance. This equivariant node representations is incompatible with link prediction in symmetric graphs (as theoretically described by https://arxiv.org/abs/1910.00452). The authors need to show why the concerns in https://arxiv.org/abs/1910.00452 about equivariance node representations for link prediction are not an issue in this model.\n3. The authors need to better describe why it is OK to have an inductive model (GNN) output the mean and standard deviation of the embeddings while the community assignments and actual node embeddings (c_i) are both transductive. If the method is transductive, couldn't we also perform a transductive learning procedure with a hierarchical model (so that c_{ik} for all nodes in community k have the same prior Normal(mu_k,sigma_k))? It is unclear why we need to use the GNN.", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work proposes a Probabilistic Matrix Factorization method that uses an inductive (equivariant) GNN as a proposal distribution for the node embedding averages and variances. The method is based on Bayesian hierarchical models with spike and slab priors, so that we node embeddings are separated from the nodes' community assignments.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "Please address Weaknesses 1,2,3.", "broader_impact_concerns": "No concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "rj5b8UdejQ", "reviewer": "Reviewer_xbLj", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The model design for NORAD is technically sound.\n- The contribution of having an interpretable unsupervised node representation learning method is valuable.\n\nWeakness:\n- The datasets used in the experiments are too limited.\n- Demonstration of the usefulness of the model is missing.", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper makes a systematic analysis of VGAEs and shows that attribute decoding is important for node representation learning. The authors further propose a new learning model, NORAD, which encodes node representations in an interpretable approach.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "1 Explore more challenging datasets:\n- The link prediction tasks are too easy to solve. All the baseline models almost got perfect performance. The authors should explore more challenging datasets, for example, OGB link prediction tasks.\n2 Add experiments for more types of tasks:\n- In addition to unsupervised learning tasks, the authors should demonstrate that the learned node embeddings are helpful. A good experiment to explore is to use the fixed node embeddings from NORAD, and train simple classifiers for standard node classification tasks.", "broader_impact_concerns": "No concerns about the ethical implications of the work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "YAOTnKmX0D", "reviewer": "Reviewer_R5jC", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\nThe paper proposes reasonable modifications to a well-known architecture, studying existing solutions in the literature and comparing them under a common theoretical framework. \nAll contributions are motivated and tested appropriately through ablation studies. \nThe paper is well-written and easy to follow, all concepts needed to understand the work are explained where appropriate. \n\nOverall, I think the paper is in good shape besides some improvements that could be made to the experiments section (See below). \n\n\n# Weaknesses\n\nI only have comments related to the experiments: \n\n- It is not clear if the baselines have a number of parameters comparable to the proposed method. Does the extra performance come at a significant computational cost? If so, this should be quantified and discussed. \n\n- The experiments are conducted on very few and small datasets. The GNN community has long moved past the citation networks, so I advise the authors run their experiments on better datasets like OGB or similar. As it is, the results are unlikely to transfer to practical/non-benchmark problems. \n\n- The experiment on interpretability should also compare the interpretability of the other baselines. As it is, it is not clear if the proposed method is actually more interpretable than the baselines. ", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a set of modifications to the standard variational graph autoencoder model by Kipf and Welling, aiming to increase its performance and interpretability.\n\nThe main architectural contributions are the following: \n\n1. Add a dedicated feature decoder\n2. Change the latent prior to a sparse distribution (Bernoulli-like)\n3. Add a procedure to separately deal with disconnected nodes, aiming to improve their attribute and connectivity recovery\n4. Change the architecture and losses of the encoder and decoders to be more powerful\n\nThe authors show that the proposed architecture provides some advantages in two tasks and four datasets. The experiments also include an ablation study of the proposed architectural improvements to show that they are all beneficial. \nFinally, the authors study the interpretability of the learned node attributes to recover the semantic meaning of the communities identified by the model. They show that the computed attributes have a nice semantic clustering. ", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "## Typos\n- Page 3: \"let ... denotes the mutual information\" -> denote\n- Page 3: \"this makes the encoder has no incentive\" -> this means (?)\n\n## Miscellaneous issues\n\n- The paragraph about fixing the bias in link prediction is unclear to me. The training adjacency matrix will surely contain zeros that represent missing edges and non-edges, but this distinction is known a priori and already in the VGAE paper they used negative sampling to only sample the correct non-edges as negative samples. \nI don't understand the reasoning behind what the authors claim on page 3. ", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes an alternative approach to generate node embeddings that are more interpretable than other approaches proposed in the literature. Not all reviewers agree that the generated embeddings are (easily) interpretable, and this is true in general terms. However, the paper shows evidence that the generated embeddings are more interpretable than the ones obtained by other approaches. I think this is an interesting contribution. This improvement is mainly obtained  thanks to the adoption of a modified loss function jointly with a graph modelling exploiting a probabilistic matrix factorization approach. Both choices impose a bias whose implications have not been fully discussed in the paper, and they constitute one of the major concerns by one reviewer. Considering the nature of TMLR, whose aim is to provide a fast but in-depth revision of short manuscripts, I think the current manuscript can be accepted provided that a careful revision of the paper explicitly discussing such implications, also in relation to other relevant papers (such as the appropriately mentioned paper https://arxiv.org/abs/1910.00452), is prepared. The development of a full theory formally unveiling the family of graphs that are properly modelled by the proposed approach can be the subject of an extended version. 
Decision: Accept (poster)