Title: ATTRIBUTED GRAPH LEARNING WITH 2-D GRAPH CONVOLUTION Anonymous

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.

1. INTRODUCTION:

In an attributed graph, each node is associated with a feature vector, and nodes are connected by edges encoding their relations. Commonly seen attributed graphs include citation networks where each node is a document represented by a bag-of-words 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 friendship, and protein-protein interaction networks where each protein is represented by a 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 of methods (Yang et al., 2015; Pan et al., 2016; Huang et al., 2017) is devoted to learning efficient node representations of an 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 et al., 2006; Weston et al., 2008; Yang et al., 2016) classify nodes in an attributed graph by training a supervised classifier on node features 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 state-of-the-art 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 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 be highly noisy and sparse. For example, in a web graph such as Wikipedia, a 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 networks are scale-free (Albert & Barabási, 2002) , which means there exist many low-degree nodes. Since these nodes may have very few or even no 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 a different dimension -the relations between feature attributes, in addition to node relations. Likewise, a 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 AI category usually contain words such as "learning", "robotics", "machine", "neural", etc. These indicative words for AI 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 in a similar way as the node relations do, only in a different dimension. Importantly, attribute relations can complement node relations in node representation learning. For instance, consider a document that has no links to 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 a 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 on the node dimension can reduce intra-class variance of node features, which explains the success of many existing methods. Further, we show that with a 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.

• Empirical Study: We implement DSGC for node classification and clustering on attributed graphs, and compare it with state-of-the-art 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.

2. RELATED WORKS:

Structural Graph Learning. Methods for structural graph learning only utilize graph structures (node relations). A common approach is to learn smooth low-dimensional embeddings of nodes using Markov random walks (Szummer & Jaakkola, 2002; Perozzi et al., 2014; Grover & Leskovec, 2016) , Laplacian eigenmaps (Belkin & Niyogi, 2004) , spectral kernels (Chapelle et al., 2003; Zhang & Ando, 2006) , autoencoders (Wang et al., 2016; Cao et al., 2016; Ye et al., 2018) and generative adversarial nets (Dai et al., 2018; Wang et al., 2018) . Another direction is graph-based semi-supervised classification, which includes methods based on low-density graph partition (Blum & Chawla, 2001; Blum et 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., 2015; Pan et al., 2016; Huang et al., 2017) or clustering nodes (Xia et al., 2014; Zhou et al., 2010; Li et al., 2018) by applying nonnegative matrix factorization, random walk statistics, or Laplacian eigenmaps on both graph structures and node features. Some node clustering methods use a Bayesian model (Xu et 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., 2011) . Statistical relational learning methods model node relations and features with probabilistic graphical models, e.g., rela-tional Markov networks (Taskar et al., 2002) . Another category of related work is the graph-based semi-supervised node classification methods that exploit both graph structures and node features. For example, iterative classification algorithm (Sen et al., 2008) iteratively classifies an unlabeled node using its neighbours' labels and features. Manifold regularization (Belkin et al., 2006) , deep semi-supervised embedding (Weston et al., 2008) , and Planetoid (Yang et al., 2016) classify node features by training a supervised classifier with a Laplacian or embedding-based regularizer.

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, 2016) proposed to use 1-D graph convolution for attributed graph learning. To avoid the expensive eigen-decomposition, ChebyNet (Defferrard et al., 2016) uses a polynomial filter represented by k-th order polynomials of graph Laplacian via Chebyshev expansion. Graph convolutional networks (GCN) (Kipf & Welling, 2017) further simplifies ChebyNet by designing an efficient layer-wise propagation rule via a 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 et al., 2017) , graph attention networks (Velickovic et al., 2018) , gated attention networks (Zhang et al., 2018a) , FastGCN (Chen et al., 2018b) , dual graph convolutional neural network (Zhuang & Ma, 2018) , stochastic GCN (Chen et al., 2018a) , attributed network representation learning (Zhang et al., 2018c) , LanczosNet (Liao et al., 2019) , deep graph infomax (Velickovic et al., 2019) , graph Markov neural networks (Qu et al., 2019) , DisenGCN (Ma et al., 2019a ), MixHop (Abu-El-Haija et al., 2019) , etc. A recent interesting research direction is on learning graph structures for graph neural networks, e.g., Bayesian GCN (Zhang et al., 2018b) and LDS (Franceschi et al., 2019) . Remarkably, LDS can automatically learn a graph for data samples even when it is not available.

Some attributed graph clustering methods based on 1-D graph convolution also showed promising performance, including graph autoencoder and graph variational autoencoder (Kipf & Welling, 2016) , marginalized graph autoencoder (Wang et al., 2017) , adversarially regularized graph autoencoder 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-dimensional graph Fourier transform can be found in (Kurokawa et al., 2017) . Different from Kurokawa et al. (2017) , here we propose a localized 2-D graph convolution to circumvent the computationally intensive graph Fourier transform. Furthermore, we propose an even simpler dimensionwise separable 2-D graph convolution to 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 G (1) and G (2) , denote the vertex sets by V (1) and V (2) , the edge set by E (1) and E (2) , and the weighted adjacency matrix by A (1) and A (2) . A 2-D graph signal x on (G (1) , G (2) ) is a real-valued function f : V (1) × V (2) → R, which can be conveniently represented in matrix form:

EQUATION

where n = |V (1) | and m = |V (2) |. In this paper, G (1) represents the given node graph; G (2) represents the constructed attribute affinity graph; and X is the node feature matrix, which is a 2-D signal on the two graphs. We call the adjacency matrices A (1) and A (2) node affinity matrix and attribute affinity matrix respectively.

Define the graph Laplacian of G (1) and G (2) as L l = D (1) -A (1) and L r = D (2) -A (2) respectively. Denote by λ i and µ j the eigenvalues of L l and L r , and

U = [u 1 , • • • , u n ] and V = [v 1 , • • • , v m ]

the corresponding eigenbasis respectively, then the n × m outer products u i v j form a basis for the linear space R n×m . It is known as 2-D graph Fourier basis -an analogy of the Fourier basis in classical harmonic analysis in graph domain. The corresponding eigenvalue pair (λ i , µ j ) is known as the frequency of basis matrix u i v j . Then, a 2-D graph signal X can be decomposed as:

EQUATION

Then, we can define 2-D graph Fourier transform as S = U XV , where S is 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 (frequency) 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 domain. 2-D spectral graph convolution is a function conv : R n×m → R n×m that takes signal X as input and outputs a new signal Z:

EQUATION

where p(λ, µ) : R × R → R is the frequency response of the convolution; • is Hadamard (elementwise) product; and P ∈ R n×m with P ij = p(λ i , µ j ) 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 U , V needed for Fourier transform. Similar to (Defferrard et al., 2016) on 1-D graph convolution, here we propose 2-D spatial graph convolution to avoid intensive computation. Without loss of generality, we restrict the frequency response p(•, •) to be a polynomial of two variables λ, µ with parameters Θ ∈ R n×m , i.e., p(λ, µ) = i,j θ ij λ i µ j . Then, the 2-D spectral graph convolution in Eq. ( 3) becomes

EQUATION

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 1 and k 2 the largest exponent of λ and µ in the polynomial p respectively, then i > k 1 and j > k 2 imply θ ij = 0. The convoluted signal z ij of vertex pair (ν

EQUATION

j ) only depends on the neighbourhood of ν

(1) i within k 1 hops and the neighbourhood of ν

(2) j within k 2 hops, so the filter is said to be k 1 -localized on G (1) and k 2 -localized on G (2) , and the size of the kernel

Θ is k 1 × k 2 .

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 1 × k 2 still involves at least k 1 × k 2 matrix multiplications. Inspired by the depthwise separable convolution proposed in (Howard et al., 2017) , we streamline spatial graph convolution by restricting the rank of Θ to be one. Consequently, Θ is decomposed as an outer product of two vectors θ (1) ∈ R n and θ (2) ∈ R m . The frequency response p can be decomposed as a product of two single variable polynomials, i.e., p(λ, µ) = p 1 (λ)p 2 (µ), where p 1 (λ) = i θ

(1) i λ i and p 2 (µ) = j θ

(2) j µ j . Finally, the 2-D spatial graph convolution in Eq. ( 4) becomes Z = GXF , where G = p 1 (L l ) and F = p 2 (L r ).

(5)

We call Eq. ( 5) dimensionwise separable graph convolution (DSGC). The fastest way to compute it only requires k 1 + k 2 matrix multiplications, much less than the k 1 × k 2 matrix multiplications needed by a general 2-D spatial graph convolution.

We call GX node graph convolution and G the node graph convolutional filter. Similarly, we call XF 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. 1 , the node affinity 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 be classified or clustered.

4. INTRA-CLASS VARIANCE REDUCTION BY DSGC:

Given a data distribution, the lowest possible error rate an classifier can achieve is the Bayes error rate (Fukunaga, 2013) , which is caused by the intrinsic overlap between different classes and cannot be avoided. In 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 x i and their labels y i are observations of a random vector X = [X 1 , • • • , X m ] and a random variable Y respectively. We define the variance of random vector X to be the sum of the variance of each dimension X j , i.e., the trace of the covariance matrix of X. According to law of total variance (Grinstead & Snell, 2012), the variance of X can be divided into intra-class variance and inter-class variance: 

EQUATION

i = j G ij x j .

When G is a stochastic matrix, the output feature vector z i is a weighted average of the neighbours of x i . Denote by Z a random vector of z i . Intuitively, as long as each node i has enough sameclass neighbours, Z will have a smaller IntraVar/InterVar 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 A (1) , we have the following theorem.

Theorem 1. When q is sufficiently small, the IntraVar/InterVar ratio of Z is less than or equal to that of X, i.e.,

EQUATION

)

The proof is given in 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 IntraVar/InterVar ratio.

4.2. INTRA-CLASS VARIANCE REDUCTION BY ATTRIBUTE GRAPH CONVOLUTION:

In the following, we show that a proper attribute graph convolutional filter F can also reduce the IntraVar/InterVar ratio. We use the convention that the random vector X is a column vector, and hence the attribute graph convolution XF results in a new random vector F X. We also assume that the node features are mean-centered, i. Then, after attribute graph convolution, the intra-class variance of data becomes

EQUATION

Theorem 2. If the attribute graph convolutional filter F is a 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.,

i

F ij = j F ij = 1 and F ij ≥ 0, ∀ i, j ⇒ E Var F X|Y ≤ E [Var (X|Y)] .

The proofs of Eq. ( 8) and Theorem 2 are given in the Appendices. Eq. ( 8) suggests that to reduce intra-class variance, the attribute affinity graph should connect attributes X i and X j with small or even negative covariance Cov (k) ij . For example, in Figure 1 , the attributes Att3 and Att4 are both indicative of class 2, but negatively correlated w.r.t. class 2, so connecting them in the attribute affinity graph can greatly reduce the intra-class variance of class 2.

To achieve a low IntraVar/InterVar ratio, in addition to reducing intra-class variance, we 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 expectations conditioned on Y. Formally, each attribute X j has K conditional expectations w.r.t. Y, which are denoted as a vector e j = (E [X

j |Y = 1] , • • • , E [X j |Y = K]) ∈ R K .

We have the following. Theorem 3. If ∀F ij = 0, e i -e j 2 ≤ ε, then the distance between e j and e j = i F ij e i is also less than or equal to ε, i.e., e i -e j 2 ≤ ε, ∀F ij = 0 ⇒ e j -e j 2 ≤ ε, and ε can be arbitrarily small with a proper F .

By Theorem 3, 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 interclass 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 a low IntraVar/InterVar ratio and improve performance. Again, it can be seen in Figure 1 that the attributes Att3 and Att4 have exactly the same class means, but are negatively correlated w.r.t. class 2, and connecting them in the attribute affinity graph reduces the intra-class variance of class 2 to 0.

5. 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 an unsupervised manner by applying DSGC on X, i.e.,

EQUATION

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 perceptron 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 Z 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 SEMI-SUPERVISED 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-end semi-supervised learning models including GCN (Kipf & Welling, 2017), GAT (Velickovic et al., 2018) and GraphSAGE (Hamilton et al., 2017) . For example, to incorporate DSGC into the vanilla GCN, we can modify the first layer propagation of GCN as:

EQUATION

where H (1) is the hidden units in the first layer, W (1) ∈ R m×l is the trainable parameters of GCN, and σ is a nonlinear function such as ReLU. Both G and F are fixed filters, where G is the node graph convolutional filter of GCN, and F is the proposed attribute graph convolutional filter.

Importantly, Eq. (10) can be considered as feeding a filtered feature matrix XF 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 XF much easier to classify and guarantees to help train a better model. Further, it can be shown that the model trained by Eq. ( 10) is essentially different from that of GCN almost surely. For GCN, the model is freely chosen from the parameter space W (1) , while the model trained by Eq. ( 10) is restricted in a subspace F W (1) . Since F is low-pass (section 6.2), it is also low-rank, and F W (1) is a small subspace of R m×l 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 F W (1) has measure zero, which is an extremely small subset of R m×l .

6. IMPLEMENTATION OF DSGC 6.1 NODE GRAPH CONVOLUTIONAL FILTERS:

The node affinity graph (A (1) ) is given as part of the dataset. There are various graph convolutional filters available (Li et al., 2019) , e.g., the one used in GCN (Kipf & Welling, 2017) is a 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:

EQUATION

)

where D 1 is the degree matrix of A (1) . We observe in our experiments that the performance of the symmetrically normalized node affinity matrix (GCN filter) is similar.

6.2. ATTRIBUTE GRAPH CONVOLUTIONAL FILTERS:

A key issue in implementing DSGC is to construct the attribute affinity graph (A (2) ). Possible ways of constructing A (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 (PPMI). Positive PMI (Church & Hanks, 1990 ) is a common tool for measuring the association between two words in natural language processing. Given a pair of words w i and w j , the edge weight is defined as the PPMI between w i and w j :

EQUATION

where p(w i , w j ) and p(w i ) are learned by sliding a window over a 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, we use a symmetrically normalized affinity matrix as the filter:

EQUATION

)

where D 2 is the degree matrix of A (2) .

Word embedding based k-NN graphs. Word embedding is a collection of techniques that map vocabularies 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 semantic relations between words (Bakarov, 2018) , they can be used for constructing an attribute affinity graph. With the embedding vectors, we can construct a k-NN graph with some proximity 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., 2019) :

EQUATION

)

where D 2 is the degree matrix of A (2) . Note that the filters in Eq. ( 13) 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 1 since the PPMI affinity matrix is very dense. According to the analysis in Li et al. (2019) , Eq. ( 13) and ( 14) are both low-pass filters.

7. EMPIRICAL STUDY:

To validate the effectiveness of DSGC, we conduct extensive experiments for semi-supervised node classification and node clustering on three large real-world attributed networks including 20 Newsgroups (20 NG) (Lang, 1995) , Wikispeedia (Wiki) (West et al., 2009; West & Leskovec, 2012) and Large Cora (L-Cora) (McCallumzy et al., 1999; Li et al., 2019) .1 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, we demonstrate the variance reduction effect of both node graph convolution and attribute graph convolution. As shown in Figure 2 , 1-D graph convolution with either G or F already greatly reduces the IntraVar/InterVar 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 point-wise mutual information and word embedding respectively. We compare DSGC with the following baselines: 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 al., 2017) , graph attention networks (GAT) (Velickovic et al., 2018) , and deep graph infomax (DGI) (Velickovic et al., 2019) . We also try to incorporate DSGC into GCN, GAT, GraphSAGE, and LDS (Franceschi et al., 2019) (see the experimental setup of LDS in Appendix A.4) as 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 1 , 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. 1) Node graph convolution does not always help. On 20 NG and L-Cora, methods based on 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.0%, much lower than that of 20 NG (96.8%) and L-Cora (76.5%) (see Table 5 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 (XF ) with either PPMI or Emb outperforms all the baselines by a large margin. DSGC (XF ) 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 as 20 NG and L-Cora, DSGC (GXF ) performs much better than either DSGC (GX) or DSGC (XF ). 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, it is comparable with the best baseline. On both datasets, for tasks with 20 labels per class, DSGC (GXF ) with Emb also outperforms all the baselines; for tasks with 5 labels per class, it outperforms all the baselines except DGI. This shows that node graph convolution and attribute graph convolution can complement each other and lead to 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 performance on such a noisy graph, DSGC (XF ) performs better than DSGC (GXF ). • As shown in Table 2 , for node classification with 20 labels per class on all three datasets, after incorporating DSGC, the performances of GCN, GAT, LDS, and GraphSAGE 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 or 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 et al., 2017) , ARGE and ARVGE (Pan et al., 2018) , and AGC (Zhang et al., 2019) . We also compare with spectral clustering (Spectral) that operates on a similarity matrix constructed by applying linear kernel on the node representations.

Performance. To evaluate the clustering performance, we adopt two widely-used metrics (Aggarwal & Reddy, 2014): 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 (XF ) with PPMI already outperforms most baselines by a large margin. On Wiki, DSGC (XF ) with PPMI or Emb significantly outperforms all the baselines. 2) Similar to the classification tasks, 2-D graph convolution is effective. On 20 NG, DSGC (GXF ) with PPMI can further improve upon the very strong performance of DSGC (XF ) and performs the best; On L-Cora, DSGC (GXF ) with PPMI or Emb improves upon either DSGC (GX) or DSGC (XF ) and outperforms most baselines significantly. On Wiki, DSGC (XF ) performs better than DSGC (GXF ), 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 a 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, we 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. 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 performance by grid search. DSGC follows the network setting and hyperparameters of GCN, which are a 2-layer structure with 64 hidden units and 0.015 learning rate. We set the balancing parameter α in LP as 100. We largely follow Velickovic et al. (2018) to set network structures and hyperparameters 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 et 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 GraphSAGE is the same as Hamilton et al. (2017) (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 et al. (2019) , 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.

All models are tested on a 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 a 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., 2017) , the corruption level p is 0.4, the number of layers is 3, and the parameter λ is 10 -5 . For ARGE and ARVGE (Pan et al., 2018) , we construct encoders with a 32-neuron hidden layer and a 16-neuron embedding layer. The discriminators are built by two hidden layers with 16 neurons and 64 neurons respectively. We train all the autoencoder-related 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 to get the clustering results. We repeat each method for 10 times, and show the mean clustering results and the standard deviations.

APPENDIX B PROOF OF THEOREM 1 IN SECTION 4.1

We suppose that nodes from the same class are connected with probability p, and nodes from different classes are connected with probability q, i.e., the adjacency matrix A (1) of node graph obeys Pr(a ij = 1) = p, if y i = y j q, if y i = y j , Pr(a ij = 0) = 1 -p, if y i = y j 1 -q, if y i = y j (15)

and G = D -1 A (1) 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 q is sufficiently small, Z has an IntraVar/InterVar ratio less than or equal to that of X, i.e., E [Var (Z|Y)]

EQUATION

)

Proof. The proof consists of two parts. In the first part, we prove that inter-class variance is unchanged after node graph convolution, when q approximates 0, i.e., lim 

E [G ij ] E [x j ] + j,yj =k E [G ij ] E [x j ] = j,yj =k E [a ij ] E [x j ] + j,yj =k E [a ij ] E [x j ] j E [a ij ] = p j,yj =k E [X|Y = k] + q j,yj =k E [x j ] N K (p -q) + N q = N K pE [X|Y = k] + q j E [x j ] -q j,yj =k E [x j ] N K (p -q) + N q = N K (p -q)E [X|Y = k] + N qE [X] N K (p -q) + N q = (p -q)E [X|Y = k] + KqE [X]

(p -q) + Kq When q approximates 0, E [z i |y i = k] will approximate E [X|Y = k], so 

Combining Eq. ( 19) and Eq. ( 21), we prove that when q is sufficiently small,

EQUATION

:

Note that we did not use the "Cora", "Citeseer" and "PubMed" datasets as in(Kipf & Welling,

2017;Yang et al., 2016;Sen et al., 2008), since the attribute (word) lists are not provided in these datasets.

Figures and Tables:

Figure 1: Illustration of DSGC.

e. E [X] = 0. Denote by Cov (k) = Cov (X|Y = k) the covariance matrix of X w.r.t. each class, and denote by π k = Pr(Y = k) the portion of each class.

Figure 2: IntraVar/InterVar ratios.

Figure 3: t-SNE visualization of "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 TIMEThe training time is summarized in Figure4. 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.

Var (E [Z|Y]) = Var (E [X|Y]) . (17)In the second part, we prove that intra-class variance becomes smaller after node graph convolution, i.e., E [Var (Z|Y)] ≤ E [Var (X|Y)] , (18) when G is a stochastic matrix.Part 1. Inter-class variance is unchanged. Sincez i = j G ij x j , we have E [z i |y i = k] = j E [G ij ] E [x j ]# by linearity of expectation = j,yj =k

[Z|Y = k] = i,yi=k Pr(Z = z i |y i = k)E [z i |y i = k] = i,yi=k Pr(Z = z i |y i = k)E [X|Y = k] = E [X|Y = k] . Hence, Var (E [Z|Y]) = Var (E [X|Y]) . (19)Part 2. Intra-class variance becomes smaller. Denote by Cov (•, •) the covariance of two random variablesij G il Cov (x j , x l ) # property of variance≤ j,l G ij G il Var (x j ) Var (x l ) ij Var (x j |y j = k) z i |y i = k)Var (z i |y i = k) ≤ Var (X|Y = k) . k)Var (X|Y = k) #by the above inequality = E [Var (X|Y)] .

We are interested in the IntraVar/InterVar ratio. Here, we assume that each class of data Pr (X|Y = k) follows a unimodal distribution (e.g. Gaussian, chi-square, Laplace), a class of most common distributions in the real world, and with roughly convex contours. Under this assumption, a low IntraVar/InterVar 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 CONVOLUTIONAs 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 a new feature vector z

Table content: <table/>

Classification accuracy. ± 0.20 8.62 ± 0.20 55.77 ± 0.97 38.97 ± 3.15 9.53 ± 0.05 10.54 ± 0.19 MLP 65.77 ± 0.22 36.10 ± 1.11 51.05 ± 0.71 33.56 ± 2.43 60.86 ± 0.69 29.95 ± 1.04 GLP 76.21 ± 0.18 47.86 ± 1.63 67.58 ± 1.06 51.04 ± 1.61 33.42 ± 1.44 15.38 ± 1.37 GCN 76.14 ± 0.24 47.70 ± 1.64 66.69 ± 0.98 48.62 ± 1.81 48.65 ± 0.65 38.30 ± 1.48 GAT 75.16 ± 0.25 49.14 ± 1.55 66.49 ± 1.01 49.27 ± 2.25 48.88 ± 0.68 36.90 ± 1.75 DGI 73.34 ± 0.27 66.57 ± 0.63 61.39 ± 0.50 54.77 ± 1.24 49.70 ± 1.63 43.64 ± 1.89 GraphSAGE 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) 76.27 ± 0.20 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.22 43.41 ± 0.99 55.34 ± 0.66 38.13 ± 2.20 68.43 ± 0.37 54.25 ± 0.99 PPMI 76.10 ± 0.21 61.45 ± 0.74 58.54 ± 0.79 44.58 ± 2.00 69.53 ± 0.36 58.44 ± 1.48 DSGC (GXF ) Emb 77.38 ± 0.14 55.24 ± 1.21 68.38 ± 0.85 52.87 ± 1.56 58.66 ± 0.65 45.71 ± 1.64 PPMI 81.91 ± 0.20 70.35 ± 0.72 67.60 ± 0.82 54.07 ± 1.13 58.35 ± 0.52 46.72 ± 1.66 and indicate using/not using G or F .

Table content: <table><tr><td>Datasets</td><td/><td colspan="2">20 NG</td><td colspan="2">L-Cora</td><td>Wiki</td><td/></tr><tr><td>Methods</td><td>G F</td><td>20 labels</td><td>5 labels</td><td>20 labels</td><td>5 labels</td><td>20 labels</td><td>5 labels</td></tr><tr><td>LP</td><td/><td>16.39</td><td/><td/><td/><td/><td/></tr></table>

Improve baselines with DSGC. ± 0.25 66.49 ± 1.01 48.88 ± 0.68 PPMI 80.52 ± 0.16 67.00 ± 0.65 55.51 ± 0.38 GCN 76.14 ± 0.24 66.69 ± 0.98 48.65 ± 0.65 PPMI 81.80 ± 0.22 65.83 ± 0.87 60.22 ± 0.71 LDS 75.74 ± 0.68 62.51 ± 0.70 62.89 ± 0.61 PPMI 81.98 ± 0.46 62.94 ± 0.32 66.97 ± 0.63 GraphSAGE 65.73 ± 0.17 57.28 ± 0.71 65.52 ± 0.62 PPMI 76.27 ± 0.33 60.23 ± 1.81 67.26 ± 0.52 indicates not using F .

Table content: <table><tr><td>Methods</td><td>F</td><td>20 NG</td><td>L-Cora</td><td>Wiki</td></tr><tr><td>GAT</td><td/><td>75.16</td><td/><td/></tr></table>

Clustering performance. 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.40 53.27 ± 2.17 36.46 ± 0.06 22.53 ± 0.03 38.10 ± 0.01 36.07 ± 0.02 DSGC (GXF ) Emb 43.40 ± 0.66 50.97 ± 0.58 40.75 ± 0.02 33.05 ± 0.04 30.50 ± 0.01 25.48 ± 0.03 PPMI 52.25 ± 1.97 61.34 ± 1.07 41.24 ± 0.04 30.92 ± 0.01 31.37 ± 0.08 26.06 ± 0.20 and indicate using/not using G or F .

Table content: <table><tr><td>Datasets</td><td/><td colspan="2">20 NG</td><td colspan="2">L-Cora</td><td/><td>Wiki</td></tr><tr><td>Methods</td><td>G F</td><td>Acc(%)</td><td>NMI(%)</td><td>Acc(%)</td><td>NMI(%)</td><td>Acc(%)</td><td>NMI(%)</td></tr><tr><td>Spectral</td><td/><td colspan="6">25.29 ± 1.01 28.18 ± 0.74 28.22 ± 1.01 11.61 ± 0.04 29.25 ± 0.00 21.83 ± 0.00</td></tr><tr><td>GAE</td><td/><td colspan="6">38.92 ± 1.39 44.58 ± 0.40 34.45 ± 0.76 22.38 ± 0.18 33.78 ± 0.32 22.88 ± 0.20</td></tr><tr><td>VGAE</td><td/><td colspan="6">25.04 ± 0.81 25.72 ± 0.77 29.45 ± 1.25 17.53 ± 0.15 33.83 ± 0.45 21.46 ± 0.19</td></tr><tr><td>MGAE</td><td/><td colspan="6">47.83 ± 2.33 56.14 ± 1.00 35.87 ± 0.97 30.57 ± 0.98 32.73 ± 1.16 27.95 ± 2.29</td></tr><tr><td>ARGE</td><td/><td colspan="6">42.04 ± 0.50 44.13 ± 0.91 36.07 ± 0.05 27.74 ± 0.01 26.49 ± 0.10 17.17 ± 0.05</td></tr><tr><td>ARVGE</td><td/><td colspan="6">21.10 ± 0.61 21.79 ± 0.49 26.45 ± 0.03 12.94 ± 0.01 33.82 ± 0.13 21.42 ± 0.11</td></tr><tr><td>AGC</td><td/><td colspan="6">38.83 ± 0.84 47.08 ± 1.57 41.76 ± 0.01 33.65 ± 0.01 32.74 ± 0.01 24.90 ± 0.01</td></tr><tr><td>DSGC (GX)</td><td/><td colspan="6">38.42 ± 0.66 46.28 ± 0.93 38.26 ± 0.02 30.66 ± 0.02 31.43 ± 0.09 24.16 ± 0.18</td></tr><tr><td>DSGC (XF )</td><td/><td/><td/><td/><td/><td/><td/></tr></table>

Dataset statistics.

Table content: <table><tr><td>Dataset</td><td>20 NG</td><td colspan="2">Wiki L-Cora</td></tr><tr><td>Vertices</td><td>18846</td><td>3767</td><td>11881</td></tr><tr><td>Edges</td><td colspan="2">147034 129597</td><td>64898</td></tr><tr><td>Classes</td><td>20</td><td>9</td><td>10</td></tr><tr><td>Features</td><td>11697</td><td>18316</td><td>3780</td></tr><tr><td>Connected Components</td><td>8504</td><td>303</td><td>833</td></tr><tr><td>Intra-class edge ratio</td><td>96.8%</td><td>38.0%</td><td>76.5%</td></tr></table>

Peer review (iclr2020):
This work proposes a 2D graph convolution to combine the relational information encoded both in the nodes and in the edges. The 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. It is not straightforward to understand the limitations on the size of graphs. The 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.