Attributed Graph Learning with 2-D Graph Convolution
Authors: Qimai Li
Xiaotong Zhang
Han Liu
Xiao-Ming Wu
Venue:  (2020)
Keywords: 2-D Graph Convolution
Attributed Graph
Representation learning

Abstract: Graph convolutional neural networks have demonstrated promising performance in attributed graph learning, thanks to the use of graph convolution that effectively combines graph structures and node features for learning node representations. However, one intrinsic limitation of the commonly adopted 1-D graph convolution is that it only exploits graph connectivity for feature smoothing, which may lead to inferior performance on sparse and noisy real-world attributed networks. To address this problem, we propose to explore relational information among node attributes to complement node relations for representation learning. In particular, we propose to use 2-D graph convolution to jointly model the two kinds of relations and develop a computationally efficient dimensionwise separable 2-D graph convolution (DSGC). Theoretically, we show that DSGC can reduce intra-class variance of node features on both the node dimension and the attribute dimension to facilitate learning. Empirically, we demonstrate that by incorporating attribute relations, DSGC achieves significant performance gain over state-of-the-art methods on node classification and clustering on several real-world attributed networks. 


Under review as a conference paper at ICLR 2020
ATTRIBUTED GRAPH LEARNING WITH 2-D GRAPH CONVOLUTION
Anonymous authors Paper under double-blind review
ABSTRACT
Graph convolutional neural networks have demonstrated promising performance in attributed graph learning. thanks the use of graph convolution that effective- ly combines graph structures and node features for learning node representations. However, one intrinsic limitation of the commonly adopted 1-D graph convolution is that it only exploits graph connectivity for feature smoothing, which may lead to inferior performance on sparse and noisy real-world attributed networks. To address this problem, we propose explore relational information among node attributes to complement node relations for representation learning. In particular, we propose to use 2-D graph convolution to jointly model the two kinds of rela- tions and develop a computationally efficient dimensionwise separable 2-D graph convolution (DSGC). Theoretically, we show that DSGC reduce intra-class variance of node features on both the node dimension and the attribute dimension facilitate learning. Empirically, we demonstrate that by incorporating attribute relations, DSGC achieves significant performance gain over state-of-the-art meth- ods on node classification and clustering on several real-world attributed networks.
INTRODUCTION
In an attributed graph, each node is associated with feature vector, and nodes are connected by edges encoding their relations. Commonly seen attributed graphs include citation networks where each node a document represented by a bfg-of-wordd feature vector and edges are citation links, web graphs where each webpage is also represented as a vector of words and edges are hyperlinks, social networks where each user is represented by a user profile vector and edges indicate user friend- ship, and poteiin-rrotiin interaction networks where each protein is represented by list of protein signatures and edges encode interactions between proteins. Learning on attributed graphs including node classification and clustering finds many important applications in real-world networks.
Since the connectivity patterns and node contents of an attributed graph usually contain different information, it often requires joint modelling both aspects of information to achieve good learning performance. A major class methods (Yang et al. 2015] Pan et al.] 2016 Huang et al. 2017)) devoted to learning efficient node representations of attributed graph via nonnegative matrix factorization or random walk statistics and then perform downstream learning tasks with the learned representations. A number of semi-supervised classification methods (Belkin al., 2006)] Weston et al. 2008 Yang et al.) 2016) classify nodes in an attributed graph by training a supervised classifier on node Teatures with some kind of graph regularizer. Recently, a series of works based on graph convolutional neural networks including ChebyNet (Defferrard et al., 2016). graph convolutional
networks (GCN) (Kipf & Welling 2017). ). GraphSAGE (Hamilton et al. 2017) and graph attention
networks (GAT) (Velickovic et al. 2018) have been shown to achieve ofte-of-the-ane performance in node classification and clustering (Kipf & Welling 2016 Wang et al. 2017 on attributed graphs.
The key component of these models is one-dimensional (1-D) graph convolution, a function that naturally combines graph structures and node contents by aggregating a node's features with its neighbours'. As shown in (Li et al. 2019), the graph convolutional operator used in GCN and many follow-up works acts as a low-pass graph filter that smooths a node's 's features with its neighbours' Under the assumption that nearby nodes tend to be in the same class, it can produce similar feature representations for nodes in the same class, thereby making them easier to be classified or clustered. While this works well for attributed graphs with clear cluster structures, real-world networks could

---

Under review as a conference paper at ICLR 2020
be highly noisy and sparse. For example, in web graph such Wikipedia, hyperlink between two webpages does not necessarily indicate that they belong to the same category, so mixing their features could be harmful for learning. Furthermore, it has been shown that many real-world net- works are scale-free (Albert & Barabási 2002). which means there exist many low-degree nodes. Since these nodes may have very few even links to other nodes, it would be difficult and even impossible for them to learn similar feature representations as other same-class nodes, which is an intrinsic limitation of the 1-D graph convolution that is commonly adopted in existing models.
To address these limitations, we propose to explore relational information on different dimension the relations between feature attributes, in addition to node relations. Likewise, relation between two feature attributes should reflect some kind of similarity between them. The assumption is that attributes that tend to indicate same classes should have strong relations. For example, in a citation network, node attributes are words, and documents of Al category usually contain words such as "learning". "robotics", "machine", "neural", etc. These indicative words for Al category should have much stronger relations among themselves than with other non-indicative words. These informative relations can be used to construct an attribute affinity graph to smooth node features a similar way the node relations do, only in different dimension. Importantly, attribute relations can complement node relations in node representation learning. For instance, consider a document that has links others and hence it is impossible to do feature smoothing with node relations. But with attribute relations, it can still learn similar feature representations as other same-class nodes.
In this paper, we make the following contributions.
Methodology: We propose to use 2-D graph convolution to jointly model node relations and attribute relations for learning node representations of attributed graphs. Further, we develop computationally efficient dimensionwise separable 2-D graph convolution (DS- GC), which is equivalent to performing 1-D graph convolution alternately on the node dimension and the attribute dimension respectively.
Theoretical Insight: We show that regular 1-D graph convolution the node dimension can reduce intra-class variance of node features, which explains the success of many ex- isting methods. Further, we show that with properly constructed attribute affinity graph, graph convolution on the attribute dimension can also reduce intra-class variance of node features. Jointly, our analysis provides a theoretical justification of DSGC.
We implement DSGC for node classification and clustering on attributed graphs, and compare it with tate-of-the-ar methods on a citation network, a web graph, and an email network. The results demonstrate the superiority of DSGC over regular 1-D graph convolution on spare and noisy real-world attributed networks. We also show that DSGC can be plugged into existing models to substantially improve their performance.
Empirical Study:
2 RELATED WORKS
Structural Graph Learning, Methods for structural graph learning only utilize graph structures (node relations). A common approach is learn smooth low-dimensional embeddings of nodes ing Markov random walks (Szummer & Joak 2002 Perozzi et al., 2014: Grover & Leskovec
2016), Laplacian eigenmaps (Belkin & Niyogi 22004) spectral kernels (Chapelle al.] Zhhng
& Ando 2006), autoencoders (Wang et al.
2016 Cao et al. 2016 Ye et al. 2018) and generative ad-
versarial nets (Dai al., 2018 Wang al. 2018). Another direction is braph semi-supervised
classification, which includes methods based on low-density graph partition (Blum & Chawla 20001
Blum al. 2004: Joachims 2003) and the popular label propagation method and its variants (Zhu
et al. 2003 Zhou et al. 2004 Bengio et al., 2006 Hein & Maier] 2007 Wu et al. 2012).
Attributed Graph Learning. Methods for attributed graph learning take into account both graph structures and node features. A major class of methods learns node representations (Yang et al.) 2013 Pan et al. 2016 Huang et al., (017) or clustering nodes (Xia et al., 2014 Zhou et al. 2010 Li al. 2018 8) by applying nonnegative matrix factorization, random walk statistics, Laplacian eigenmaps on both graph structures and node features. Some node clustering methods use a Bayesian model (Xu al. 2012 Bojchevski & Günnemann 2018) or design a distance measure that trades off structural and feature information (Zhou et al. 2009; Cheng et al.) (01T). Statistical relational learning methods model node relations and features with probabilistic graphical models, e.g., rela-
2

---

Under review as a conference paper at ICLR 2020
tional Markov networks (Taskar et al. 2002). Another category of related work is the graph- semi-supervised node classification methods that exploit both graph structures and node features. For example, iterative classification algorithm (Sen al. 2008) iteratively classifies node using its neighbours' labels and features. Manifold regularization (Belkin et al.) (006), deep semi-supervised embedding (Weston al.] 2008), and Planetoid (Yang al.] 2016) classify node features by training a supervised classifier with a Laplacian or umbedding-basee regularizer.
unlabeled
Graph Neural Networks. Another line of research on attributed graph learning is based on graph neural networks (Scarselli et al. 2009 Li et al. 2016). Inspired by the success of convolutional neural networks (CNN) on Euclidean data, recent works (Bruna et al. 2014, [Henaff' et al. 2015 Duvenaud et al.) 2015: Atwood & Towsley| (016) proposed to use 1-D graph convolution for at-
ChebyNet (Defferrard et al.) 2016) uses polynomial filter represented by k-th order polynomials of graph Laplacian via Cheby- shev expansion. Graph convolutional networks (GCN) (Kipf & Welling 2017) further simplifies ChebyNet by designing an efficient layer-wise propagation rule via first-order approximation of spectral graph convolution. GCN achieved outstanding results in semi-supervised classification and inspired many follow-up works including MoNet (Monti et al. 2017), GraphSAGE (Hamilton al, 2017). graph attention networks (Velickovic et al.) 2018)), gated attention networks (Zhang et al, 2018a), FastGCN (Chen al., (018b)), dual graph convolutional neural network (Zhuang & Ma
tributed graph learning. To avoid the expensive
2018). stochastic GCN (Chen et al.] 8a), attributed network representation learning (Zhang et al,
2018c), LanczosNet (Liao et al. 2211). deep graph infomax /Velickovic al. 2019), graph Markov neural networks (Qu et al. 2019), DisenGCN (Ma et al. 2019a), MixHop (Abu-El-Haija et al., 2019. etc. recent interesting research direction on learning graph structures for graph neural networks, e.g., Bayesian GCN (Zhang et al. (b)18)) and LDS (Franceschi et al. 2019). Remarkably, LDS can automatically learn a graph for data samples even when it not available.
Some attributed graph clustering methods based on 1-D graph convolution also showed promis- ing performance, including graph autoencoder and graph variational autoencoder (Kipt & Welling, 2016), marginalized graph autoencoder (Wang et al., 2017), adversarially regularized graph autoen- coder and adversarially regularized variational graph autoencoder (Pan et al. 2018), and adaptive graph convolution (Zhang et al. (2019). More comprehensive reviews of graph neural networks can be found in (Cai et al. 2018 Zhang et al. 2018d Zhou et al. 2018).
3 2-D GRAPH CONVOLUTION
In this section, we present 2-D graph convolution for attributed graph learning. A comprehensive introduction of multi-dimennional graph Fourier transform can be found in (Kurokawa et al.) (017). Different from Kurokawa et al. (0117). here we propose localized 2-D graph convolution to cir- cumvent the computationally intensive graph Fourier transform. Furthermore, we propose an even simpler dimensionwise separable 2-D graph convolution efficiently model both node relations and attribute relations along the two dimensions of the feature matrix of an attributed graph.
3.1 2-D GRAPH FOURIER TRANSFORM AND SPECTRAL GRAPH CONVOLUTION
A 2-D graph signal is a function defined on the Cartesian product of the vertex sets of two graphs. Formally, given two weighted undirected graph (1)) and G( denote the vertex sets by y(1) and y(2), the edge set by g(I) and g(2,, and the weighted adjacency matrix by (1) and (2)) 2- D graph signal x on (I()), g(2) ) is a real-valued function f ((1) y(2) - R, which can be conveniently represented in matrix form:
X = (Zir) E Raxm
Dij f(v (1) )
(1)
where n = |VO] and m = |2(2) In this paper, (()) represents the given node graph: ((2) repre- sents the constructed attribute affinity graph; and X the node feature matrix, which is 2-D signal on the two graphs. We call the adjacency matrices A (1) and (2) node affinity matrix and attribute affinity matrix respectively.
Define the graph Laplacian of g() and g(2) as L, = D -A)) and L, = ( A2) respective- ly. Denote by X; and μıj the eigenvalues of L, and L,, and U [ur,".. ... Un, and V =[01,'' Um)
3

---

Under review as a conference paper at ICLR 2020
the corresponding eigenbasis respectively, then the outer products f form a basis for the linear space RR It is known as 2-D graph Fourier basis analogy of the Fourier basis in classical harmonic analysis in graph domain. The corresponding eigenvalue pair (Ass Pt)) ) is known as the frequency of basis matrix u.o.. Then, a 2-D graph signal X can be decomposed as:
x = Σ (1y(u,0)) UUSV', S = (8ij) ) E R
(2)
Then, can define 2-D graph Fourier transform S U XV, where S called the spectrum of signal X or Fourier coefficients.
Based on 2-D graph Fourier transform, we can now manipulate 2-D graph signals in the spectral (frequencyy domain and define 2-D spectral graph convolution. By the convolution theorem. the convolution of two signals equals to point-wise multiplication of their spectrum in the spectral do- main. 2-D spectral graph convolution is a function conv: R - R that takes signal X as input and outputs new signal Z:
Z = Σ ((Ai,,)ssssuuuuu USS U("
(3)
where μ)), R x R - I is the frequency response of the convolution; is Hadamard (element- wise) product; and P E Raxm with P.j- = p(>, my) is the frequency response in matrix form.
3.2 FAST LOCALIZED 2-D SPATIAL GRAPH CONVOLUTION
Although Eq. (3) well defines 2-D graph convolution, it is often impractical to perform convolution in the spectral domain, due to the high cost of computing the eigenbasis J V needed for Fourier transform. Similar (Defferrard
2016) on 1-D graph convolution. here we propose 2-D s- patial graph convolution to avoid intensive computation. Without loss of generality, we restrict the frequency response -(-.-) to be polynomial of two variables X, l with parameters @ === i.e.
p(), pa) = Ei, Mij''u.. Then, the 2-D spectral graph convolution in Eq. (3) becomes
m-1mm-
Z E Σ L1LLLLL
Eq. (4 is called 2-D spatial graph convolution, as it manipulates the signal X in the spatial domain. Parameter @ is called the kernel of the convolution. Here, the spatial convolutional filter is localized. Denote by k and 22 the largest exponent X and μ in the polynomial p respectively, then i > k and j > ly imply 0zj = O. The convoluted signal Ziy of vertex pair (v."), ,13 (2)) only depends on the neighbourhood of v/ within kn hops and the neighbourhood of yj within k2 hops, so the filter is kn x kz.
(2)
said to be ki -localized on g(3) and lg-localized on g(2), and the size of the kernel
Dimensionwise Separable 2-D Graph Convolution (DSGC) Although the above spatial graph convolution avoids the computationally expensive Fourier transform, its general form with kernel size k x lo still involves at least 4 x f2 matrix multiplications. Inspired by the depthwise sep- arable convolution proposed
(Howard et al.) 2017), we streamline spatial graph convolution by restricting the rank of θ to be one. Consequently, C is decomposed as outer product of two vectors (1) E Rn and ((2) R The frequency response p can be decomposed as produc- of two single variable polynomials, i.e., p(), μ) Pı (A)p2(()) where (1(A) -E, O. X and (2(1) = Σ, ) μd. Finally, the 2-D spatial graph convolution in Eq. (4) becomes
(5) (5) dimensionwise separable graph convolution (DSGC). The fastest way to compute it only requires &n loz matrix multiplications, much less than the k hi matrix multiplications needed by a general 2-D spatial graph convolution.
Z = GXF,F where G p1 (Ln) and F P2())..
We call Eq.
We call G.X node graph convolution and G the node graph convolutional filter. Similarly, we call F attribute graph convolution and F the attribute graph convolutional filter. Notably, G and F can complement each other to learn better node representations. As illustrated in Fig. T the node affinity
4

---

Under review as a conference paper at ICLR 2020
Node affinity graph
Attribute affinity graph
Alll
AR2
Ant
AB
Aftt
2/3
1/3
Att4
b
1/3
2/3
A113
AM2
anx
2014
Aud
1/2
1/2
1/2
X
J/ 1/3
GX
And
1/2
1/2
GXF
12 2/1
1/2
1/2
Node Class
1/2
Node Class
G
Attribute
Figure I: Illustration of DSGC.
graph only captures node relations of Class 1, and applying node graph convolution on the feature matrix X smooths the node features of Class 1, but it does not affect those of Class 2. Fortunately, the attribute affinity graph encodes complementary relational information on another dimension, and further applying attribute graph convolution makes the node features of Class 2 similar and those of Class 1 even more similar, thereby making them much easier to classified or clustered.
4 INTRA-CLASS VARIANCE REDUCTION BY DSGC
Given a data distribution, the lowest possible error rate an classifier can achieve the Bayes error rate (Fukunaga 2013), which is caused by the intrinsic overlap between different classes and cannot be avoided. this section, we show that DSGC with proper graph convolutional filters can reduce intra-class variance of the data distribution while keeping class centers roughly unchanged, hence reducing the overlap between classes and improving learning performance.
Intra-class Variance and Inter-class Variance. Suppose samples æ; and their labels ys obser- vations of a random vector X = [X Xm] and a random variable Y respectively. We define the variance of random vector X be the sum of the variance of each dimension X,, i.e., the trace of the covariance matrix of X. According to law of total variance (Grinstead & Snell 2012). the
variance of X can divided into intra-class variance and inter-class variance:
Var (X) E [Var (XlV) + Var (R (X
Intra-class Variance
Inter-class Variance
where the conditional variance Var (X k) is the variance of class i and the conditional ex- pectation E [X|Y k:] is the k-th class center. Intra-class variance (IntraVar) measures the average divergence within each class, while inter-class variance (InterVar) measures the divergence among class centers. We are interested in the IntraVar/ /InterVa ratio. Here, we assume that each class of data Pr (X Y k) follows unimodal distribution (e.g. Gaussian, chi-square, Laplace), class of most common distributions in the real world, and with roughly convex contours. Under this assump- tion, low Intra Var Inter Var ratio generally indicates low classification error, since the class overlap is reduced. This is also verified by our experiments on real attributed networks in section 7
4.1 INTRA-CLASS VARIANCE REDUCTION BY NODE GRAPH CONVOLUTION
As variance of sample mean is always less than variance of individual samples, averaging samples of the same class can always reduce intra-class variance. Actually this is how node graph convolution works. For any node i, node graph convolution GX produces new feature vector 2; = Σ, Gij When G is stochastic matrix, the output feature vector 2; is weighted average of the neighbours of x; Denote by Z a random vector of 2, Intuitively. as long as each node i has enough same- class neighbours, Z will have a smaller Intra Vara/Iter/ai ratio than X. Formally, assume that the graph is generated by a stochastic block model, where nodes from the same class are connected with probability p and those from different classes are connected with probability q. Then, with the stochastic graph filter G D-1 (1), have the following theorem.
5

---

Under review as a conference paper at ICLR 2020
Theorem 1. When q is sufficiently small, the IntraVarr/Inert Var ratio of E is less than equal to that of X, i.e.,
E [a [ Y Var (E Y Var EE [X
Var X
The proof is given the Appendices. Under the assumption that nodes in the same class are most likely to be connected, node graph convolution G can reduce intra-class variance while keeping inter-class variance roughly unchanged, thereby decreasing the Intra Varranaret Var ratio.
4.2 INTRA-CLASS VARIANCE REDUCTION BY ATTRIBUTE GRAPH CONVOLUTION
In the following, show that proper attribute graph convolutional filter F also reduce the IntraVar/Inter ratio. We use the convention that the random vector X is a column vector, and hence the attribute graph convolution X results in new random vector F X. We also assume that the node features are mean-centered, i.c. E [ O. Denote by Cov
Cov (X k) the covariance matrix of X w.r.t. each class, and denote by тy = Pr(Y = k) the portion of each class. Then, after attribute graph convolution, the intra-class variance of data becomes
E Var x[X)] - - Th E (k) (FF') )
Cov
Theorem 2. If the altribute graph convolutional filter F is doubly stochastic matrix, then the output of attribute graph convolution has an intra-class variance less than equal to that of X. i.e.
-5-- Fig and Fig 2 i,
E V [F x|1)] < E [aar (X])).
The proofs of Eq. (8) and Theorem are given in the Appendices. Eq. (8) suggests that to reduce intra-class variance, the attribute affinity graph should connect attributes X; and X5 with small or
even negative covariance Cov For example, in Figure the attributes Att3 and Att4 are both indicative of class 2, but negatively correlated w.rt. class 2, so connecting them in the attribute affinity graph can greatly reduce the intra-class variance of class 2.
To achieve low Intra Var/Inter ratio, in addition reducing intra-class variance, also need to keep the class centers apart after convolution, which then depends on the quality of the attribute affinity graph. A good attribute affinity graph should connect attributes that share similar expecta- tions conditioned on Y. Formally, each attribute Xj has K conditional expectations w.r.t. Y, which are denoted as a vector ej = (E [Y = 1), ... ,E[X, = K]) E R We have the following.
Theorem 3. If VFij 0. |le. e less than or equal to s, i.e.
then the distance between e, and ē₁ E, Fije; is also
l|e: - - 21 < E, VFJ # 4
+ - 2 Se
and e can be arbitrarily small with a proper F.
By Theorem since the conditional expectations of each attribute may change little after attribute graph convolution, one can infer that the class centers will also change little, and so does the inter- class variance. Combining Theorems 2 & 3 it suggests that a proper attribute affinity graph should connect attributes that have similar class means but are less positively correlated, so as to achieve low Intra Var/InterVaa ratio and improve performance. Again, it can be seen in Figure D that the attributes Att3 and Att4 have exactly the same class means, but are negatively correlated w.r.t. class and connecting them in the attribute affinity graph reduces the intra-class variance of class 2 to O.
ATTRIBUTED GRAPH LEARNING WITH DSGC
5.1 UNSUPERVISED NODE REPRESENTATION LEARNING
Given an attributed graph with node feature matrix X, we can learn the node representations Z in unsupervised manner by applying DSGC X, i.e.,
Z GXF.
(

---

Under review as a conference paper at ICLR 2020
and then perform various downstream learning tasks with Z.
Node Classification. With the learned node representations Z. we can simply train a classifier such as multilayer pereeptron with the labeled nodes, and then apply the trained classifier on the unlabeled nodes to predict their labels.
Node Clustering. With the learned node representations Z, we propose to cluster nodes as follows. We first apply a linear kernel on to learn pairwise proximity between nodes, i.e., K = ZZ and then perform spectral clustering (Perona & Freeman 1998 Von Luxburg 2007) on K.
5.2 END-TO-END SUPERISDE LEARNING
For semi-supervised learning on attributed graphs, we can also use DSGC to replace the 1-D graph convolution used in existing end-to aad-to-end semi-supervised learning models including GCN (Kipf & Welling 201l GAT (Velickovic et al. 2018) and GraphSAGE (Hamilton et al. (017)) For example, to incorporate DSGC into the vanilla GCN, we can modify the first layer propagation of GCN as:
H (2) = (GXFW")).
(10)
where (L) is the hidden units in the first layer, W E TRmxi is the trainable parameters of GCN, and a is a nonlinear function such ReLU. Both G and F are fixed filters, where G is the node graph convolutional filter of GCN, and is the proposed attribute graph convolutional filter.
Importantly, Eq. (IO can be considered as feeding filtered feature matrix X F instead of the raw feature matrix X to GCN. By our above analysis, a proper attribute graph filter F can reduce intra-class variance, which makes X F much easier to classify and guarantees to help train better model. Further, it can be shown that the model trained by Eq. (TO) is essentially different from that of GCN almost surely. For GCN, the model is freely chosen from the parameter space (1), while the model trained by Eq. (10p restricted in a subspace FW()), Since F is low-pass (section 6.2). also low-rank, and FW(1) is small subspace of m.xi projected by F. Model parameters in this subspace are generally better in terms of the generalization performance (test accuracy), due to the variance reduction property of F. However, the model learned by Eq. (10) can hardly be learned by GCN, since the subspace FW(11 has measure zero, which is an extremely small subset of mmxx
IMPLEMENTATION OF DSGC
6.1
NODE GRAPH CONVOLUTIONAL FILTERS
The node affinity graph (1(1) is given as part of the dataset. There are various graph convolutional filters available eti 2019), e.g., the one used in GCN (Kipf & Welling 2017) is symmetrically normalized node affinity matrix. In our experiments, we use a row normalized node affinity matrix
(consistent to our analysis in section 4.1] of order 2 (following GCN) as the filter for node graph convolution:
= (DT A0)?
(11)
where D2 is the degree matrix of A1), We observe in our experiments that the performance of the symmetrically normalized node affinity matrix (GCN filter) is similar.
6.2 ATTRIBUTE GRAPH CONVOLUTIIONAL FILTERS
A key issue in implementing DSGC is to construct the attribute affinity graph (2) Possible ways of constructing (2) include extracting entity relation information from existing knowledge bases, building a similarity graph from features, or identifying correlations by domain knowledge. In the following, we describe two methods for text data, which have been proven useful by our experiments.
Positive point-wise mutual information (PPMT). Positive PMI (Church & Hanks 1990) is com- mon tool for measuring the association between two words in natural language processing, Given a pair of words ua and wy, the edge weight defined as the PPMI between wi and wy:
(2) PPMT Wi, wy)
p(w, wy) log
(12)
p(w;; ()()))
7

---

Under review as a conference paper at ICLR 2020
where p(w, w1;) and p(w;) are learned by sliding window over large corpus of text. PMI reflects word collocation, as it assumes that if two words co-occur more than expected under independence, there must be some kind of semantic relation between them, which is often true in practice. With the constructed attribute affinity graph A (2) by PPMI, in our experiments, normalized affinity matrix as the filter:
symmetrically
F D= A D2
(13)
where D2 the degree matrix of A
Word embedding based k-NN graphs. Word embedding is collection of techniques that map vo- cabularies to vectors in a Euclidean space. Embeddings of words are pre-trained vectors learned from corpus with algorithms such as GloVe (Pennington et al.) 2014). Since word embeddings capture se- mantic relations between words (Bakarov] 2018), they can be used for constructing an attribute affinity graph. With the embedding vectors, we construct k-NN graph with some proximi- metric such as the Euclidean distance. With the constructed attribute affinity graph A (2), in our experiments, we use the following one-step lazy random walk filter (Li et al. (019)):
F= (I A D2 1/2
(14)
where D2 is the degree matrix of (2) Note that the filters in Eq. 113 and (14 are slightly different, since the diagonal weight of the affinity matrix constructed by word embedding is much smaller than that of the PPMI affinity matrix, and we want to assign sufficient weight to each attribute itself. Also, we use filters of order since the PPMI affinity matrix is very dense. According to the analysis in are both low-pass filters.
Li et al. 2019). Eq. 13) and
[4)
EMPIRICAL STUDY
To validate the effectiveness of DSGC, we conduct extensive experiments for semi- cemi-supervised node classification and node clustering on three large real-workd attributed networks including 20 News-
groups (20 NG) (Lang] 1995), Wikispeedia (Wiki) (West et al. 2009 West & Leskovee (012) and Large Cora (L-Cora) (McCallumzy et al. 1999: Li et al. 2019 ). Due to space limitation, details of datasets, experimental setup and computational time are provided in the Appendices.
Variance Reduction. First of all, to verify our analysis in section 4 demonstrate the variance reduction effect of both node graph convolution and attribute graph convolution. As shown in Fig- ure 2 I-D graph convolution with either G or F already greatly reduces the Intra Varraaarr Manterreraar ratio, and together they further significantly reduce the ratio.
7.1 NODE CLASSIFICATION
Baselines. We test the proposed node classification method by DSGC with or without using the node graph convolutional filter (G)) and the attribute graph convolutional filter (F) in five cases. We use a two-layer multilayer perceptron as the classifier for DSGC. PPMI and Emb denote constructing the attribute affinity graph with positive pose mutual information and word embedding respec- tively. We compare DSGC with the following basclines: label propagation (LP) (Wu et al.) 2012). multi-layer perceptron (MLP), GCN (Kipf & Welling 2017), generalized label propagation (GLP) (Li et al. 2019). GraphSAGE (Hamilton et 2l.7) graph attention networks (GAT) (Velickovic al. 2018), and deep graph infomax (DGI) (Velickovic al. 2019). We also try incorporate DSGC into GCN, GAT, GraphSAGE, and LDS (Franceschi et al. 2019) (see the experimental setup of LDS in Appendix A.4) described in section 5.2 to improve their performance.
Performance. We test semi-supervised node classification under two scenarios -20 labels per class and 5 labels per class. For each task, we report the mean classification accuracies and standard deviations over 10 runs, as summarized in Table [ where the top 2 accuracies are highlighted in bold. In Table 2, we report the results of GAT, GCN, GraphSAGE, and LDS after incorporating DSGC. The following observations can be made.
Note that we did not use the "Cora", "Citeseer" and "PubMed" datasets as in Kipf & Welling 2017 Yang 2016
Sen et al. 2008), since the attribute (word) lists are not provided in these datasets.
8

---

Under review as a conference paper at ICLR 2020
Table 1: Classification accuracy.
Datascts
20 NG
L-Cora
Wiki
Methods
20 labels
labels
20 labels
5 labels
20 labels
5 labels
LP
16.39
1 0.0
8.62 0.20 55.77 1 0 38.97 3.15 9.53 0.0
10.54
0.19
MLP
X
X
65.77
0.022
36.10
i.11 51.05 0.71
33,56 2.43 60.86 0.69
29.95 +: 1.04
GLP
V
x
76.21
+018
47.86
1.63 67.58
+ 106
51.04
= 1.11
33.42
+ 144
15.38 = 1.37
GCN
V
X
76.14
224
47.70
1.64 66.69 0 48.62
48.65
38,30
GAT
75.16
49.14
= 1.55 66.49
+ 1o1 49.27
225
48.88
0.6 36,90
DGI
73.34 4: 0:027
66.57
0.3 61.39
+ 0.50 54.77 1.24
49.70
1.63
43.64 1.89
GraphSAGE
X
65.73 + 0.17
42.48
0.77 57.28
+ 0.71 46,79
1.91
65.52
+ 0.62
48.81
+ 0.76
DSGC (GX)
X
76.27
1:200 47.92 1.57 67.16
+ 1.04 51.93 = 1.46
49.78
+: 0.50
43.79 +: 1.48
DSGC (XF)
Emb
68.08
+: 0.222
43.41
= 0.99
55.34
0.66
38.13 13
2.20
68.43
0.37
54.25 0.99
PPMI
76
021
61.45
0.74
58.54 + 0.79
44.58
2.00
69.53
+ 0.36
58.44 +: 1.48
DSGC F)
Emb
77.38 0.14
55.24
= 1.21
68.38
52.87
1.56
58.66
45.71
PPMI
81.91 o.2 70.35 0.72
67.60
+ 0,2 54.07
1.13
58.35
+ 0.52 46.72 + 1.66
and X indicate using/not using G or F.
Table 2: Improve baselines with DSGC.
Methods
20
L-Cora
Wiki
GX
XF, F-PPMI
=XF, F=Emb
GXF, F=PPMI
GXF, F=Emb
75.16 = o25 66.49 + 1.1 48.88 +: 0.68
GAT
128.0
PPMI
80.52 0.16 67.00 +: 0.65 55.51 1: 0.38
64.0
76. 024 66.69 1: 0.98 48.65 1: 0.65
GCN
18.0
PPMI
81.80 0.2 65.83 + 0.77 60.22 + 0.71
4.0
75.74
62.51 + 0.70 62.89 +
LDS
PPMI
81.98 + 046 62.94 + 0.32 66.97 + 0.63
NG
Wiki
L-Cora
66.773 0.17 57.28 a0 65.52 + 0.62
GraphSAGE
Figure 2: Intra Var Inter Var ratios.
PPMI 76.27 0.3 60.23 +: 1881 67.26 : 0.5
X indicates not using F.
1) Node graph convolution does not always help. On 20 NG and L-Cora, methods based node graph convolution such as DSGC (GX), GLP, GCN and GAT all outperform MLP significantly. However, on Wiki, node graph convolution harms the performance, which is due to the highly noisy hyperlink graph with intra-class edge ratio 38.00 18.0% much lower than that of 20 NG (96.8%) and L- Cora (76.5% 5%) (see Table in the Appendices). This shows the limitation of node graph convolution.
2) Attribute graph convolution works. On all the three datasets, DSGC (XF) outperforms MLP by a large margin. This shows that attribute graph convolution can learn useful node representations even when there are no connections between nodes. Remarkably, on Wiki, where the hyperlink graph is of bad quality, DSGC (X F) with either PPMI Emb outperforms all the baselines by a large margin. DSGC (X with PPMI improves upon the best baseline by 4% and 10% in absolute accuracy for tasks with 20 labels and 5 labels per class respectively.
3) 2-D graph convolution is effective.
For datasets with good node graphs such 20 NG and L-Cora, DSGC (GXF) performs much better than either DSGC (GX) or DSGC F).).. DSGC (GXF) with PPMI achieves the best performance. On 20 NG, it improves upon the best baseline by more than 5% for tasks with 20 labels per class, and about 4% for tasks with 5 labels per class, both in absolute accuracy. On L- Cora, comparable with the best baseline. On both datasets, for tasks with 20 labels per class, DSGC (GXF) F) with Emb also outperforms all the basclines; for tasks with 5 labels per class, outperforms all the baselines except DGI. This shows that node graph convolution and attribute graph convolution can complement each other and lead significant performance gain.
For datasets with bad node graphs such as Wiki, DSGC (GXF) significantly improves upon DSGC (GX) and outperforms all the baselines except GraphSAGE, which uses extra labeled data for validation while DSGC uses none. Nevertheless, since node graph convolution degrades perfor- mance such noisy graph, DSGC (X F) performs better than DSGC (GX F).

---

Under review as a conference paper at ICLR 2020
Table 3: Clustering performance.
Datascts
20 NG
L-Cora
Wiki
Methods
Acc(%)
NMI(%)
Acc(%)
NMI(%)
Acc(%)
NM](%)
Spectral
25.29 1: 101
28.18 = 0.74 28.22
1: 1.01
11.61 0.04
29.25
0.00
21.83
0.00
GAE
/
X
38.92 1: 1.39
44.58
0040 34.45
0:766
22.38 1.18 33.78
0:32
22.88
1: 0.20
VGAE
J
x
25.04
25.72
=0m
1
1:25
17.53
2.15 33.83
0.4
21.46 + 0.19
MGAE
V
X
47.83 2m
56.14
= 1.00 35.87
=007
30.57
0098
32.73
1.16
27.95 2.29
ARGE
42.04 0
44.13
= 091
36.07
2005
27.74
26.49
=0.00
17.17
= 0.08
ARVGE
21.10 0.1
21.79
0.49
26.45
+ 0.0
12.94 0.01
33.82
0.13
21.42 4 0.11
AGC
X
38.83 + 024
47.08
1.57
41.76 + oot
33.65
0:01
32.74
0.01
24.90 + 0.01
DSGC (GX)
V
X
38.42 0.66
46,28
0.93
38.26
+ 0.00 30.66 = 0.02
31.43
0.00
24.16 = 0.18
DSGC (XFF
Emb
28.99
+: 0.06
33.22
= 0.10
30.80
+: 0.56
17.46 0:21
35.45
0.91
33.44 :: 0.66
PPMI
48.36
+ 2.0
53.27
2.17
36.46
+ 0.6
22.53 0.03
38.10
+: 0.01
36.07 +: 0.02
Emb
43.40 0.6
50.97 = 0.58
40.75
33.05
30.50
25.48
DSGC F)
PPMI
52.25 + 197 61.34 1.07
41.24 + 0.44
30,92 0.01
31.37
+ 0.08
26.06 + 0.20
and X indicate using/not using G or F.
As shown in Table for node classification with 20 labels per class on all three datasets, af- ter incorporating DSGC, the performances of GCN, GAT, LDS, and GraphS are substantially improved in most cases. This further verifies the effectiveness of 2-D graph convolution.
7.2 NODE CLUSTERING
Baselines. We test the proposed node clustering method by DSGC (section 5.1 with without using G and F in five cases. We compare DSGC with strong baselines for attributed graph clustering including GAE and VGAE (Kipf & Welling, 2016), MGAE (Wang al., 2017), ARGE and ARVGE (Pan et al. 2018), and AGC (Zhang et 2019). We also compare with spectral clustering (Spectral) that operates on a similarity matrix constructed by applying linear kernel the node representations.
Performance. To evaluate the clustering performance, we adopt two widely-used metrics (Aggarwal & Reddy, 2014h: clustering accuracy (Acc) and normalized mutual information (NMI). The results are shown in Table 3 where the top 2 results are highlighted in bold. The following observations can be made. 1) Attribute graph convolution works very well. On 20 NG, DSGC (X F) with PPMI already outperforms most baselines by large margin. On Wiki, DSGC (X F) with PPMI or Emb significantly outperforms all the baselines. 2) Similar to the classification tasks, 2-D graph convolu- tion is effective. On 20 NG, DSGC (GXF) F)) with PPMI can further improve upon the very strong performance of DSGC (X F') and performs the best; On L-Cora, DSGC (GX with PPMI or Emb improves upon either DSGC (GX) or DSGC (X F) and outperforms most baselines significantly. On Wiki, DSGC (XF) performs better than DSGC (GXF). F), due to the low-quality hyperlink graph as explained above.
For both classification and clustering, we observe that in most cases DSGC with PPMI can achieve better performance than with Emb. This shows the effectiveness of PPMI in capturing meaningful
word relations based on information theory and statistics (Church & Hanks 1989), whereas Emb only relies on distance metric for measuring word similarity.
8 CONCLUSION
In this paper, we have proposed to model attributed graphs with 2-D graph convolution. We have demonstrated theoretically and empirically that by exploiting attribute relations in addition to node relations, a simple and efficient dimensionwise separable 2-D graph convolution (DSGC) can learn better node representations than existing methods based on regular 1-D graph convolution on noisy and sparse real-word networks. We believe 2-D graph convolution is a promising tool for attributed graph learning, and there is much left to be explored. In future work, plan to further investigate the construction of attribute affinity graphs for different types of attributed networks, apply DSGC to solve various practical problems, and design new efficient filters for 2-D graph convolution.
10

---

Under review as a conference paper at ICLR 2020
REFERENCES
Sami Abu-El-Haija. Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In ICML, pp. 21-29, 2019.
Charu C Aggarwal and Chandan K Reddy. Data Clustering: Algorithms and Applications. CRC Press, Boca Raton, 2014.
Réka Albert and Albert- László Barabási. Statistical mechanics of complex networks. Reviews of modern physics, 74(1 (:47, 2002.
James Atwood and Don Towsley. Diffusion-comvolutionaal neural networks. NeurlPS, pp. 1993 2016.
Amir Bakarov. A survey of word embeddings evaluation methods. CoRR,
2018.
M. Belkin and P. Niyogi. Semi-supervised learning Riemannian manifolds. Machine Learning, 56(1))209-23) 2399,39,,9. 2004.
M. Belkin, P. Niyogi, and V. Sindhwani. Manifold regularization: A geometric framework for learn- ing from labeled and unlabeled examples. Journal of Machine Learning Research, 7(1):2399- 2434, 2006.
Y. Bengio, O. Delalleau, and N. Le Roux. Label propagation and quadratic criterion. Semi- supervised Learning, pp. 193-216, 2006.
A. Blum and S. Chawla. Learning from labeled and unlabeled data using graph mincuts. In JCML, pp. 19-26, 2001.
A. Blum, J. Lafferty, M.R. Rwebangira, and R. Reddy. Semi-supervised learning using randomized mincuts. In ICML, pp. 13, 2004.
Aleksandar Bojchevski and Stephan Günnemann. Bayesian robust attributed graph clustering: Joint learning of partial anomalics and group structure. In AAAI, pp. 2738-2743 2018.
Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks graphs. ICLR, 2014.
HongYun Cai, Vincent W. Zheng, and Kevin Chen-Chuan Chang. comprehensive survey of graph embedding: Problems, techniques, and applications. IEEE TKDE, 30(9):1616-)) 16376666666666 2018.
Shaosheng Cao, Wei Lu, and Qiongkai Xu. Deep neural networks for learning graph representations. In AAAI, pp. 1155-1152, 2016.
O. Chapelle, J. Weston, and B. Scholkopf. Cluster kernels for semi-supervised learning. NeurlPS, pp. 601-608, 2003.
Jianfei Chen, Jun Zhu, and Le Song. Stochastic training of graph convolutional networks with variance reduction. In ICML, pp. 941-949, 2018a.
Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: Fast learning with graph convolutional networks via importance sampling. In ICLR, 2018b.
Hong Cheng, Yang Zhou, and Jeffrey Xu Yu. Clustering large attributed graphs: A balance between structural and attribute similarities. ACM TKDD, 5(2):12:1-12:333 2011.
Kenneth Ward Church and Patrick Hanks. Word association norms, mutual information and lexi- cography. In 27th Annual Meeting of the Association for Computational Linguistics, 26-29 June 1989, University of British Columbia, Vancouver, BC, Canada, Proceedings., pp. 76 83, 1989.
Kenneth Ward Church and Patrick Hanks. Word association norms, mutual information, and lexi- cography. Computational Linguistics, 16(1):22-29, 1990.
Quanyu Dai, Qiang Li, Jian Tang, and Dan Wang. Adversarial network embedding. In AAAI, 2018.

---

Under review as a conference paper at ICLR 2020
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks graphs with fast localized spectral filtering. In NeurIPS. pp.
2016.
David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Assuuu-Guzzzz and Ryan Adams. Convolutional networks on graphs for learning molecular fingerprints. In NeurlPS, pp. 2224-2232, 2015.
Luca Franceschi, Mathias Niepert, Massimiliano Pontil, and Xiao He. Learning discrete structures for graph neural networks. In ICML, pp. 1972-1982, 2019.
Keinosuke Fukunaga. Introduction to statistical pattern recognition. Elsevier, 2013.
Charles M Grinstead and James Laurie Snell. Introduction to probability. American Mathematical Soc., 2012.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In ACM SIGKDD, pp. 855-864. ACM, 2016.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NeurlPS, pp. 1024-1034, 2017.
Matthias Hein and Markus Maier. Manifold denoising. In NeurlPS, pp. 561-568, 2007.
Mikael Henaff, Joan Bruna, and Yann LeCun. Deep convolutional networks on graph-structured
data. CoRR, abs/ abss/150..0513,, 2015.
Andrew Howard, Menglong Zhu, Bo Chen, Dmitry Kalenichenko, Weijun Wang, Tobias Weyand, Marco Andreetto, and Hartwig Adam. Mobilenets: Efficient convolutional neural networks for mobile vision applications. arXiv preprint urXiv:1704.0000 00704404466.... 2017.
Xiao Huang, Jundong Li, and Xia Hu. Accelerated attributed network embedding, In SIAM ICDM, pp. 633 641, 2017.
T. Joachims. Transductive learning via spectral graph partitioning. In ICML, pp. 2003.
Thomas N Kipf and Max Welling. Variational graph auto-encoders. NIPS Workshop on Bayesian Deep Learning, 2016.
Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional network- In ICLR, 2017.
Takashi Kurokawa, Taihei Oki, and Hiromichi Nagao. Multi-dimensional graph fourier transform. arXiv preprint arXiv:1712.07811 2017.
Ken Lang. Newsweeder: Learning to filter netnews. In ICML, pp. 331-339, 1995.
Qimai Li, Xiao-Ming Wu, Han Liu, Xiaotong Zhang, and Zhichao Guan, Label efficient semi- supervised learning via graph filtering. In CVPR, pp. 9582-9591, 2019.
Ye Li, Chaofeng Sha, Xin Huang, and Yanchun Zhang. Community detection attributed graphs: an embedding approach. In AAAL, pp. 338-344- 348-345,20 2018.
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard S. 7emel. Gated graph sequence neural networks. In ICIR, 2016.
Renjie Liao, Zhizhen Zhao, Raquel Urtasun, and Richard S Zemel. Lanczosnet: Multi-scale deep graph convolutional networks. CORR, abs/1901 .01484, 2019.
Jianxin Ma, Peng Cui, Kun Kuang, Xin Wang, and Wenwu Zhu. Disentangled graph convolutional networks. In ICMI., pp. 4212-4221, 2019a.
Jiaqi Ma, Weijing Tang, Ji Zhu, and Qiaozhu Mei. A flexible generative framework for graph-based semi-supervised learning. CoRR, 107619 2019b.
12

---

Under review as a conference paper at ICLR 2020
Andrew McCallumzy, Kamal Nigamy, Jason Renniey, and Kristie Seymorey. Building domain- specific search engines with machine learning techniques. In Proceedings of the AAAI Spring Symposium Intelligent Agents in Cyberspace, pp. 28 29-39. Citeseer, 1999.
Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodolà, Jan Svoboda, and Michael M. Bronstein. Geometric deep learning on graphs and manifolds using mixture model cnns. In CVPR, pp. 5425-5434, 2017.
Shirui Pan, Jia Wu, Xingquan Zhu, Chengqi Zhang, and Yang Wang. Tri-party deep network repre- sentation. In IJCAI, pp. 1895-11911 2016.
Shirui Pan, Ruiqi Hu, Guodong Long, Jing Jiang, Lina Yao, and Chengqi Zhang. Adversarially regularized graph autoencoder for graph embedding. In ICAA, pp. 2609-2615, 2018.
Jeffrey Pennington, Richard Socher, and Christopher Manning. Glove: Global vectors for word representation. In EMNLP, pp. 1532-1543, 2014.
Pietro Perona and William Freeman. A factorization approach grouping. In ECCV, pp. 655-670, 1998.
Bryan Perozzi, Rami A1-Rfou, and Steven Skiena. Deepwalk: Online learning of social representa- tions. In ACM SIGKDD, pp. 701-710, 2014.
Meng Qu, Yoshua Bengio, and Jian Tang. GMNN: graph markov neural networks. In ICML, pp. 1241-5250, 2019.
Claudio Saccá, Michelangelo Diligenti, and Marco Gori. Collective classification using semantic based regularization. In JEEE ICMLA, volume 1, pp. 283-286, 2013.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. JEEE Transactions Neural Networks, 20(1):61-80. 2009.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. Al Magazine, 29(3):93-106, 2008.
M. Szummer and T. Jaakkola. Partially labeled classification with Markov random walks. In NeurlP- S. pp. 945-952, 2002.
Benjamin Taskar, Pieter Abbeel, and Daphne Koller. Discriminative probabilistic models for rela- tional data. In UAI, pp. 485-492, 2002.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In ICLR, 2018.
Petar Velickovic, William Fedus, William L. Hamilton, Pictro Liò, Yoshua Bengio, and R. Devon Hjelm. Deep graph infomax. In ICLR, 2019.
Ulrike Von Luxburg. A tutorial on spectral clustering. Statistics and computing, 17(4):395-416 2007.
Chun Wang, Shirui Pan, Guodong Long, Xingquan Zhu, and Jing Jiang. Mgae: Marginalized graph autoencoder for graph clustering. In CIKM, pp. 889-898, 2017.
Daixin Wang, Peng Cui, and Wenwu Zhu. Structural deep network embedding. In ACM SIGKDD, pp. 1225 1235-1224,2222 2016.
Hongwei Wang. Jia Wang, Jialin Wang, Miao Zhao, Weinan Zhang, Fuzheng Zhang, Xing Xie, and Minyi Guo. Graphgan: Graph representation learning with generative adversarial nets. In AAAI, 2018.
Robert West and Jure Leskovec. Human wayfinding in information networks. In WWW, pp. 619- 628,2012 2012.
Robert West, Joelle Pineau, and Doina Precup. Wikispeedia: An online game for inferring semantic distances between concepts. In IJCAI, pp. 1598-1603 1603, 2009.
13

---

Under review as a conference paper at ICLR 2020
Jason Weston, Frédéric Ratle, Hossein Mobahi, and Ronan Collobert. Deep learning via semi- supervised embedding. In ICML. pp. 1
2008.
Xiaoming Wu, Zhenguo Li, Anthony M. So, John Wright, and Shih-fu Chang. Learning with Par- tially Absorbing Random Walks. In NeurlPS, pp. 3077-3085, 2012.
Rongkai Xia, Yan Pan, Lei Du, and Jian Yin. Robust multi-view spectral clustering via low-rank and sparse decomposition. In AAAI, pp. 2149-2155 2014.
Zhiqiang Xu, Yiping Ke. Yi Wang, Hong Cheng, and James Cheng. A model-based approach to attributed graph clustering. In ACM SIGMOD, pp. 505-516, 2012.
Cheng Yang, Zhiyuan Liu, Deli Zhao, Maosong Sun, and Edward Y Chang. Network representation learning with rich text information. In IJCAI, pp. 2111-2117, 2015.
Zhilin Yang, William W Cohen, and Ruslan Salakhutdinov. Revisiting semi-supervised learning with graph embeddings. In ICML, pp. 40-48, 2016.
Fanghua Ye, Chuan Chen, and Zibin Zheng. Deep autoencoder- like nonnegative matrix factorization for community detection. In CIKM, pp. 1402, 2018
Jiani Zhang, Xingjian Shi, Junyuan Xie, Hao Ma, Irwin King, and Dit- Yan Yeung. Gaan: Gated attention networks for learning on large and spatiotemporal graphs. In UAI, pp. 339-349, 2018a.
T. Zhang and R.K. Ando. Analysis of spectral kernel design based sumi-supervised learning. In NeurlPS, pp. 1601-1608, 2006.
Xiaotong Zhang, Han Liu, Qimai Li, and Xiao-Ming Wu. Attributed graph clustering via adaptive graph convolution. In IJCAI, pp. 4327-4333, 2019.
Yingxue Zhang. Soumyasundar Pal, Mark Coates, and Deniz Üstebay. Bayesian graph convolutional neural networks for semi-supervised classification. CoRR, 1tt./1111.111000 2018b.
Zhen Zhang, Hongxia Yang, Jiajun Bu, Sheng Zhou, Pinggang Yu, Jianwei Zhang, Martin Ester, and Can Wang. ANRL: attributed network representation learning via deep neural networks. In IJCAL, pp. 4155-3161. 2018c.
Ziwei Zhang, Peng Cui, and Wenwu Zhu. Deep learning on graphs: A survey. CoRR, ab- s/1812.04200 2018d.
Denny Zhou, Olivier Bousquet, Thomas N Lal, Jason Weston, and Bernhard Schölkopf. Learning with local and global consistency. In NeurlPS, pp. 321-328, 2004.
Jie Zhou, Ganqu Cui, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, and Maosong Sun. Graph neural networks: A review of methods and applications. CoRR, abs/18 0tss/182200844, 2018
Yang Zhou, Hong Cheng, and Jeffrey Xu Yu. Graph clustering based on structural/atrribute similar- ities. Proceedings of the VLDB Endowment, 2(1):718-729, 2009.
Yang Zhou, Hong Cheng, and Jeffrey Xu Yu. Clustering large attributed graphs: An efficient incre- mental approach. In ICDM, pp. 689-698, 2010.
Xiaojin Zhu, Zoubin Ghahramani, and John D Lafferty. Semi-supervised learning using gaussian fields and harmonic functions. In ICML, pp. 912-919, 2003.
Chenyi Zhuang and Qiang Ma. Dual graph convolutional networks for graph classification. In WWW, pp. 499-508, 2018
graph-based based semi-supervised
14

---

Under review as a conference paper at ICLR 2020
Appendices
Appendix A provides details about the experiments section 7 and presents additional experimental results. Appendix B and provvide proofs of the theorems in section 4.
APPENDIX A EXPERIMENT DETAILS AND SUPPLEMENTARY EXPERIMENTS
A.1 DATASET DETAILS
Table 4: Classes of each dataset.
Datasets
Classes
talk.politics guns talk.politics. mideast talk.politics. misc talk. calk.religion.it misc soc.religion.co wel.igioon.ccrriiaann
sci.crypt sci.electronies sci.med scissace alt.atheism
rec.autos
comp.g graphics
rec. rec.motoreycles rec.sport.baseball baseball
comp.os ms ans-wwndows..o mise comp.sys. yys.ibm.pc.....o pardarr comp.sys.mmr wys.mac..aaaaee hard comp. windows.x
20 NG
rec.sport spoke. fisc.forsale
christian
Everyday Life Countries Citizenship
Religion People
Science
Design and Technology Language and literature
Wiki
History
Networking Data Structures Algorithms and Theory Operating Systems Programming Information Retrieval Databases
Artificial Intelligence
Encryption and Compression
Hardware and Architecture Human Computer Interaction
L-Cora
20 Newsgroups (20 NG) Lang
1995) is an email discussion group, where each node is an email and there are 18846 emails in total. Each email is represented by an 16697-dimension tf-idf feature vec- tor. Two emails are connected by an edge they replies the same one. These emails are categorized into 20 classes listed in Table
Wikispeedia (Wiki) West et al. (2009); West & Leskoved (2012) is a webpage network in which the nodes are 3767 Wikipedia webpages, and the edges web hyperlinks. Each webpage is described by a 1-dmmeminnn tf-idf vector. We remove several tiny classes from the dataset, so the webpages distribute more evenly across the remaining 9 categories, which are also listed in Table
Large Cora (L-Cora) McCallumzy et al, 1999) is a citation network in which the nodes are comput- science research papers represented by 3780 dimension of tf-idf values. Two papers connected by an undirected edge and only if one cites the other. These citation links form a node graph. The nodes in the dataset originally categorized into topic hierarchical tree with 73 leaves. After removing the papers that belong to no topic and the ones that have no authors or title, a subset of 11881 papers is obtained Saccá al. 2013). These papers are then classified into 10 highest-level topics in the topic hierarchy, as listed in Table 4 We name this dataset "Large Cora" to distinguish from the "Cora" dataset with 2708 papers used in LnjKipf Welling (2017); Yang al. (2016); Sen et al. (2008). Note that we did not test on this "Cora" and the "Citeseer" and "PubMed" datasets as Kipf & Welling (2]7)): Yang al. (2016); [Sen et al. (2008), because the attributes (words) are not provided in these datasets.
The statistics of the datasets are summarized Table 5 where the last row shows the intra-class edge ratio of the node graph of each dataset, which can reflect the quality of the graph.
A.2 VISUALIZATION
In Figure 3
visualize the results of performing graph convolution the node features of 20 NG dataset by t-SNE. It can be seen that graph convolution can successfully reduce the overlap among classes, and 2-D graph convolution more effective than 1-D.
15

---

Under review as a conference paper at ICLR 2020
Table 5: Dataset statistics.
Dataset
20 NG
Wiki
L-Cora
Vertices
18846
3767
11881
Edges
147034
129597
64898
Classes
Features
11697
18316
3780
Connected Components
8504
303
833
Intra-class edge ratio
96.8%
38.0%
76.5%
(a) X
(b) GX
(c) X
(d) GXF
Figure 3: t-SNE visualization "20 NG (a) Raw features; (b) Results of node graph convolution;
(c) Results of affinity graph convolution; (d) Results of 2-D graph convolution (DSGC).
A.3 TRAINING TIME
The training time is summarized in Figure We can see that DSGC is several times faster than GCN, GAT, DGI and GraphSAGE. This is because DSGC only performs graph convolution once before training, while others need to do graph convolution in every training step.
2.5.0
128.0
Trumiig Time's
16.0
2.0
1.0
GCN
GAT
DGI
AGE
DSGC-PPMI
DSGC-Eamb
DSOC-G
USGC-G-PMI
DSQC-G-tmb
L-Cora
20NG
Wiki
Figure 4: Training time of DSGC and baselines.
A.4 PARAMETER SETTINGS FOR NODE CLASSIFICATION
For DSGC, we test positive point-wise mutual information (PPMI) and word embedding based k--N graphs (Emb) for constructing the attribute affinity graph. For constructing the PPMI graph, we set the context window size to 20 and use the inverse distance as co-occurrence weight. For constructing the Emb graph, use GeoVe Pennington al. 2014) to learn word embeddings and set the number of nearest neighbours & = 20. The classifier of DSGC a two-layer multi-layer perceptron (MLP) with 64 hidden units. The MLP is trained with Adam Optimizer for 200 epochs with 0.015 learning rate. For the sake of fair comparison to all baselines and to make sure our method can work well in practice, do not extra labeled data for validation
methods and the baselines, unless
16

---

Under review as a conference paper at ICLR 2020
otherwise stated. Instead, we always select the model with the lowest train loss in the 200 epochs. In each run, the dataset is randomly split into a labeled set and an unlabeled set. The classification results are averaged over 10 runs.
Hyperparameters of all models, including our methods and baselines, are tuned to its best perfor- mance by grid search. DSGC follows the network setting and hyperparameters of GCN, which are 2-layer structure with 64 hidden units and 0.015 learning rate. We set the balancing parameter a in 2018)
LP 100. We largely follow Velickovie of GAT, which are 2 layers, 8 heads, 8 neurons of each head, 0,005 learning rate, 400 epochs, and 0.3 dropout. Our setting of DGI is the same as Velickovic al. (2019), except that the number of hidden units is decreased to 128, so it can be fitted into our GPU memory. Our setting of GraphS is the same as Hamilton et al. (2077) (using 30% data as validation set), except that the number of samples in layer 2 is reduced to 5, also due to limited GPU memory. Parameters of GLP are same as [Li et al. 2019). For LDS Franceschi al. (2099), since it cannot scale to the size of 20 NG (out of GPU memory), we follow the authors to select a 10-category subset of 20 NG. For each dataset, both the training set and validation set for LDS contain 20 labels per class.
network structures and hyperparameters
All models are tested on platform with Intel(R) Xeon(R) CPU E5-2640 v4 @ 2.40GHz and single NVIDIA(R) GeForce(R) GTX 1080 Ti.
A.5 PARAMETER SETTINGS FOR NODE CLUSTERING
For our method DSGC, the attribute affinity graphs PPMI and Emb are constructed in the same way as in node classification. For other baselines. we follow the parameter settings described in the original papers. In particular, for GAE and VGAE (Kipf & Welling 2016). we construct encoders with a 32-neuron hidden layer and 16-neuron embedding layer, and train the encoders for 200 iterations using the Adam algorithm with a learning rate of 0.01. For MGAE (Wang et al.) (017). the corruption level p is 0.4, the number of layers is 3, and the parameter À is 10-P, For ARGE and ARVGE Pann et al. 2018). we construct encoders with a 32-neuron hidden layer and 16-neuron embedding layer. The discriminators are built by two hidden layers with 16 neurons and 64 neurons respectively. We train all the autoencoder-relatee models for 200 iterations and optimize them using the Adam algorithm. The learning rate and the discriminator learning rate are both 0.001. For AGC (Zhang et al. 2019), the maximum iteration number is 60. For fair comparison, these baselines also adopt spectral clustering as DSGC get the clustering results. We repeat each method for 10 times, and show the mean clustering results and the standard deviations.
17

---

Under review as a conference paper at ICLR 2020
APPENDIX B PROOF OF THEOREM IN SECTION 4.1
We suppose that nodes from the same class are connected with probability p, and nodes from dif- ferent classes are connected with probability q. i.e., the adjacency matrix A (1) of node graph obeys
Pr(ais = = p. if Vj 9. y Vj : Pr(a.; 0)
{{
{ 1 p. y Vj
(15)
q, if Vj
and G = D--D--AA A is a stochastic matrix. We also assumes that classes are balanced, i.e., Pr(Y k) 1/K for all k, then we have following theorem.
=
Theorem 1. When is sufficiently small, Z has an IntraVar, Maatar/n//Vaaaa Var ratio less than or equal to that of i.e.
E Var ( Var (E Y
E Var (X] Var (E [X]
(16)
Proof. The proof consists of two parts. In the first part, we prove that inter-class variance is un- changed after node graph convolution, when q approximates 0, i.e.
lim Var (E [ = Var (E [ Y])
(17)
4-0
In the second part, we prove that intra-class variance becomes smaller after node graph convolution, i.e,
E Var (Z] E [Var (x/Y)),
(18)
when is a stochastic matrix.
Part 1. Inter-class variance is unchanged. Since
2i Σ Gijag,
we have
E
[22
k]
Σ E [Giy]
Emay]
# by linearity of expectation
Σ E E[G [
Σ B[Gij] [xy
Ei E [ass] E [ar,] + EimEth E [1:s] E [zy)
Σ, E [Mas]
p PES. E X Y k3 + 9 Ej E [[x,]
K (p 9) + Ng
PE
N R
X = k] + E, E [xx,)] - 1 E j.v, =k E [x,
X (p 9) + Nq
N (p
4 [ = k] + NqE [
R (p 4) Nq
pp 9) [X = k] + KgE
(p 9) + Kg
When y approximates 0, E [z,ly, = k] will approximate E E = k), so
E T = k] Σ
Pr(Z 2:/y; 4)) [2.1y = k]
=
Pr(Z = z X
i
E X Y 1:]
Hence,
Var (E 2Z Y
Var E (X
(19)
18

---

Under review as a conference paper at ICLR 2020
Part 2. Intra-class variance becomes smaller. variables. We have
Denote by Cov (:.)) the covariance of two random
Var
Giyes
= Σ City (ar( + Σ
GiyGaoCv
# property of variance
3
Σ GiyGav Var (xz)) Var (ar))
# property of covariance
2
Σ Guyy Var (a3))
Since
Var (2//g) k) Var
Eisar Bi
G.yy Var (2, = k)
# by the above inequality
Σ Givy Var Y = k)
Var (X = kt)
# since EGi =1
Var (x|Y= = k),
have
Var ( k) = Σ
Pr(Z = 2:/y/ = k) Var (zilys = k:) s Var (X| = k))
(20)
f.
Then we have
E Var (Z|Y)-
Σ Pr(W Var (2 = k))
< Pr(Y = k Var (xlY = k)
# by the above inequality
= E Var (X W)
(21)
Combining Eq. 19 and Eq.
21 we prove that when is sufficiently small,
E Var [Z) Y))
Var (X))
<
(22)
Var EE 2 Y))
Var (E XXY]
19

---

Under review as a conference paper at ICLR 2020
APPENDIX C PROOF OF THEOREM 2 IN SECTION 4.2
Theorem 2. If the attribute graph convolutional filter F is doubly stochastic matrix, then the output of attribute graph convolution has an intra-class variance less than or equal to that of X. i.e.
-
- - = and Fú 20,ii
= E [aa F ('X S E Var (X()).
Proof. We first prove lemma that variance of each class will not increase after attribute graph convolution, i.e. Var (FT random vector. Based on definition of variance in section 4, we have
X| -W=A, =) < Var (X = k). Denote by Cov (-) the covariance matrix of
Var (F X k)) = Tr (Cov (F X| = k))
Tr (F Cov (X = k) F)
# property of covariance
Tr (Cov Y k) FF
# cyclic property of trace
Σ Cov (xi, x - k)) (FF
# property of trace
COV (FF)) )ij
Var (X, V =k
Var (X, k) (FF )
# property of covariance
Σ OiT (FF,(FFF), )is
# o E R" o, & /Var(X
VJ
o FF
S
| l2
eigenvalues of no more than
Σ Var (X+|Y= = k)
Var Y k).
Next, we prove the theorem with the above lemma. Denote by T = Pr(Y = Ic) the portion of each class, then we have
E Var
F T X|X)]
Var F X = k)
Cov (k) (FF )ıs
Var (X = k)
k
E Var (X
Construction of Doubly Stochastic Filter Given an attribute affinity matrix A (2), one could easily construct a doubly stochastic filter F by the following steps: 1) compute graph Laplacian ( (2) A (2); 2) compute doubly stochastic graph matrix Ω = (I + L -2) 3) take Ω as new attribute affinity matrix, choose polynomial p with nonnegative coefficients that sum and let F = p(.)). It can be easily seen that F is doubly stochastic.
20

---

Under review as a conference paper at ICLR 2020
APPENDIX D PROOF OF THEOREM 3 IN SECTION 4.2
Theorem 3. If Fi o 0. |le; - E5ll2 S e, then the distance between ej and ēj = E; Fiye; is also less than or equal i.e.
- 21 E, vFs
lle, -ēyl2 Se
and can be arbitrarily small with proper F. Proof.
||e, - 2 =
Cj Σ Pijei
Σ Fij(ez - -ei)
# since Fo
2
S Σ Fig |le, - -eill2
# Cauchy-Schwanl inequality
$ Σ
Fiye =E
Next, we prove that there exists such an F that is 0. This is equivalent finding doubly stochastic F satisfying E; F.ye, e, for all j. Since F = T is a trivial solution, is solvable. Denote by m the number of attributes, and denote by K the number of classes. This linear system consists of m(K K + 2) equations and m² variables. In most real-world attributed networks, the number of attributes is far greater than the number of classes, so the number of variables in this linear system is greater than the number of equations. Given that it is solvable, it must have infinite number of solutions other than I. Thus, & can be arbitrarily small with a proper
21


Reviews:
[{"review_id": "Hkg7Wc8QqS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This work proposes a 2D graph convolution to combine the relational information encoded both in the nodes and in the edges.\n\nThe basic idea is to reduce the intra-class variance. The authors provide theorems and proofs to support this claim even though it is quite intuitive that smoothing with similar neighbours preserves higher variance with respect to dissimilar neighbours.\n\nIt is not straightforward to understand the limitations on the size of graphs.\n\nThe experimental analysis provides the empirical evidence of the properties of the proposed method. It is worthwhile to remark that connectivity is not necessarily helpful, like in the wiki dataset where connected nodes are not similar.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "H1lM6AJEqB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes a new 2-D graph convolution method to aggregate information using both the node relation graph and the attribute graph generated using, e.g., PMI and KNN. The motivation does make sense that using 1-D convolution along the node dimension might not enough for learning representation for those low-degree nodes. Then, the attribute relation might be used to further smooth the node representation. The assumption could be that documents in a class are likely to consist of similar (related) words. To achieve this, the information aggregation along the node and the attribute dimension is implemented via a product of three matrices, the node graph convolutional filter computed from node affinity matrix, the attribute graph convolutional filter computed the attribute affinity matrix given by PMI or KNN, and the node-attribute matrix, which can be one main contribution. \nBesides, the paper also includes a detailed discussion of intra-class variance reduction. They evaluated the proposed method on both the mode classification and the node clustering against several existing methods, demonstrated that the proposed method almost always outperforms those methods on the two datasets. Overall, it is an interesting paper. \n\nFor aggregating the information along the node dimension and the attribute dimension, as mentioned in the paper, is it possible to firstly do the propagation over the attribute graph using a 1-layer GCN, followed by another 1-layer GCN over the node relation graph, similar to dense graph propagation module in “Rethinking knowledge graph propagation for zero-shot learning”?\n\nThere are two ways to build an attribute graph. The experiments seem to show that the performance is quite different. It would be good to have some discussion on this. \n\nOne motivation is about the low-degree nodes, where the attribute graph might help. It would be good to have a study on the performance of the methods on those low-degree nodes. ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "B1l3QabUKS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors propose a method that incorporates two types of graphs into a graph convolutional networks:\n\n(1) the given graph, which the authors refer to as node affinity graph, and \n(2) the graph that models an affinity between node attribute values.\n\nThe main contribution of their work is a type of graph convolution that combines convolutions operating on these two graphs. \n\nThe paper is densely written and provides several mathematical derivations that are unnecessary to convey the proposed method. Personally, I don't see any benefits in having sections 3.1-3.4 in the main paper. The method actually proposed and evaluated in the paper is described in section 3.5. Sections 3.1-3.4 could be moved to an appendix. They confuse the reader more than they help. (They demonstrate knowledge of graph signal processing on the parts of the authors but little more.)\n\nTrying to provide some theoretical analysis of the proposed method (and standard graph convolutions) by showing that the intra-class variance is reduced is laudable. The theorems, however, only hold under strong assumptions and could, in my opinion, also be moved to an appendix. In the end, they don't have any bearing on the performance of the methods using real-world datasets. Adding some experiments to analyse to what extent the assumptions made by the theorems are met in the given datasets would be an interesting addition to the paper. \n\nThe authors discuss related work sufficiently with one exception: there has been recent work on learning the structure of graph neural networks. See for example [1]. The structure is derived/bootstrapped using node attribute similarities and it is shown that augmenting the graph with these new edges improves accuracy significantly. I would like to point the authors specifically to Figure 2 and Table 1 in said paper, where the authors show that adding edges (e.g., based on some node attribute affinity before or during training) is beneficial and improves accuracy. It would therefore be interesting to see how the authors proposed 2-D convolution would compare to a baseline where the edges based on attribute affinity are added to the original (node affinity) graph. It is a (somewhat simpler) alternative way to combine node affinity and node attribute graphs. \n\n[1] https://arxiv.org/pdf/1903.11960.pdf\n\nThe empirical results are mixed. Due to the numerous different variations of DSGC for which experiments were conducted, the difference between DSGC and existing methods is probably not statistically significant (a bonferroni correction was not performed to counteract the multiple comparisons). \n\nOverall this an interesting paper that introduces a way to incorporate node attribute affinity graphs. It is too densely written and could benefit from moving the theoretical parts to an appendix. They don't really add much to the core of the paper. Moreover, the authors do not consider approaches that also add edges to the graph (based, e.g., on attribute value similarity or during learning, see e.g. [1]) showing that that improves performance even when using a vanilla GCN. A comparison to a baseline that simply adds edges based on attribute affinity to the graph and applied a vanilla GCN should be part of the evaluation. The empirical results are mixed and don't show a clear advantage of the proposed method. \n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies the problem of graph learning with attributes, and propose a 2-D graph convolution that models the node relation graph and the attribute graph jointly. The paper proposes and efficient algorithm and models intra-class variation. Empirical performance on 20-NG, L-Cora, and Wiki show the promise of the approach.

The authors responded to the reviews by updating the paper, but the reviewers unfortunately did not further engage during the discussion period. Therefore it is unclear whether their concerns have been adequately addressed.

Overall, there have been many strong submissions on graph neural networks at ICLR this year, and this submission as is currently stands does not quite make the threshold of acceptance.
Decision: Reject