Edge Representation Learning with Hypergraphs
Authors: Jaehyeong Jo
Jinheon Baek
Seul Lee
Dongki Kim
Minki Kang
Sung Ju Hwang
Venue: NeurIPS 2021 Poster (2021)
Keywords: Graph Neural Network
Edge Representation Learning
Graph Pooling
Hypergraph

Abstract: Graph neural networks have recently achieved remarkable success in representing graph-structured data, with rapid progress in both the node embedding and graph pooling methods. Yet, they mostly focus on capturing information from the nodes considering their connectivity, and not much work has been done in representing the edges, which are essential components of a graph. However, for tasks such as graph reconstruction and generation, as well as graph classification tasks for which the edges are important for discrimination, accurately representing edges of a given graph is crucial to the success of the graph representation learning. To this end, we propose a novel edge representation learning framework based on Dual Hypergraph Transformation (DHT), which transforms the edges of a graph into the nodes of a hypergraph. This dual hypergraph construction allows us to apply message-passing techniques for node representations to edges. After obtaining edge representations from the hypergraphs, we then cluster or drop edges to obtain holistic graph-level edge representations. We validate our edge representation learning method with hypergraphs on diverse graph datasets for graph representation and generation performance, on which our method largely outperforms existing graph representation learning methods. Moreover, our edge representation learning and pooling method also largely outperforms state-of-the-art graph pooling methods on graph classification, not only because of its accurate edge representation learning, but also due to its lossless compression of the nodes and removal of irrelevant edges for effective message-passing.

Edge Representation Learning with Hypergraphs
Jaehyeong Jo Jinheon Baek'", Seul Lee':, Dongki Kim', Minki Kang', Sung Ju Hwang 1.2
KAIST' AITRICS South Korea
harryjo97@kaistt.co ac. kr, jinheon baekOkaist. ac. el1emlee77900gmai. com, cleverki@haist.ac kc. zexc11330kaist.ac. kr, sjhwang620kaist.co ac. ac.kr
Abstract
Graph neural networks have recently achieved remarkable success in representing graph-structured data, with rapid progress in both the node embedding and graph pooling methods. Yet, they mostly focus capturing information from the nodes considering their connectivity, and not much work has been done in representing the edges, which are essential components of graph. However, for tasks such as graph reconstruction and generation, as well as graph classífication tasks for which the edges are important for discrimination, accurately representing edges a given graph is crucial to the success of the graph representation learning. To this end, propose novel edge representation learning framework based on Dual Hypergruph Transformation (DHT), which transforms the edges of a graph into the nodes of hypergraph. This dual hypergraph construction allows us to apply message-passing techniques for node representations to edges. After obtaining edge representations from the hypergraphs, we then cluster drop edges to obtain holistic graph-level edge representations. We validate our edge representation learning method with hypergraphs on diverse graph datasets for graph representation and generation performance, on which our method largely outperforms existing graph representation learning methods. Moreover, our edge representation learning and pooling method also largely outperforms state-of-the. art graph pooling methods on graph classification, not only because of its accurate edge representation learning, but also due to its lossless compression of the nodes and removal of irrelevant edges for effective message-passingg
Introduction
The recent demand in representing graph-structured data, such as molecular, social, and knowledge graphs, has brought remarkable progress in the Graph Neural Networks (GNNs) [44, 37J. Early works GNNs [23, 15, 39] aim accurately represent each node reflect the graph topology, by transforming, propagating, and aggregating information from their neighborhoods based on message- passing schemes [12]. More recent works focus on learning holistic graph-level representations, by proposing graph pooling techniques that condense the node-level representations into smaller graph or single vector. While such state-of of-the-rrt node embedding or graph pooling methods have achieved impressive performances on graph-related tasks (c.g., node classification and graph classification), they have largely overlooked the edges, which are essential components of graph.
Most existing GNNs, including ones that consider categorical edge features [32, 12], only implicitly capture the edge information in the learned node/graph representations when updating them. While
"Equal contribution
Code is available at http:///iihubbcoo//harry///////1
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Input Graph
Dual Hypergraph Transformation (DHT)
HyperCluster
Global Edge Representation
(a) Tylenol (Beneficial)
Message Possing
HyperDrop
Output Graph
Message Passing
Badd-to-Hypereda Edge-to-Node
(b) NAPQI (Toxic)
DHT
Figure 1: (Left)): The two molecular graphs have the identical set of nodes, but possess completely different properties due to the difference in edges. (Right); An illustration of the proposed edge representation learning framework with two novel edge pooling schemes. The grey box in the center describes the proposed Dual Hypergraph Transformation, where the numbers (letter)) denote the corresponding edges (nodes) in the graph and nodes (hyperedges) in the hypergraph. The two blue boxes in the right illustrate the proposed edge pooling methods, HyperCluster which clusters similar edges, and HyperDrop which drops unnecessary edges.
few of them aim to obtain explicit representations for edges [20, 13, 40], they mostly use them only to augment the node-level representations, and thus suboptimally capture the edge information. This is partly because many benchmark tasks for GNN performance evaluation, such as graph classification, do not require the edge information to be accurately preserved. Thus, on this classification task, simple MLPs without any connectivity information can sometimes outperform GNNs [9, 18]. However, for tasks such as graph reconstruction and generation, accurately representing the edges of graph is crucial to success, as incorrectly reconstructing geaeeernngggnriiingggggg edges may result complete failure of the tasks. For example, the two molecules (a) and (b) in Figure have exactly the same set of nodes and are only different in their edges (bond types), but exhibit extremely different properties.
To overcome such limitations of existing GNN methods in edge representation learning, we propose a simple yet effective scheme represent the edges. The main challenge of handling edges is the absence or suboptimality of the message-passing passing scheme for edges. We tackle this challenge by representing the edges as nodes in hypergraph, which is generalization of a graph that can model higher-order interactions among nodes as one hyperedge can connect an arbitrary number of nodes. Specifically, we propose Dual Hypergraph Transformation (DHT) to transform edges of the original graph to nodes of a hypergraph (Figure 1), and nodes to hyperedges. This hypergraph-basedd approach is effective since it allows us to apply any off-the-shelf message-passing schemes designed for level representation learning, for learning the representation of the edges of a graph.
However, representing each edge well alone insufficient in obtaining an accurate representation of the entire graph. Thus we propose two novel graph pooling methods for the hypergraph to obtain compact graph-level edge representations, namely HyperCluster and HyperDrop. Specifically, for obtaining global edge representations for an entire graph, HyperCluster coarsens similar edges into a single edge under the global graph pooling scheme (see HyperCluster in Figure 1). On the other hand, HyperDrop drops unnecessary edges from the original graph by calculating pruning scores on the hypergraph (see HyperDrop in Figure 1). HyperCluster is more useful for graph reconstruction and generation as it does not result in the removal of any edges, while HyperDrop is more useful for classification as learns to remove edges that are less useful for graph discrimination.
We first experimentally validate the effectiveness of the DHT with HyperCluster, on the reconstruction of synthetic and molecular graphs. Our method obtains extremely high performance on these tasks, largely outperforming baselines, which shows its effectiveness in accurately representing the edges. Then, we validate our method on molecular graph generation tasks, and show that it largely outperforms base generation methods, as it allows us to generate molecules with more correct bonds (edges). Further, we validate HyperDrop on 10 benchmark datasets for graph classification, on which HyperDrop outperforms all hierarchical pooling baselines, with larger gains on social graphs, for which the edge features are important. Our main contributions are summarized as follows:
We introduce novel edge representation learning scheme using Dual Hypergraph Transforma- tion, which exploits the dual hypergraph whose nodes are edges of the original graph, on which we can apply off-the-shelf message-passingg passing schemes designed for node-level representation learning.
We propose novel edge pooling methods for graph-level representation learning, namely Hyper- Cluster and HyperDrop, to overcome the limitations of existing node-based pooling methods.
We validate our methods on graph reconstruction, generation, and classification tasks, on which they largely outperform existing graph representation learning methods.
We depict only the heavy atoms, as conventional preprocessing of molecular graphs drops hydrogen atoms.

---

2 Related Work
Graph neural networks Graph neural networks (GNNs) mostly use the message-passing scheme [12] to aggregate features from their neighbors. Particularly, Graph Convolutional Net- work (GCN) [23] generalizes the convolution operation in the spectral domain of graphs, and updates the representation of each node by applying the shared weights on it and its neighbors' representations. Similarly, GraphSAGE [15] propagates the features of each node's 's neighbors to itself, based on simple aggregation operations (c.g., mean). Graph Attention Network (GAT) [34] considers the relative importance on neighboring nodes with attention, to update each node's representation as the weighted combination of its neighbors', Xu et al. [39] show that simple sum on neighborhood aggregation makes GNNs as powerful as the Weisfeiler-Lehman (WL) test [36], which is effective for distinguishing different graphs. While GNNs have achieved impressive success on graph-re graph-related tasks, most of them only focus on learning node-level representations, with less focus on the edges.
Edge-aware graph neural networks Some existing works on GNNs consider edge features while updating the node features [3], however, they only use the edges as auxiliary information and restrict the representation of edges as the discrete features with categorical values. While a few methods [20, 12, 13, 40] explicitly represent edges by introducing edge-level GNN layers, they use the obtained edge features solely for enhancing node features. Also, existing message- paassaggg schemes for nodes are not directly applicable to edge-level layers, as they are differently designed from the node-level layers, which makes it challenging to combine them with graph pooling methods [41] for graph-level representation learning. We overcome these limitations by proposing a dual hypergraph transformation scheme, to obtain a hypergraph whose nodes are edges of the original graph, which allows us apply any message- paaiggngggggnggggg layers designed for nodes to edges.
Graph transformation Recently, some works [21. 27] propose to transform the original graph into a typical graph structure, to apply graph convolution for learning the edge features. Specifically, they construct line graph [16], where the nodes of the line graph correspond to the edges of the original graph, and the nodes of the line graph are connected if the corresponding edges of the original graph share the same endpoint. However, the line graph transformation has obvious drawbacks: 1) the transformation is not injective, thus two different graphs may be transformed into the same line graph; 2) the transformation is not scalable; 3) node information in the original graph may be lost during the transformation. Instead of using such a graph structure, we use hypergraphs, which can model higher-order interactions among nodes by grouping multi-node relationships into a single hyperedge [3]. Using the hypergraph duality [31], edges of the original graph are regarded as the nodes of a hypergraph. For example, Lugo-Martinez and Radivojac [26] cast hyperlink prediction task as an instance of node classification from the dual form of the original hypergraph. On the other hand, Kajino [22] uses the duality to extract useful rules from the hypergraph structures by transforming molecular graphs, for their generation. However, none of the existing works exploit the relation between the original graph and the dual hypergraph for edge representation learning.
Graph pooling Graph pooling methods aim to learn accurate graph-level representation by com- pressing a graph into a smaller graph or vector with pooling operations. The simplest pooling approaches are using mean, sum or max over all node representations [1, 39]. However, they treat all nodes equally, and cannot adaptively adjust the size of graphs for downstream tasks. More advanced methods, such as node clustering methods, coarsen the graph by clustering similar nodes based on their embeddings [41, 4], whereas the node pruning methods reduce the number of nodes from the graph by dropping unimportant nodes based on their scores [11, 24]. Ranjan et al. [29] combine both node pruning and clustering approaches, by dropping meaningless clusters after grouping nodes. Back et al. [2] propose to use attention- based operations for considering relationships between clusters. Note that all of those pooling schemes not only ignore edge representations, but also alter the node set by dropping, clustering, merging nodes, which result in an inevitable loss of node information.
3 Edge Representation Learning with Hypergraphs
In this section, we first introduce our novel edge representation learning framework with dual hypergraphs, which we refer to as Edge HyperGraph Neural Network (EHGNN), and then propose two novel edge pooling schemes for holistic graph-level representation learning: HyperCluster and HyperDrop. We begin with the descriptions of graph neural networks for node representation learning.
3

---

Input Graph
Dual Hypergraph Transformation
Dual Hypergraph G" Node X"
Node
X
(+)
(b)
Incidence
Incieecce M' M
(d)
(c)
Edge
(a) Edge-to-Node
(b) topperto-ypeerdge
Hyperedge
F
(d) Node-to-Edge
(c) Hyperedge to Node
F' =
Figure 2: Dual Hypergraph Transformation. Illustration of the proposed graph-to truph-to-hypenn hypergraph transformation.
Graph neural networks A graph G with n nodes and m edges, is defined by its node features E Rnndd, edge features E E Rmmx",, and the connectivity among the nodes represented by an adjacency matrix A E R=x=. Here, d and d' are the dimensions of node and edge features, respectively. Then, given a graph, the goal of a Graph Neural Network (GNN) is to learn the node-level representation with message-passingg between neighboring nodes [12] as follows:
X
x = UPDATE , AGGREGATE ({
[x Vu E EN(0; a)}))
(1)
where (4) is the node features at I-th layer, AGGREGATE is the function that aggregates messages from a set of neighboring nodes of the node v, UPDATE the function that updates the representation of the node v from the aggregated messages, and ((;; A) is the set of neighboring nodes for the node v. obtained from the adjacency matrix A. Such message-passing schemes can incorporate the graph topology into each node by updating its representation with the representation of its neighbors.
3.1 Edge representation learning with dual hypergraph transformation
Edge representation learning To reflect the edge information message-pussing, some works on GNNs first obtain the categorical edge features between nodes, and then use them on the AGGRE- GATE function in equation 1, by adding multiplying the edge features the neighboring node's features [12, 32] (see Section A. of the supplementary file for more details). Similarly, few recent works aim to obtain explicit edge representations, but only to use them as auxiliary information to augment the node features, by adding or multiplying edge features to them [13, 40J. Thus, existing works only implicitly capture the edge information in the learned node representations. Although this might be sufficient for most benchmark graph classification tasks, many real-world tasks of graphs (e.g., graph reconstruction and generation) further require the edges to be accurately represented as the information on edges could largely affect the task performance.
Even worse, to define pressage-passing function for edge representation learning, existing works pro- pose additionally create the adjacency matrix for edges, either by defining the edge neighborhood struc- ture [40] or using the line graph transformation [20]. However, these are highly suboptimal as obtaining the adjacency of edges requires O(n²) time complex- ity (see Section A.3 of the supplementary file for detailed descriptions), as shown in Table 1. This
Table 1: Transformation and message- paagee-pasiingggg. complexities of edge-aware GNNs, line graph, and our EHGNN for the star graph, in which one hub node is connected n other nodes.
Models
Transformation Mesage-passing
Complexity
Edge aware GNNs
O(n")
O(n)
Line graph
O(x))
O(n))
HHGNN (Ours)
O(n)
O(x)
the main obstacle for directly applying existing message-passingg schemes for nodes to edges. To this end, we propose a simple yet effective method to represent the edges of graph, using a hypergraph.
Hypergraph A hypergraph is generalization of graph that can model graph-structured data with higher-order interactions among nodes, wherein a single hyperedge connects an arbitrary number of nodes, unlike in conventional graphs where an edge can only connect two nodes. For example, in Figure 2, the hyperedge B defines the relation among three different nodes. To denote such higher-order relations among arbitrary number of nodes defined by a hyperedge, we use an incidence matrix M E {0, 1)mmm which represents the interaction between n nodes and m hyperedges, instead of using an adjacency matrix A E {0, 1]"X" that only considers interactions among n nodes. Each entry in the incidence matrix indicates whether the node is incident to the hyperedge. We can formally define a hyperagraph G* with nodes and m hyperedges, as a triplet of three components
G = (x* M E*), where X* E Raxd is the node features, E E IRmxdd is the hyperedge features, and M E (0, 1]axm is the incidence matrix of the hypergraph. We can also represent conventional graphs in the form of hypergraph, G (X, M, E), in which hyperedge in the

---

incidence matrix M is associated with only two nodes. In the following paragraph, we will describe how to transform the edges of graph into nodes of hypergraph, for edge representation learning.
Dual Hypergraph Transformation If we can change the role of the nodes and edges of the graph with a shared connectivity pattern across the nodes and edges, while accurately preserving their information, then we can use any node-based achieve this, inspired by the hypergraph duality [3. 31J, we propose to transform an edge of the original graph into a node of a hypergraph, and a node of the original graph into a hyperedge of transformation
pressage-passin schemes for learning edges. To
the same hypergraph. We refer this wraph-to-hypergrang Transformation (DHT) (see Figure 2). To be more precise, during the transformation, we interchange the structural role of nodes and edges from the given graph, obtaining the incidence matrix for the new dual hypergraph simply by transposing the incidence matrix of the original graph (see the incidence matrix in Figure 2). Along with the structural transformation through the incidence matrix, the DHT naturally interchanges node and edge features across G and G' (see the feature matrices in Figure 2). Formally, given a triplet representation of graph. DHT is defined as the following transformation:
Dual Hypergraph
DHT G MX E) - G (E, .)).
(2)
where we refer to the transformed G as the dual hypergraph of the input graph G. Since the dual hypergraph G = (E, M X) retains all the information of the original graph, we can recover the original graph from the dual hypergraph with the same DHT operation as follows:
DHT- G = (E, M x) G (X, M).
This implies that DHT is a bijective transformation. DHT is simple to implement, does not incur the loss of any features or topological information of the input graph, and does not require additional memory for feature representations. Moreover, DHT can be sparsely implemented using the edge list, which is the sparse form of the adjacency matrix, by only reshaping the edge list of the original graph into the hyperedge list of the dual hypergraph (see Section A.2 of the supplementary file for details), which is highly efficient terms of time and memory. Thanks to DHT, we define the mnessage-passing between edges of the original graph as the message-passing between nodes of its dual hypergraph.
Message-passing on the dual hypergraph for edge representation learning After transforming the original graph into its corresponding dual hypergraph using DHT, we can perform the message- passing between edges of the input graph, by performing the message-passingg between nodes of its dual hypergraph G (E, M X), which is formally denoted as follows:
E((+1) UPDATE E(D,, AGGREGATE ((E)): VV E ((eeM*)))
(4)
where EU!) is the node features of G at (-th layer, the AGGREGATE function summarizes the neighboring messages of the node e of the dual hypergraph G*, and the UPDATE function updates the representation of the node from the aggregated messages. Here (ee; MT) is the neighboring node set of the node e in G*, which we obtain using the incidence matrix T of G*. Furthermore, instead of using the dense incidence matrix, we can sparsely implement the message-passing on the dual hypergraph with the hyperedge list, from which the complexity of gressage-passing on the dual hypergraph reduces to O(m), which is equal to the complexity of message-passing between nodes on the original graph (See Section A.3 of the supplementary file for details). Note that, since the form of equation 4 the same as the form of equation 1, we can use any graph neural networks which realize the message- passesppssnngggg operation in equation 1, such as GCN [23], GAT [34], GraphSAGE [15], and GIN [39], for equation 4. In other words, to learn the edge representations E of the original graph, we do not require any specially designed layers, but simply need to perform DHT to directly apply existing off-the-shelf message-passe passinn schemes to the transformed dual hypergraph.
To simplify, we summarize the equation follows: (++1) GNN (x(), (1) M, E and the equation 4 as follows: E(++1) = GNN "DW,'' , = EHGNN (x(),, M,, E"), where EHGNN indicates our edge representation learning framework using DHT. After updating the edge features E(L) with EHGNN, E(4) is returned to the original graph by applying DHT on the dual hypergraph G*. Then, the remaining step is how to make use of these edge-wise representations to accurately represent the edges of the entire graph, which we describe in the next subsection.
5

---

3.2 Graph-level edge representation learning with edge pooling
Existing graph pooling methods do not explicitly represent edges. To overcome this limitation, we propose two novel edge pooling schemes: HyperCluster and HyperDrop.
Graph pooling The goal of graph pooling is to learn a holistic representation of the entire graph. The most straightforward approach for this is to aggregate all the node features with mean or sum operations [1, 39], but they treat all nodes equally without consideration of which nodes are important for the given task. To tackle this limitation, recent graph pooling methods propose to either cluster and coarsen nodes [41, 4] or drop unnecessary nodes [11, 24]. While they yield improved performances on graph classification tasks, they suffer from an obvious drawback: inevitable loss of both node and edge information. The node information is lost as nodes are dropped and coarsened, and the edge information is lost as edges for the dropped nodes or internal edges for the coarsened nodes are removed. To overcome this limitation, we propose graph-level edge representation learning scheme.
HyperCluster
We first introduce HyperCluster, which is novel edge clustering method to coarsen similar edges into a single edge, for obtaining the global edge representation. Generally, a clustering scheme for nodes of the graph [41, 4] is defined as follows:
pool = CT M = C
(5)
where X E Tlot xd and M E TR'pp Xm denote the pooled representations, X' GNN (X, M, EE) Rnxd is the updated node features, and C E R= the cluster assignment matrix that is generated from the X'. Following this approach, the proposed HyperCluster clusters similar edges into single edge, by clustering nodes of the dual hypergraph obtained from the original graph via DHT. In other words, we first obtain the node representation of the dual hypergraph E' = EHGNN (X, M, E) E Rmxd" and then cluster the nodes of the dual hypergraph as follows:
E = -CTE', (M = M MTM
(6)
where Egool E you xd' and Mool E R denote the pooled edge representation and the incidence matrix of the input graph respectively, and C E Pmmxmppo is the cluster assignment matrix generated from the input edge features E'. Since HyperCluster coarsens the edges rather than dropping them, this edge pooling method is more appropriate for tasks such as graph reconstruction.
HyperDrop We propose another edge pooling scheme, HyperDrop. which drops unnecessary edges to identify task-relevant edges, while performing lossless compression of nodes. Conventional node drop methods [11, 24] remove less relevant nodes based on their scores, as follows:
pool
Xidx
M = Mide : idr top, (score()))
where idæ is the row-wise (i.e., node mode- indexing vector, score(-) computes the score of each node with learnable parameters, and (-) selects the top h elements in terms of the score. However, this approach results in the inevitable loss of node information, as it drops nodes. Thus, we propose to coarsen the graph by dropping edges instead of nodes, exploiting edge representations obtained from our EHGNN. HyperDrop selects the top-ranked edges of the original graph, by selecting the top-ranked nodes of the dual hypergraph. The pooling procedure for HyperDropp is as follows:
Epool
Eide
(Mpool y = (M") Jide ida = ttpp (score( (E)).
(8)
Then, we can obtain the pooled graph Grool = (X, M E by applying DHT to the pooled dual hypergraph. HyperDrop is most suitable for graph classification tasks, as it identifies discrim- inative edges for the given task. Since HyperDrop preserves the nodes intact, it can also be used for node-level classification tasks, which is impossible with exiting graph pooling methods that modify nodes. In another point of view, the proposed HyperDrop can be further considered as a learnable graph rewiring operation, which optimizes the graph for the given task by deciding whether to drop or maintain the nodes. Finally, a notable advantage of such HyperDrop is that it alleviates the smoothigg problem in deep GNNs [25] (i.e., the features of all nodes converge to the same values when stacking large number of GNN layers). As HyperDrop learns to remove unnecessary edges, the sasssge-passsigg only happens across relevant nodes, which alleviates over-smoothing

---

Figure 3: Edge reconstruction results the ZINC molecule dataset by varying the pooling ratio. Solid lines denote the mean, and shaded areas denote the standard deviation of 5 runs.
Figure 4: Edge reconstruction results of the synthetic twa-moon graph. The edge fea- tures are represented by colors.
GGCNal MPNN+GGPPol
RGCN y GMPaol
Hypercluster (ours)
[4] Original
(b) EGCN GMiPool
(4) MPNN GMilool
LGNN+GMPool
Accuracy (%)
Validity (%)
Exact Match (%)
100
000
100
90
80
R-GCN GMPPol
(e) EGNN GMPool
(n HyperCluster (Ours]
20
15
10 Pooling ratio (%)
Pooling ratio 196
Pooling ratio (%)
HyparCllster
[n] Original
(bJR-GEN GMPool
MPNN GMPool GMPao
EGMN a GMPool
Accuracy (%)
Validity (%)
Exact Match (%)
90
75
(c11 Durs
(c2) Ours clustered
80
60
25
20
10
15 Pooling ratio (9)
1.
30 15. Paoling ratio (8)
15
Figure 6: Graph reconstruction examples. Red dashed circles and squares indicate the incorrectly predicted edges and nodes, re- spectively. (c.2) shows the assigned clusters of edges as colors using our method.
Pooling ratio 1%6
Figure 5: Graph reconstruction results on the ZINC molccule dataset by varying the pooling ratio. Solid lines denote the mean, and shaded areas denote the standard deviation of 5 runs.
Experiments
We experimentally validate the effectiveness of EHGNN coupled with either HyperCluster or Hyper- Drop on four different tasks: graph reconstruction, generation, classification, and node classification.
4.1 Graph reconstruction
Accurately reconstructing the edge features is crucial for graph reconstruction tasks, and thus we validate the efficacy of our method on graph reconstruction tasks first.
Experimental setup We first validate our EHGNN with HyperCluster on the edge reconstruction tasks, where the goal is to reconstruct the edge features from their compressed representations. Then, we evaluate our method on the graph reconstruction tasks to validate the effectiveness of ours in holistic graph-level learning. We start with edge reconstruction of synthetic two-moon graph, where node features (coordinates) are fixed and edge features are colors. For edge and graph reconstruction of real-world graphs, we use the ZINC dataset [19] that consists of 12K molccular graphs [7], where node features are atom types and edge features are bond types. We use accuracy, validity, and exact match evaluation metrics. For more details, please see Section C. of the supplementary file.
Implementation details and baselines We compare the proposed EHGNN framework against edge-aware GNNs, namely EGCN [17], MPNN [12], R-GCN [32], and EGNN [13], which use the edge features as auxiliary information for updating node features. We further combine them with an existing graph pooling method, namely GMPool [2], obtain a graph-level edge representation for a given graph. In contrast, for our method, we first obtain edge representations with EHGNN, using GCN [23] as the message-passing function, and then coarsen the edge-wise representations using HyperCluster, whose cluster assignment matrices are obtained using GMPool [2]. For node reconstruction, we set pesssage-passing to GCN and graph pooling GMPool [2] for all models. We provide further details of the baselines and our model in Section C.1 of the supplementary file.
Edge reconstruction results Figure 4 shows the original two-moon graph and edge-reconstructed graphs, where edge features are represented as colors, exhibiting clustered patterns. The baselines fail to reconstruct the edge colors, since they implicitly learn edge representations by using edge features as auxiliary information to update nodes, hence mixing the colors of the neighboring edges. On the other hand, our method distinguishes each edge cluster, which shows that our method can capture meaningful edge information by clustering similar edges. Moreover, as shown in Figure 3, our model obtains significantly higher performance over all baselines on the edge reconstruction task of molecular graphs, in all evaluation metrics. The performance gain of our method over baselines notably large exact match, which demonstrates that explicit learning of edge representation essential for the accurate encoding of the edge information.
7

---

MotdAh BA
Dataset
Metries
MARS [38]
MARS ERGNN (Ours)
Success Rate
59.53 2.11
64.30 1.54
5
QED 0.67)
95.71 + 0.09
96.36 = 0.49
ZINC15
0.1
GSK33 (2 0.6)
86.52 2: 1.67
90.63 = 2.57
JNK3 0.6)
71.52
73,60
3.0
Discriminator Iteration
500
1000 1500
0.0g
Discriminator Iteration
500
1000
1500
Table 2:
Graph generation results on MARS. The
Figure 7: Graph generation results on MolGAN.
results are the mean and standard deviation of differ- ent runs. Best performance and its comparable results
Solid lines denote the mean, and shaded areas denote the standard deviation of different runs.
(p 0.05) from the t-test are highlighted in bold.
Graph reconstruction results To verify the effectiveness of learning accurate edge representations for reconstructing both the node and edge features, we now validate our method on the molecular graphs in Figure 5. Combining our edge representation learning method (EHGNN + HyperCluster) with the existing node representation learning method (GCN + GMPool) yields incomparably high reconstruction performance compared to the baselines in exact match, which demonstrates that learning accurate edge representation, as well as node representation, is crucial to the success of the graph representation learning methods on graph reconstruction.
Qualitative analysis We visualize the original and reconstructed molecular graphs in Figure 6. As shown in Figure 6 (b), the bascline cannot reconstruct the ring structures of the molecule, whereas our method perfectly reconstructs the rings well as the atom types. The generated edge clusters in Figure 6 (c.2) further show that our method captures the detailed substructures of the molecule, as can see the cluster patterns of hexagonal and pentagonal rings. More reconstruction examples of molecular graphs are shown in Figure 3 of the supplementary file.
Graph compression To validate the effectiivnness of our method in large and dense graph compression, we further ap- ply EHGNN with HyperCluster
Relative Size to the Original Graph (%)
Original
GMT
Ours (> (595
Ours (> (>75%)
the Erdos-Renyi random
100
graph [8] having six discrete edge features, where the number
of nodes is fixed to 10 while the number of edges increases
50-
from 103 to 10 In Figure 8, we report the relative mem- ory size of the compressed graph after pooling the features,
against the size of the original graph. We compare our method
5.0 7.5
20.0
Number of Edges (10')
which compresses both the nodes and edges, against the node pooling method, namely GMT [2]. As the number of edges increases, we observe that compressing only the node features is insufficient for obtaining compact representations, whereas our method is able to obtain highly compact but accurate rep- resentation which can be assured from the sufficiently high edge reconstruction accuracy. We believe that our proposed framework can not only learn accurate representations of nodes and edges, but also effectively compress their features, especially for large-scale real-world graphs, such as social networks or protein-protein interaction (PPI) graphs.
Figure 8: Graaph compression results. For ours, we report the relative size to the original graph where the edge recon- struction accuracy is higher than 95% and 75%, respectively.
4.2 Graph generation
As shown in Figure I (left), graph generation depends heavily on the edge representations, as the model may generate incorrect graphs (e.g.. toxic chemicals rather than drugs) if the edge information is inaccurate. Thus, we further validate our EHGNN on the graph generation tasks.
Experimental setup We directly forward the edge representation from the EHGNN to molecule generation networks, namely MoIGAN [5] and MArkov moleculaR Sampling (MARS) [38]. Mol- GAN uses the Generative Adversarial Network (GAN) [14], to generate the molecular graph by balancing weights between its generator and discriminator. MolGAN uses R-GCN [32] for nove-level bessage--asssigg whereas, for ours, we first obtain the edge representations using EHGNN, and use them with mean pooling in the graph encoder. For evaluation metrics, we use the Synthetic Accessibility (SA) and Druglikeness (QED) scores. We further apply EHGNN to MARS [38] that generates the molecule by sequentially adding or deleting its fragment, with MCMC sampling. While the original model uses MPNN [12] to implicitly obtain edge representations for adding and deleting actions, we use EHGNN to explicitly learn edge representations. We train models to maximize four
8

---

Table 3: Graph classification results. The results the mean and standard deviation over 10 different runs. Best performance and its comparable results (p > 0.05) from the t-test are highlighted in bold. Hyphen (-) denotes that take more than 10 days. The results for the baselines are taken from Back et al. [2].
Bischemical
TU:
Maalecale
D&D
PROTEINS
MUTAG
IMDH-B
IMDB-M
COLLAB
HIV
Tox31
TesCast
RHMP
graphh
1118
1900
1500
5000
41327
78.11
8516
2019
264
30.00
19.77
74.49
25.51
18.78
24.06
Mlggs
715.66
72.83
19.79
16.53
65.94
2457.75
27.47
19.37
19.26
25:95
Dergie
13:19 0,63
32
73.43
0.39
50.24
0.32
75.33
0.011
11.30
1.26
73.15
0:0.1
66 94
GNN
GUN
90.19 L.07
13,86 6.55
24
16
1.00
20.50 2 1.78
$1.10
13.26-4
72.28
0.40
0.86
48.13
50.30
3:
0.61
1.3h
30.59
78.00
0.02
0.63
16.80
15.05
1.00
1.35
75.04
23:33
= 0.800
1.334
60.83
00.63
1.055
0.46
$1.85
55.47
1.73
1,00
10..0
20.04
Glubal
GMI
13.90
76.72 0.59
6.93
15,09
00.59
83.44
52.18
73.45
50.66
90.74
3.0.4
0.54
T.85
1.25
77.30
05:54
0.75
1.171
08.31
96
1.76
163
73007
11.36 6,87
7/114
0.50
$1.31
1041
1.86
1:331
11%
ToykcPea
0.85
07.47
Hicrarchical
MinCutPool
75.23
0.54
74.72
0:48
19.17
164
7265
0.75
51.04
0.70
90.37
0.34
15.37
2.05
75.31
= 066
02.48
+ 1.33
55.97
= 1.33
71.36
ASAi-
76.56-1
1/34
73.22
063
37.83
1.49
72:11
0:30
50.75
0.7%
76.64
0.50
12.06
1.40
72.24
185
56.9
182
53.50
2
09.73
Edlehhad
05.85
0.55
75.12
0826
72.45
0.34
72.
1.10
73:77
60.00
1.91
Ours
HiyeDrop GMT 78.39
HoyesDoop
76,74
0.33
0.65
75.39
79.39
2:
2 0.26
0.45
$4.00
55.72
+ 0.69
5 061
73.95
14,55
0.6
0.1
51.61
51.45 2 0.25 90.59 = 0.33
6: 041
$1.29
=: 0.25
77.84 =
76.79
0.56
0.37
75,95
77.58 e 0.43 66.15 4 0.65
=
0.32
64.21
2: 0.70
69.16 = 1.04
69,04 = 0.85
72.28
73.97
molecule properties: inhibition scores against two proteins, namely GSK33 and JNK3 (biological); QED and SA scores (non-biological.. Then we report the success rate at which the molecule satisfies all the properties. For more details, please see Section C.2 of the supplementary file.
MolGAN results Figure 7 shows the SA and QED scores of the generated molecules, of the Mol- GAN architecture with different encoders. Our EHGNN framework obtains significantly improved generation performance, over the original MoIGAN which uses the R-GCN encoder and the MolGAN with GMPool, a state-of-the-art global node pooling encoder. This is because EHGNN learns explicit edge representation which enhances the ability of the discriminator to distinguish between real and generated graphs. The improvement in the discriminator also leads to notably more stable results compared to the baselines, which show a large variance in the quality of the generated molecules.
MARS results To perform correct editing actions to generate graphs with MARS, we need accurate edge representations, edges determine the structure of the generated molecule. Table 2 shows that using our EHGNN achieves significantly higher generation performance over original MARS, which uses edges as auxiliary information only to enhance node representations. Notably, performance gain on the GSK3,3 inhibition score for which structural binding is important, suggests that accurate learning of edges leads to generating more effective molecules that interact with the target protein.
4.3 Graph and node classification
Now, we validate the performance of our EHGNN with HyperDrop on classification tasks. Our approach is effective for the classification of graphs with or without edge features, since it allows lossless compression of nodes, and drops edges to allow message-passing only across relevant nodes.
Following the experimental setting of Baek et al. [2], we use the GCN as the node-level message-passin passsenasnnggg layers for all models, and compare our edge pooling method against the existing graph pooling methods. For this experiment, our HyperDrop uses SAGPool [24] on the hypergraph, which is node drop pooling method based self-attention. We use 6 datasets from the TU datasets [28] including three from the biochemical domains (i.c., DD, PROTEINS, MUTAG) and IMDB-MULTY COLLAB). Also, we further use the 4 molecule datasets (i.e., HIV, Tox21, ToxCast, BBBP) from the recently released OGB datasets [17]. We evaluate the accuracy of each model with 10-fold cross validation [43] on the TU datasets, and use ROC-AUC as the evaluation metric for the OGB datasets. For both datasets, we follow the standard experimental settings, from the feature extraction the dataset splitting. We provide additional details of the experiments in Section C.3 of the supplementary file.
Experimental setup
the remaining half from the social domains (i.e.,
Baselines We compare our EHGNN with HyperDrop, against the set encoding (DeepSet [42]).
GNNs with naive pooling baselines (GCN and GIN [23, 391), and -fate-of-the-ar hierarchical pooling methods (DiffPool [41], SAGPool [24], TopkPool [11], MinCutPool [4], ASAP [29], EdgePool [6), and HaarPool [35]) that drop or coarsen node representations. We also additionally compare or
combine the state-of-the-art global node pooling methods (SortPool [43], GMT (2]) with our model, for example, HyperDrop + GMT. For more details, see Section C.3 of the supplementary file.

---

Modd
MUTAGG
PROTEINS
Tox21
Bropédge Zandon Drop)
Hyphrbrip (Sum)
Hypettop
0..00:00::00 75,80 a: 0.45 7648 0:33
Cora
Citeseer
HyperTuore
14.50 4 1:50 72.76
4-1 1:17 76.68
0.56
wr Kandlbrp
N3.00
1:15
74.9 + 1:51 76.3 0447
10
Hope
7660
BHGNN
1.78 73.24 75.04
4 of layers
of lapers
Table 4: Ablation study of Hyper- Figure 9: Edge pooling results Figure 10: Node classification re- Drop on the MUTAG, PROTEINS, the COLLAB dataset. Colors de- sults. Lines denote means over 10 and Tox21 datasets for classification. note connected components.
runs and shades denote variances.
Classification results Table 3 shows that the proposed EHGNN with HyperDrop significantly outperforms all hierarchical pooling baselines. This is because HyperDrop not only retains nodes by removing edges that less useful for graph discrimination, but also explicitly uses the edge representations for graph classification. Since HyperDroop does not remove any nodes on the graph, it can be jointly used with any node pooling methods, and thus, we pair HyperDrrop with GMT. This model largely outperforms GMT, obtaining the best performance on most of the datasets, which demonstrates that accurate learning of both the nodes and edges is important for classifying graphs. We further visualize the edge pooling process of HyperDrop in Figure 9, which shows that our method accurately captures the substructures of the entire graph, which leads to dividing the large graph into several connected components, thus adjusting the graph topology for more effective message- message-passing, We provide more visual examples of edge drop procedures in Section D.3 of the supplementary file.
To see how much each component contributes to the performance gain, we conduct an ablation study on EHGNN with HyperDrop. Table 4 shows that, compared with a model that only uses node features (i.e., w/o EHGNN), learning explicit edge representations significantly improves performance. Our model EHGNN with HyperCluster, or without HyperDrop, or the model with random edge drop obtains decent performance, but substantially underperforms HyperDrop.
Ablation study
Over-smoothing with deep GNNs Lastly, we demonstrate that our EHGNN with HyperDrop alleviates the over-smoothing problem of deep GNNs on semi-supervised node classification tasks, which is not possible for the existing node-based pooling methods. We follow the settings of existing works [23, 34, 10] and provide the experimental details in Section C.4 of the supplementary file. As shown in Figure 10, HyperDrop retains the accuracy as the number of layers increases, whereas the naive GCN or random drop [30] results largely degraded performance, since HyperDrop identifies and preserves the task-relevant edges while the sampling- campling-based methods randomly drop the edges. Further, our method outperforms BatchNorm which alleviates over-smoothing by yielding differently normalized feature distribution at each batch. This is because HyperDrop splits the given graph into smaller subgraphs that capture meaningful message- pagggggggannngggg substructures as shown in Figure
Conclusion
We tackled the problem of accurately representing the edges of graph, which has been relatively overlooked over node representation learning. To this end, we proposed a novel edge representation learning framework using Dual Hypergraph Transformation (DHT), which transforms the edges of the original graph into nodes on a hypergraph. This allows us to apply a message message-passing scheme for node representation learning, for edge representation learning. Further, we proposed two edge pooling methods to obtain a holistic edge representation for given graph, where one clusters similar edges into single edge for graph reconstruction and the other drops unnecessary edges for graph classification. We validated our edge representation learning framework on graph reconstruction, generation, and classification tasks, showing its effectiveness over relevant baselines.
6 Acknowledgements and Disclosure of Funding
We thank the anonymous reviewers for their constructive comments and suggestions. This work was supported by Institute of Information & communications Technology Planning & Evaluation (ITPP) grant funded by the Korea government (MSIT) 10o2201--0-00073 Artificial Intelligence Graduate School Program (KAIST), and No.2021-02 10-1-00,,, Artificial Intelligence Innovation Hub), and the Engineering Research Center Program through the National Research Foundation of Korea (NRF)
funded by the Korean Government MSIT MRRF2001RRIAAA1059922
10

---

References
[1] James Atwood and Don Towsley. Diffusiin-convolutional neural networks. In Advances in Neural Information Processing Systems 29: Annual Conference Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, pages 1993-2001. 2016.
[2] Jinheon Back, Minki Kang, and Sung Ju Hwang. Accurate learning of graph representations with graph multiset pooling. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net,222 2021.
[3] Claude Berge. Graphs and hypergraphs. 1973.
[4] Filippo Maria Bianchi, Daniele Grattarola, and Cesare Alippi. Spectral clustering with graph neural networks for graph pooling. arXiv preprint, 1rXiv:1907.0048) 2019.
[5] Nicola De Cao and Thomas Kipf. Molgan: An implicit generative model for small molecular graphs. arXiv preprins, arXiv:1805.1199 11933, 2018.
[6] Frederik Diehl. Edge contraction pooling for graph neural networks. arXiv preprint arXiv: 10990, 2019.
[7] Vijay Prakash Dwivedi, Chaitanya K. Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv preprint, arXiv:2003.00982, 2020.
[8] P. Erdös and A Rényi. On the evolution of random graphs. In PUBLICATION OF THE MATHEMATICAL INSTITUTE OF THE HUNGARIAN ACADEMY OF SCIENCES, pages 17-61, 1960.
[9] Federico Errica, Marco Podda, Davide Bacciu, and Alessio Micheli. fair comparison of graph neural networks for graph classification. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
[10] Wenzheng Feng, Jie Zhang, Yuxiao Dong, Yu Han, Huanbo Luan, Qian Xu, Qiang Yang, Evgeny Kharlamov, and Jie Tang. Graph random neural networks for semi-supervised learning on graphs. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
[11] Hongyang Gao and Shuiwang Ji. Graph u-nets. Proceedings of the 36th International Conference Machine Learning, ICML. 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 2083-2092. PMLR, 2019.
[12] Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pages 1263-1272. PMLR, 2017.
[13] Liyu Gong and Qiang Cheng. Exploiting edge features for graph neural networks. In IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2019, Long Beach, CA, USA, June 16-20, 2019, pages 221192199 Computer Vision Foundation / IEFF, 2019.
[14] Ian J. Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron C. Courville, and Yoshua Bengio. Generative adversarial networks. arXiv preprint, arXiv:1406.2666 2014.
[15] William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017 4-9 December 2017, Long Beach, CA, USA, pages 1024-1033 2017.
[16] Frank Harary and R. 7. Norman. Some properties of line digraphs. Rendiconti del Circolo Matematico di Palermo, 9:161-168, 1960.

---

[17] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint, ar 2XXi:2005.00687. 2020.
[18] Qian Huang, Horace He, Abhay Singh, Ser-Nam Lim, and Austin Benson. Combining label propagation and simple models out-performs graph neural networks. In International Conference on Learning Representations, 2021.
[19] John J. Irwin, Teague Sterling, Michael M. Mysinger, Erin S. Bolstad, and Ryan G. Coleman. ZINC: A free tool to discover chemistry for biology. J. Chem. Inf. Model., 52(7):1757-1768, 2012.
[20] Xiaodong Jiang, Pengsheng Ji, and Sheng Li. Censnet: Convolution with edge-node switching in graph neural networks. In Proceedings of the Eighth International Joint Conference on Artificial Intelligence, IJCAI 2019, Macao, China, August 10-16, 2019, pages 2656-2662. ijcai.org, 2019.
[21] Xiaodong Jiang, Pengsheng Ji, and Sheng Li. Censnet: Convolution with edge-node switching in graph neural networks. In Sarit Kraus, editor, Proceedings of the Twintt-Eighah International Joint Conference on Artificial Intelligence, IJCAI 2019, Macao, China, August 10-16, 2019, pages 3666-2662. ijcai.org, 2019.
[22] Hiroshi Kajino. Molecular hypergraph grammar with its application molecular optimization. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning. ICML 2019, 9-15 June 2019, Long Beach. California, USA, volume 97 of Proceedings of Machine Learning Research, pages 3183-3191. PMLR, 2019.
[23] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings, 2017.
[24] Junhyun Lee, Inyeop Lee, and Jaewoo Kang. Self-attention graph pooling. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 3734-3743. PMLR, 2019.
[25] Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervises learning. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Intelligence (IAAI-18), and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018, pages 3335-5.45. AAAI Press, 2018
[26] Jose Murtinet and Predrag Rudivojac. Classification in biological networks with hyper- graphlet kernels. arXiv preprint, arXiv: 703.04823, 2017.
[27] Federico Monti, Oleksandr Shchur, Aleksandar Bojehevski, Or Litany, Stephan Günnemann, and Michael M. Bronstein. Dual-primal graph convolutional networks. arXiv preprint, LrXiv:1806.00770 2018
[28] Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. Learning convolutional neural networks for graphs. In Proceedings of the 33nd International Conference on Machine Learning, ICML 2016, New York City, NY, USA, June 19-24, 2016, volume 48 of JMLR Workshop and Conference Proceedings, pages 2014-2023. JMLR.org, 2016
[29] Ekagra Ranjan, Soumya Sanyal, and Partha P. Talukdar. ASAP: adaptive structure aware pooling for learning hierarchical graph representations. In The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty- Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020, pages 5470-5477. AAAI Press, 2020.
[30] Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
12

---

[31] Edward Scheinerman and Daniel Ullman. Fractional graph theory: rational approach to the theory of graphs. Courier Coporation, 2011.
[32] Michael Sejr Schlichtkrull, Thomas N. Kipf. Peter Bloem, Rianne van den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. In The Semantic Web - 15th International Conference, ESWC 2018, Heraklion, Crete, Greece, June 3-7, 2018, Proceedings. volume 10843 of Lecture Notes in Computer Science, pages 593-607, Springer, 2018.
[33] Shikhar Vashishth, Soumya Sanyal, Vikram Nitin, and Partha P. Talukdar. Composition-basee multi-relational graph convolutional networks. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020, 2020.
[34] Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings, 2018.
[35] Yu Guang Wang, Ming Li, Zheng Ma, Guido Montúfar, Xiaosheng Zhuang, and Yanan Fan. Haarpooling: Graph pooling with compressive haar basis. arXiv preprint 2019.
[36] B. Yu. Weisfeiler and A. A. Leman. Reduction of graph to a canonical form and an algebra arising during this reduction. 1968.
[37] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. A comprehensive survey on graph neural networks. arXiv preprint #xXiv:1901.005000 2019.
[38] Yutong Xie, Chence Shi, Hao Zhou, Yuwei Yang. Weinan Zhang, Yong Yu, and Lei Li. Mars: Markov molecular sampling for multi-objective drug discovery. arXiv preprint, arXiv:2103.1043) 10432, 2021.
[39] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
[40] Yulei Yang and Dongsheng Li. NENN: incorporate node and edge features in graph neural networks. In Proceedings of The 12th Asian Conference on Machine Learning, ACML 2020, 18-20 November 2020, Bangkok, Thailand, volume 129 of Proceedings of Machine Learning Research, pages 593-608. PMLR, 2020.
[41] Zhitao Ying. Jiaxuan You, Christopher Morris, Xiang Ren, William L. Hamilton, and Jure Leskovec. Hierarchical graph representation learning with differentiable pooling. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, 3-8 December 2018, Montréul, Canada, pages 4805- 4815, 2018.
[42] Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabás Póczos, Ruslan Salakhutdinov, and Alexander J. Smola. Deep sets. In Advances in Neural Information Processing Systems 30: Anmual Conference on Neural Information Processing Systems 2017, 4-9 December 2017, Long Beach, CA, USA, pages 3391-3401, 2017.
[43] Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Intelligence (1AAI-18), and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018, pages 4438 1338-445. AAAI Press, 2018.
[44] Jie Zhou, Ganqu Cui, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, and Maosong Sun. Graph neural networks: A review of methods and applications. arXiv preprint, arXiv: 181 1.004444 2018.
13


Reviews:
[{"review_id": "cyCsgaASaXL", "reviewer": "Reviewer_HuNj", "summary": "This paper introduces an edge representation learning framework using Dual Hypergraph Transformation which transforms input graph to hypergraph and uses graph convolution network on the hypergraph to obtain edge representations.\nThey further introduce Hypercluster and Hyperdrop functions as pooling to get graph representations for global tasks such as graph classification.\nMessage passing in hypergraphs ensures that information of edges in the original graphs is not lost.", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "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": "Overall the approach is simple and easy to implement.\n\nHowever, I have the following concerns:\n1. Novelty: Converting an input graph to a hypergraph to get edge representations is a known approach. The authors combine this with graph convolution network which is also common in graph representation learning. This limits the novelty of the approach. Further, HyperCluster and HyperDrop are also simple implementations of clustering and dropping nodes.\n2. Experiments - Dataset Size and Time: The authors have shown results on several tasks including edge and graph reconstruction, graph generation and graph and node classification. However, most of these data sets are small with no more than 6000 edges. As they are changing to edge space, the authors should show how the model performs on big data sets as well as the time taken in comparison to node based approaches to showcase the utility of the approach. \n3. Experiments - Baselines and Performance: For node and graph classification, authors have not compared their results with the state-of-the-art methods. For e.g., graph classification using HGP-SL (https://arxiv.org/pdf/1911.05954v3.pdf) gets accuracy of 84.91% and 80.96% on PROTEINS and D&D respectively. The authors achieve an accuracy of 75.39% and 78.39% which is lower. Similarly, node classification using GCN-LPA (https://arxiv.org/pdf/2002.06755v1.pdf) achieves accuracy of 88.5% and 78.7% on CORA and Citeseer respectively. HyperDrop achieves a performance of around 75-80% and 65-70% respectively. Please comment on the difference in numbers between state-of-the-art and paper's performance. Further, for edge and graph reconstruction, the authors should show performance comparison with approaches such as Structural Deep Network Embedding (SDNE) which has shown to perform well on this task.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "RkLn67nKhcX", "reviewer": "Reviewer_QU8H", "summary": "This paper propose Edge HyperGraph Neural Network to learn edge representation. Given an input graph, it first perform a dual hyper-graph transformation, which convert a node in the original graph to an edge in the transformed graph; then it run standard GNN on the transformed graph. The proposed method empirically work well on many graph learning tasks, ranging from edge reconstruction, graph reconstruction to node classification.", "questions": "", "limitations": "", "rating": 4, "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": "I am not very impressed with the novelty of this paper. To me, the net effect of EHGNN is simply running standard GNN on a transformed line graph [1], which has been done in the past (for example see [2]). In particular:\n\n - Quote 197-198 in the main text: \"Here N (e; M^T) is the neighboring node set of the node e in G∗, which we obtain using the incidence matrix M^T of G∗.\" and also line 42-43 in the appendix \"this is because two edges are said to be adjacent if they share the same node\". It seems to me that two nodes in the hyper-graph are connected if the corresponding edges in the original graph are incident to the same node. If this is the case, then the EHGNN is simply the \"line graph neural network\"[2, Section II.C] under a fancy name. \n\nIf the method itself is not novel, judging the significance of the empirical results are not meaningful. Moreover,\n\n - The example in the introduction (figure 1) is simply not scientifically correct, since Tylenol would have two extra hydrogen atoms and is therefore different from NAPQI even from the perspective of regular GNN. In general, molecular propriety does not depend on the edges (whether it is single bond or double bond) but rather depend on geometries, despite the fact that traditionally chemists use different edges (bond) for intuitive understanding purposes. I understand the author here is just trying to make a point about the importance of edge representation, but please use a valid example to motivate the method.\n\n[1] Chris Godsil and Gordon Royle. 2001. Algebraic Graph Theory. Springer\n\n[2] Cai et al. Line Graph Neural Networks for Link Prediction, 2020", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Societal Impact: There is no significant negative societal impact associated with this research.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "3aLz67_TWyp", "reviewer": "Reviewer_KF8o", "summary": "The paper introduces a framework, EHGNN, through which edge representations can explicitly be learned via a combination of standard message passing and a dual hypergraph transform (DHT). More concretely, DHT converts graph edges into nodes and graph nodes into hyper-edges, yielding a dual graph over which standard message passing techniques are subsequently applied to yield edge representations. Furthermore, the paper proposes two new edge-based pooling mechanisms, namely HyperCluster (a clustering-based pooling approach), and HyperDrop (which selects a set of hyper-edges to be eliminated, and thus only preserves the most informative hyper-edges), to combine edge information and obtain graph-level information.\n\nIn addition to EGGNN, the paper presents related work on edge-aware node aggregation GNNs, as well as similar pooling mechanisms, and highlights the importance of explicitly factoring in edge information and representing this with dedicated embeddings. Moreover, the work presents a comprehensive empirical study of EHGNN, both in isolation and in combination with node representation GNNs, on several graph representation learning tasks (e.g. graph reconstruction, graph classification, graph generation) and a large set of standard benchmarks, and shows that the model achieves substantial performance improvements, which can largely be attributed to its explicit representation of edge structures.", "questions": "", "limitations": "", "rating": 4, "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": "The paper proposes a simple method to explicitly represent edge information which builds on the literature in message passing GNNs and leverages an intuitive graph duality structure. This approach is clearly presented, easy to follow, and achieves good results, suggesting significant potential in better incorporating edge information within current GNN models. Moreover, the paper conducts a thorough empirical analysis, and convincingly argues for the value of edge information in the field of graph representation learning. However, the paper has some key limitations that need to be addressed.\n\nFirst, the novelty of the approach seems limited, and appears to be somewhat overstated. In particular, the related works mentioned in the paper seem highly similar in essence to the separate components (pooling, DHT) being proposed, and the differences raised (e.g., lines 106-107) do not come across as conceptually substantial.  In my view, the main strength of this paper lies in highlighting the value of edge information, and performing a thorough empirical study toward showing this point, and arguing how this approach manages to bridge this gap. Therefore, I suggest that the authors emphasize their arguments more, and develop their work more along this direction.\n\nSecond, the EHGNN framework, as the authors acknowledge, does not jointly capture both node and edge information. Indeed, EHGNN successfully captures edge information in its representations, and in doing so vastly outperforms standard GNNs which only implicitly handle edges, but (1) this is not surprising, as the model is explicitly modelled for this setting, and, more importantly, (2) this model then suffers in terms of capturing node information, which then motivates the use of a parallel second model for standard node representation learning. Therefore, this framework is not conceptually more powerful than existing models, as it simply applies these models on a dual graph, and this limits its significance. Hence, a more balanced presentation of the results, framing EHGNN more in terms of a means of highlighting the current gaps in edge representation learning, and less so as a standalone model, should be considered. I agree with the authors' comment in the supplementary material that a joint model is an interesting avenue for future work, but also think that this view should be better reflected in the main body of the paper, and that such a model is what is ideally needed to make this paper more conceptually significant.\n\nFinally, I have some minor comments about the writing of the paper. For example, I find that the tasks in the experimental section should be defined within the main body of the paper, as I had to search for these definitions and infer them from the supplementary material to fully understand the results and the discussions. Moreover, concepts such as the compression ratio in that section should also be made clearer and be presented more carefully. \n\nAll in all, the paper makes a thorough empirical study to confirm intuitions about the importance of edge representations within graph representation learning. However, its proposed approach, EHGNN, is not sufficiently novel, and fails to properly capture node information, which current GNNs do well. This limits its applicability without combining with a standard GNN, and makes that the model itself does not provide any conceptual improvement over existing models. Hence, this paper does not currently make sufficient contributions in my opinion to motivate acceptance. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have acknowledged the limitation of EHGNN in terms of capturing node information, and mention solving this as an avenue for future work in the supplementary material. However, their overall presentation of EHGNN can be improved to better reflect this limitation, in line with my comments in my main review.", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4.5 hours"}, "extra_text": {}}, {"review_id": "-bkzFwiV2UY", "reviewer": "Reviewer_dR4y", "summary": "This paper focuses on learning accurate edge representations for tasks such as graph reconstruction and generation where the importance of discriminative edge representations is often being neglected in most previous research. The authors introduce a novel edge representation learning framework based on the proposed hypergraph transformation which enables message passing over edges. Besides, the authors propose two pooling methods to cluster and drop edges to obtain holistic graph-level representations. They have conducted extensive experiments on multiple benchmarks to validate the effectiveness of the proposed framework and pooling methods on several important graph-based tasks. ", "questions": "", "limitations": "", "rating": 4, "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": "This paper has a good motivation and focuses on an interesting problem. Intuitively, accurate edge representations may be as effective as node representations for graph-based tasks. Existing works mostly pay attention to node representation learning and how to learn useful edge representation is under-explored. The authors propose to transform normal graphs to hypergraph, so as to fulfill message passing among edges. In terms of the originality and novelty, this proposed idea is good. \nHowever, it is a little disappointing that there are not many technical contributions in this paper. The proposed idea is simple and many researchers can come up with such an idea. Basically, by modeling the edges as another type of nodes, the original graph can be seen as a bipartite graph, and it is common to transform bipartite graphs to hypergraphs in a wide range of graph-based tasks such as recommendation. \nWhen performing the message-passing among edges (nodes in the hypergraph), the proposed method needs to look up the adjacency matrix to find neighboring nodes. The process is similar to that of hypergraph neural networks which have been proposed and studied several years ago. The authors claimed that “Although acquiring the neighboring node set from the incidence matrix costs O(m), compared to using the adjacency matrix which costs O(n), this cost can be ignored by using the sparse implementation of DHT explained above” in page 5. Actually, both the hypergraph incident matrix and the graph adjacency matrix can have sparse implementations. This cannot be the advantage of the proposed framework.\nAs for the pooling methods, it is not clear what the advantages of HyperCluster and HyperDrop when compared with methods such as DiffPool. It looks like that these two pooling methods cannot be trained in an end-to-end way, which is the advantage of DiffPool. Besides, these two pooling methods are intuitively designed. No new ideas are provided in this part.\nThe quality of the presentation is good and this paper is easy to follow. However, the experimental results are insignificant. Only small improvements are observed, which would question the necessity of applying the proposed framework to graph-based tasks.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The number of edges is usually hundreds of times the number of nodes in real-world network. Learning edge representations requires far more memory compared with learning node representations. The authors should address this problem. Whether the hyperCluster and Hyperdrop can be performed before representation learning to tackle the memory issue?", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes edge representation learning framework in graphs based on a hyper graph transformation. The reviewers agreed that the problem motivation has some merits. However, all the reviewers had hard time discerning what’s the novelty of the proposed work, and the significance of the contribution. In future submission, it would help to have a better description on the novelty of the significance of the contribution, and contrast it with existing work more clearly. 


Decision: Accept (Poster)