Octave Graph Convolutional Network
Authors: Heng Chang
Yu Rong
Somayeh Sojoudi
Junzhou Huang
Wenwu Zhu
Venue:  (2020)
Keywords: Graph Convolutional Networks
Octave Convolution
Graph Mining

Abstract: Many variants of Graph Convolutional Networks (GCNs) for representation learning have been proposed recently and have achieved fruitful results in various domains. Among them, spectral-based GCNs are constructed via convolution theorem upon theoretical foundation from the perspective of Graph Signal Processing (GSP). However, despite most of them implicitly act as low-pass filters that generate smooth representations for each node, there is limited development on the full usage of underlying information from low-frequency. Here, we first introduce the octave convolution on graphs in spectral domain. Accordingly, we present Octave Graph Convolutional Network (OctGCN), a novel architecture that learns representations for different frequency components regarding to weighted filters and graph wavelets bases. We empirically validate the importance of low-frequency components in graph signals on semi-supervised node classification and demonstrate that our model achieves state-of-the-art performance in comparison with both spectral-based and spatial-based baselines.

Under review as a conference paper at ICLR 2020
OCTAVE GRAPH CONVOLUTIONAL NETWORK
Anonymous authors Paper under double-blind review
ABSTRACT
Many variants of Graph Convolutional Networks (GCNs) for representation learn- ing have been proposed recently and have achieved fruitful results in various do- mains. Among them, spectral- based GCNs constructed via convolution theo- rem upon a theoretical foundation from the perspective of Graph Signal Processing (GSP). However, despite most of them implicitly erate smooth representations for each node, there is limited development on the full usage of underlying information from low-frequency components. Here, we first introduce the octave convolution on graphs in spectral domain. Accordingly. we present Octave Graph Convolutional Network (OcrGCN), novel architecture that learns representations for different frequency components regarding weighted filters and graph wavelets bases. We empirically validate the importance of low- frequency components in graph signals on semi-supervised node classification and demonstrate that our model achieves state-of-the-an performance comparison with both spectral-based and spatial-based baselines.
low-pass filters that gen-
INTRODUCTION
The family of Graph Convolutional Networks (GCNs) (Zhang et al.) 2018), which generalizes the traditional Convolutional Neural Networks (CNNs) from Euclidean structure data to graphs, has achieved remarkable success in various application domains, including but not limited social
networks (Chen et al.) [0188), computer vision (Kampffmeyer et al. 2018). text classification (Yao al. 2019) and applied chemistry (Liao et al. 2019).
Existing methods of GCNs design falls into two categories: spatial-based based methods and spectral- based methods (Wu et al., 2019). On the surface, the spatial-based models directly perform infor- mation aggregation through graph topology. However, this aggregation can be viewed as a simplified convolution operation on spectral domain with the theoretical foundation in Graph Signal Process- ing (GSP). GSP extends the concepts in Discrete Signal Processing (DSP) and focuses analyzing and processing data points whose relations are modeled as graph (Shuman et al., 2013 Ortega et al., 2018). In standard signal processing problems, the underlying "real signal" is usually assumed to have low frequencies (Rabiner& & Gold 1975). Recent works (Wu et al. 2019 Machara 2019) re- veal that the spectral-basede GCNs can be viewed an implicit low-pass-type filter based denoising mechanism on the spectral domain. However, there is still a lack of the explicit learning architec- ture of GCNs to extract the beneficial information from low-frequency while making full use of the high-frequency under certain scenarios.
Considering the signal processing problem in computer vision, a natural image can be decomposed into low spatial frequency component containing the smoothly changing structure, e.g., back- ground, and a high spatial frequency component describing the rapidly changing fine details, e.g., outlines. To accommodate with this phenomenon. (Chen et al. 2019) proposed Octave Convolution (OctConv) to learn the octave feature representations, which factorizes convolutional feature maps into two groups at different spatial frequencies and process them with different convolutions at their corresponding frequency. Similarly, the octave mechanism is observed in graph representational learning more naturally. The eigenvectors associated with small eigenvalues carry smoothly varying signal, encouraging nodes that are neighbors to share similar values. In contrast, the eigenvectors associated with large eigenvalues carry sharply varying signal across edges (Donnat et al.) 2018). Accordingly, extending octave convolution from images to graphs sheds light on the explicit learning of GCNs regarding the representation of different frequencies.

---

Under review as a conference paper at ICLR 2020
Isput Graph
Octave Cunvolution
Low Umw-Tnepancy Componeres
Lows Fregurguyyyy rmprosmtttioo
Paoling
((W))
compononts
reprssetations
Figure 1:
The overview of octave convolutional learning on graphs in spectral domain.
Different from the scale-space theory (Lindeberg. 2013) utilized in OctConv (Chen al. 2019
to define the low- and high-frequene spaces, graph signal processing (GSP) provides us a way to directly divide the low- and high-frequency components based on the ascending ordered eigenvalues of Laplacian. Inspired from this, we propose to consider the octave feature in the spectral domain to construct new graph convolutional model: Octave Graph Convolutional Network OctGCN. In OctGCN, with particular design of filters for different spectrum, we allocate different weights on low- and fighffrequency. Spectral graph wavelets are chosen as feature transformation bases due to their local and sparse property. Two parameters further introduced to construct the filters for reducing the parameter complexity to the same as (Kipf & Welling, 2017). which critical when labels of training data limited. Meanwhile, importance of low and high pass filters. Figure provides the overview of the design of OcIGCN in spectral domain. We validate the effectiveness of our model via experiments on semi-supprvised node classification tasks, where the expressive power of GCNs is crucial to capture the underlying beneficial information in graph signals. Our results confirm the importance of low-frequency in graphs and bring interpretability to the innate character of GCNs. In addition, empirical results show that our proposed method consistently rivals the state-of-ar methods from both spectral-based and spatial -basel baselines on real-world datasets.
employ the attention mechanism learn the
RELATED WORK
Spectral convolutional networks on graphs. Existing methods of defining a convolutional op- eration on graphs can be broadly divided into two categories: spectral based and spatial based methods (Zhang et al.) 2018). We focus on the spectral graph convolutions in this paper. Spec- tral CNN (Bruna et al. 2014) first attempts to generalize CNNs to graphs based on the spectrum of the graph Laplacian and defines the convolutional kernel in the spectral domain. (Boscaini et al.) 2015) further employs windowed Fourier transformation to define a local spectral CNN approach. ChebyNet (Defferrard et al.) 2016) introduces fast localized convolutional filter on graphs via Chebyshev polynomial approximation. Vanilla GCN (Kipt Welling 2017) further extends the spectral graph convolutions considering networks of significantly larger scale by several simplifi- cations. (Khasanova Frossard 2017) learns graph-based features on images that are inherently invariant isometric transtormations. Cayleynets (Levie et al. 2018) alternatively introduce Cayley polynomials allowing to efficiently compute spectral filters on graphs. Lanczos algorithm is utilized LanczosNet (Liao al.) (2019) to construct low-rank approximations of the graph Laplacian for convolution. SGC (Wu et al. 2019) further reduces the complexity of Vanilla GCN by successively removing the non-linearities and collapsing weights between consecutive layers. Despite their effec- tive performance, all these convolution theorem based methods lack the strategy to explicitly treat low- and high-frequene components with different importance.
Spectral graph wavelets. Theoretically, the lifting scheme is proposed for the construction of wavelets that can be adapted to irregular graphs in (Sweldens) 1998). (Hammond et al. 2011) defines wavelet transforms appropriate for graphs and describes a fast algorithm for computation via fast Chebyshev polynomial approximation. For applications, (Tremblay & Borgnat 2014) utilizes graph wavelets for multi-scale community mining and obtains local view of the graph from each node. (Donnat et al., (2018) introduces the property of graph wavelets that describes information diffusion and learns structural node embeddings accordingly. GWNN (Xu et al.) 2019a) first attempts to construct graph neural networks with graph wavelets. These works emphasize the local and sparse property of graph wavelets for graph signal processing both theoretically and practically.
2

---

Under review as a conference paper at ICLR 2020
Octave feature representation. In computer vision, (Chen al. 2019) first defines octave feature representations based on scale-space theory and reduces spatial redundancy of vanilla CNN models. (Durall et al. 2019) further leverages octave convolutions for designing stabilizing GANs. To our knowledge, this the first time that octave feature representations are considered in irregular graph domain and established with graph convolutional neural networks.
3 PROPOSED APPROACH
3.1 PRELIMINARY
We denote G E} as an undirected graph, where [V| = n is the set of n nodes, and E the set of edges. The adjacency matrix is defined as A with A., = A,, describing the edge connecting node and node j. The graph Laplacian matrix
defined as the difference = D A, where D2 = -; Aig is a diagonal degree matrix. The normalized graph Laplacian matrix is referred
as In - D AD- where In is the identity matrix. The graph Laplacian L can be decomposed into its eigenvalue components, L UAU such that for the set of eigenvalues in ascending order {Ai]==0 12-1 An S A I ... S An-1, the diagonal eigenvalue matrix is defined as A = diag.Aa.....,. 1 and U (u1, u2,..., u,,) is the eigenvector matrix.
Since L is real symmetric matrix, it has real, non-negative eigenvalues { Ao S A1 S S An known as the frequencies of graph. These eigenvalues have associated a complete set of orthonormal eigenvectors in U, identified Laplacian eigenvectors. In Graph Signal Processing (GSP), we denote frequency components with small/large eigenvalues of Laplacian as low/high frequencies. Given a signal and graph Laplacian L, the Graph Fourier Transform with respect to L is defined as the signal æ U æ, and the inverse (i)GFT of æ with respect to L U (Shuman et al. 2013).
(GFT) of
3.2 SPECTRAL GRAPH CONVOLUTION
The spectral convolution on graphs is normally defined as the multiplication of signal on every node with diagonal filter go diag(0) parameterized by in the Fourier domain:
Ug U x,
Ge The filters are usually understood as a function of the eigenvalues. Inspired by (Maehara 2019),
decompose the spectral convolution process graphs from the perspective of GSP four steps: 1. Compute the graph bases U: 2. Graph spectral transform on signal x with U 3. Filtering with go: 4. Reconstruct the signal features in the spatial domain with U. In this sense, the design of filter is essential to the performance of spectral convolution. Broadly, the filter design can be divided into two categories: it is either learned by the neural network (Bruna al., 2014 Xu al.
2019a) or directly fixed as the eigenvalues via approximation (Kipf & Welling 2017 Wu et al.
2.19). In this paper, we will focus on the first kind.
Spectral CNN (Bruna et al. 2014) generalizes the convolutional net by operating on the spectrum of weights, given by the ordered eigenvectors of graph Laplacian. The structure of k-th layer is constructed as:
x - 2 EFtTU
F 2=1
j 1,
(2)
where X E TRRXP is the signal with p input channels and X E RR the convolved signal matrix. X [:.4] and X- are the i-th and j-th column of X and x respectively. go of k-th layer is defined as Fk. which is a diagonal filter matrix be learned for each input channel in spectral domain. h is real valued nonlinear activation function, e.g., ReLU(-) max (0, 1). Thus. the parameter complexity of Spectral CNN is On x p x q), which generally demands a huge amount of training data for parameter learning.
[[]]
3.3 WHY SPECTRAL GRAPH WAVELET?
Graph wavelet neural network (GWNN) Xu et al. 2019a) expands the spectral convolution from Fourier transformation wavelet transformation. Let gs (A) -> be a heat kernel filter with
3

---

Under review as a conference paper at ICLR 2020
scaling parameter s. In GSP (Hammond et al.) 2011 Shuman et al. 2013), the spectral graph wavelet Vas is defined as the signal resulting from the modulation in the spectral domain of a signal æ centered around the associated node i. Then, the graph wavelet transform is conducted by employing a set of wavelets 1/.- = (#s1, 2/2,.... Vsn) as bases. Formally, the spectral graph wavelets are given as:
Ve = Ug.U",
where U is Laplacian cigenvectors of L = D A or normalized Laplacian L = - AD à 9s diag( [g (A1), 9, (A2), ..... Is (A..) is scaling matrix with heat kernel. The inverse of graph wavelets ,, obtained by simply replacing the ga(A) in vhs with g-(-)) corresponding to the heat kernel (Donnat et al. (018). Similarly, smaller indices in graph wavelets correspond to low- frequency components and vice versa.
Similar to GFT, after replacing the Fourier bases with spectral graph wavelets, the graph wavelet transformation of a signal x on graph is defined as x = v5y x and the inverse graph wavelet trans- form is = &. Replacing the graph Fourier transform in spectral convolution (Equation ! with graph wavelet transform, the graph wavelet convolution can be obtained as:
g * "
The benefits that spectral graph wavelet bases have over Fourier bases mainly fall into two aspects: 1. Given the sparse real-world networks, the graph wavelet bases are usually much more sparse than Fourier bases, e.g., the density of V. is 2.8% comparing with 99.1% of U (Xu et al. (019a). The sparseness of graph wavelets makes them more computationally efficient for use. 2. In spectral graph wavelets, the signal vi resulting from heat kernel filter Is is typically localized on the graph and in the spectral domain (Shuman al., 2013). By adjusting the scaling parameter s, one can easily constrain the range of localized neighborhood. Smaller values of generally associate with smaller neighborhoods.
Employing the same strategy as in Spectral CNN (Bruna et al. 2014), GWNN designs the same diagonal filter F to be learned for each input channel. The structure of k-th layer of GWNN
X = to (1.... [Sl
F F x (a))
1=1, : 4
Note that both Spectral CNN and GWNN employ the same filters for learning full frequency com- ponents. As mentioned before, the parameter complexity of Spectral CNN is large since each pair of input and output channel requires learning an individual diagonal filter matrix 2.j- GWNN further reduces the parameter complexity by dividing each layer into two components: feature transforma- tion and graph convolution:
feature transformation X² = =
(6)
graph convolution : x++1 = h (=,
where W E IR is the feature transformation parameter matrix similar to Vanilla GCN Kippf & Welling 2017). In such a way, the feature transformation operation is detached from graph convolution and the parameter complexity is decreased from from O(n x q) to O( + x q)
3.4 OCTAVE CONVOLUTIONAL LAYER
In contrast to the scale-space theory-based octave feature representation utilized in computer vi- sion (Lindeberg] 2013), Graph Signal Processing provides us a more principle way in the spectral domain. To better capture the different importance of low- and high- frequency components and combining the benefits of graph wavelets, we can naturally construct each layer in an octave convo- lution manner by learning two different filters as:
feature transformation:
X X*W,, = X*W
(8)
graph convolution: x = tha F. f XE x F F
where FÊ E dxd and F&- E (n--xx)))))))))) d) are the diagonal filter matrix for graph convolution to be learned with different weights for low- and high- components, respectively. d is the parameer
4

---

Under review as a conference paper at ICLR 2020
Table 1:
The overview of dataset statistics.
Dataset
Nodes
Edges
Classes
Features
Label rate
Citeseer
3,327
4,732
3,703
0.036
Cora 2,708
5,429
1,433
0.052
Pubmed 19.717
44,338
3
500
0.003
to select the proportion d/ n of frequency components. dss and VaL are the corresponding low- and high- frequency graph wavelet bases. Further, with a pooling operation on the outputs and non-linear activation function, the structure of the k-th layer in our structure can be defined as
X = h (oooling((.1 X V.H V F
(10)
We refer this proposed architecture as Octave Graph Convolutional Network (OcrGCN).
Since the parameters in the diagonal convolution filtering kernels could be huge especially for large graphs, the graph-based semi-supervised learning might prohibit the parameter learning due to the limited amount of training data. To mitigate this issue, we further reduce the parameter complexity by constructing the graph convolution kernel F with two parameters ag and ag, and keeping the same weight matrix W shared between low- and high- frequency components
x = 1n (oPoolling(var
Val x W
disH
x w
OHH
(11)
For the learning of weights of low- and high-frequency components as and an, we adopt the attention strategy to constraint them within the scale of (0, 1):
exp (a..)
0, = softmax(a.) = E. exp(a.))
* I, H
Hence, introduce three more syper-parameters to be tuned: a and aH control the importance of low and high frequency components, and parameter d specify the ratio low frequencies we
expect to represent the graph. In this way, reduces the parameter complexity from O(n n + p g) in GWNN (Xu et al. 2019a) to O(p x 4), which is the same as Vanilla GCN (Kipf & Welling 2017
3.5 FAST SPECTRAL GRAPH WAVELET APPROXIMATION VIA CHEBYSHEV POLYNOMIALS
Directly computing the transformation according Equation 3 is intensive for large graphs since diagonalizing Laplacian commonly requires (n3) operations. Luckily, (Hammond et al. 2011) provides us method to fast approximate the spectral graph wavelet via Chebyshev polynomials. Let be the fixed scaling parameter in the heat filter kernel gs (A) e - and M be the degree of the Chebyshev polynomial approximations for the scaled wavelet (Larger value of M yields more accurate approximations but higher computational cost in opposite), the graph wavelet is given by
M
co + Σ Ci).) i=1
1/ = 2
C Jo cos (ccos0++) 2e 2 ----+
(12)
where -= 2------11 I, and J+(-)) is the Bessel function of the first kind. The proof can be referred Amps to (Hammond et al., 201T). With this Chebyshev polynomial approximation, the computational cost of spectral graph wavelets is decreased to [ +M xn). Due the real world graphs usually sparse, this computational difference can be very significant.
EXPERIMENTS
4.1 DATASETS
We evaluate our proposed OcrGCN on semi-supervised node classification task. The experimen-
tal setup is closely followed (Yang al. 2016 Kipf & Welling 2017). Statistical overview of
5

---

Under review as a conference paper at ICLR 2020
Table 2: Experimental results (in percent) semi-supervissd node classification.
Model
Citeseer
Cora
Pubmed
LP (Zhu 2003)
45.3
68.0
63.0
ICA (Lu & Getoor (003)
69.1
75.1
73.9
ManiReg [Belkin et 2006)
60.1
59.5
70.7
SemiEmb WWsstnn et al.
2012)
59.6
59.0
71.1
DeepWalk (Perozzi al.
2014
43.2
67.2
65.3
Planetoid Yang et al. 2016)
64.7
75.7
77.2
Spectral CNN (Bruna et al.
2014)
58.9
73.3
73.9
ChebyNet (Defterrard et
2016
69.8
81.2
74.4
Vanilla GCN (Kipt & Welling
2017
70.3
81.5
79.0
GWNN (Xu al.
2019a
71.7
82.8
79.1
LNet (Liao et al. 2019)
7
AdaLNet (Liao
2019
68.7
8.14
7.41
SGC (Wu et al.
20199)
7.1
8.0
0.0
MoNet (Monti et al.
(017)
8..7
78.8
GAT (Velčković al.
2018
0.7
8.70
79.0 0.3
GIN
Xuu et al.
2019b)
66.1
1..6
77.0 = 1.2
DGI (velickovic et al. 2019
11.8
8.6
76.8 = 0.6
OctGCN (this paper)
72.1 0.2
83.5 0.2
80.5 0.3
datasets is given in Table Three real-world datasets are chosen as benchmarks: Citeseer, Cora and Pubmed (Sen et al., 2008). In these citation networks, nodes are documents with corresponding bag-of-words features and edges are citation links. Label rate denotes the ratio of labeled nodes fetched in training process. We keep the label rate consistent with the classic public split, which is 20 labeled nodes per class in each dataset for training. Meantime, the test set contains 1000 labeled samples for prediction accuracy evaluation, and the validation set includes 500 labeled samples for determining
4.2 BASELINES
We first compare against traditional baselines, i.e., label propagation (LP) (Zhu et al. 2003) iterative classification algorithm (ICA) (Lu Getoor] 2003), manifold regularization (ManiReg) (Belkin al. 2006), semi-supervised embedding (SemilEb) (Weston et al.) 22012) skip-gram based graph embeddings (DeepWalk) (Perozzi et al., 2014) and Planetoid (Yang et al.) 2016).
Then we compare the most recent and state-of-the-art baselines from both spectral and spatial graph neural networks, since they are shown effective for semi-supervised settings. For spectral approaches based convolution theorem,
compare OctGCN with the Spectral CNN (Bruna et al. 2014), ChebyNet (Defferrard et al. 2016), Vanilla GCN (Kipf & Welling 2017). GWNN (Xu al. 2019a), ) LNet/AdalNNet (Liao et al. 2019) and SGC (Wu al. 2019). For spatial based meth-
ods, we select the MoNet (Monti et al. 2017). GAT (Veličković et al. 2018). GIN (Xu et al. 2019b)
and DGI (Velickovic al. 2019) comparisons.
4.3 EXPERIMENTAL SETUP
For all experiments, a 2-leyer network of our model is constructed using TensorFlow (Abadi al. 2015) with 64 hidden units. We train our model utilizing the Adam optimizer (Kingma & Ba 2014) with an initial learning rate Ir 0.01. We terminate training if validation accuracy does not improve for 100 consecutive steps, and most runs finish in less than 200 steps expected. We initialize the weights matrix following (Glorot Bengio 2010), employ 5 x L2 regularization on weights and dropout input and hidden layers to prevent overfitting (Srivastava al. 2014).
For syper-parameters for constructing wavelets vh, we adopt the selection the scaling parameter and sparseness threshold (the elements of th set to 0 when smaller than t) in (Xu et al. 2001a),, i.e., s 0.7 t = x 10 for Citeseer, s = 1.0 = 10-4 for Cora and s 0.5 1 x 10-7 for Pubmed, since both smaller s and are shown not sensitive datasets. For

---

Under review as a conference paper at ICLR 2020
Boot Popkait
cleeeet
0.000
0.4075
pubmed
0.730
Claneliialion Aquurocy
0.000
MM
0.3550
Cansaficatio
Classiication
0211
2,005
0:6000
0.115
8.00
6.7955
0.11
3,855
0.160
9810
0.792
0.805
0.7920
022
6.6
02
fow--rrueency components
Fraction low-frqquency components
Fracton low-traqunncy components
Figure 2: The performance of learned OctGCN w.r. the proportion of low-frequency components. The best fraction is marked with the red vertical line.
Learned weights oz and of OcIGCN for low and high frequency w.r. the best fraction of low frequency components d/n (number followed after the name of datasets).
Table 3:
Dataset
Citeseer (15%)
Cora (5%)
Pubmed (10%)
Octave filter weights
0,
O,Fr
0,
at
Learned value
0.838
0.162
0.722
0.278
0.860
0.140
Table 4:
The mean Silhouette Coefficient of learned samples. Larger is better.
Dataset
Citeseer
Cora
Pubmed
Model
Vanilla GCN
GWNN
OctGCN
Vanilla GCN
GWNN
OcGGN
Vanilla GCN
GWNN
OcrGCN
Silhouette score
0.038
0.050
0.083
0.119
0.153
0.220
0.110
0,130
0.171
the only hyper-parameter of OctGCN, the optimal proportion d/n n of low-frequency components for each dataset, determined through grid search and studied in next Section. The weights of low- and high-frequency components a and a are both initialized with and learned automatically, In experiments, Max-pooling is chosen to demonstrate the importance the low-frequency components.
4.4
EXPERIMENTAL RESULTS
4.4.1 PERFORMANCE OF OctGCN ON NODE CLASSIFICATION
In Table we demonstrate how our model performs on public splits taken from (Yang et al., 2016). The results of baselines strietly consistent with the numbers from literature. With the limited information given in semi-supervised learning, We achieve average test accuracy of 72.1% 1%, 83.5%, and 80.5% on Citeseer, Cora and Pubmed, respectively. As OctGCN learned the octave feature representations for graph in spectral domain, it can demonstrate the meaningful information extracted from the underlying "true signal" from low-frequency over high-frequene This is the main reason that explains why OctGCN outperforms other bascline methods.
4.4.2 ANALYSIS ON INTERPRETABILITI
In Figure how the proportion d/ of low-frequency components affect the performance studied. fine-tune the proportion in a range of 50%,5%% ....... 95%). The best proportion of low-frequency components are 15%, 5%, and 10% for Citeseer, Cora and Pubmed, respectively. The learned weights low- and fighhfrreuenccy components aj and a w.r.t the best proportion for each dataset demonstrated in Table B accordingly. It's clearly to note that the small proportion of low- frequency components are essential to the learning octave feature representation. The results are in line with the importance of low-frequency in GSP and bring interpretability to the nature of GCNs.

---

Under review as a conference paper at ICLR 2020
(a) Vanilla GCN on Citeseer
GWNN on Cileseer
(c) OcIGCN on Cileseer
(d) Vanilla GCN on Cora
(e) GWNN on Cora
(I) OcIGCN on Cora
(g) Vanilla GCN on Pubmed
(h) GWNN on Pubmed
(i) OctGCN on Pubmed
Figure 3: The t-SNE visualization of OcGGN comparing with spectral convolution based baselines. Each color corresponds to different class that the embeddings belongs to.
4.4.3 T-SNE VISUALIZATION OF LEARNED EMBEDDINGS
Jable|ppresent the mean Silhouette Coefficient (Rousseeuw 1987 over learned samples, larger the silhouette score is, better the clustering performs. We choose two representative baseline meth- ods, i.e., Vanilla GCN (Kipf & Welling 2017) and GWNN (Xu et al. 2019a) for comparison. We indicate that OcGCC achieves the best quality of embeddings. Figure 3 depicts the t-SNE visualization (Maaten & Hinton 2008) of learned embeddings on all three citation datasets. We visualize the local and sparse property of spectral graph wavelets that utilized in GWNN and OcIGCN. Further, the intersections of different classes are more separated in the results our Oct- GCN, since the octave feature embeddings learned from our model tend capture the importance information in low- ow-frequency components and effectively alleviate the noise from high-frequenge
5 CONCLUSION
In this paper, we propose OctGCN, a novel spectral- graph convolutional neural network to learn the representation of graph with respect different frequency components. By distinct design of filters for low- and high-frequency our model can effectively capture the octave feature repre- sentations and enhance the interpretability of GCNs. To the best of our knowledge, this the first attempt on octave convolution for graphs. An interesting direction for future work is to extend the definition of octave convolution from spectral domain to spatial domain, in order to pursue more efficient architectures for learning with graphs.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Martin Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, Tensorflow: Large-scale machine learning heterogeneous systems, 2015. Software available from tensorflow. org, 1(2), 2015.
Mikhail Belkin, Partha Niyogi, and Vikas Sindhwani. Manifold regularization: A geometric frame- work for learning from labeled and unlabeled examples. Journal of Machine Learning Research, 7:2399-244 2434, 2006.
Davide Boscaini, Jonathan Masci, Simone Melzi, Michael M Bronstein, Umberto Castellani, and Pierre Vandergheynst. Learning class-specific descriptors for deformable shapes using localized spectral convolutional networks. In Computer Graphics Forum, volume 34, pp. 13-23. Wiley Online Library, 2015.
Joan Bruna, Wojeiech Zaremba, Arthur Szlam, and Yann Lecun. Spectral networks and lo- cally connected networks on graphs. In International Conference on Learning Representations (ICLR2014), CBLS, April 2014, pp. tttp-oopenrevew. 2014.
Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, and Xu Sun. Measuring and relieving the over-smoothing problem for graph neural networks from the topological view. arXiv preprint arXiv:1909.05211, 2019.
Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: Fast learning with graph convolutional networks via importance sampling. In ICIR 2018: International Conference on Learning Representations 2018, 2018. URL httttttps:// /acd/emic microsoftt,
com/ wwt.c//.pppppccettccec
Yunpeng Chen, Haoqi Fan, Bing Xu, Zhicheng Yan, Yannis Kalantidis, Marcus Rohrbach, Shuicheng Yan, and Jiashi Feng. Drop an octave: Reducing spatial redundancy in convolutional neural networks with octave convolution. arXiv preprint arXiv: arXiv:1904.080 1904.05049, 2019.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. neural information processing systems, pp. 3844 3852, 2016.
Claire Donnat, Marinka Zitiik, David Hallac, and Jure Leskovec. Learning structural node embed- dings via diffusion wavelets. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1320-1329, 2018.
Ricard Durall, Franz-Josef Pfreundt, and Janis Keuper. Stabilizing gans with octave convolutions. arXiv preprini arXiv:1905.1222 1905. 2019.
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pp. 249-256, 2010.
David K. Hammond, Pierre Vandergheynst, and Rémi Gribonval. Wavelets on graphs via spectral graph theory. Applied and Computational Harmonic Analysis, 30(2):129-1500 2011.
Michael Kampffmeyer, Yinbo Chen, Xiaodan Liang, Hao Wang, Yujia Zhang, and Eric Xing. Re- thinking knowledge graph propagation for zero-shot learning. arXiv preprint arXiv: arrXiv/805..11 1805.11724 2018. URL/ttts:: /ttp///ccammcccccm/cm www.mmmsccc....coooooomomomo wtt.:como//paaa http://tcccccmppppe///333322222
Renata Khasanova and Pascal Frossard. Graph-based isometry invariant representation learning. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 1847- 1856. JMLR. org, 2017.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint a4Xiv:1412.c 69800 2014.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. international conference learning representations, 2017.

---

Under review as a conference paper at ICLR 2020
Ron Levie, Federico Monti, Xavier Bresson, and Michael M Bronstein. Cayleynets: Graph con- volutional neural networks with complex rational spectral filters. IEEE Transactions on Signal Processing, 67(1):97-109, 2018.
Renjie Liao, Zhizhen Zhao, Raquel Urtasun, and Richard S. Zemel. Lanczosnet: Multi-scale deep graph convolutional networks. In ICLR 2019: 7th International Conference on Learning Repre- sentations, 2019.
Tony Lindeberg. Scale-space theory in computer vision, volume 256. Springer Science & Business Media, 2013.
Qing Lu and Lise Getoor. Link-based classification. In ICML 2003, pp- 496-503 2003.
Laurens van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of machine learning research, 97Nv))25579 2008.
Takanori Maehara. Revisiting graph neural networks: All we have is low-pass filters. arXiv preprint 1rXivv1905.09550, 2019.
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 2017 IEEE Conference on Computer Vision and Puttern Recognition (CVPR), pp. 5425-5434, 2017.
Antonio Ortega, Pascal Frossard, Jelena Kovačević, José MF Moura, and Pierre Vandergheynst. Graph signal processing: Overview, challenges, and applications. Proceedings of the IEEE, 106 (5):008-224 -288 2018.
Bryan Perozzi, Rami AI-Rfou, and Steven Skiena. Deepwalk: Online learning of social repre- sentations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 701-710. ACM, 2014.
Lawrence R Rabiner and Bernard Gold, Theory and application of digital signal processing. Engle- wood Cliffs, NJ, Prentice-Hall Inc., 1975. 777 p., 1975.
Peter Rousseeuw. Silhouettes: graphical aid the interpretation and validation of cluster analy- sis. Journal of computational and applied mathematics, 20:53-65, 1987.
Prithviraj Sen, Galileo Mark Namata, Mustafa Bilgic, Lise Getoor, Brian Gallagher, and Tina Eliassi-Rad. Collective classification in network data, Ai Magazine, 29(3):93-106, 2008
David I Shuman, Sunil K. Narang, Pascal Frossard, Antonio Ortega, and Pierre Vandergheynst.
The emerging field of signal processing graphs: Extending high-dimensional data analysis to networks and other irregular domains. IEEE Signal Processing Magazine, 30(3):83-98, 2013.
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: simple way prevent neural networks from overfitting. The journal of machine learning research, 199)):129-1958, 2014.
Wim Sweldens. The lifting scheme: A construction of second generation wavelets. SIAM journal on mathematical analysis, 29(2):511-546, 1998.
Nicolas Tremblay and Pierre Borgnat. Graph wavelets for multiscale community mining. JEEE Transactions Signal Processing, 62(20):5227-5239) 2014.
Petar Velickovie, William Fedus, William L. Hamilton, Pietro Liò, Yoshua Bengio, and R. Devon Hjelm. Deep graph infomax. In ICLR 2019: 7th International Conference on Learning Repre- sentations, 2019.
Petar Veličkovié, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In ICLR 2018: : International Conference on Learning Repre- sentations 2018, 2018.
Jason Weston, Frédéric Ratle, Hossein Mobahi, and Ronan Collobert. Deep learning via semi- supervised embedding. Neural Networks: Tricks of the Trade (2nd ed.), pp. 639-655, 2012.
10

---

Under review as a conference paper at ICLR 2020
Table 5: The average gap of MAD and INR between the low- and high- frequency components in benchmark datasets. Smaller MAD indicates better smoothness and larger INR indicates that the frequency components contain richer information.
Dataset
Citeseer
Cora
Pubmed
MADL - MADH
-3.7 x 10-4
9.0 x 10-3
1.. x 10-5
INR, IN
0.018
0.002
0.005
Felix WU, Amauri H. Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Q. Weinherger. Simplifying graph convolutional networks. In 2C19. Thirty-sixth International Conference on Machine Learning, pp. 6861-6871, 2019.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S Yu. A comprehensive survey on graph neural networks. arXiv preprint arXiv:1901.00550 2019.
Bingbing Xu, Huawei Shen, Cao, Yunqi Qiu, and Xueqi Cheng. Graph wavelet neural network.
international conference on learning representations, 2019a.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks. ICLR 2019 7th International Conference on Learning Representations, 2019b.
Zhilin Yang, William W. Cohen, and Ruslan Salakhutdinov. Revisiting semi-supervised learning with graph embeddings. In ICML 2016, pp. 40 40-48, 2016.
Liang Yao, Chengsheng Mao, and Yuchen Luo. Graph convolutional networks for text classification.
AAAI 2019: Thirty-Third AAAI Conference on Artificial Intelligence, 33:7370-7377, 2019. URL
https://acadenin microsoft wwtp:pppptpppp/eeeeeeee
Ziwei Zhang, Peng Cui, and Wenwu Zhu. Deep learning on graphs: survey. arXiv preprint arXiv:1812.04202. 2018.
Xiaojin Zhu, Zoubin Ghahramani, and John D. Lafferty. Semi-supervised learning using gaussian fields and harmonic functions. In /CML 2003, pp. 912-919, 2003.
6 APPENDIX
6.1 LOW-FREQUENT COMPONENTS IMPLY BETTER SMOOTHNESS AND PPORMATION-TO-NONT RATIO
The different importance of low- and high-frequency components of graphs that contributes to the learning of modern GNNs is observed recently (Donnat et al. 2018 Machara 2019). Concretely, the low-frequency components in graphs usually indicate smooth varying signals which reflect the locality property (the neighbor nodes trend to be similar with each other) in graphs, thus they capture more information than the high- frequfrry components and should be more beneficial for the representational learning as revealed in our experiments. To this end, we investigate two measures in (Chen et al. 2019): Mean Average Distance (MAD) and Information-to-Noise Ratio (INR) w.r.t different spectrum basis. Different spectrum basis has a corresponding node in graph, which we refer as low- and high- frequency node.
MAD reflects the smoothness of node representation. Given node and the feature x, on it as signal, we take its eigenvector u, to multiply x, as the transformed feature x, in spectral domain. Then the MAD of v is calculated by taking the average of cosine distances between the transformed feature of v and that of its I-hop neighbors. The lower MAD indicates better smoothness. INR is defined as the proportion of nodes from the same class INR reflects the information contained in nodes and the higher INR indicates the richer information. For each dataset, compute the average MAD and INR of top-50% low-fiee wow-frequency nodes (MAD, and IN R,,) and rest high-freug gegh-rreuency nodes (MAD,, and IN R,)) and report the gap between low- and high- frequency nodes in Table
through the 1-hop neighborhood of v.

---

Under review as a conference paper at ICLR 2020
We can observe that the low-frequency components in real graphs indeed smoother than that of high-frequence (lower MAD). Meanwhile, they have higher INR. which indicates they contain richer information. In the vein, argue that the low-frequency components may carry more in- formation than that of the high-frequency components and should be more beneficial for the rep- resentational learning. Therefore, comparing with all other spectral-basee methods that treat both low- and high-frequency components identically during training, our proposed octave convolutional structure model could gain more from this octave nature existing in graphs
12


Reviews:
[{"review_id": "rygxsZzmqH", "reviewer": "AnonReviewer3", "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": "This paper proposes to use octave convolution to learn a representation of a graph.\nTypically, a learning on a graph is done either in a spatial domain or in a spectral domain.\nA spectral domain based approach uses a eigenvalue decomposition form of a graph Laplacian (a symmetric matrix) and learning a filter that acts on the eigenvalue of a graph Laplacian while preserving eigenvectors of a graph Laplacian.\nThis architecture is called the graph convolutional network on a spectral domain.\n\nThis paper's main contribution is to adapt octave convolutional network's architecture to the usual graph convolutional network. While I believe that this is the first work on applying the idea behind octave convolutional network architecture, separating low and high frequency component in the learning stage, to graph convolutional network architecture, I cannot see a good motivation on why this architecture is good for learning on a graph.\nA comprehensive study in the paper shows a better performance gain compared to the existing method, but it would be better if the gains were substantial or the authors presented a good motivation on why this architecture is good in some cases.\n\nOverall, I think the paper is well-written, but I would suggest to present more meaningful justification why and when the octave GCN is better than the GCN.", "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 assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "rJlkKoAe5r", "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": "Despite reading the paper multiple times,  I am not sure I have the background to know whether what is written is significant or not. I'm aware of work on general semi-supervised learning and see the much better performance of this approach compared to things like label propagation, but cannot say for sure whether the idea is novel/significant.\n\nOne q for authors -- I don't understand the core component of the proposal, is the key ingredient that have different weighting between low vs high that causes the better performance on tasks ? or is that we have less dependencies across variables (as reflected in the computational costs) that gets the better performance ?", "extra_scores": {"experience_assessment": "I do not know much about 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 did not assess the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "BJgIcnIOcB", "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": "This paper extends the previous graph wavelet neural network with separate computation for low frequency and high frequency part. The idea is to bring the octave convolution in vision to the graph domain. Experiments on three benchmark node classification tasks show comparable performances as previous methods. \n\nOverall the paper is written in a coherent and self-contained way, where the paper clearly states the related work and the contribution of this newly proposed work. Also it is interesting to see that normalizing the diagonal filter, tying the weights for low/high frequency parts would make the generalization better. However, there are several major concerns with the paper:\n\n1. The contribution is somewhat limited. The main component is based on GWNN. While the GWNN itself takes the full spectrum of basis already, the formulation in (8) and (9) should somehow capture the same information. I think the paper spends too much content on the reviews, while lacks the intuition or theoretical explanations of the proposed formulation. \n\n2. Having marginal improvement on the three benchmarks is not that interesting. Also given the results are mixed with other baselines, I think more experiments (e.g., on large graphs, or graph-level supervised tasks, etc.) are necessary to demonstrate the empirical gain using the proposed formulation. \n\n3. Regarding the experiments, is it true that d/n=0 and d/n=1 should have exactly the same results? \n\n4. In Figure 2, I guess d/n=0 should be reduced to the GWNN. But it seems the performance is different than GWNN on citeseer and cora. Why there’s such inconsistency, or did I miss anything? ", "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 assessed the sensibility of 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: Two reviewers are negative on this paper while the other one is slightly positive. Overall, the paper does not make the bar of ICLR and thus a reject is recommended.
Decision: Reject