Graph Convolutional Normalizing Flows for Semi-Supervised Classification and Clustering
Authors: Tianchun Wang
Farzaneh Mirzazadeh
Xiang Zhang
Jie Chen
Venue: Submitted to ICLR 2023 (2023)
Keywords: graph convolutional network
normalizing flow
generative model

Abstract: Graph neural networks (GNNs) are \emph{discriminative models} that directly model the class posterior $p(y|\mathbf{x})$ for semi-supervised classification of graph data. While being effective for prediction, as a representation learning approach, the node representations extracted from a GNN often miss useful information for effective clustering, because that is not necessary for a good classification. In this work, we replace a GNN layer by a combination of graph convolutions and normalizing flows under a Gaussian mixture representation space, which allows us to build a \emph{generative model} that models both the class conditional likelihood $p(\mathbf{x}|y)$ and the class prior $p(y)$. The resulting neural network, GC-Flow, enjoys two benefits: it not only maintains the predictive power because of the retention of graph convolutions, but also produces high-quality clusters in the representation space, due to the structuring of the representation as a mixture of Gaussians. We demonstrate these benefits on a variety of benchmark data sets. Moreover, we show that additional parameterization, such as that on the adjacency matrix used for graph convolutions, yields additional improvement in classification and clustering.


Under review as a conference paper at ICLR 2023
GRAPH CONVOLUTIONAL G FLOWS FOR SEMI-SUPERVISED CLASSIFICATION & CLUSTERING
Anonymous authors
Paper under double-blind review
ABSTRACT
Graph neural networks (GNNs) discriminative models that directly model the class posterior p(y| x) for semi-supervised classification of graph data. While be- ing effective for prediction, as representation learning approach, the node rep- resentations extracted from a GNN often miss useful information for effective clustering, because that is not necessary for good classification. In this work. we replace GNN layer by combination of graph convolutions and normalizing flows under a Gaussian mixture representation space, which allows us to build a generative model that models both the class conditional likelihood p( px((y) and the class prior p(y). The resulting neural network, GC-Flow, enjoys two benefits: it not only maintains the predictive power because of the retention of graph convo- lutions, but also produces well-separated clusters in the representation space, due the structuring of the representation strate these benefits on a variety of benchmark data sets. Moreover, we show that additional parameterization, such that on the adjacency matrix used for graph convolutions, yields additional improvement in clustering.
mixture of Gaussians. We demon-
INTRODUCTION
Semi-supervised learning Zhu 2008 refers to the learning of classification model by using typi- cally small amount of labeled data with possibly large amount of unlabeled data. The presence of the unlabeled data, together with additional assumptions (such as the manifold and smoothness assumptions), may significantly improve the accuracy of classifier learned even with few labeled data. A typical example of such model in the recent literature the graph convolutional network the graph structure (considered an exten-
(GCN) of Kipf & Welling (2017). which capitalizes sion of a discretized manifold) underlying data to achieve effective classification. GCN, together with other pioneering work on parameterized models, have formed flourishing literature of graph neural networks (GNNs), which excel at node classification (Zhou et al., 2020: Wu et al., 2021).
However, driven by the classification task, GCN and other GNNs may not produce node representa- tions with useful information for goals different from classification. For example, the representations do not cluster well in some cases. Such a phenomenon is of surprise. For instance, when one treats the penultimate activations as the data representations and uses the last dense layer as linear classifier, the representations need only be close to linearly separable for an accurate classification; they do not necessarily form well-separated clusters.
This observation leads to a natural question: can one build a representation model for graphs that not only is effective for classification but also unravels the inherent structure of data for clustering? The answer is affirmative. One idea is to, rather than construct a discriminative model p(y x) as all GNNs do, build a generative model p(xly)p(v) whose class conditional likelihood is defined by explicitly modeling the representation space, for example by using a mixture of well-separated unimodal distributions. Indeed, the recently proposed FlowGMM model (Izmailov et al. (020)) uses a normalizing flow to map the distribution of input features to a Gaussian mixture, resulting in well- structured clusters. This model, however, is not designed for graphs and it underperforms GNNs that leverage the graph structure for classification.
In this work, present graph convolutional normalizing flows (GC-Flows), generative model that not only classifies well, but also yields node representations that capture the inherent struc- ture of data, result forming high-quality clusters. We can relate GC-Flows to both GCNs and

---

Under review as a conference paper at ICLR 2023
(a) FlowGMM Silhouette = 0.725, F1 = 0.518
(b) GCN
(c) GC-Flow (this work) Silhouctte = 0.733, F1 = 0.817
Silhouctte = 0.341, F1 = 0.808
Figure I: Representation space of the data set Cora under different models, visualized by t-SNE. Coloring indicates groud-truth labeling. Silhouette coefficients measure cluster separation. Micro- F1 scores measure classification accuracy.
FlowGMMs. On the one hand, GC-Flows incorporate each GCN layer with invertible flow. Such a flow parameterization allows training a model through maximizing the likelihood of data repre- sentations being Gaussian mixture, mitigating the poor clustering effect of GCNs. On the other hand, GC-Flows augment a usual normalizing flow model (such as FlowGMM) that is trained on independent data, with one that incorporates graph convolutions as inductive bias in the param- eterization, boosting the classification accuracy. In Figure [ we visualize for graph data set the nodes in the representation space using t-SNE. suggests that GC-Flow inherits the clustering effect of FlowGMM while being similarly accurate to GCN for classification.
few key characteristics of GC-Flows are follows:
1. A GC-Flow is GNN, because being applied to graph data, it computes node representations by using the graph structure. contrast, a FlowGMM is not a GNN.
GC-Flow a generative model, admitting FlowGMMs as a special case when graph absent.
3. As generative model, the training loss function of GC-Flows involves both labeled and unla- beled data, similar to FlowGMMs, while that of GNNs involves only the labeled data.
Significance. While classification is the dominant node-level task that concerns the current litera- ture on GNNs, the importance of clustering in capturing the inherent structure of data is undeniable. This work addresses a weakness of the current GNN literature caanttur-pprticullaryy the separation of clus- ters. A Gaussian mixture representation space properly reflects this goal. The normalizing flow is vehicle to parameterize the feature transformation, so that it encourages the formation of separated Gaussians. is a generative model that return data densities. The likelihood training is organi- cally tied to a generative model, whereas existing methods based on clustering or contrastive losses externally encourage the GNN to produce clustered representations, without a notation of densities.
RELATED WORK
Graph neural networks (GNNs) are machineries to produce node-level and graph-level representa- tions, given graph-structured data as input (Zhou et al. 2020 Wu et al.) 2021). A popular class of GNNs are message passing neural networks (MPNNs) (Gilmer et al., (017). which treat informa- tion from the neighborhood of a node as messages and recursively update the node representation through aggregating the neighborhood messages and combing the result with the past node repre- sentation. Many popularly used GNNs can be considered form of MPNNs, such as GG-NN (Li
al. 2016), GCN (Kipf Welling 2017), GraphSAGE (Hamilton et al. 2017). GAT (Veličković
al.
2018 and GIN (Xu et al. 2019).
Normalizing flows are invertible neural networks that can transform a data distribution to a typically simple one, such as the normal distribution (Rezende & Mohamed, 2015 Kobyzev al.) 2021 PPapamakarios et al. 2021). Because invertibility, one may navigate the input and output distri- butions for purposes such as estimating densities and sampling new data. The densities of the two distributions are related by the change-of-variee -orvariable formula, which involves the Jacobian determinant of the flow. Computing the Jacobian determinant is costly in general; thus, many proposed neural
2

---

Under review as a conference paper at ICLR 2023
networks exploit constrained structures, such the triangular pattern of the Jacobian, to reduce the computational cost. Notable examples include NICE (Dinh et al. 2015), IAF (Kingma et al. 2016),
MAF (Papamakarios et al.] 2017), RealNVP (Dinh al.; 2017). Glow (Kingma & Dhariwal 2018
and NSF (Durkan et al. 2019). While these network mappings are composed of discrete steps, an- other class of normalizing flows with continuous mappings have also been developed, which use parameterized versions of differential equations (Chen et al., 2018b Grathwohl et al. 2019).
Normalizing flows can be used for processing or creating graph-structured data in different ways. For example, GraphNVP (Madhawa et al. 2019) and GraphAF (Shi et al.) 2020) are graph gen- one-shot
erative models that use normalizing flows generate graph and its node features and sequential manner, respectively. GANF (Dai & Chen (022) uses an acyclic directed graph to factorize the otherwise intractable joint distribution of time series data and uses the estimated data density to detect anomalies. GNF (Liu et al. 2019) is both graph generative model and graph neural network. For the latter functionality, GNF is relevant to our model, but its purpose is to clas- sify rather than to cluster, thus missing the representation-space modeling and a training objective suitable for clustering. Furthermore, the architecture of GNF differs from ours in the role the graph plays. For method, the graph adjacency matrix is part of the flow mapping, hence provoking a determinant calculation with respect to the matrix; whereas for GNF, the graph is used in the parameterization of affine coupling layer and it incurs determinant calculation. CGF (Deng) et al. (2199) extends the continuous version of normalizing flows to graphs, where the dynamics of the differential equation is parameterized as a message passing layer. The difference between our model and CGF inherits the general difference between discrete and continuous flows in how different parameterizations transform distributions.
Under the focus on clustering, several graph-based methods were developed based on the use of GNNs for feature extraction. For example, Fettal et al. (2022) use a combination of reconstruction and clustering losses to train the GNN; whereas Zhu et al. (222) Li et al. (022); y Jing et al. (2022) use contrastive losses. Different from ours, these methods do not model the data (or representation) space with distributions as generative methods do. We empirically compare with several contrastive methods and demonstrate that our model significantly outperforms them in cluster separation.
PRELIMINARIES
In this section, review few key concepts and familiarize the reader with notations to be used throughout the paper.
3.1 NORMALIZING FLOW
Let E RDD be D-dimensional random variable. A normalizing flow is vector-valued invertible mapping f(x): : TRD - TR that normalizes the distribution of x to some base distribution, whose density is easy to evaluate. Let such base distribution have density (2), where f(x). With the change-of-variabl formula, the density of x, p(x), can be computed as
(1) where Vf denotes the Jacobian of f. In general, such flow may be the composition of T constituent flows, all of which are invertible. In notation, we write f = fr fr-1 o ... o fi, where 1x((-11) = ( for all i, and ()) = x and (T) = z. Then, the chain rule ex- product of the Jacobian determinants of each constituent flow:
p(x) = π (f(x)) det Vf(x)),
presses the Jacobian determinant det Vf(x) I det (x(-))))
In practical uses, the Jacobian determinant of each constituent flow needs be easy to compute, so that the density p(x) in (T) can be evaluated. One example that serves such purpose the affine coupling layer of Dinh et al. (2017). For notational simplicity, we denote such a coupling layer by gxx) = y. which in effect computes
Yd+I.D= XX+1ID C cxp(s(x(aa)) + t(x
Yidd Xt:ds
where d = [D/2] and s, t IRd - DD-d are any neural networks. It is simple to see that the Jacobian is triangular matrix, whose diagonal has value 1 in the first d entries and exp(s) in the remaining D - d entries. Hence, the Jacobian determinant is simply the product of the exponential of the outputs of the s-network; that is, det Vg(x) - exp(s:).
3

---

Under review as a conference paper at ICLR 2023
3.2 GAUSSIAN MIXTURE AND FLOWGMM
Different from majority of work that take the base distribution in normalizing flow to be single Gaussian, we consider be a Gaussian mixture, because this natural probabilistic model for clustering. Using l to index mixture components (K in total), we express the base density π x(2)
T (z)) = Σ OuN(z: Es) with N(z: pa. Σx) exp(- ( ua) > (z px)) (2x) (det )/2
(2)
1/2
where 6b 2 are mixture weights that sum to unity and μud and Σg are the mean vector and the covariance matrix of the k-th component, respectively.
A broad class of semi-supervisee learning models specifies a generative process for each data point through defining p(y)))p(y). where p(y) is the prior class distribution and p(xly) is the class conditional likelihood for data. Then, by the Bayes' Theorem. the class prediction model p(y[x) is proportional p(x pyy) Among them, FlowGMM (Izmailov et al. 2020) makes use of the flow transform z = f(x) and defines p(x = k) (f(x):; ; p4: ] det Vf(x) with ply k) = Oz.
This definition is valid, because marginalizing over the class variable y. one may verify that p(x) E, p(x()((((p))))))) is consistent with the density formula ( when the base distribution follows (
3.3 GRAPH CONVOLUTIONAL NETWORK
The GCNs (Kipf & Welling 2017 are a class of parameterized neural network models that specify the probability of class y of node x. p(y| x), collectively for all nodes in a graph, without defining the data generation process as in FlowGMM, To this end, we let A E R= be the adjacency matrix of the graph, which has nodes, and let X [x1.... x,,"' E Rax be the input feature matrix, with x; being the feature vector for the i-th node. We further let P E ==* be the output probability matrix, where K is the number of classes and Pik ply k(x:). An L-llaer GCN is written
X (
o; (AX((
i = 1, I.
(3)
where == and P (L). Here, a; is an element-wise activation function, such as ReLU, for the intermediate layers i L, while σr is the row-wise softmax activation function for the final layer. The matrices W i O,..., L 1, are learnable parameters and À denotes a certain normalized version of the adjacency matrix A. The standard definition of À for undirected graph Å D AD where À A I and D diag E, A.)). but note that many other variants of A are used in practice as well (such as A D A).
4 METHOD
The proposed graph convolutional normalizing flow (GC-Flow) extends usual normalizing flow acting on data points separately to one that acts on all graph nodes collectively. Following the notations used in Section 3.3. starting with (0) X, where X is an n X D input feature matrix for all nodes in the graph, we define a GC-Flow F(X) = D + R that is composition of T
constituent flows F Fr FT-1 .... F1, where each constituent flow F, computes
X =AX(X( i= i.....,
(4)
X0
The final representation of the nodes the matrix (T).
GC- Flowloowie is normalizing flow. Similar to other normalizing flows, each constituent flow preserves the feature dimension; that is, each F, is an R= - x function. Furthermore, we let act on each row of the input argument (i) separately and identically. In other words, from the functionality perspective, F, can be equivalently replaced by some function f; RIXD - RIxD that computes x (x(()) for node j. The main difference between GC-Flow and usual flow is that the input argument of f; contains only the information of node but also that of its
4

---

Under review as a conference paper at ICLR 2023
neighbors. One may consider a usual flow to be special case of GC-Flows, when À I (e.g,, the graph contains no edges).
Moreover, GC-FLow is GNN. In particular, constituent flow F, of resembles GCN layer À to the flow/layer input X When A results from the normalization defined by GCN, such graph convolution approximates a low- pass filter (Kipf & Welling) 2017). In a sense, the GC-Flow architecture is more general than GCN architecture, because one may interpret the dense layer (represented by the parameter matrix W 1) followed by a nonlinear activation oi (3) as an example of the constituent flow F; in However, such conceptual connection needs few adjustments to make a GC-Flow and a GCN mathematically equivalent, because W in GCN is not required to preserve the feature dimension and o; of GCN has zero derivative on the negative axis, compromising invertibility, The nearest adjustment can be made via using the Sylvester flow (van den Berg et al., 2018), which adds a residual connection and uses an additional parameter matrix U to preserve the feature dimension ( ( + oi
of (3) by making use of graph convoluiions-muliipll
(-)()))) However, the Sylvester flow generally has limited capacity (Kobyzev al. 202T) and more sophisticated flow instead used as F;, such the affine coupling layer introduced in Section 3.1
major distinction between the GC-Flow and a usual GNN lies the training objective. To en- courage good clustering structure of the representation Z, we use maximun-likelihod kind of objective for all graph nodes, because it is equivalent to maximizing the likelihood that forms a Gaussian mixture:
max L
1-A [D:]
Σ (x.
logp(x,y=k) Duul
log lxg)(
(5)
where Dj denotes the set of labeled nodes, D. denotes the set of unlabeled nodes, and x E (0, 1) is a tunable hyperparameter balancing labeled and unlabeled information. It is useful to compare L with the usual (negative) cross-entropy loss for training GNNs. First, for training a usual GNN, no loss is incurred on the unlabeled nodes, because their likelihoods are not modeled. Second, for labeled node x with true label k, the negative cross-entropy is logp(y = k[x), while the likelihood term over labeled data in (5) is joint probability of x and y/: log y = k) log p(y k|x) + log (x). Fundamentally, GC-Flow belongs to the class of generative classification models, while GNNs belong to the class of discriminative models. Under Bayesian paradigm, the former models the class prior and the class conditional likelihood, while the latter models only the posterior.
In what follows, we will define the proposed probability model ((xly))(()) for a node x, that the loss can be computed and the label y can be predicted via argmax,, p(y = k[x). We first need an important lemma on the Jacobian determinant when graph convolution involved in the flow.
4.1 DETERMINANT LEMMA
The Jacobian determinant of each constituent flow F, defined in (4) is needed for training a GC- Flow. The Jacobian is an nD nD matrix, but it admits special block structure that allows the determinant to be computed as a product of determinants on D) matrices of size X n, after rear- rangement of the QR factorization factors of the Jacobians of f,. The following lemma summarizes this finding; the proof is given in the appendix. For notational convenience, we remove the flow index and use to denote a generic constituent flow.
Lemma 1. Let X E REXD D. and À E R=x=. Let Y = G(X), =GG(X,, where x= AX and G. R + RaxD acts each row of the input matrix independently and identically. Let g: R + R be functionally equivalent to G; that is, yi (xx)) where y; and x; are the i-th row Y and X, respectively. Then, |det ddY
det A " det Vg(x,)).
xx
Putting back the flow index, the above lemma suggests that, by the chain rule, the Jacobian determi- nant of the entire GC-Flow F is
T IIII det (E
det VF(X) = det A TD
(6)
==
For notational convenience and consistency with the GNN literature, here we omit the often-used bias term.
5

---

Under review as a conference paper at ICLR 2023
Note that to maintain invertibility of the flow, the matrix A must be nonsingular. We will define the probability model for GC-Flow based on equality 66
4.2 PROBABILITY MODEL
Different from a usual normalizing flow, where the representation z; for the i-th data point depends on its input feature vector Xg, in GC-Flow, z, depends on (a possibly substantial portion of) the entire node set X. because of the A-multiplication. To this end, we use p(X) and π (Z) to denote the joint distribution the node feature vectors and that of the representations, respectively. We still have, by the change-of-variin variable formula,
(X) (2) det VF(X)),
where the Jacobian determinant has been derived convenience, we opt to let (Z) be expressed т T(Z) [2) (Z2)) .Z.)). where each <(z,) is an independent and identically distributed Gaussian mixture (2). Similarly, we assume the nodes to be independent to start with; that is, p(X) p(x1) (x²2) p(...)
Under the freedom of modeling and for
For generative modeling. a task is to model the class prior p(y) and the class conditional likelihood p(x y), such that the posterior prediction model p(y|x) can be easily obtained proportional to p(x pyy), by Bayes' Theorem. To this end, we define
p(x; b. k) (2z;; M4, Ex]l det A/TD/n I1 det Vf, (x((0) and p(u:
k) ox- (8)
Such definition is self consisensit First, marginalizing over the label ys and using the Gaussian mixture definition (2 for (z,). we obtain the marginal likelihood
pxx;) = π (2:)) det A/DD/" IT det (T
Then, by the modeling of (Z) and p(X), taking the product for all nodes and using the Jacobian determinant formula derived in (6), we exactly recover the density formula 7 We will use and (9 to compute the labeled part and the unlabeled part of the loss ()), respectively.
The modeling of T (Z) product of <(z,)' reflects independence. which may seem conceptually at odds with graph convolutions, where node's representation depends on the information of nodes in it's T-hop neighborhood. However, nothing prevents the convolution results to be independent, just like the case that usual normalizing flow can decorrelate the input features and make each transformed feature independent, when postulating standard normal distribution output. the aim of the independence of the z 's that enables finding the most probable GC-Flow.
4.3 TRAINING AND COSTS
Despite inheriting the generative characteristics of FlowGMMs (including the training loss), GC- Flows are by nature a GNN, because the graph convolution operation (A mulliplicaaiin) involves a node's neighbor set when computing the output of a constituent flow for this node. Due to space limitation, we discuss the complication of training and inference owing to neighborhood explosion in Appendix C these discussions share great similarities with the GNN case. Additionally, we compare the full-batch training costs of GC-Flow and GCN in Appendix D which suggests that they are comparable and admit the same scaling behavior.
4.4 IMPROVING PERFORMANCE THROUGH PARAMETERIZING Ā
So far, we have treated À as the normalization of the graph adjacency matrix A defined by GCN (see Section 3.3 One convenience of doing so is that det A is constant and can be safely omitted in the loss calculation. One may improve the quality of GC-Flow through introducing parameterizations to A. One approach, which we call GC- GC-Flow-p, is to parameterize the edge weights. This approach is similar to GAT (Veličković et al. 2018) that uses attention weights to redefine A. Another approach, which we call GC-Flow-l, is to learn A in its entirety without resorting to the (possibly unknown) graph structure. For this purpose, several approaches have been developed; see, e.g., |Fanceschi et al. 2019); Wu et al. (2020); (Shang al. (202T); Fatemi al. (202T); Dai & Chen (2022)

---

Under review as a conference paper at ICLR 2023
Table 1: Comparison of GMM-based generative models, GNN-based discriminative models, and GC-Flow for -umi-supeeiseed classification and clustering. Standard deviations are obtained by repeating model training ten times. For each data set and metric, the two best cases are boldfaced.
Cora
Citeseer
Pubmed
Silhouette
Micro-F1
Silhouette
Micro-F1
Silhouette
Micro-FI
FlowGMM
0.739 + 0.015
0.504 + 0.021
0.609 + 0.034
0.512 + 0.044
0.653 + 0.031
0.734 + 0.014
GMM on X
0.162 + 0.000
0.163 + 0.000
0.071 + 0.000
0.085 + 0.000
0.062 + 0.000
0.581 + 0.000
GMM on Ax
0.144 + 0.000
0.173 + 0.000
0.089 + 0.000
0.182 + 0.000
0.183 + 0.000
0,411 + 0.000
GCN
0.340 = 0.003
0.813 = 0.007
0.314 + 0.016
0.700 = 0.025
0,453 = 0.006
0.791 0.004
GraphSAGE
0.346 + 0.004
0,801 + 0.005
0.278 + 0.007
0.697 = 0.007
0.440 = 0.018
0.769 + 0.011
GAT
0.383 + 0.003
0.825 + 0.005
0.304 + 0.003
0.702 + 0.007
0.435 + 0.010
0.774 + 0.005
GC-Flow
0.734 + 0.006
0.815 = 0.011
0.538 + 0.022
0.714 = 0.011
0.669 = 0.021
0.791 = 0.009
Computers
Photo
Wiki-CS
Silhouette
Micro-F1
Silhouette
Micro-F1
Silhouette
Micro-Fl
MM
0.540 + 0.024
0.614 + 0.026
0.704 0.027
0.599 + 0.089
0.677 + 0.011
0.671 + 0.011
GMM on X
-0,018 = 0.00
0.102 + 0.000
-0.024 + 0.00
0.120 + 0.000
0.088 + 0.000
0.124 + 0.000
GMM on Ax
-0.021 + 0.00
0.062 + 0.000
-0.041 + 0.00
0.098 + 0.000
0.026 + 0.000
0.188 0.000
GCN
0,357 = 0.026
0.812 = 0.016
0.388 + 0.003
0.891 = 0.012
0.264 = 0.005
0.775 + 0.005
GraphSAGE
0.434 + 0.030
0.761 + 0.024
0.386 + 0.007
0.839 + 0.020
0.233 + 0.009
0.771 + 0.003
GAT
0.431 + 0.015
0.814 0.023
0.425 + 0.020
0.900 + 0.009
0.278 + 0.008
0.773 + 0.003
GC-Flow
0.487 + 0.012
0.847 + 0.007
0.655 1 0.013
0.917 + 0.004
0.717 1 0.010
0.775 1 0.002
In a later experiment, we will give examples for GC-Flow-p and GC-Flow-I (see Appendix B for details) and investigate the performance improvement over GC-Flow. Note that the parameterization may lead to different À for each constituent flow. Hence, we add the flow index (1) to A and rewrite
the Jacobian determinant (6 as det VF(X) = IT]= (I 1 II det Vf, (x)(((()))) The probability models ( and
9 are correspondingly rewritten, respectively, as
p(x,/y/ ly:
kt) == Niz pax. Ex) 1[,=1 det P/) det (E(()(") | and p(u: k) Φk.
p(x,) = ग (2,) 17 det p det Vf, (x) )1
These two formulas are used to substitute the labeled and unlabeled parts of the loss 5 respectively.
5 EXPERIMENTS
In this section, we conduct a comprehensive set of experiments to evaluate the performance of GC- Flow graph data and demonstrate that it is competitive with GNNs for classification, while being advantagcous in learning representations that extract the clustering structure of the data.
Data sets. We use six benchmark node-classification data sets, Data sets Cora, Citeseer, and Pubmed are citation graphs, where each node is a document and each edge represents the cita- tion relation between two documents. We follow the predefined splits in Kipf & Welling (2017). Data sets Computers and Photo are subgraphs of the Amazon co-purchase graph (McAuley et al.) 2015). They do not have a predefined split. We randomly sample 200/1 100//000/0000 nodes for train- ing/ hng/valiiation/eesting for Computers and 80/620/1000 for Photo. The data set Wiki-CS is a web graph where nodes are Wikipedia articles and edges are hyperlinks (Meryye Cangea 2020). We use one of the predefined splits. For statistics of the data sets, see Table in Appendix
Baselines. We compare GC-Flow with both discriminative and generative models. For discrimina- tive models, we use three widely used GNNs: GCN, GraphSAGE, and GAT. For generative models, besides FlowGMM, we use the basic Gaussian mixture model (GMM). GMM not parameterized; it takes either the node features X or the traph-transformed features X = Ax as input.
Metrics. For measuring classification quality, we use the standard micro-averaged Fl score. For evaluating clustering, we mainly use the silhouette coefficient. This metric does not require ground- truth cluster labels and it measures the separation of clusters. Better separation indicates a more interpretable structure. We additionally use NMI (normalized mutual information) and ARI (ad- justed rand index) to measure clustering quality with known ground truths.
7

---

Under review as a conference paper at ICLR 2023
(a) FlowGMM
(b) GCN
(c) GC-Flow
Figure 2: Representation space of the data set Pubmed under different models.
Implementation details and hyperparameter information may be found in Appendix
Classification and clustering performance. Table lists the Fl scores and the silhouette coeffi- cients for all data sets and all compared models. GNNs are always better than GMMs for classifica- tion; while the flow version of GMM, FlowGMM, beats all GNNs on cluster separation. Our model, GC-Flow, is competitive with the better of the two and is always the best or the second best. When being the best, some of the improvements are rather substantial, such as the score for Computers and the silhouette coefficient for Wiki-CS, It is interesting to note that the basic GMMs perform rather poorly. This phenomenon is not surprising, because without any neural network parameteri- zation, they cannot compete with other models that allow feature transformations to encourage class separation or cluster separation.
To further illustrate the clustering quality of GC-Flow, we compare with several contrastive-based methods that produce competi- tive clusterings: DGI (Veličković et al. 2019), GRACE (Zhu et al.
Clustering performance of various GNN methods. The two best cases are boldfaced. Data set: Cora.
Table 2:
NMI
ARI
Silhouette
DGI GRACE GCA GraphCL
0.592 0.001
0.570 + 0.002
0.330 + 0.0X)
0.475
0.028
0.394 1 0.047
0.153 0.011
0.418
0.053
0.259 1 0.058
0.301 1 0.005
2020 GCA Zhu et al.) 2021).
0.577 1 0.002
0.482 1 0.003
0.297 1 0.002
GraphCL Yoou et al. (0200) and Khasahmadi 2020). Table 2 lists the results for Cora and Table 5 in Appendix Fincludes more data sets. For Cora, GC-Flow delivers the best per- formance all metries, with silhouette score more than double of the second best. Compared with NMI and ARI, silhouette is a metric that takes no knowledge of the ground truth but measures solely the cluster separation in space. This result suggests that the clusters obtained from GC-Flow are more structurally separated, albeit improving less the cluster agreement.
MVGRL
0.612 0.026
0.576 + 0.062
0.369 = 0.013
MVGRL (Hassani
GC-Flow
0.621 0.013
0.631 + 0.008
0.734 0.006
Training behavior. Figure 5 (see Appendix FD plots the convergence behavior of the training loss for FlowGMM, GCN, and GC-Flow. All methods converge favorably, with GCN reaching the plateau earlier, while FlowGMM and GC-Flow converge a rather similar speed.
Visualization of the representation space. To complement the numerical metrics, we visualize the representation space of FlowGMM, GCN, and GC-Flow by using a t-SNE plot (Van der Maaten & Hinton 2008), for qualitative evaluation. The representations for FlowGMM and GC-Flow are the 2, "ss while those for GCN extracted from the penultimate activations. The results for Cora given earlier in Figure we additionally give the results for Pubmed in Figure 2 From both figures, one sees that similar to FlowGMM. GC-Flow exhibits a better clustering structure than does GCN, which produces little separation for the data. More visualizations are provided in Appendix
Analysis on depth. Figure plots the performance FlowGMM, GCN, and GC-Flow as the num- ber of layers/flows increases. One sees that the classification performance of GCN deteriorates with more layers, in agreement with the well-known oversmoothing phenomenon (Li et al. 2018), while the clustering performance is generally stable. On the other hand, the classification performance of FlowGMM and GC-Flow does not show a unique pattern: for Cora, it degrades, while for Pubmed, it stabilizes. The clustering performance of FlowGMM and GC-Flow generally degrades, except for the curious case of GC-Flow on Cora. where the silhouette coefficient shows a V-shape. Neverthe- less, generally smaller depth is preferred for all models.
8

---

Under review as a conference paper at ICLR 2023
03
2
0.44
CChor Mape7)
92-
(08
FavdhNoki (9)
Heddle Poori])
04
cox Meurit)
4
20
12
24
5
25
16
25
30
20
24
25
32
(a) Cora
(b) Pubmed
(a) Cora
Figure 3: Performance variation with respect to the network Figure 4: Performance variation with respect to the labeling rate.
depth/number of flows.
Table 3: Effect of modeling A. Boldfaced numbers indicate improvement over GC-Flow.
Pubmed
Computers
Photo
Silhouette
Micro-F1
Silhouctte
Micro-F1
Silhouctte
Micro-F1
GC-Flow
0.669 0.021
0.791 + 0.009
0,487 0.012
0.847
0.007
0.655 1 0.013
0,917
0.004
GC-Flow-p
0.804 1 0.010
0.790 1 0.007
0.706 1 0.019
0.841 1 0.006
0.874 1 0.011
0.914 1 0.008
GC-Flow-1
0.856 1 0.029
0.783 1 0.009
0.582 1 0.020
0.851 + 0.009
0.842 1 0.006
0.911 + 0.005
Analysis on labeling rate. Figure the performance of FlowGMM, GCN, and GC-Flow the number of training labels per class increases. One sees that for all models, the performance generally improves with more labeled data. The improvement is more steady and noticeable for classification, while being less significant for clustering. Additionally, GC-Flow classifies significantly better than does GCN at the low-labeling rate regime, achieving 10.04% relative improvement in the F1 score when there are only two labeled nodes per class.
Improving performance with additional parameterization. We experiment with two variants of GC-Flow by introducing parameterizations to A. The variant GC-Flow-p uses an idea similar to GAT, through embedding flow inputs and computing an additive attention on the graph edges to redefine their weights. Another variant GC-Flow- also computes weights, but rather than using them
to define A, it treats each weight as a probability of edge presence and samples the corresponding Bernoulli distribution to obtain a binary sample A. The details are given in Appendix B
Table 3 lists the performance of GC-Flow-p and GC-Flow-l on three selected data sets, where the improvement over GC-Flow is notable. The improvement predominantly appears for clustering, with the most striking increase from 0.487 706.. The increase of silhouette coefficients generally come with a marginal decrease in the F1 score, but the decrement amount is below the standard deviation. one occasion (Computers), the Fl score even increases, despite also being marginal.
6 CONCLUSIONS
We have developed generative GNN model which, rather than directly computing the class pos- terior p(y]x), computes the class conditional likelihood p(xly) and applies the Bayes rule together with the class prior p(y) for prediction. A benefit of such a model is that one may control the rep- resentation of the data (e.g., a clustering structure) through modeling the representation distribution (e.g., optimizing it toward mixture of well-separated unimodal distributions). We achieve so by designing the GNN as a normalizing flow that additionally incorporates graph convolutions. Inter- estingly, the graph adjacency matrix appears in the density computation of the normalizing flow as a stand-alone term, which could be ignored if is a constant, or casily optimized if it is parameterized. We demonstrate that the proposed model not only maintains the predictive power of the past GNNs, but also produces high-quality clusters in the representation space.
REFERENCES
Jie Chen, Tengfei Ma, and Cao Xiao. FastGCN: Fast learning with graph convolutional networks via importance sampling. In ICLR, 2018a.

---

Under review as a conference paper at ICLR 2023
Ricky T. Q. Chen, Yulia Rubanova, Jesse Bettencourt, and David Duvenaud. Neural ordinary dif- ferential equations. In NeurIPS, 2018b.
Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh. Cluster-GCN: An efficient algorithm for training deep and large graph convolutional networks. In KDD, 2019.
Enyan Dai and Jie Chen. Graph-augmented normalizing flows for anomaly detection of multiple time series. In ICLR, 2022.
Zhiwei Deng. Megha Nawhal, Lili Meng, and Greg Mori. Continuous graph flow. Preprint arXiv:1908.0244 09..0008,4,, 2019.
Laurent Dinh, David Krueger, and Yoshua Bengio. NICE: Non-linear independent components estimation. In ICLR Workshop, 2015.
Laurent Dinh, Jascha Sohl-Dickstein, and Samy Bengio. Density estimation using real NVP. In ICLR, 2017.
Conor Durkan, Artur Bekasov, lain Murray, and George Papamakarios. Neural spline flows, In NeurlPS, 2019.
Bahare Fatemi, Layla El Asri, and Seyed Mehran Kazemi. SLAPS: Self-supervision improves structure learning for graph neural networks. In NeurIPS, 2021.
Chakib Fettal, Lazhar Labiod, and Mohamed Nadif. Efficient graph convolution for joint node representation learning and clustering, WSDM, 2022.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. RLGM@ @CLR, 2019.
Luca Franceschi, Mathias Niepert, Massimiliano Pontil, and Xiao He. Learning discrete structures for graph neural networks. In 2019.
Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In ICML, 2017.
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In AISTATS, pp. 249-256, 2010.
Will Grathwohl, Ricky Q. Chen, Jesse Bettencourt, Ilya Sutskever, and David Duvenaud. FFJORD: Free-form continuous dynamics for scalable reversible generative models. In ICLR, 2019.
William I.. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. NIPS, 2017.
Kaveh Hassani and Amir Hosein Khasahmadi. Contrastive multi-view representation learning on graphs. ICML, 2020.
Pavel Izmailov, Polina Kirichenko, Mare Finzi, and Andrew Gordon Wilson. Semi-supervised learn- ing with normalizing flows. ICML., 2020.
Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterizztioo with gumbel-softtax. Preprint 4xxiv:1611.01144, 2016.
Baoyu Jing, Shengyu Feng, Yuejia Xiang, Xi Chen, Yu Chen, and Hanghang Tong. X-GOAL:
Multiplex heterogeneous graph prototypical contrastive learning. CIKM, 2022.
Tim Kaler, Nickolas Stathas, Anne Ouyang, Alexandros-Stavros Iliopoulos, Tao B. Schardl, Charles F. Leiserson, and Jie Chen. Accelerating training and inference of graph neural networks with fast sampling and pipelining. In MLSys, 2022.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In ICLR, 2015.
10

---

Under review as a conference paper at ICLR 2023
Diederik P. Kingma and Prafulla Dhariwal. Glow: Generative flow with invertible 1xl convolutions. In NeurlPS, 2018.
Diederik P. Kingma, Tim Salimans, Rafal Jozefowicz, Xi Chen, Ilya Sutskever, and Max Welling. Improving variational inference with inverse autoregressive flow. NeurIPS, 2016.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. ICLR, 2017.
Ivan Kobyzev, Simon J.D. Prince, and Marcus A. Brubaker. Normalizing flows: An introduction and review of current methods. IEEE Transactions on Pattern Analysis and Machine Intelligence, 43(11):3964-39) 3979, 2021.
Bolian Li, Baoyu Jing, and Hanghang Tong. Graph communal contrastive learning. In WWW, 2022.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In AAAI, 2018.
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. In ICLR, 2016.
Jenny Liu, Aviral Kumar, Jimmy Ba, Jamie Kiros, and Kevin Swersky. Graph normalizing flows. In NeurlPS, 2019.
Christos Louizos, Max Welling, and Diederik P Kingma. Learning sparse neural networks through 1.0 regularization. Preprint arXiv: 1712.01371 2017.
Dongsheng Luo, Wei Cheng, Wenchao Yu, Bo Zong. Jingchao Ni, Haifeng Chen, and Xiang Zhang. Learning to drop: Robust graph neural network via topological denoising. In WSDM, pp. 779- 787, 2021.
Chris J Maddison, Andriy Mnih, and Yee Whye Tch. The concrete distribution: A continuous relaxation of discrete random variables. Preprint arXiv:1611.00712. 2016.
Kaushalya Madhawa, Katushiko Ishiguro, Kosuke Nakago, and Motoki Abe. GraphNVP: An in- vertible flow model for generating molecular graphs. Preprint arXiv:1905. 11600, 2019.
Julian McAuley, Christopher Targett, Qinfeng Shi, and Anton Van Den Hengel. Image-based rec- ommendations on styles and substitutes. In SIGIR, pp. 43-52, 2015.
Péter Mernyei and Cătälina Cangea. Wiki-es: A wikipedia-based benchmark for graph neural net- works. Preprint arXhv:2007.02901, 2020.
George Papamakarios, Theo Pavlakou, and Iain Murray. Masked autoregressive flow for density estimation. In NIPS, 2017.
George Papamakarios, Eric Nalisnick. Danilo Jimenez Rezende, Shakir Mohamed, and Balaji Lak- shminarayanan. Normalizing flows for probabilistic modeling and inference. Journal of Machine Learning Research, 22(57): 2021.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury. Gregory Chanan, Trevor Killeen, Zeming Lin. Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high- performance deep learning library. NewrIPS, 32, 2019.
Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al. Scikit-leam: Machine learning python. Journal of Machine Learning Research, 12:2825-2830. 201
Danilo Rezende and Shakir Mohamed. Variational inference with normalizing flows. In JCML., 2015.
Chao Shang, Jie Chen, and Jinbo Bi. Discrete graph structure learning for forecasting multiple time series. In ICLR, 2021.

---

Under review as a conference paper at ICLR 2023
Chence Shi, Minkai Xu, Zhaocheng Zhu, Weinan Zhang, Ming Zhang, and Jian Tang. GraphAF: flow-based autoregressive model for molecular graph generation. In ICLR, 2020.
Rianne van den Berg, Leonard Hasenclever, Jakub M. Tomczak, and Max Welling, Sylvester nor- malizing flows for variational inference. In UAI, 2018
Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of Machine Learning Research, 9(11), 2008.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Liò, and Yoshua Bengio. Graph attention networks. In ICLR, 2018.
Petar Veličković, William Fedus, William L. Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. In ICLR, 2019.
Zonghan Wu, Shirui Pan, Guodong Long, Jing Jiang, Xiaojun Chang, and Chengqi Zhang, Con- necting the dots: Multivariate time series forecasting with graph neural networks. In KDD, 2020.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 32(1):4 (014):4422 24, 2021.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks? In ICLR, 2019.
Rex Ying. Ruining He. Kaifeng Chen, Pong Eksombatchai, William L. Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. KDD, 2018.
Yuming You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. In NeurIPS, 2020.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graph- SAINT: Graph sampling based inductive learning method. In ICLR, 2020.
Jie Zhou, Ganqu Cui, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: A review of methods and applications. Al Open, 1: 57-81, 2020.
Xiaojin Zhu Semi-supervised learning literature survey, Technical Report TR1530, University of Wisconsin-Madison 2008.
Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Deep graph contrastive representation learning. Preprint M.Xiv:2006.04131, 2020.
Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Graph contrastive learning with adaptive augmentation. WWW, 2021.
Difan Zou, Ziniu Hu, Yewen Wang, Song Jiang, Yizhou Sun, and Quanquan Gu. Layer-dependent importance sampling for training deep and large graph convolutional networks. In NeurIPS, 2019.
12

---

Under review as a conference paper at ICLR 2023
A
PROOF OF LEMMA I
The Jacobian dY ax
di an nD x nD matrix. By the chain rule, an entry of it is where J == (g(x;) E DxD Hence, aX can expressed as the following block matrix (up to permutation and transpose that do not affect the absolute value of the determinant):
Aspji jq
XX
AnJJ
A
A in
A2
Az2J²
Azn2²
J
A
AnnJ
Since any matrix admits a QR factorization, let Q'R' for all i, where Q' is unitary and R upper-triangular. Then, the above block matrix is equal
A
RIRR R
R
Q2
R
R
R R
Q"
R
RnnR" R"
Because left block matrix is unitary, it does not change the determinant. Hence, we only need to compute the determinant of the right block matrix. We may rearrange this matrix into the following form, while maintaining the absolute value of the determinant:
A +
Su
A
S12
À @ S
R
R
R R
S
À
S
À o S
R
R
where
S
ij
for all i, pairs
A AOST
S
A
LOST Sm2
À Sma
R
R
R
Because each R is upper-triangular, the matrix 8 is zero whenever i > j. Therefore, the block matrix above is block upper- trianglar and absolute determinant equal
D II det A @ ) ==1
Note that S is a matrix with identical rows, for each i. Then, by definition of determinant (see the Leibniz formula), det A @ Stt) = -eet(A) A) R R ... R Therefore,
det A @ Sz) det A D. R R
R R R2
R
RDDD ...D.l
det A D det J
det I det J
which concludes the proof.
B PARAMETERIZATIONS OF Ā
With parameterization, A may differ in the constituent flows. Hence, we use the flow index j to distinguish them; i.e., Á ()) Let graph be denoted by G = (V,&), where V is the node set and is the edge set.
B. GC-FLOW-P VARIANT
The GC-Flow-p variant parameterizes A by using an idea similar to GAT (Veličković et al. 2018 where an existing edge ki. E E is reweighted by using attention scores. Let E, Eg : R + R be two embedding networks that map a D D-dimensional flow input to d-dimensional vector, and let M 2d - I be a ferw-forward network. compute two sets of vectors
h ( ReLU (E((x(-1))
(G-1) ReLU (x((((i1))
13

---

Under review as a conference paper at ICLR 2023
and concatenate them compute a pre-attention coefficient dik for all (i, &: ())
5 lk
MMn (1) 118 ( 1)
=
Then, constructing a matrix ( where
LoakyRoLL(a
if((, E otherwise,
x0
we define ( through row-wise softmax:
(i) softmax((()))
This parameterization differs from GAT mainly in using more complex embedding networks E, and Eg than single feed-forward layer to compute the vectors h b(d-1) and 8k (i-1) Moreover, we do not use multiple heads.
B.2 GC-FLOW-L VARIANT
The GC-Flow-l variant learns new graph structure. For computational efficiency, the learning of the structure is based on the given edge set E that is, only edges are removed from & but no edges inserted outside E. The method follows Luo et al. (202I). which hypothesizes that the existing edge set is noisy and aims at removing the noisy edges.
The basic idea uses prior work on differentiable sampling (Maddison et al. 2016 Jang et al. 2016), which states that the random variable
e <=o((ooge- log (1 + ( (T)
where ~ Uniform (0.
(10)
follows a distribution that converges to a Bernoulli distribution with success probability p + e=")-1 > 0 tends to zero. Hence, we if parameterize w and specify that the presence of an edge between a pair of nodes has probability p, then using e computed from (TO) to fill the corresponding entry of A will produce matrix A that close to binary. We can use this matrix in GC-Flow, with the hope of improving classfiicatonn/llusternng performance due the ability of denoising edges. Moreover, because (10) differentiable with respect to w, we can train the parameters of w like in usual gradient-based training.
To this end, we let E,, E2 R + Rd be two embedding networks that embed the pairwise flow inputs
a (1) bk
tanh
Ej (x
tanh
Eg (x(x1)
((,
b L
tanh
Eg x
tanh Ej (xx
(ii E
( (7) where a ik
E Rdd and o is the Hadamard product. Then, we take their difference and compute
( with = tanh (1" (a - b(())
followed by
2 5k - -0
log (1- (1 w0( -((2))/)
where c~ Uniform (0. ().
which returns approximate Bernoulli sample for the edge ki, When 7 is sufficiently close to zero, this sample may not be close enough to binary, and in particular, it is strictly nonzero. To explicitly zero out an edge, we follow Louizos al. (2017) and introduce two parameters, 7
and & 1, to remove small values of e
A A min (1, max (e()) (e)200) where
c =
eli 7) 7
= 0), but This definition ()) does not insert new edges to the graph (i.c., when (i, $ E, A0) ik only removes (denoises) some edges (i, kt) originally in E.
14

---

Under review as a conference paper at ICLR 2023
C TRAINING AND INFERENCE
Despite inheriting the generative characteristics of FlowGMMs (including the training loss), GC- Flows are by nature a GNN, because the graph convolution operation (A (A-muliiliication involves node's neighbor set when computing the output of constituent flow for this node. Across all constituent flows, the evaluation of the loss on a single node will require the information of the entire Thhop neighborhood, causing scalability challenges for large graphs. One may perform full- batch training (the deterministic gradient decent method), which minimizes the multiple evaluations on node in any constituent flow. Such an approach is the most convenient implement in the current deep learning frameworks; typical GPU memory can afford handling a medium- scale graph and CPU memory can afford even larger graphs. If one opts to perform mini-batch training (the stochastic gradient decent method), neighborhood sampling for GNNs (e.g., node-wise (Hamilton) jet al. 2017, Ying et al. 20188) layer-wise (Chen et al. 8018a| Zou et al.) 2019), or subgraph- sampling (Chiang et al. 10199/Zngg et al. 2020h) is a popular approach to reducing the computation within the hhp neighborhood.
Inference is faced with the same challenge as training, but since it requires only single pass on the test set, doing so in full batch or by using large mini-batches may suffice. If one were to use nor- mal mini-batches with neighborhood sampling (for reasons such as being consistent with training), empirical evidence of success has been demonstrated in the GNN literature (Kaler et al.) 2022).
D COMPLEXITY ANALYSIS
Let us analyze the cost of computing the likelihood loss 5 for GC-Flows. Based on ( and ()) the cost consists of three parts: that to compute X ()) Ax for each constituent flow indexed by j. that to compute the Jacobian determinant det (x{")) for each node i, and that to compute the graph-related determinant det A. For a fixed graph, the third part is constant and is omitted in
training. The cost of the second part varies according to the type of the flow. If we use an affine-
coupling flow exemplified in Section 3.1 let the cost of the s and t networks be Cst. Then, the cost of computing the overall loss can be summarized as
((uz(A)DT DTADDT++TCC nTCCst.
(11)
where nz( A) denotes the number of nonzeros of À and recall that D and T are the feature dimension and the number of flows, respectively. An affine-coupling flow can be implemented with varying architectures. For example, for usual MLP, Cat = O hahht1), where ha [D/2]; hi... -, are hidden dimensions; and hG. = 2 [ Note that ((Cat) dominates the cost of computing a matrix determinant, which is only O(D), because the Jacobian matrix triangular in an affine-coupling flow.
It would be useful to compare the above cost with that of the cross-entropy loss for a usual GCN:
O( (z((A) EJ d, + Ef dzdz-1),
(12)
where dg D; di ... d1 are hidden dimensions; and dy K, the number of classes. Here, we assume that the GCN has T layers, comparable to GC-Flow. The two costs (TT) and (12) are comparable, part by part. For the first part, DT is comparable to Σ dj. if all the d, 's are similar. In some data sets, the input dimension of GCN is much higher than the hidden and output dimen- sions, but we correspondingly perform a dimension reduction on the input features when running GC-Flows (as is the practice in the experiments), reducing DT to D'T for some D' < D. For the second part, the number L of hidden layers in each flow typically small number (say, 5), and the hidden dimensions hj 's are comparable to the input dimension hg. rendering comparable terms TCst versus Σ d,dj+1- Overall, the computational costs of GC-Flow and GCN are similar and their scaling behaviors are the same.
worth noting that when one parameterizes A, the cost of computing A for each flow/layer j will need to be added to the loss computation, for both GC-Flows and GCNs. The cost depends on the specific parameterization and it can be either cheap or expensive. Additionally, GC-Flows require the computation of det Á G), whose cost depends on the structure of the matrix, which in turn is determined by the parameterization.
15

---

Under review as a conference paper at ICLR 2023
E
EXPERIMENT DETAILS
Data sets. Table summarizes the statistics of the benchmark data sets used in this paper.
Table 4: Data set statistics.
Data set
# Nodes
Edges
# Features
# Classes
Traiin/alltest
Cora
2,708
5,429
1,433
7
140 500 1,000
Citeseer
3,327
4,732
3,703
120 500 1,000
Pubmed
19,717
44.338
500
3
60 500 1,000
Computers
13,381
245,778
767
10
200 1,300 / 1,000
Photo 7,487
119,043
745
8
80 620 1,000
Wiki-CS 11,701
216,123
300
10
580 / 1,769 5,847
Computing environment. We implemented all models using PyTorch (Paszke et al., 2019), Py- Torch Geometric (Fey & Lenssen] 2019), and Scikit-learn (Pedregosa al. 20111. All data sets used the experiments are obtained from PyTorch Geometrie. We conduct the experiments on server with four NVIDIA RTX A6000 GPUs (48GB memory each).
Implementation details. For fair comparison, we run all models on the entire data set under the transductive semi-supervised setting. All models are initialized with Glorot initialization (Glorot & Bengio 2010) and are trained using the Adam optimizer (Kingma & Ba 2015). For reporting the silhouette coefficient, k-means
for 1000 epochs. For all models all data sets, the & weight decay factor is set to 5 x 10-4 and the number of training epochs is set to 400. For all the early stopping strategy the F1 score on validation set. In all experiments, we use À (D + (A + I), where D diag(E, Aiz). For FlowGMM, GC-Flow, and its variants, we clip the norm of the gradients to with the range [-50, 50). For GC-Flow-l and GC- Flow-p, since A ()) in each flow may not has a full rank, we add to A a diagonal matrix with damping value 10 Moreover, the slope in LeakyReLU is set 0.2. In all models involving normalizing flows, we use RealNVP (Dinh et al. (017)) with coupling layers implemented by using MLPs. Following Izmailov et al. (2020), the mean vectors are parameterized as some scalar multiple of the vector of all ones, and the covariance matrices are parameterized as some scalar multiple of the identity matrix. On the other hand, the GMM models are implemented by using Scikit-learn with full covariance matrices. The number of training epochs for GMMs is set to 200.
models,
Too large a feature dimension renders challenge on the training a normalizing flow. Hence, we perform dimension reduction in such case. For Cora, Pubmed, Computers, and Photo, we use PCA to reduce the feature dimension to 50; and for Citeseer, to 100. We keep the dimension 300 on Wiki-CS without feature reduction.
Hy pyperparameters. We use grid search to tune the hyperparameters FlowGMM, GC-Flow, and its variants. The search spaces are listed in the following:
Number of flow layers: 2, 4, 6, 8, 10, 12, 14, 16, 18, 20;
Number of dense layers in each flow: 6, 10, 14;
Hidden size of flow layers: 128, 256, 512, 1024;
Weighting parameter X: 0.01, 0.05, 0.1, 0.15, 0.2, 0.25, 0.3, 0.35, 0.4, 0.45, 0.5;
Gaussian mean and covariance scale: [0.5, 10];
Initial learning rate: 0.001, 0.002, 0.003, 0.005;
Dropout rate: 0.1, 0.2, 0.3, 0.4, 0.5, 0.6.
Additionally, for GC-Flow-p and GC-Flow-l:
Number of dense layers in E, and Eg: 4, 6;
Hidden size of dense layers in E, and Ey: 128, 256;
Embedding dimension d: 8, 16.
16

---

Under review as a conference paper at ICLR 2023
For GCN and GraphSAGE. set the hidden size to 128, dropout rate to 0.5, and learning rate to 0.01. For GAT, we follow Veličković et al. (2018) to set the hidden size to 8, the number of attention heads to 8, droupout rate to 0.6, and the learning rate 0.005.
The results in Table for GC-Flow are obtained by using different number of flows and number of layers per flow for different data sets. For Computers, Photo, and Wiki-CS, we use 4, 2, and 2 flows, respectively, with dense layers in each flow. For Cora, Citeseer and Pubmed, we use 4, 10 and 10 flows, respectively, with 10 dense layers in each flow.
The results in Table 3 also use different number of flows and layers. For GC-Flow-p, on Cora, Citeseer, Pubmed, Photo, and Wiki-CS, use 10 flows; while Computers, we flows. For GC-Flow-I, we use flows for Wiki-CS and 4 flows for the rest of the data sets, For both For GC- Flow-p and GC-Flow-I, there are 6 dense layers per flow on Wiki-CS while 10 per flow on the rest of the data sets.
F ADDITIONAL EXPERIMENT RESULTS
Clustering performance. Table 5 compares the clustering performance between GC-Flow and var- ious contrastive- based GNN methods, for Citeseer and Pubmed. GC-Flow maintains the attractively best performance on the silhouette score, which measures cluster separation. For the cluster as- signment metrics, GC-Flow remains competitive on ARI, which measures cluster similarity, while falling back on NMI, which measures cluster agreement.
Table 5:
Clustering performance of various GNN methods. The two best cases are boldfaced. Data sets: Citeseer (top) and Pubmed (bottom).
NMI
ARI
Silhouette
DGT
0.427 + 0.001
0.399 + 0.002
0.314 0.000
GRACE
0.380 + 0.017
0.378 + 0.023
0.219 + 0.014
GCA
0.336 + 0.008
0.279 = 0.005
0.251
0.015
GraphCL
0.417 0.001
0.372 1 0.002
0.299 0.001
MVGRL
0.468 + 0.002
0.445 - 0.004
0.305
0.000
GC-Flow
0.405 + 0.013
0.426 + 0.014
0,538
0.022
NMI
ART
Silhouctte
DGI
0.379 + 0.001
0.361 + 0.002
0.426 0.001
GRACE
0.305 + 0.075
0.261 + 0.111
0.149 + 0.008
GCA
0.488 + 0.016
0.511 + 0.030
0.354 = 0.014
GraphCL
0.337 1 0.001
0.308 1 0.002
0.412 0.002
MVGRL
0.391 0.001
0.361
1 0.001
0.441
0.001
GC-Flow
0.384 1 0.011
0.460 1 0.015
0.655
0.013
Training behavior. Figure plots the conver- gence of the training loss for various methods. The loss for GCN is the cross-entropy while the loss for FlowGMM and GC-Flow is the likelihood. All the curves smooth and ex- hibit reasonable decay, suggesting convergence expected. GC-Flow converges similarly to
FC-Flow
FlowGMM GCN
-15
ness-entropy
Likellhood
-10
FlowGMM, while GCN converges faster.
400
Visualization of the representation space. Figure 6 shows the t-SNE plots for data sets Citeseer, Computers, Photo, and Wiki-CS, one per row.
-80
100
300
400
# Iterations
Figure 5: Convergence of the training loss (Cora).
17

---

Under review as a conference paper at ICLR 2023
(a) FlowGMM
(b) GCN
(c) GC-Flow
(d) FlowGMM
(e) GCN
GC-Flow
FlowGMM
(h) GCN
GC-Flow
(i) FlowGMM
(k) GCN
()) GC-Flow
Figure 6: Representation space of several data sets under different models. Data from top to bottom: Citeseer, Computers, Photo, and Wiki-CS.
18


Reviews:
[{"review_id": "FB5XXdj8-P", "reviewer": "Reviewer_kEff", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper focused on learning a structured node representation on top of a GNN model. It follows the idea of FlowGMM and applies normalizing flow to the GNN model. The proposed GC-Flow model leads to significantly better clustering results and improves node classification. ", "summary_of_the_review": "This paper has good writing and is well-organized. The model proposed is very interesting to the community and demonstrates strong power in improving the clustering performance of current GNN models. But generally, I feel the authors do not have a clear definition of what kind of significant problem they want to solve, or they do not explore the benefits of their model enough. The baselines in the experiment are also too weak. I vote for the rejection by this time unless the authors could clearly tackle the weakness I mentioned before.", "strength_and_weaknesses": "Strengths:\n1. The proposed GC-Flow model is an innovative generative model on the graph data, which considers the interdependency among instances (nodes) and incorporates it into the normalizing flow model. \n2. The improvement in the clustering results is very significant, and the visualization demonstrates that GC-Flow has a more interpretable latent representation.\n\nWeakness:\n1. The main drawback of this paper lies in that it fails to identify a significant problem in the current GNN models. I admit the method proposed is interesting, but I cannot see the significance of the problem it studies. If the main purpose of adding normalizing flow is to increase the clustering performance, why do not consider adding the community partition losses/clustering losses to the supervised losses? Adding normalizing flow is not that straightforward to realize this goal.\n\n   As pointed out by FlowGMM, it does not actually increase the performance too much but treats interpretability and broad applicability as its main advantage. I think it is unnecessary to introduce normalizing flow on GNN to improve the clustering performance only. \n\n2. The baselines are too weak and graph contrastive learning methods [1,2,3] are totally missing from the baselines, which are expected to have good performance in both clustering and node classification. Both [2] and [3] have the loss to explicitly encourage clustering. \n\n[1] Graph Contrastive Learning with Adaptive Augmentation. Zhu et al., WWW 2021.\n\n[2] Graph Communal Contrastive Learning. Li et al.,  WWW 2022.\n\n[3] X-GOAL: Multiplex Heterogeneous Graph Prototypical Contrastive Learning, Jing et al., CIKM 2022.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Dd7aftFDts2", "reviewer": "Reviewer_qGKA", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper presents GC-Flow, a generative framework to generate the representation of graphs. The framework is effective for node classification and unravels the inherent structure of data for clustering. More specifically, GC-Flow takes both the advantages of normalizing flows and graph convolutions. For prediction, it computes the class conditional likelihood p(x|y) and applies the Bayes rule together with the class prior p(y). Experimental results have shown the effectiveness of various benchmarks compared with the related baselines.", "summary_of_the_review": "The paper is strong, and I recommend it for acceptance. The proposed method is simple and practical. It also provides interesting insights into normalizing flows and GNNs. However, there is still room for improvement. I kindly hope the authors consider the points highlighted in my reviews.", "strength_and_weaknesses": "Strengths:\n1. This work is quite interesting. The paper provides a new angle to understand the graph node representation from clustering by the nature of normalizing flows, which is rarely considered in GNNs. \n2. The proposed GC-Flow is simple and practical on various datasets. In addition, two variants are studied which show the flexibility of the GC-Flow framework. \n3. Extensive experiments show the effectiveness of the proposed method. Some of the experimental results are inspiring. The hyperparameter tuning in the appendix is clear and reasonable.\n4. The appendix contains solid derivations for Lemma 1, which is well organized and clear to understand.\n\nWeaknesses:\n1. In Eq.(8) and Eq.(9), the authors define the class-conditional likelihood $p(x_i|y_i=k)$ and marginal likelihood $p(x_i)$. However, the total loss function is not illustrated clearly. It is better to briefly describe a concrete formulation of the loss function for GC-Flow. \n2. There is no analysis of complexity. Scalability is important for flow-based generative models. As the paper described, GC-Flow is based on normalizing flows, and there is a need to calculate the Jacobian determinant. Considering the #train/val/test listed in Table 3, I am wondering if only a part of the samples for each data set were used for the empirical study. I suggest the authors add complexity analysis to improve this paper.\n3. Some important related works are missing. It is better for the authors to discuss some differences and connections between GC-Flow and the method [1] which also aims to model distributions of graph-structured data using normalizing flows. Besides, related works on node clustering [2] are missing.\n\n[1] Deng, Z., Nawhal, M., Meng, L., & Mori, G. (2019). Continuous graph flow. arXiv preprint arXiv:1908.02436.\n\n[2] Fettal, C., Labiod, L., & Nadif, M. (2022). Efficient Graph Convolution for Joint Node Representation Learning and Clustering. WSDM.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "4l4BSEVTbW", "reviewer": "Reviewer_bfhQ", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposed to use the combination graph convolution and normalizing flows to replace the traditional GNN layers. Comparing with the conventional normalizing flow that transform an original x into a latent z (usually Gaussian distributed), there are two main differences here. First, instead of only transforming the original data x, at each intermediate step of transformation, the model will first fuse the data from neighboring nodes and then transform the fused data using a standard NF transformation. Second, different from conventional NF that intend to eventually transform the raw data x into a Gaussian distributed representation, the proposed method transforms data into mixture Gaussian distribution, hoping to produce representations that are friendly for clustering. A set of experiments were conducted to show the proposed model could be simultaneously good at classification and clustering.", "summary_of_the_review": "The proposed method looks like a direct combination of GNN and NF, making the technical contribution here limited. To guarantee the tractability of NF, the proposed model has to abandon the transformation of feature operation XW before passing to neighbors, making the modeling ability of GNN reduced significantly. The experiments cannot support the claims or objectives, neither.", "strength_and_weaknesses": "Strength:\n1)\tThe paper is well organized.\n2)\tThe idea of combining graph convolution into normalizing flow and using Gaussian mixture distribution to encourage clustered representation learning is interesting, \n3)\tExperimental results demonstrate that the representations learned under the proposed method appear to be more clustered than the previous GNN models, in addition to maintaining classification performance.\n\n\nWeaknesses\n1)\tThe proposed method can be viewed as a direct combination of GCN and normalizing flow, with the ultimate transformed distribution, which is Gaussian in conventional NF, replaced by Gaussian mixture distribution, encouraging the latent representation to be more clustered. Technically, there is no enough new stuffs here.\n2)\tMore Seriously, to ensure the intractability of the normalizing flow after absorbing the graph neural network, the proposed model has to replace the basic operation \\sigma(AXW) with the operation \\sigma(AX) in the graph neural networks, abandon the feature affine transformation operation, i.e., XW, before passing the intermediate representations to neighboring nodes. Since the W is the main parameters to be learned in GNN, abandoning it means the representation ability of GNN is restricted significantly. The experimental results also show that the proposed model brings very little gains over the old models like GCN and GAT on classification tasks.\n3)\tWithout using the feature affine transformation AXW, then the dimension of intermediate hidden representations will always be kept the same as that of input feature since the NF have to maintain the dimension unchanged. Then, if the dimension of input feature is very high, in addition to the complexity issue, the learned feature will be also be very high, which may not be very useful as nowadays we often expect the learned features to be compact.\n4)\tFor the experiments, since the paper want to demonstrate the proposed model is able to learn clustering-friendly representations, we expect to directly see how the model performs on clustering task on the clustering performance metric, like accuracy ACC, normalized mutual information NMI etc, rather than the indirect Silhouette criteria, which is not meaningful at all.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "1Le2Yxql5H", "reviewer": "Reviewer_cUhi", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a method to replace a GNN layer by a combination of graph convolutions and normalizing flows under a Gaussian mixture representation space. The proposed method not only classifies well, but also yields node representations that capture the inherent structure of data, as a result forming high-quality clusters (i.e. cluster well).\n", "summary_of_the_review": "I am not fully on board on the motivation of this and the results section. ", "strength_and_weaknesses": "Strength: \nThe paper proposes a coherent story, etc\n\nWeakness:\n1 replace GNN layer with graph convolutions & normalizing flows will significantly add more computational burden? especially inverse of Jacobians? Will the normalizing flow harder to train due to  intermediate stage of graph functions' ill behaviour (due to graph convolution), leading to instability and divergence of the algorithm? \nHave the author consider other priors than gaussian mixture?\n\n\n2. The paper reports microF1 score in Table 1\n\nHow does the paper’s performance compare with leaderboard here\nhttps://paperswithcode.com/sota/node-classification-on-pubmed\nfor example, pubmed acc is 91+ \n\nhow does performance compare with https://arxiv.org/pdf/2109.05641v1.pdf\nhttps://arxiv.org/pdf/2012.06113.pdf (Table 3)\nseems much better than Table 1 of the paper. \nCan the author clarify? \n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject