TWIN GRAPH CONVOLUTIONAL NETWORKS: GCN WITH DUAL GRAPH SUPPORT FOR SEMI-SUPERVISED LEARNING
Authors: Feng Shi
Yizhou Zhao
Ziheng Xu
Tianyang Liu
Song-Chun Zhu
Venue:  (2020)
Keywords: Graph
Neural Networks
Deep Learning
semi-supervised learning

Abstract: Graph Neural Networks as a combination of Graph Signal Processing and Deep Convolutional Networks shows great power in pattern recognition in non-Euclidean domains. In this paper, we propose a new method to deploy two pipelines based on the duality of a graph to improve accuracy. By exploring the primal graph and its dual graph where nodes and edges can be treated as one another, we have exploited the benefits of both vertex features and edge features. As a result, we have arrived at a framework that has great potential in both semisupervised and unsupervised learning.

Under review as a conference paper at ICLR 2020
1 TWIN GRAPH CONVOLUTIONAL NETWORKS: GCN WITH DUAL GRAPH SUPPORT FOR SEMI-SUPERVISED LEARNING
Anonymous authors Paper under double-bling review
ABSTRACT
Graph Neural Networks as a combination of Graph Signal Processing and Deep Convolutional Networks shows great power in pattern recognition in non- Euclidean domains. In this paper, we propose a new method to deploy two pipelines based on the duality of graph improve accuracy. By exploring the primal graph and its dual graph where nodes and edges can be treated as one an- other, we have exploited the benefits of both vertex features and edge features. As result, we have arrived at framework that has great potential in both semi- supervised and unsupervised learning.
INTRODUCTION AND MOTIVATION
Convolutional Neural Networks (CNNs) (Lecun et al. (1998) has been very successfully used for automated feature extraction Euclidean domains, especially for computer vision, such as 2D im- age classification, object detection, etc. However, many real-life data has non-Euclidean graph structure in nature, from which we want to investigate the underlying relations among different objects by utilizing the representation of nodes and edges. Recently, research on applying the gen- cralization of Convolutional Neural Networks to the non-Euclidean domains has attracted growing attention. As result, branch of research on Geometric Deep Learning (Bruna et al. (2013) based on that has been ignited. Previous works including ChebNet (Defferrard et al. (2016)) and GCN (Kipf & Welling (217)) have demonstrated strong results in solving problems in supervied learning where the labels of only a few objects are given, and we want to find out the labels of other objects through their inner connections. Current methods generalizing convolution operations in- clude both spatial and spectral domains (Bruna et al. (201)). The spatial one deals with each node directly in the vertex domain while the spectral one takes a further step in converting signals via graph Fourier transform into the spectral domain. However, that the interchangeable and complementary nature between nodes and edges are generally ignored in previous research. As a result, the duality of the graph is not fully utilized. If treat those edges in the original, or known as the primal graph, as the nodes in the new graph, and original nodes as edges, we can arrive a new graph that further exploits the benefits of edge features. such a way, we are able to get both the primal graph and the dual graph (Monti et al. (018)). By combining both the vertex features and the edge features, we will be able solve wider range of problems and achieve better performance. In this paper, we propose a new approach to transform the primal graph into its dual form and have implemented two pipelines based on these two forms of graph to improve the accuracy and the performance. With two pipelines, we also exploited path to make the model wider instead of merely deeper. Meanwhile, we have developed new framework that can be applied later on both supervisd learning and unsupervised learning.
critical weakness would be the fact

---

comprehensive and Under review as a conference paper at ICLR 2020
2
RELATED WORK
Graph-based semi-supervised learning aims to annotate data from a small amount of label data on graph. To learn the vectors that can recover the labels of the training data well as distinguish data with different labels, conventionally, graph Laplacian regularizer gives penalty between sampling based graph Laplacian matrix (Zhu al. (2003); (ndo & Zhang (2007); Weston et al.) (2012). )
Sample-based method takes random walk to get samples from the context of data points in order to propagate information (Perozzi al. (2014); Yang al. (2016); Grover & Leskoved (2016))
Graph Convolutional Networks generalize the operation of convolution from grid data to graph data (Wu et al. (2019). After the emergence of the spectral-based convolutional networks on graph (Bruna et al. (2013)), ChebNet (Defferrard et al. (2016)) approximate the filters by Chebyshev polynomials according the Laplacian eigendecomposition. GCN(Kipt & Welling (2017) sim- plifies ChebNet by introducing its first-order approximation and can be viewed as a spatial-base based perspective. which requires vertices in the graph to propagate their information to the neighbors. MoNet(Monti et al. (2017)) is spatial-based method, of which convolution is defined a Gaussian mixture of the candidates. GAT(Veličkovi et al. (2017)) applies the attention mechanism to the graph network. DGI( Veličkkvé et al. (2018)) proposes framework to learn the unsupervised rep- resentations on graph- straptstructured data by maximizing location mutual information. We refer to Zhou et al. (2018); Xu et al. (2018); [Battaglia et al. (2018): Wu et al. (2019) as
thorough review on graph neural networks.
Dual approaches on graph networks usually unlike the above mono-methods. apply mixed meth- ods to study graph networks. DGCNnZhuang & Ma (2018)) makes a balance between the spatial- based domain and spectral-based domain by regularizing their mutual information. GIN et al.. (2188) proposes a dual-path from graph convolution on texts and another network on images to gather cross-most cross-modal information into a common semantic space. DPGCNN(Monti et al. (2018)) ex- tends the classification on vertices to edges by considering the attention mechanism on both. Our study follows this path, which classifies vertices from the relationship between them (edges) and regularization from the mutual information between classification on both vertices and edges.
3 METHODOLOGY
3.1 PRELIMINARIES
Let G = (V,E,A) denote a graph, where V (1...., NN is the set of nodes with |V] N, & the set of edges, and A = (A(iJ)vv + 0) E RNNN is the adjacency matrix. When ς is undirected then A is symmetric with Ai, Ag,i, . an undirected graph, otherwise a directed graph. The Lapla- cian matrix, also acts a propagation matrix, has the combinatorial form as I D A E NNN and its normalized form is C
D AD-1, where D diag(d(1),.. d(N)) E RNNN is the degree matrix of graph G with d(i) = Σ _jE Ai,j and I E R N is the identity matrix. In some literature, the random walk Laplacian Tew I D 11 A is employed to directed graph g.
3.2 GRAPH CONVOLUTIONS AND CONVOLUTIONAL NETWORKS ON GRAPHS
Let L = T be the eigendecomposition, where U E N is composed of orthonormal eigen- basis and A diag(X (1g, A1..... ... AN-1) is a diagonal matrix of eigenvalues which denotes frequen- cies of graph G and \; and u, form an eigenpair. The convolutional operator #g on the graph signal x is defined by
f f=g *g gg x= ((V*))
(('=)))UGUU
where f= U x and و = UTg are regarded as the graph Fourier transform of graph signal x and graph filter y. respectively: / U--) product. & diag(oo. ... 11) behaves as spectral filter coefficients. Graph convolution can be approximated by polynomial filters, the k-th order form is
) is the inverse graph Fourier transform, and @ is the Hadamard
K UGUT x = Σ C.L'r = U
F 0:10 T EoAN i=0
(2)
0=0
2

---

Under review as a conference paper at ICLR 2020
where 82 denotes coefficients and G ~ 0,A' equivalently 9(A,) 0,A. Based on the
above approximation, ChebNet (Defferrard et al. (2016)) further introduces Chebyshev polynomials into graph filters of the convolutional layers for the sake of computational efficiency. Chebyshev polynomials are recursively expressed as (a) (x)) - Tz-2(z) with To(x) = and
Ti (x) The graph filter then becomes
UGU x = U Σ ATTT())) U³x --'='/'>>- Σ (,T,(L) ==0
(3)
where É 2/ C denotes the scaled normalized Laplacian for all eigenvalues X [ 1,
and 0; is trainable parameter. Graph Convolutional Network (GCN) (Kipf & Welling 2017 is variant of ChebNet which only takes first two terms of Equation (3) By setting the coefficients do and 01 as 0 0g -0 and with Amax 2, the convolution operator in convolution layer of GCN is induced 9 g 0 + D à AD $ )az With renormalization trick, + D à AD à is further replaced by D AD- 1 where À A and D D 1.
3.3 GRAPH AND ITS DUAL
(1,4)
a) Primal Graph
a) Dual Graph
Figure 1: Primal graph and its dual graph: a) graph G, which represents a primal graph, with nodes; b) the corresponding dual graph graph G its left side; arrow-ares demonstrate the conversion between G and G.
In graph theory, The definition of the dual varies according the choice of embedding of the graph G. For planar graphs generally, there may be multiple dual graphs, depending on the choice of planar embedding of the graph. In this work, we follow the most common definition. Given plane graph the primal graph, the dual graph & {} ε, E, is
= (V,, A}, which is designated graph that has vertex (or node) for each edge of G. The dual graph ý has an edge whenever two edges of G share at least one common vertex. To be clarified, the vertices (i.j) and (j. i) of dual graph 9 converted from undirected graph are regarded the same. Fig shows the conversion from primal graph to its dual counterpart. When vertices of the primal graph embed features (or signals in terminology of spectral graph theory), the features of dual node be obtained by ap- plying a specified functions to its corresponding primal nodes' features, i.e. the simplest applicable function is calculate the distance between the features of two nodes. In addition, if the edges of primal graph possess features or attributes, we also take them into account as the their inherited fea- tures of dual nodes. Take node (1, 2) of dual graph in [T) as an example, its feature is obtained by performing the dlement-wise subtraction to the feature vectors of nodes 0 and 3 of primal graph in Fig Ia). i.e. [1, 01,0, 1 [0, 10,-1,17 1)
3.4
TWIN GRAPH CONVOLUTIONAL NETWORKS
The Twin Graph Convolutional Nenworks (TwinGCN) proposed in this work consists of two pipelines. Both pipelines are built with the same architecture as GCN, and contain two convolu- tion layers in each pipeline, shown in Fig The upper pipeline acts exactly as GCN; however, the lower takes the dual features X derived from primal features X as its inputs (as described
3

---

Under review as a conference paper at ICLR 2020
X
GCW1
GCWg
SD
gonerate dual features
Suftmax
loss
xt.
a/
Softmax
X
1GON]
4GCN2
Z
ségregate to vvertex domain/
festures In domain
Y
create
Figure 2: Architecture of TwinGCN: Two pipleline architecture, the upper is for primal graph, the lower is for the dual graph. The predictions of the two pipelines are combined with their KL- Divergence for final results.
in section the predictions outputs in dual vertex domain (i.e. edge domain primal) is then aggregated to primal vertex domain. The goal of introducing dual pipeline into the model is that desire utilize the predictions on the dual node (edges in primal graph) affect the predictions on primal nodes since the knowledge about those neighbors of node can be propagated through edges.
For the purpose of training the dual pipeline, we also need to get the labels of dual nodes. Let us take an example, given a dual node (i,j) (corresponds to an edge in primal graph), primal node has label and has label 8, then dual node (i,j) is assigned with label (a, 33..
One thing worth mentioned that TwinGCN's convolution layers are not limited to those used in GCN, they can be replaced with other types of convolution layer, such ChebNet, GWNN (Xu ctt al. 2019)), etc.
The convolution layers in the pipelines perform graph convolution operations with shared weights as learnable parameters, mathematically expressed as
H(+1) (D AD- H(w())
where ( is the activation in 1-th layer, W()) is learnable weights that layer. represents non- linear activation function, e.g. ReLU. For the task of emmisuupreised node classification, the loss function is defined
C= C=-IEv,pn Yn
(5)
1=1
where Y' is set of node labels for L V labeled node set, F denotes the number of labels of the nodes, and Z is predicted outcome, a softmax
output of the network.
In order to take effect of dual pipeline the prediction of primal pipeline, we adopt KullbackLeeibler Divergence (DKL) as a regularization term in training. Suppose that P(Y predictions by primal pipeline and | = P( X) is the derived predictions obtained through an aggregation from the predictions on dual labels by dual pipeline to primal label predictions. X is derived from X as aforementioned (Section 3.3). We first calculate the joint probability matrix P(Y, Ý) of two matrices XX) and (X)
P(Y = Σ P(yl=) P(YX))
(6)
ZEX
we further get the marginal probabilities of P(Y) and P(Ý) from P(Y KullbackLeibler Diver- gence DEL is evaluated by
DKL (AI1T) = Σ P(y)log
P(ú)
EPT)
P(y) [ogP()) log P(v)
P(y)
YEY
DEY
4

---

Under review as a conference paper at ICLR 2020
finally, we attains the loss function
- Cp 02Cp + KLD
(8)
where 01, 82, and 8g are trainable coefficients.
dual loss
La
aggregated primal primal loss
(aggregate to vertex domain]
II.
01
1.0
L
00
00.
0
N
10
00
0
I
g
10
01
primal-dual label incidence matrix
M
M
primal-dual node
incidence matrix
Figure 3: Fast algorithm for calculating the aggregated primal predictions from dual predictions
Fig illustrates a fast algorithm deriving primal predictions from predictions of dual pipeline. It is conducted by introducing two special incidence matrices. The matrix the left hand side (N M, N = [V] and M (ε() is incidence matrix in which the rows represent primal nodes, each column depicts whether primal node in a row has an incidence in the dual node represented by this column. The rightmost matrix is the incidence matrix of primal labels presenting in dual labels with dimension L x L. Although these two matrices are extremely sparse when node number is very large (we store them in compressed form), by taking advantage of GPU's powerful computing capability, the delicate sparse matrix multiplication subroutine, e.g. Nvidia's cuSARSE, runs much faster than codes with loops for lumping the incidences.
4 EXPERIMENTS
In this section, we evaluate the performance of TwinGCN, we mainly focus on semi-supervised node classification in current work. Actually, TwinGCN also support unsupervised learning by changing the loss functions which we will fulfill in future work.
4.1 DATASETS
We conduct experiments three benchmark datasets and follow existing studies (Defferrard al. (016)) Kipf & Welling (2017); Xu et al. (2019) etc.) The datasets include Cora, Citeseer, and Pubmed (Sen et al. (2008)). All these three datasets are collected from their corresponding citation networks, the nodes represent documents and edges are the citations. Table 4.1 shows details of these datasets. Label rate indicates the portion of the available labeled nodes used for training. The training process takes 20 labeled samples for each class for every dataset.
Dataset Nodes
Edges
Features
Label Rate
Classes
Train/Valid/Test Nodes
Cora 2,708
5,429
1,433
0.052
140 / 500 1,000
Citeseer
3,327
4,732
3,703
0.036
120 500 1,000
Pubmed
19,717
44,338
500
0.003
60/ 500 1,000
Table
The Statistics of Datasets
4.2 BASELINES AND EXPERIMENT SETTINGS
Since both pipelines our proposed architecture work with graph convolution based on spectral graph theory, we recent works, such ChebNet (Defferrard et al. (2016) GCN (Kipf & Welling

---

Under review as a conference paper at ICLR 2020
2017), ) and GWNN (Xu et al. 2019) ) etc. These models maintain the same graph Lapalacian base structure, unlike some other methods take partial graph structure, e.g. FastGCN (Chen et al. (2018)) applies Monte Carlo importance sampling edges. however, this kind of method only guarantees the convergence as the sample size goes to infinity.
For the sake of consistency for comparison, the hyper-parametert for training are kept the same for primal pipeline as other models. The primal are composed with two graph convolution layers with 16 hidden units and applied with ReLU non-linear activations. Loss is evaluated with the softmax function. Dropout (Srivastava et al. 2014)) of primal pipeline is set to = 0.5 for the primal. We use the Adam optimizer (Kingma & Ba (2015)) for optimizing the weights with an initial learning rate ly = 0.01.
As the dual graph is normally much bigger than the counterpart primal graph, its adja- cency/Laplacian matrix and the number of dual nodes becomes quadratically larger, e.g. N nodes with N (N-1) 1) edges set its dropout rate higher than 70%. We also introduce sampling rate to extract small fraction from the total dual node labels. Having a large number of edges in the primal graph also means large number of dual nodes. In such situation, the performance will be degraded severely.
fully-connected graph. Therefore, to avoid overfitting on dual pipeline,
4.3 PERFORMANCE OF TWINGCN
The quantitative comparison among different models is given in Table 4.4 For node classifica- tion, TwinGCN achieves similar results or outperforms with some datasets. The performance gain comes from the aggregation of knowledge propagated through edges (or dual nodes) trained by dual pipeline. However, primal pipeline only will ignore the dependency between labels of nodes.
Method
Cora
Citeseer
Pubmed
ChebNet
81.2%
69.8%
74.4%
GCN
81.5%
70.3%
79.0%
GWNN
82.8%
71.7%
79.1%
DGI
82.3%
71.8%
76.8%
DGCN
83.5%
72.6%
80.0%
TwinGCN 82.7%
72.8%
79.8%
Table 2: Results of Node Classification
Fig.4a) illustrate that when compared to the GCN, TwinGCN bearing two pipelines converges slower but achieves higher accuracy as the number of epoch increases. This because that we have two pipelines through mutual interaction. In Fig.4b), we observe that two loss curves of traditional GCN and TwinGCN have very similar decreasing trends. However, the loss curve of TwinGCN is slightly above GCN because the loss of TwinGCN is the summation of both primal and dual pipelines.
4.4 ANALYSIS
To test whether the introduced dual pipeline and regularization improve the basic GCN pipeline, conducted controlled experiments to make comparison among GCN, GCNs with pipelines original graph and dual graph and TWinGCN(GCNs with both pipelines and regularization by KL- divergence).
Method GCN
Cora
Citeseer
Pubmed
81.5% + 0.3%
70.8% + 0.1%
78.8% + 0.1%
GCN(double-pipeline) TwinGCN
81.6% + 0.4%
72.5% + 1.0%
79.8% + 2.3%
83.0% + 1.3%
72.5 + 0.8%
79.5% + 1.2%
Table Comparison results
Table shows the comparison results: the average test accuracy and the standard deviation from the model which has the best validation accuracy. The pipeline the dual graph increases the

---

Under review as a conference paper at ICLR 2020
Validation Accuracy Curve
0.80
Accuracy Percentage
0.75
0.70
0.60
Val Accuracy (TwinGCN)
Val Accuracy (GCN)
0.30
130
200
Epochs
Loss Function Curve
Val Loss (TwinGCN)
Val Loss (GCN)
1.4
LoSs
14-
50
100
150
203
250
300
350
400
Epochs
Figure 4: a) Mean and standard deviation of validation accuracy on Cora; b) Loss function of vali- dation
performance of GCN, indicating that applying relationship between nodes be powerful tool in the classification task. The (aaaaariaattoooK-divveeeree However, TwinGCN suffers from larger uncertainty suggested by the larger standard deviation.
CONCLUSION AND FUTURE WORK
In this work, propose the TwinGCN with parallel pipelines working both the primal graph and its dual graph, respectively. TwinGCN achieves the state-of-the-art performance in semi- supervised learning tasks. Moreover, TwinGCN's ability not limited this, extend its power/utilization into unsupervised learning by altering its loss functions.
ACKNOWLEDGMENTS
Use unnumbered third level headings for the acknowledgments. All acknowledgments, including those funding agencies, go at the end of the paper.

---

Under review as a conference paper at ICLR 2020
REFERENCES
Rie K Ando and Tong Zhang. Learning on graph with laplacian regularization. In Advances in neural information processing systems, pp. 25-32, 2007.
Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro SonzaezZGonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint arXiv:/86..01 1806.01211, 2018.
Joan Bruna, Wojeiech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. arXiv preprint arXiv: /3/2.6203, 2013.
Jie Chen, Tengfei Ma, and Cao Xiao. FastGCN: Fast learning with graph convolutional networks via importance sampling. In International Conference on Learning Representations, 2018. URL
https://openreviee net www.:eettteotttteeeeeeeee Forummiddooooeeoooe syytumitsdrttt
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Proceedings of the 30th International Conference
on Neural Information Processing Systems, NIPS' 16. pp. 3844-3852, USA, 2016. Curran Asso- ciates Inc. ISBN 978-1-5108-3881-11
URL http: d1 acm. org/ citat ion. ?fm?id
3157382.31577
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 855-864, ACM, 2016.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In the 3rd International Conference for Learning Representations, San Diego, 2015, 2015. URL http: Published as conference
llaaxiv.orgg//...aaaaaoo.......a ats///b///140 6980 cite paper at.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In International Conference on Learning Representations (ICLR), 2017.
Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recog- nition. Proceedings of the IEEE, 86(11):2278-232) Nov 1998. doi: 10.999....
Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodola, Jan Svoboda, and Michael M Bronstein. Geometric deep learning on graphs and manifolds using mixture model enns. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 5115-
5124, 2017.
Federico Monti, Oleksandr Shchur, Aleksandar Bojchevski, Or Litany, Stephan Günnemann, and Michael M Bronstein. Dual-primal graph convolutional networks. arXiv preprint arXiv:18066 00770. 2018.
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social repre- sentations. In Proceedings of the 20th ACM SIGKDD international conference Knowledge discovery and data mining, pp. 701-710. ACM, 2014.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic. Lise Getoor, Brian Galligher, and Tina Eliassi- Rad. Collective classification in network data. Al Maguzine, 29(3):93, Sep. 2008 doi: 10. 1609 aimag v293.2229,3 URL https: wwwp///wwwwc.o aaai www.o/////oo.oo.ooooooooooo http:///iiiiiiee.pppppepappppp/e
index. wwt.pee..ppp//ammmaaiiineeee
article/view/211
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdi- nov. Dropout: A simple way to prevent neural networks from overfitting. Journal of Ma- chine Learning Research, 15:199911958, 2014. URL http::// wrg. wtt.prrpppppp//...555.
Sr vastavallll 14a. .4.htmll
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 10903, 2017.
8

---

Under review as a conference paper at ICLR 2020
Petar Veličkovié, William Fedus, William L Hamilton, Pietro Liö, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. arXiv preprint 1oXiv:8809.10344 2018.
Jason Weston, Frédéric Ratle, Hossein Mobahi, and Ronan Collobert. Deep learning via semi- supervised embedding. In Neural Networks: Tricks of the Trade, pp. 639-655, Springer, 2012.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip Yu. A comprehensive survey on graph neural networks. arXiv preprint arXiv: 2019.
Bingbing Xu, Huawei Shen, Qi Cao, Yungi Qiu, and Xueqi Cheng. Graph International Conference on Learning Representations, 2019. URL URL/ntpsss//openeeviee.
network. In
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural 2018.
networks? arXiv preprint
Zhilin Yang, William W Cohen, and Ruslan Salakhutdinov. Revisiting semi superviee learning with graph embeddings. arXiv preprini urXiv:/603.08850 2016.
Jing Yu, Yuhang Lu, Zengchang Qin, Weifeng Zhang, Yanbing Liu, Jianlong Tan, and Li Guo. Modeling text with graph convolutional network for cross- cross-modal information retrieval. In Pacific Rim Conference on Multimedia, pp.
Springer, 2018.
Jie Zhou, Ganqu Cui, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, and Maosong Sun. Graph neural networks: review of methods and applications. arXiv preprint arXiv:1812.08434, 2018.
Xiaojin Zhu, Zoubin Ghahramani, and John D Lafferty. Semi-supervised learning using gaussian fields and harmonic functions. In Proceedings of the 20th International conference on Machine learning (ICML-03), pp. 912-919, 2003.
Chenyi Zhuang and Qiang Ma. Dual graph convolutional networks for graph- based semi-supervised classification. In Proceedings of the 2018 World Wide Web Conference, pp. 499-508. International World Wide Web Conferences Steering Committee, 2018.
A APPENDIX
A.1 SPASITY
TwinGCN, which introduces additional pipeline, increases the number of parameters as well as sparsity. For the graph with m nodes and n edges, the sparsity of the Laplacian matrix is O( " ). If we denote n, the degree of node i, for the dual graph which takes edges as nodes and connect edges which share the same node, the sparsity of the dual Laplacian matrix is
Sparsity($) = (0(=
n,(n; 1)/2
n
which can be as small as O (( when each node has the average number of degree, i.e. n, 2n


Reviews:
[{"review_id": "SJemyeYW5r", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper describes a new dual method for graph convolutional networks that combines the features from the graph and it's dual, in two pipelines. The paper builds on the architecture as in GCN and in addition to the dual pipelines, one from the graph and other it's dual, employs KL divergence to achieve the final prediction.\n\nThe paper leaves inadequate explanation on the results, where the proposed TwinGCN comes short in 2 of 3 methods compared to other methods in Table 1, which cannot be ignored considering the slow convergence and marginal improvements, compared to GCN with double pipeline in Table 3. This leaves the premise of the authors on adding improvements to the learning ability by bringing in features from dual graph on shaky grounds.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "S1xQZ57pKr", "reviewer": "AnonReviewer2", "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 two graph convolutional network for semi-supervised node classification. The model is composed of two GCNs, one on the primal graph and one on the dual graph. The paper is well written and easy to follow. However, the novelty and contribution are rather limited, and the performance improvement of the proposed method is rather limited. Following are the detailed comments:\n\n1. The novelty and contribution of the paper are rather limited. The idea of dual graph has been exploited by [1]. The proposed method is simple combination of prime and dual without convincing explanation on why primal dual graph can improve the performance. The authors may need to give more explanations on why such combination can improve the performance.\n\n2. The performance improvement of the proposed method is marginal. In fact, the proposed method doesn’t outperform DGCN\n\n3. Experiments need to be improved. The authors didn’t compare with GNNs that also adopts primal and dual graphs. The authors should consider comparing the proposed method with DPGCN in [1].\n\n[1] Monti, Federico, et al. \"Dual-primal graph convolutional networks.\" arXiv preprint arXiv:1806.00770 (2018).\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "BJgD85xqqB", "reviewer": "AnonReviewer4", "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 utilizes two pipelines based on the duality of a graph and the primal graph for semi-supervise learning. More specifically, the authors transform the primal graph into its dual form and build a two-pipelines architecture to learn on the primal graph and dual graph together. The goal of including a dual pipeline is to use the predictions on the dual node to affect the predictions of the primal nodes. \n\nI decided to give a weak reject to this paper for the following shortcomings:\n\n1. Novelty is not enough. Dual graphs are explored utilized to graph neural networks in some related works (such as [1]). This paper utilizes dual graphs to affect or assist the prediction on the primal nodes, which is very similar to the methods used in [1]. \n\n2. Experiments can not prove the effectiveness of this method very well. The experiments only conduct on 3 datasets and the analysis of the experimental results is not convincing and more details should be included. For example, if GCN(double-pipeline) performs better than GCN, this can somehow support the effectiveness of a double-pipeline that includes a dual graph. However, the results of TwinGCN can not support the effectiveness of regularization by KL-divergence. I think more experiments and analyses about why this method works should be explored in Section Experiments.\n\n3. The organization should be improved. In general, when introducing a model, it is better to introduce the prediction part of the model first. For example, I can get the idea of how to train the DualGCN by reading the Section Method. However, I have no idea about how the authors make a prediction on the trained DualGCN, how to transform the prediction of the dual graph to the prediction of primal nodes. I think these details are significant for this paper. Also, there are several incomplete sentences in this paper.\n\nOverall, this idea that utilizes the dual graph to assist the primal graph learning is good and can be explored in the future. For the current version, I give a weak reject for the above reasons.\n\n\n\n\nReference\n[1] Chen et al. Supervised community detection with line graph neural networks.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}]

Author rebuttal:

Meta-review: All three reviewers are consistently negative on this paper. Thus a reject is recommended.
Decision: Reject