Weighted Line Graph Convolutional Networks
Authors: Hongyang Gao
Shuiwang Ji
Venue:  (2021)
Keywords: Line graph

Abstract: Line graphs have shown to be effective in improving feature learning in graph neural networks. Line graphs can encode topology information of their original graphs and provide a complementary representational perspective. In this work, we show that the encoded information in line graphs is biased. To overcome this issue, we propose a weighted line graph that corrects biases in line graphs by assigning normalized weights to edges. Based on our weighted line graphs, we develop a weighted line graph convolution layer that takes advantage of line graph structures for better feature learning. In particular, it performs message passing operations on both the original graph and its corresponding weighted line graph. To address efficiency issues in line graph neural networks, we propose to use an incidence matrix to accurately compute the adjacency matrix of the weighted line graph, leading to dramatic reductions in computational resource usage. Experimental results on both real and simulated datasets demonstrate the effectiveness and efficiency of our proposed methods. 

Under review as a conference paper at ICLR 2021
WEIGHTED LINE GRAPH CONVOLUTIONAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
Line graphs have shown to be effective in improving feature learning in graph neural networks. Line graphs can encode topology information of their original graphs and provide a complementary representational perspective. In this work, we show that the encoded information in line graphs is biased. To overcome this issue, we propose a weighted line graph that corrects biases line graphs by as- signing normalized weights to edges. Based on our weighted line graphs, we de- velop a weighted line graph convolution layer that takes advantage line graph structures for better feature learning. In particular, it performs message passing operations on both the original graph and its corresponding weighted line graph. To address efficiency issues in line graph neural networks, we propose incidence matrix to accurately compute the adjacency matrix of the weighted line graph, leading to dramatic reductions in computational resource usage. Experi- mental results on both real and simulated datasets demonstrate the effectiveness and efficiency of our proposed methods.
INTRODUCTION
Graph neural networks (Gori et al. 2005 Scarselli al., 2009| Hamilton et al. 2017) have shown to be competent in solving challenging tasks in the field of network embedding. Many tasks have been significantly advanced by graph deep learning methods such node classification tasks (Kipf) & Welling, 2017: Veličković et al. 2017 Gao et al., 2018), graph classification tasks (Ying et al., 2018 Zhang et al.] 2018). link prediction tasks (Zhang & Chen 2018 Zhou al.] 2019). and community detection tasks (Chen et al. 2019). Currently, most graph neural networks capture the relationships among nodes through message passing operations. Recently, some works (Chen al.) 2019) use extra graph structures such as line graphs to enhance message passing operations in graph neural networks from different graph perspectives. A line graph is a graph that derived from an original graph to represent connectivity between edges in the original graph. Since line graphs can encode the topology information, message passing operations on line graphs can enhance network embeddings in graph neural networks. However, graph neural networks that leverage line graph structures need to deal with two challenging issues; those are bias and inefficiency. Topology infor- mation in original graphs is encoded in line graphs but in a biased way. In particular, node features are either overstated or understated depending on their degrees. Besides, line graphs can be much bigger graphs than original graphs depending on the graph density. Message passing operations of graph neural networks on line graphs lead to significant use of computational resources.
In this work, we propose construct a weighted line graph that can correct biases in encoded topology information of line graphs. To this end, we assign each edge in a line graph a normalized weight such that each node the line graph has a weighted degree of In this weighted line graph, the dynamics of node features are the same as those in its original graph. Based on our weighted line graph, we propose weighted line graph convolution layer (WLGCL) that performs message passing operation on both original graph structures and weighted line graph structures. To address inefficiency issues existing in graph neural networks that use line graph structures, we further propose to implement our WLGCL via an incidence matrix, which can dramatically reduce the usage of computational resources. Based on our WLGCL, we build a family of weighted line methods on graph classification tasks
graph convolutional networks (WLGCNs). We evaluate and show that WLGCNs consistently outperform previous state-of ofate-of-the-art models. Experiments on simulated data demonstrate the efficiency advantage of our implementation.

---

Under review as a conference paper at ICLR 2021
a.b
a,c
a.d
c.d
a.b
a
a.c
a.d
(a)
(b)
(c)
Figure Illustrations of an graph (a), its corresponding line graph (b), and its incidence graph (c).
BACKGROUND AND RELATED WORK
In graph theory, a line graph graph derived from an undirected graph. represents the con- nectivity among edges in the original graph. Given graph G, the corresponding line graph L(G) constructed by using edges G as vertices L(G). Two nodes L(G) are adjacent if they share common end node in the graph G (Golumbie) 2004). Note that the edges (a, b) and (b, a) in an undirected graph G correspond to the same vertex in the line graph L(G). The Whitney graph isomorphism theorem (Thatte 2005) stated that line graph has one-to-one correspondence to its original graph. This theorem guarantees that the line graph can encode the topology information in the original graph. Recently, some works (Monti et al. 2019 Diang et 20199 proposes to use the line graph structure to enhance the message pass- ing operations in graph neural networks. Since the line graph can encode the topology information, the message passing on the line graph can enhance the network embeddings in graph neural net- works. graph neural networks that use line graph structures, features are passed and transformed in both the original graph structures and the line graph structures, thereby leading to better feature learnings and performances.
al. 2018 Chen et al. 2019 Bandyopadhyay
3 WEIGHTED LINE GRAPH CONVOLUTIONAL NETWORKS
In this work, we propose the weighted line graph to address the bias in the line graph when encoding graph topology information. Based on our weighted line graph, we propose the weighted line graph convolution layer (WLGCL) for better feature learning by leveraging line graph structures. Besides, graph neural networks using line graphs consume excessive computational resources. To solve the inefficiency issue, we propose use the incidence matrix to implement the WLGCL, which can dramatically reduce the usage of computational resources.
3.1 BENEFIT AND BIAS OF LINE GRAPH REPRESENTATIONS
In this section, we describe the benefit and bias of using line graph representations.
Benefit In message-passing operations, edges are usually given equal importance and edge features are not well explored. This can constrain the capacity of GNNs, especially on graphs with edge features. In the chemistry domain, compound can be converted into graph, where atoms nodes and chemical bonds are edges. On such kinds of graphs, edges have different properties and thus different importance. However, mnessgge-psssnng operations underestimate the importance of edges. To address this issue, the line graph structure can be used to leverage edge features and different edge importance (Jiang et al.) 2019 Chen al. 2019 Zhu et al. 2019). The line graph, by its nature, enables graph neural networks to encode and propagate edge features in the graph. The line graph neural networks that take advantage of line graph structures have shown to be promising graph-related tasks (Chen et al.[[2001 2019 Xiong et al. 2011 Yao et al. 2019). By encoding node and edge features simultancously. line graph neural networks enhance the feature learning on graphs.
Bias According to the Whitney graph isomorphism theorem, the line graph L(G) encodes the topol- ogy information of the original graph G. but the dynamics and topology of G are not correctly represented in L(G) (Evans & Lambiotte, 2009). As described in the previous section, each edge in the graph G corresponds to vertex in the line graph L(G). The features of each edge con- tain features of its two end nodes. A vertex with degree in the original graph G will generate
2

---

x (d 1) edges in the line graph L(G). The message passing frequency of this node's features will change from (d) in the original graph to (dd²) in the line graph. From this point, the line graph encodes the topology information in the original graph but in a biased way. In the original graph, a node's features will be passed to d neighbors. But in the corresponding line graph, the in- formation will be passed to d x (d - 1)/2 nodes. The topology structure in the line graph L(G) will overstate the importance of features for nodes with high degrees in the graph. the contrary, the nodes with smaller degrees will be relatively understated, thereby leading to biased topology infor- mation encoded in the line graph. Note that popular adjacency matrix normalization methods (Kipf) Gong & Cheng 2019) cannot address this Under review as a conference paper at ICLR 2021
1/3+/11
a.b
a.b
1/3
1/3+1/2
a,c
1:3
8,c
1/2
1/3
a.d 1
c,d
a.d
c,d
1/2
1/3+1/2
1/2-1/2
(a)
(c)
Figure 2: An illustration of graph (a), its corresponding line graph (b), and its weighted line graph (c). Here, consider a graph with 4 nodes and 4 edges illustrated in (a). The numbers show the node degrees in the graph. In figure (b), a line graph is constructed with self-loops. Each node corresponds to an edge in the original graph. In the regular line graph, the weight of each edge is 1. Figure (c) illustrates the weighted line graph constructed as described in Section 3.2 The weight of each edge is assigned as defined in Eq. TT.
& Welling 2017 Veličković et al. 2017 issue.
Gao & Ji, 2019
3.2 WEIGHTED LINE GRAPH
In the previous section, we show that the line graph L(G) constructed from the original graph G encodes biased graph topology information. To address this issue, we propose construct weighted line graph that assigns normalized weights to edges. In regular line graph L(G), each edge assigned an equal weight of I, thereby leading to biased encoding the graph topology information. To correct the bias, we need to normalize edge weights in the line graph.
Considering each edge in G has two ends, is intuitive to normalize the weighted degree of the corresponding node in ((G) to 2. To this end, the weight for edge in the adjacency matrix F of L(G) is computed as:
1 Dr
f af
F ((a.b).(b.c)
(I)
where a, and e are nodes the graph G, (a, b) and (b, c) are edges the graph G that are connected by the node b. Dr, is the degree of the node i in the graph G. To facilitate the message passing operation, we add self-loops on the weighted line graph W L(G). The weights for self- edges computed by the second case consider the fact that they are self-connected by both ends. Figure 2
illlstrates an example of a graph and its corresponding weighted line graph.
Theorem 1. Given the edge weights in the weighted line graph WI(G) defined by Eq. the weighted degree for node (a, in W L(G) is 2.
The proof of Theorem 1 is provided in the supplementary material. By constructing the weighted line graph with normalized edge weights defined in Eq. each node (a. has a weighted degree 2. Given node with degree of d, it has d related edges in G and d related nodes in L(G). The message passing frequency of node a's features in the weighted line graph WL(G) is Σ = (d). which is consistent with that in the original graph G. Thus, the weighted line graph encodes the topology information of the original graph in unbiased way.
3

---

Under review as a conference paper at ICLR 2021
GCN
GCN
Figure 3: An illustration of our proposed weighted line graph convolution layer. We consider an input graph with 4 nodes and each node contains 2 features. Based on the input graph, we firstly construct the weighted line graph with features described in Section 3.2 Then we apply two GCN layers on the original graph and the weighted line graph, respectively. The edge features in the line graph transformed back into node features and combined with features in the original graph.
3.3 WEIGHTED LINE GRAPH CONVOLUTION LAYER
In this section, we propose the weighted line graph convolution layer (WLGCL) that leverages our proposed weighted line graph for feature representations learnings. In this layer, node features are passed and aggregated in both the original graph G and the corresponding weighted line graph (LG)..
Suppose undirected attributed graph G has N nodes and F edges. Each node and each edge in the graph contains C, and C. features, respectively. In the layer e, an adjacency matrix A E NNN,, a node feature matrix (() E R R.Nx and a edge feature matrix ( E R Fxx.. are used to represent the graph connectivity, node features, and edge features, respectively. Here, we construct the adjacency matrix propagation rule of the weighted line graph convolution layer É defined as:
F()) E ExXE of the corresponding weighted line graph. The layer-wise
(9 y()
FRC
K/6 (10)
NCC
(3)
K-O)
= x())
NxC,
(4)
(e+1)
K w! (0)
NRC
(5)
where (( XCxx0 and w E RCx are matrices of trainable parameters. B( R NXE the incidence matrix of the graph G that shows the connectivity between nodes and edges.
To enable message passing on the line graph [[G,, each edge in the graph G needs to have features. However, edge features are not available on some graphs. To address this issue, we can compute features for an edge (a, b) by summing up features of its two end nodes: v(()) = x +x Here, use the summation operation to ensure the permutation invariant property in this layer. Then, perform message passing and aggregation on the line graph Eq. 2). With updated edges features, Eq. generates new nodes features with edge features Y (9) Eq. (4 performs feature passing and aggregation on the graph G, which leads to aggregated nodes features (9)) In Eq. (5). aggregated features from the graph G and the line graph L(G) are transformed and combined, which produces the output feature matrix x (e+1), Note that we can apply popular adjacency matrix normalization methods (Kipf & Welling 2017) on the adjacency matrix A ((), the line graph adjacency matrix F(9), and the incidence matrix (().
In the WLGCL, use the line graph structure as complement to the original graph structure, thereby leading to enhanced feature learnings. Here, we use a simple feature aggregation method used in GCN (Kipf & Welling 2017). Other complicated and advanced feature aggregation methods such as GAT (Veličković et al. (017) can be casily applied by changing Eq. 2 and Eq. accordingly. Figure 3 provides illustration of our WIGGLL.
4

---

Under review as a conference paper at ICLR 2021
GEN
WELCCE
WELCCE
MLP
PPad
aPod
Figure 4: An illustration of the weighted line graph convolution network. The input graph is an undirected attributed graph. Each node in the graph contains two features. Here, GCN layer to produce low-dimensional continuous feature representations. In each of the following two blocks, use layer and a layer for feature learning and graph coarsening, respectively. We use multi-layer perceptron network for classification.
3.4 WEIGHTED LINE GRAPH CONVOLUTION LAYER VIA INCIDENCE MATRIX
In this section, we propose to implement the WLGCL using the incidence matrix. When edge features generated from node features described in Section 3.3 can significantly reduce the usage of computational resources while taking advantage of the line graph structure.
One practical challenge of using line graph structure is that consumes excessive computational resources in terms of memory usage and execution time. To use a line graph in a graph neural network, need to store its adjacency matrix, compute edge features, and perform message passing operation. Our proposed WLGCL also faces this challenge. Space and time complexities of Eq. (2). which plays the dominating role, are O O(N*) and O(E²C) Here, we set C₂ = C. for simplicity. To address this issue, we propose to use the incidence matrix B to compute the weighted line graph adjacency matrix F. The adjacency matrix F can be accurately computed with the following theorem.
O(N*C), respectively.
Theorem 2. Given an undirected graph, its incidence matrix RNE, and its degree matrix D E R., the adjacency matrix F E ExE of the weighted line graph with weights defined by Eq. 7 can be exactly compuled by
F= F B"daigg (D)- ',
(6)
where diag(.) takes a vector as input and constructs a squared diagonal matrix using the vector elements the main diagonal elements.
The proof of Theorem is provided in the supplementary material. Based on the results from
Theorem 2 can update the equations (Eq. 2 3) to generate K(0) in the WLGCL by replacing the adjacency matrix F with Eq. (6):
((O) gl0pl B X ( diag (D) B(0 (() ( L
O (D) (1)
where T
X computes edge features using node features. Notably, H B(O) B(0 only
needs to be computed once. With computed (t) we output the new feature matrix x ((+1) using equations Eq. (4 and Eq. (5)
By using the implementation Eq. (7). space and time complexities the WLGCL are reduced O(N x E) O(N*) and O(N E) O(N2 C) O(N4), respectively. Compared to the naive WLGCL implementation, they are reduced by factor of N and C², respectively. In the experimental study part, we show that the WLGCL implemented as Eq. (7) dramatically saves the computational resources compared to the naive implementation. Notably, the results in Eq. (6) can be applied to other graph neural networks that leverage the benefits of line graph structures.
3.5 WEIGHTED LINE GRAPH CONVOLUTIONAL NETWORKS
In this section, build family of weighted line graph convolutional networks (WLGCNets) that utilize our proposed WLGCLs, In WLGCNets, an embedding layer such as a fully-connected layer GCN layer is firstly used learn low-dimensional representations for nodes in the graph. Then
5

---

Under review as a conference paper at ICLR 2021
Table 1: Comparison of WI.GCNet and previous state-of-the-art models including WL (Sher- vashidze et al. 2011). PSCN (Neepert et al., 2016), DGCNN, SAGPool (Lee et al. 2019). DIFF- POOL, g- U-Net, and GIN on graph classification datasets. We report the graph classification accura- cies (%) on PROTEINS, D&D,
REDDIT-BINARY
COLLAB,
and REDDIT-MULTIOE datasets. PROTEINS
D&D
IMDBM
RDTB
RDTSK
COLLAB
RDTI2K
grapks
1113
1178
1500
2000
4999
5000
11929
nodes
39.1
284.3
13
429.6
508.5
74.5
391.4
classes
2
2
5
3
11
WL
75.0 + 3.1
78.3 + 0.6
50.9
+ 3.8
81.0 = 3.1
52.5 1 2.1
78.9 + 1.9
44.4 2.1
DGCNN
75.5 + 0.9
79.4
0.9
47.8
0.9
73.8
+ 0.5
41.8
0.6
PSCN
75.9 + 2.8
76.3 + 2.6
45.2 = 2.8
86.3 = 1.6
49.1 + 0.7
72.6 + 2.2
41.3
DIFFPOOL
76.3
80.6
75.5
47.1
SAGPool
71.9
76.5
g-U-Net
77.6
82.4 + 2.9
51.8 + 3.7
85.5 = 1.3
48.2 1 0.8
77.5 + 2.1
44.5 = 0.6
GIN
76.2 2.8
82.0
+ 2.7
52.3
+ 2.8
92.4 2.5
57.5 + 1.5
80.6 1.9
WLGCNet
78.9 1 4.2
83.8 + 2.8
56.1
+ 3.6
94.1
=
2.2
58.2 1
3.2
83.1 +
7.9
50.3 1.5
stack multiple blocks, each of which consists of WLGCL and a pooling layer (Gao & Ji 2019). Here, the WLGCL encodes high-level features while the pooling layer outputs a coarsened graph. We use the gPool layer produce a coarsened graph that helps to retain original graph structure information. To deal with the variety of graph sizes in terms of the number of nodes, we apply global readout operations on the outputs including maximization, averaging and summation (Xu al. (018). The outputs of the first GCN layer and all blocks are stacked together in the feature dimension and fed into a multi-layer perceptron network for classification. Figure provides an example of our WLGCNets.
EXPERIMENTAL STUDY
In this section, we evaluate our proposed WLGCL and WLGCNet on graph classification tasks. We demonstrate the effectiveness of our methods by comparing our networks with previous state-of- the-art models in terms of the graph classification accuracy. Besides, we evaluate the efficiency of our implementation of the WLGCL in terms of the usage of computational resources. We conduct ablation experiments to demonstrate the contributions our methods. The code and experimental setups provided in the supplementary material.
4.1 PERFORMANCE STUDY
To evaluate methods and WLGCNets, conduct experiments on graph classification tasks ing seven datasets; those are PROTEINS, D&D (Dobson & Doig (003). MUDB-MULTI (IMDBM), REDDIT-BINARY (RDTB), REDDIT-MULTISK (RITT5K), COLLAB, and REDDIT-MULTI12 (RDT12K) (Yanardag & Vishwanathan, 2015). REDDIT datasets are benchmarking large graph datasets used for evaluating graph neural networks in the community. On the datasets without node features such as RDTI2K, we use one-hot encodings of node degrees as node features (Xu et al.) 2018 To produce less biased evaluation results, we follow the practices in (Xu et al., 2018 Zhang et al. 2018) and perform 10-fold cross- cross-validation on training datasets. We use the average accuracy across 10 fold testing results with variances.
We report the graph classification accuracy along with performances of previous state-of-the- models. The results are summarized T We can observe from the results that our proposed WLGGNets significantly outperform previous models by margins of 1.3%, 1.8%. 3.8%, 1.7%, 0.7%, 2.5%, 3.2% on PROTEINS, D&D, IMDB-MULTI, REDDIT-BINARY. REDDIT-MULTISK, COL- LAB, and REDDIT-MULTII2K datasets, respectively. The promising results, especially on large benchmarking datasets such as REDDIT-MULTI2K, demonstrate the effectiveness of our proposed methods and models for network embeddings. Note that our WLGCNet uses the gPool layer from the g-U-Net. The superior performances of WLGCNets over the g-U-Net demonstrate the perfor- mance gains from proposed WLGCLL.

---

Under review as a conference paper at ICLR 2021
Table 2: Comparison of WLGGL and the WLGGL using native implementation (denoted as WLGCL,). We evaluate them on simulated data with different graph sizes in terms of the num- ber of nodes and the number of edges. All layers oulput 64 feature channels. We report the number of multiply-ades (MAdd), the amount of memory usage, and the CPU execution time. We describe
the input graph size in the format of "number of nodes / number of edges".
Input
Operator
MAdd
Saving
Memory
Saving
Time
Speedup
WL.GCL
166.478
0.00%
9.5GB
0.00%
15.73s
1.0x
1000/50000
WLGGLL
51.13B
69.28%
O. 0.19GB
97.94%
0.63s
26.2x
WLGGCLn
652.878
0.00%
37.63GB
0.00%
56.62s
1.0x
1000/100000
WLGCL
101.13B
84.51
0,38GB
98. 98.98
1.21s
47.2x
WLGCL..
1,459.27B
0.00%
86.7IGB
0.00%
134.36s
1.0x
1000/150000
WLGCL
151.13B
89.64%
0,57GB
99.34%
1.82s
74.6x
WLGCL..
1,478.66B
0.00%
99.87GB
0.00%
278.8s
1,0x
2000/150000
WLGCL
608.52B
58.85%
1.13GB
98.86%
6.19s
45.1x
4.2
COMPUTATIONAL EFFICIENCY STUDY
In Section 3.4 we propose an efficient implementation of WLGCL using the incidence matrix, which can save dramatic computational resources compared to the naive one. Here, we conduct experiments on simulated data evaluate the efficiency of our methods. We build networks that contain single layer to remove the influence of other factors. We conduct experiments on graphs of different sizes in terms of the number of nodes. Since WI.GCL takes advantage of line graph structures, the graph density has significant impact the layer efficiency. Here, the graph den- sity is defined as 2E/(N x (N - 1)). To investigate the impact of the graph density, we conduct experiments graphs with the same size but different numbers of edges.
By using the TensorFlow profile tool (Abadi et al. 2016), we report the computational resources used by networks including the number of multiply (MAdd). the amount of memory usage, and the CPU execution time. The comparison results are summarized in Table We can observe from the results that the WLGCLS with our proposed implementation putational resources than WLGCLS with naive implementation in terms of the memory usage and CPU execution time. By comparing the results on first three inputs, the advantage on efficiency of our method over the naive implementation becomes much larger as the increase of the graph density with the same graph size. When comparing results of the last two inputs with the same number of edges but different graph sizes, we can observe that the efficiency advantage of our proposed meth- ods remains the same. This shows that the graph density a key factor that influences the usage of computational resources, especially on dense graphs.
significantly less com-
4.3 RESULTS ON SMALL DATASETS
In the previous section, we evaluate our meth- ods on benchmarking datasets that are relatively large in terms of the number of graphs and the number of nodes in graphs. To provide a com- prehensive evaluation, we conduct experiments on relatively small datasets to evaluate the risk of over-fitting of our methods. Here, we use three datasets; those are MUTAG (Wale et al.
Table 3: Comparison of WLGCNet and previ- ous state-of-the-art models on relatively small datasets. We report the graph classification accu- racies on MUTAG, PTC, and IMDBB datasets.
MUTAG
PTC
IMDBB
graphs nodes
188
344
1000
17.9
25.5
19.8
WL
90.4 1 5.7
59.9
1 4.3
73.8
3.9
2008). PTC (Toivonen et al. 2003). and IMDB- BINARY (Borgwardt et al. 2005). MUTAG and PTC datasets are bioinformatics datasets with categorical features on nodes. We fol- low the same experimental settings as in Sec- tion 4.1 The results in terms of the graph clas- sification accuracy are summarized in Table 33 with performances previous state-of-the-an mod- els. We can observe from the results that our WLGCNet outperforms previous models by margins of 0.4%, 6.0%, and 3.4% on MUTAG. PTC, and IMDB-BINARE respectively. This demonstrates that our proposed models will not increase the risk of the over-fitting problem even on small datasets.
DGCNN
85.8 + 1.7
58.6
2.4
70.0
= 0.9
PSCN
92.6 4.2
60.0
1 4.8
71.0
1: 2.2
g-U-Net
87.2 7.8
64.7
6.8
75.4
3.0
GIN
90.0 1 8.8
64.6 1 7.0
75.1
5.1
WLGCNet 93.0 1 5.8
72.7 1 6.0
78.8 1. 5.1
7

---

Under review as a conference paper at ICLR 2021
4.4 ABLATION STUDY OF WEIGHTED LINE GRAPH CONVOLUTION LAYERS
In this section. we conduct ablation studies based on WLGCNets to demonstrate the con- tribution of our WLGGLLs to the entire network. To explore the advantage of line graph struc- tures, construct a network that removes all layers using line graphs. Based on the WL- GCNet, we replace WLGCLs by GCNs us- ing the same number of trainable parameters, which we denote as WLGCNet,. To compare our weighted line graph with the regular line graph, we modify our WLGGLS use regu- lar line graph structures. We denote the re- sulting network as WLGCNe4. We evaluate these networks on three datasets; those are REDDIT-BINARY REDDIT-MULTISK, and REDDIT- MULTI12K datasets. Table 4 summariie the graph classification results. We can observe from the results that both WLGCNet and WLGCNet, achieve better performances than WLGCNet,, which demonstrates the benefits of utilizing line graph structures on graph neural networks. When com- paring WLGCNet with WLGCNet,, WLGCNet outperforms WLGCNet, by margins of 0.5%, 0.5%, and 0.7% on REDDIT- BINARY, MULTISK, and REDDIT-MULTI12K datasets, respec- tively. This indicates that proposed WLGCL utilizes weighted line graph structures with unbi- ased topology information encoded, thereby leading to better performances.
Table 4: Comparison of WLGCNet, the net- work using the same architecture WLGCNet with GCN layers (denoted as WLGCNet,). ) the network using the same architecture as WLGC- Net with regular line graph convolution layers (denoted as WLGCNet,). We report the graph classification accuracies on REDDIT-BINARY, REDDIT-MULTISK, and REDIDIT-MULTII2K RDTB RDTSK
RDTI2K
WLGCNet, 93.2 # 1.5
2.2
49.1 1,5
WLGCNeti 93.6 - 2.0
57.3
3.0
49.6 H 2.8
WLGGNet 94.1 2.2
58.2 3.2
50.3 1.5
4.5 NETWORK DEPTH STUDY
Network depth in terms of the number of blocks an important hyper-paramene in the WLGC- Net. In previous experiments, we use three blocks in WLGCNets based on our empirical experiences. In this section, investigate the impact the network depth in WLGCNets on network embeddings. Based on WI.GCNet, we vary the network depth from to 5, which covers reasonable range. We evaluate these networks on PTC, PROTEINS, and REDDIT- BINARY datasets and report the graph classifi cation accuracies. Figure 3 plots the results of blocks.
90%
RITTR PTC PROTEINS
75%
70%
68%
2
WLGCNets with different numbers We can observe from the figure that the best performances are achieved on WI.GCNets with three blocks on all three datasets. When the net- work depth increases, the performances decrease, which indicates the over- over-fitting issue.
Figure 5: Comparison of WLGCNets with dif- ferent depths on PTC, PROTEINS, and REDDIT- BINARY. We report the classification accuracies.
5 CONCLUSION
In this work, we consider the biased topology information encoding in graph neural networks that utilize line graph structures to enhance network embeddings. A line graph constructed from graph can encode the topology information. However, the dynamics in the line graph are inconsistent with that in the original graph. On line graphs. the features of nodes with high degrees are more frequently passed in the graph, which causes understatement or overstatement of node features. To address this issue, we propose the weighted line graph that assigns normalized weights on edges such that the weighted degree each node is 2. Based on the weighted line graph, we propose the weighted line graph layer that leverages the advantage of the weighted line graph structure. A practical challenge faced by graph neural networks on line graphs is that they consume excessive computational resources, especially on dense graphs. To address this limitation, we propose to the incidence matrix to implement the WLGCL, which can dramatically save the computational resources. Based the WLGCL, build family of weighted line graph convolutional networks.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, al. Tensorflow: system for large- scale machine learning. In /2th {USENIX) Symposium on Operating Systems Design and Imple- mentation ((OSDI) 16), pp. 265-283, 2016.
Sambaran Bandyopadhyay. Anirban Biswas, MN Murty, and Ramasuri Narayanam. Beyond node embedding: A direct unsupervised edge representation framework for homogeneous networks. arXiv preprint arXiv:1912.051400 2019.
Karsten M Borgwardt, Cheng Soon Ong, Stefan Schönauer, SVN Vishwanathan, Alex Smola, and Pattr Kriegel. Protein function prediction via graph kernels. Bioinformatics, 21(suppL_I): i47-i56, 2005.
Zhengdao Chen, Joan Bruna Estrach, and Lisha Li. Supervised community detection with line graph neural networks. In 7th International Conference on Learning Representations, ICLR 2019, 2019.
Paul D Dobson and Andrew J Doig. Distinguishing enzyme structures from non-enzymes without alignments. Journal of molecular biology, 330(4):771-783, 2003.
TS Evans and Renaud Lambiotte. Line graphs, link partitions, and overlapping communities. Phys- ical Review E, 80(1 ):06600, 2009.
Hongyang Gao and Shuiwang Ji. Graph U-Nets. International Conference on Machine Learning. pp. 2083-2092, 2019.
Hongyang Gao, Zhengyang Wang, and Shuiwang Ji. Large-scale learnable graph convolutional networks. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1424. ACM, 2018.
Martin Charles Golumbic. Algorithmic graph theory and perfect graphs. Elsevier, 2004.
Liyu Gong and Qiang Cheng. Exploiting edge features for graph neural networks. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 9219221112 9211-9219, 2019.
Marco Gori, Gabriele Monfardini, and Franco Scarselli, new model for learning in graph domains. In 2005 IEEE International Joint Conference on Neural Networks, volume 2, pp. 729-734, 2005.
Will Hamilton, Zhitao Ying. and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, pp. 1024-1034, 2017.
Xiaodong Jiang, Pengsheng Ji, and Sheng Li. Censnet: convolution with edge-node switching in graph neural networks. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, pp. 2656-2666666 26652. AAAI Press, 2019.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. The International Conference on Learning Representations, 2015.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. International Conference on Learning Representations, 2017. 2017.
Junhyun Lee, Inyeop Lee, and Jaewoo Kang. Self-attention graph pooling, In Proceedings of The 36th International Conference on Machine Learning. 2019.
Federico Monti, Oleksandr Shchur, Aleksandar Bojchevski, Or Litany, Stephan Günnemann, and Michael M Bronstein. Dual-primal graph convolutional networks. arXiv preprint 2018.
Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. Learning convolutional neural net- works for graphs. In International Conference on Machine Learning, pp. 2014-2023, 2016.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini.
The graph neural network model. IEFE Transactions Neural Networks, 20(1):61-80. 2009.

---

Under review as a conference paper at ICLR 2021
Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn and Karsten M Borg- wardt. Weisaeiler-lhmmnn graph kernels. Journal of Machine Learning Research, 12(Sep))2539- 2011,
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, llya Sutskever, and Ruslan Salakhutdinov. Dropout: A simple way to prevent neural networks from overfitting. Journal of Machine Learning Research, 15(1):1929-1958 2014.
Bhalchandra D Thatte. Kocay's lemma, whitney's theorem, and some polynomial invariant recon- struction problems. the electronic journall of combinatorics, pp. R63-R63, 2005.
Hannu Toivonen, Ashwin Srinivasan, Ross D King, Stefan Kramer, and Christoph Helma. Statistical evaluation of the predictive toxicology challenge 2000-2001. Bioinformatics, 183-11193,,,9,, 2003.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2017.
Nikil Wale, lan A Watson, and George Karypis. Comparison of descriptor spaces for chemical com- pound retrieval and classification. Knowledge and Information Systems, 14(3):347-375, 2008.
Xi Xiong, Kaan Ozbay, Li Jin, and Chen Feng. Dynamic prediction of destinattnonnnnnnn flows using fusion line graph convolutional networks. arXiv preprint arXiv: 020.. 0005000006, 2019.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint 1rXiv:1810.00880 2018.
Pinar Yanardag and SVN Vishwanathan. A structural smoothing framework for robust graph com- parison. In Advances in Neural Information Processing Systems, pp. 2134-2142, 2015.
Weichi Yao, Afonso S Bandeira, and Soledad Villar. Experimental performance of graph neural networks on random instances of max-cut. In Wavelets and Sparsity XVIII, volume 11138, pp- 111380S. International Society for Optics and Photonics, 2019.
Zhitao Ying. Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hi- crarchical graph representation learning with differentiable pooling. In Advances in Neural Infor- mation Processing Systems, pp. 4800-450 4810, 2018
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. In Advances in Neural Information Processing Systems, pp. 5165-5175, 2018.
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In Thirty-Second AAAI Conference on Artificial Intelligence, pp. 4438 4445, 2018.
Kai Zhou, Tomasz P Michalak, Marcin Waniek, Talal Rahwan, and Yevgeniy Vorobeychik. Attack- ing iimilarity-basee link prediction in social networks. In Proceedings of the 18th International Conference on Autonomous Agents and MultiAgem Systems, pp. 305-313. International Founda- tion for Autonomous Agents and Multiagent Systems, 2019.
Shichao Zhu, Chuan Zhou, Shirui Pan, Xingquan Zhu, and Bin Wang. Relation structure- aware heterogeneous graph neural network. 2019 IEEE International Conference on Data Mining (ICDM), pp. 1534-1539. IEBE, 2019.
10

---

Under review as a conference paper at ICLR 2021
A EXPERIMENTAL SETUP
We describe the experimental setup for graph classification tasks. In this work, we mainly evaluate our methods on graph classification datasets such as social network datasets and bioinformatics datasets. The node features are created using one-hot encodings and fed into the networks. In WLGCNets, we use GCN layers as the graph embedding layers. After the first GCN layer, we stack three blocks as described in Sectionn..3) The outputs of the GCN layer and WLGCLs in three blocks are processed by readout function and concatenated as the network output. The readout function performs three global pooling operations: those are maximization, averaging, and summation. The network outputs are fed into a classifier to produce predictions. Here, we use two-layer feed- forward network with 512 units in the hidden layer the classifier. We apply dropout (Srivastaval ct al. 2014) on the network and the classifier.
We use an Adam optimizer (Kingma & Ba 2015) with learning rate of 0.001 train WLGCNets. To prevent over wver-fittnng, we apply the L2 regularization on trainable parameters with a weight decay rate of 0.0008. All models are trained for 200 epochs using one NVIDIA GeForce RTX 2080 Ti GPU on an Ubuntu 18.04 system.
B PROOF FOR THEOREM
Proof. Given nodes and b with degrees Da and D3 in a graph G, a node (a, b) in the corresponding weighted line graph W (G) connects to D and D, - nodes through and b in G, respectively. The weighted degree of the node (a, b) is computed by summing up the weights of edges that connect (a, b) other nodes through a and b, and the weight of its self-loop:
Da-1
D
1
+ 1.)
WLD (a.b) =
Σ
+
+
D
Db
D2
1=1
j=1
(8)
D₂
+
L
=2
D.
Db
A=
This completes the proof.
C PROOF FOR THEOREM 2
Proof. We construct a weighted incidence matrix by normalizing the weights as BLa. = 1/D,
Thus, the weighted incidence matrix is computed as B diag (D)-1 B. In the incidence graph, each edge is connected to its two end nodes. Thus, each column in the incidence matrix B., has non-zero entries; those are Ba,(a,)) and (a.(a.)) The same rule applies to the weighted incidence matrix B. Based on this observation, we have
BT
= Σ Blaby x Bi.(..))
(b.M)
1=1
B(a.b), Basbbe) Be,
(9)
if x
Dr
if = F(a.)
+ D.
Dv
This completes the proof.
11


Reviews:
[{"review_id": "t0KqC1d4CnV", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper introduces a GNN architecture that is based on a weighted line-graph transformation (in conjunction with a node-based architecture).\nThe central idea is that a normal line graph transformation will lead to an over-representation of certain nodes (motifs) in the network, which the authors strive to correct.\nThe efficacy of these ideas is tested in a range of numerical experiments.\n\nPro:\n* The presentation is quite clear, in my opinion apart from some smaller inaccuracies.\n* The experiments constructed appear thorough and rigorous.\n\nCons:\n* A more precise theoretical justification why their algorithm should work better (has more expressive power than other architectures) is missing\n* The improvements seen are not strong compared to other architectures\n* It seems that most of the computation could be implemented w/o ever appealing to a line graph transformation.\n\nAdditional comments:\nThe general idea of the paper sounds appealing. A line graph may be seen as a \"higher-order\" representation of a graph and thus we may (intuitively) hope that there is more information to be gained here.\nHowever, the authors argument hinges upon a single paper that shows some improvements for community detection using line-graphs, but not much further theoretical justification.\nThe fact that high-degree nodes will be over-represented (as they will have more edges in the line-graph), does not necessary mean that normalization will help. The neural network could also learn to take into account this information, in principle?\nIn particular, we know that GNN cannot be more expressive that the Weisfeiler Leman algorithm (see e.g., Morris et al); does a line-graph transformation help here and make the architecture more akin to a 2-WL network?\nI feel that some kind of stronger theoretical justification is missing here, given the computational costs of expanding the representation to edges.\nThe numerical results are not as strong to convince me in this regard.\n\nThe two theorems proven are very basic linear algebra, and cannot really be counted as a theoretical contribution here, in my opinion.\nIn particular all these ideas have already been presented in a lot of detail in the work by Evans and Lambiotte. A second citation that is missing in this context in my opinion is:\nEvans, Tim S., and Renaud Lambiotte. \"Line graphs of weighted networks for overlapping communities.\" The European Physical Journal B 77.2 (2010): 265-272.\n\nLooking at equation (7) we see that essentially all the computations in layer \\ell can be done  using node x node matrices (H, D, X), i.e., the implementation does not even need to appeal to any kind of line-graph transformation. This makes the rationale that the line-graph representation improves the learning somewhat questionable --- after all there is just a message passing between nodes going on here.\n\nIn summary, the paper provides a mixture of theory and experiments. \nUnfortunately, I feel that both the theory part and the experiments are not fully satisfactory. The theory part does not provide clear theoretical guarantees or insights why the proposed architectures would perform better, in general, I think. Moreover the computations still seem to boil down to a node-to-node message passing.\nIf the authors could provide a more rigorous justification here, this would significantly improve the paper.\n\nThe experiments appear to be rigorous, but the results are essentially on par with a number of other fully \"node-based\" methods, so it is not fully clear whether there is really a clear advantage here.\n\nMinor comments:\nHow is the incidence matrix B defined? It seems an unsigned version is used, which would be less common in a graph / network theory.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "S6I6ov6moc", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary of contribution:\nThis paper discusses graph convolutional networks.  The authors recap existing work to observe that models already exist to propagate information through graphs in two different ways:\n1. Standard propagation passes information from nodes along edges to neighboring nodes\n2. Line graph propagation adopts the same scheme on the *line graph* of the original graph:  original edges become vertices in the line graph, and these new vertices are connected when they share an endpoint in the original graph.\n\nThe authors suggest a model that simultaneously propagates information in both graphs, coupling the two propagations at each step.\n\nThey additionally observe that high-degree vertices in the original graph induce cliques in the line graph, which will naively result in over-weighting such vertices, as they have many more paths along which to propagate information.  They propose reweighting the line graph so that vertices in the line graph all have weighted degree 2.\n\nThey perform a series of experiments using this combined propagation scheme through the graph and the weighted line graph.  The experiments cover graph classification tasks, and are well thought out.  There are a number of tasks with larger graphs, plus experiments with smaller graphs to test over-fitting.  There are a few ablation studies, and a sensitivity study on depth of their architecture.\n\nStrong points:\n* The weighting argument for line graphs seems natural, and as far as I can tell the authors are the first to propose this.\n* The coupling of propagation in the two graphs is elegantly established and also seems natural\n* The experiments are well-defined, and the results themselves are pretty compelling (but please see question below)\n\nWeak points / concerns:\n* The main proposed points of novelty in the paper are as follows, as far as I can tell:\n  N1: Weighted line graphs.  Line graphs themselves have been used before, and the weighting scheme itself is straightforward -- I believe it has been used before in combinatorial algorithms based on line graphs.\n  N2: There is a small optimization to avoid materializing the cliques in the line graph during propagation, but this also seems natural; in fact, it would be a bug not to retain the propagation structure in this clearly more efficient representation.\n  N3: The coupling of propagations in equation 5 seems nice.\nThese haven't been studied before, and N3 seems quite nice, but I don't see significant mathematical advances in this structure or significant advances in information flow.  I still feel pretty good about the contributions of the paper as they combine a number of natural steps, and they show good empirical outcomes.\n\nQuestions for the authors:\nQ1. In Table 1, I'm surprised that the WLGCNet has confidence intervals that overlap significantly with, say, GIN for many of the datasets.  However, there is never an inversion in the order of the winning system.  Depending on how the CIs were computed, this seems like an unexpected coincidence, which makes me think I may not understand the computation of the confidence intervals here.  Would appreciate some clarification.\nQ2. The optimization holds only for graphs where the edge features are materialized from the vertex features.  Does this hold for all the datasets?  ", "extra_scores": {}, "extra_text": {}}, {"review_id": "NHFrT1acso", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposed a GNN model based on a weighted line graph, which adds weights to the line graph for the original input graph in a node/graph property prediction task. The line graph is a graph built on the original graph but with edges as nodes. A new convolution called weighted line graph convolution layer (WLGCL) is proposed to overcome the issue of \"biased topological information\" of the line graph. The weights for the line graph in WLGCL are computed based on the node degree of the original graph, which implies the node degree in the line graph is always 2. The WLGCL can be implemented for different kinds of graph convolution, which rule incorporates graph connectivity, node features and edge features.  \nExperiments compared the performance of the proposed model with existing GNN methods on graph classification tasks and computational complexity with other methods.\n1. The WLGCL introduces the weights for edges in line graph convolution, which reduces the computational cost. The performance of WLGCL on some graph classification datasets are good. \n2. The WLGCL is a weighted version of the line graph neural networks (LGNNs) as studied previously in [Chen, Li, Bruna, Supervised Community Detection with Line Graph Neural Networks, ICLR 2019]. \nBesides saving the computational cost and removing biased degree information, what are other benefits over LGNN? Is there a significant improvement of the test accuracy against LGNN on various types of graph datasets? Maybe saying “biased topological information” here is misleading as what change the WLGCL makes compared to LGNN is the node degree.\n3. The experiments, like Table 1, compare with some existing GNNs methods. The author should compare with more existing GNNs, such as GAT. The new datasets, Open Graph Benchmarks, should also be tested to show the performance of the proposed GNN model.\n4. What is the performance of WLGCL with the normalisation of the adjacency matrix on graph classification tasks?\n5. The study of the test accuracy vs depth of the GNN with WLGCL indicates the WLGCL may work in deep nets. Will increase the depth further be beneficial or not? Is there any interpretation from information theory?", "extra_scores": {}, "extra_text": {}}, {"review_id": "Mfs33e1HUw2", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "# Summary\nThis paper introduces a weighted line graph formulation (WLGCL) which corrects the over-counting (\"bias\") of high-degree node features in a line-graph based convolutional network. Further, the paper uses Incidence Matrix to implement WLGCL updates which reduces the space complexity ($O(N^4) \\to O(N^3)$) and time complexity ($O(N^4 C) \\to O(N^4)$) compared to the naive implementation. The paper shows empirical evaluation on downstream task of graph classification and shows gain in accuracy. \n\n# Observations\n- The use of the word \"dynamics\" (Page 1, paragraph 2) in the context of over-representation of node features in the message passing is very confusing. Typically, \"dynamics\" in the context of graph networks often implies changing graph structure which is not the case here. The usage is taken from [Evans & Lambiote, 2009] (https://arxiv.org/pdf/0903.2181.pdf) but in that context it refers to random walks. \n\n- The paper mentions on Page 4 last line that \"advanced feature aggregation methods such as GAT\" can easily be applied to the line graph. This should be demonstrated, e.g., in the supplementary material.  As a note, in the paper [Monti et al. 2018] (available only on https://arxiv.org/pdf/1806.00770.pdf) also presents line-graph formulation with GAT applied to the line graph. \n\n- [Bandhopadhyay et al. 2019]  also present a weighted line graph but since it is only present on Arxiv (https://arxiv.org/abs/1912.05140), I disregard lack of comparison with that paper. \n\n- It is not clear which datasets have node features - this should be clearly mentioned preferably in the main text but if not definitely in the supplementary material. \n\n-  The paper claims performance improvement over graph U-net which demonstrates the benefit of weighted approach which does unbiased node-feature updates. For PROTEINS and COLLAB datasets, the standard deviation of the proposed method is significantly higher than competing methods - what would be the possible explanation for this? \n\n- The benefit of using Incidence Matrix based updates is clear in terms of space and time complexity. However, I would like to see comparison with other methods on space/time complexity if focussing solely on graph classification task. \n\n# Optional remarks \n- It is not necessary but might be useful to show evaluation on other downstream tasks.  For example, in downstream task of node classification - CORA, Citeseer, Pubmed (see e.g., the Graph U-nets paper). \n\n- The node feature bias might be more relevant when there are edge features as well. To my understanding, the current datasets do not have edge features.  For example, please see the CensNet paper (cited as Jiang, 2019 in this paper) and the multi-task classification datasets (_Tox21_ and _Lipophilicity_)\n\n# Minor comments\n- What is the dropout rate (Appendix A)? \n- As the model trains, a plot showing the test metrics would be good in the supplementary. \n\n# Recommendation \nOverall, I vote to reject the paper. I do not disagree with the main premise of the paper but feel that it needs some rewriting as well as additional empirical evaluation.", "extra_scores": {}, "extra_text": {}}, {"review_id": "Bc0ZRGeWpfE", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes passing messages on the line graph for learning representations of graphs. To overcome the bias that high-degree nodes are over-emphasized during message passing, the authors propose to reweight edges in the line graph. Then it performs message passing on both the original graph and the weighted line graph. The authors also use incidence matrix in their model to reduce computation overhead. Overall, this paper is well written and easy to follow. The experimental results demonstrate the effectiveness and efficiency of the proposed method. However, I have the following concerns:\n\n1. In eq.1, the weight of self loops is 1/D_b + 1/D_a, but it is unclear why it should be designed like this. Does it mean that self loops are more important in the line graph? It seems more likely for the purpose of deriving Theorem 1.\n\n2. In eq. 2-5, how is the edge feature matrix Y_l updated to Y_{l+1} is not specified.\n\n3. In experiments the authors only conduct experiments on graph classification. Can the proposed method be applied to node classification? Does it work on large graphs with thousands of nodes?\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposed a GNN model based on a weighted line graph (dual of the input graph), where information is simultaneously propagated on both graphs, coupling the two propagations at each step. 

Overall, the reviewers were lukewarm about the paper, with some raised criticism including 
- limited novelty in light of Monti et al. 2018
- limited theoretical justification
- unconvincing and incomplete experiments, not offering significant improvement compared to other alternatives

While the presented approach is interesting, we believe the paper is below the bar and recommend Rejection. 

Decision: Reject