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///////2
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 geaeeernngggnrniingggggg 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-pasiingggge 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 sasssae-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 GMPPool
(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 Be
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
= 6.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
13
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
73077
11.36 6,87
7/114
0.50
$1.31
1041
1.86
1:331
11%
ToyicPea
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 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- pagggggggannnggggg 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 MRRF2001RRIAAA1009922
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 preprini, 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": "g4prZQZeMSc", "reviewer": "Reviewer_EuYn", "summary": "--------------------------------------------------------------------------------------------------------------------------\n\n* Most graph representation learning methods focus on representing nodes or entire graphs but not edges.\n* The paper proposes a dual hypergraph transformation of the input graph (nodes become hyperedges while edges become nodes) to easily learn representations of edges in the graph (the key idea is to use a node representation learning method on the dual).\n* Experiments on graph reconstruction and graph generation, two tasks in which edges are crucial, demonstrate the benefits of the proposed edge representation learning method.", "questions": "", "limitations": "", "rating": 5, "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": "--------------------------------------------------------------------------------------------------------------------------\n\n### **Strengths**\n\n--------------------------------------------------------------------------------------------------------------------------\n\n1. **Quality of Submission**\n\nThe methods used (Dual Hypergraph, HyperCluster, HyperDrop) are appropriate for the tasks (graph reconstruction, generation, and classification). \nThe submission is a complete piece of work (i.e., not a work in progress).\nThe authors have also evaluated the weaknesses (albeit briefly) of their work (page 14 of supplementary/appendix).\n\n--------------------------------------------------------------------------------------------------------------------------\n\n2. **Clarity of Presentation**\n\nThe submission is well-organised and well-written.\nThe submission contains a detailed supplementary material that includes code, details of additional experiments, and descriptions of baselines, datasets, tasks, and hyperparameters.\nThe code seems well-organised and can be easily adapted by others without much effort.\n\n--------------------------------------------------------------------------------------------------------------------------\n\n### **Weaknesses**\nThe submission can be strengthened by improving the originality, significance of the contributions and positioning with prior work better.\n\n--------------------------------------------------------------------------------------------------------------------------\n\n1. **Originality of Contributions**\n\nThe tasks are not new and the methods used are well-known.\nThe hyperedges of the dual hypergraph are not treated any differently from pairwise edges: the key idea is to run a known graph-based method on the transpose of the incidence matrix (a straightforward idea) as discussed in line 207.\nHyperCluster and HyperDrop are also straightforward adoption of known techniques from prior graph pooling models [e.g., (i) Hierarchical graph representation learning with differentiable pooling, NeurIPS'18, (ii) Self-attention graph pooling, ICML'19] to nodes of the dual hypergraph. \n\n--------------------------------------------------------------------------------------------------------------------------\n\n2. **Significance of Experimental Results**\n\nThe graph generation results in Table 2 reveal higher variances for the proposed method than baselines. \nThe experimental methodology could be strengthened by using statistical tests to validate the significance of performance gains.\nThe authors should clarify how a simple Multi-layer Perceptron (MLP) baseline (without graph connectivity information) performs on graph reconstruction, generation tasks (this would strengthen claims made in lines 37--42).\n\n--------------------------------------------------------------------------------------------------------------------------\n\n3. **Positioning with Prior Work**\n\nLearning representations for both nodes and hyperedges in a hypergraph has been a recent topic of research interest which includes the following publications:\n* Be More with Less: Hypergraph Attention Networks for Inductive Text Classification, In EMNLP'20\n* Session-based Recommendation with Hypergraph Attention Networks, In SDM'21.\n\nThe submission can be strengthened by positioning (and comparing) with hypergraph attention networks since they can be applied easily to a dual hypergraph.\nThe results on oversmoothing (Figure 10) are not surprising since dropping nodes and/or edges from a graph is  well-known to alleviate oversmoothing issues, e.g., Bayesian Graph Neural Networks with Adaptive Connection Sampling, ICML'20.\n\n--------------------------------------------------------------------------------------------------------------------------", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Adequately addressed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 hours"}, "extra_text": {}}, {"review_id": "KnGvilHxLL", "reviewer": "Reviewer_5K8S", "summary": "The paper proposes a new approach for computing edge-level representations. The core idea of the paper is to realize message passing not just in the original graph (the primal) that is provided in input to the model, but on the dual hypergraph (where nodes are edges and hyperedges are nodes in the primal) where additional processing such as clustering or dropping can be applied in order to respectively compute graph-wise edge representations or improve the quality of message passing on the primal as irrelevant edges are hopefully dropped on the dual. The authors validate the quality of the model on graph/edge reconstruction tasks on synthetic and molecular datasets (ZINC12), graph generation and graph classification tasks.", "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": "Overall I believe the paper is on the acceptance side despite there are a number of issues I would like the authors to clarify in the rebuttal.\n\nFirst of all, the authors refer to the dual of the original graph (the primal) as an hypergraph (as multiple nodes are connected by same edges in the dual), however they don’t exploit at all the hypergraph nature of the dual and realize message passing on it as if it was a simple graph. This idea is not novel and was already exploited in https://arxiv.org/abs/1806.00770 for computing edge level representations that can be used for refining an attention mechanism on the primal. Additionally, the complexity of processing the dual as described in the paper - Table 1 seems to be wrongly stated. The authors mention that alternative methods for constructing the adjacency matrix of the dual require O(m^2) operations (with m = number of edges), however because of the sparse nature of the adjacency matrix (if I’m not mistaken) this can actually be realized resorting to edge lists and dictionaries (one mapping edges to incident nodes and one mapping nodes to incident edges) with a complexity equal to O(m*d_max) (with d_max the maximum node degree), which is significantly cheaper and actually the same complexity required by the method of the authors for processing the dual. In this sense, the authors mention in the paper that they can just transpose the incidence matrix of the primal for obtaining the incidence matrix of the dual hypergraph, but they don’t provide any detail on how this can avoid the construct of an edge list in the dual which I believe is still required for realizing message passing therein. I would be happy if the authors could clarify this detail in their rebuttal.\n\nWhile the idea of processing the dual graph is not novel per se, to the best of my knowledge using message passing on the dual to identify not so relevant or noisy edges in the primal (and thus realize some sort of learnable rewiring operation) is a new contribution to the field (and personally what I found to be the most interesting bit of the paper). However, the justification for why one would want to use this seems to be rather weakly justified in the paper. The authors in particular stress that for graph classification tasks, dropping edges (and not nodes) allows to compute lossless graph-wise representations as all nodes are preserved in the final aggregation process while not so relevant edges are removed. However, one could argue the same for the edges of the dual graph and that, as some edges might be noisy in the primal, some edges might be noisy in the dual which would correspond to dropping nodes in the original graph (in this case loosing some information in the node-wise final aggregation process would actually be beneficial for graph classification problems). Hence, while I believe there is some merit in the idea of pruning the original graph, learning to discard some edges if needed, the justification presented in the paper doesn’t seem to be well argued and I would recommend the authors to rephrase this in terms of rewiring the original graph. I would like the authors to additionally reply on this in their rebuttal as well.\n\nSimilarly to the above, the idea of coupling a graph-wise representation based on node features with one explicitly aimed at representing edges I believe is a new (despite not particularly original) contribution that seems to favour graph generation and reconstruction tasks in particular.\n\nOn the experimental side, I believe the experiments are overall good and extensive, however I think there might be room for improvement. In particular, for the edge and graph reconstruction tasks, the authors compare with previous approaches that only implicitly use edge features for refining node representations. However, while the importance of computing edge representations seems clear from the experiment, I believe comparing with https://dl.acm.org/doi/abs/10.1145/3394486.3403389 / https://www.ijcai.org/Proceedings/2019/0366.pdf  that explicitly compute edge representations in the message passing procedure coupled with a suitable pooling (e.g. even a simple mean/sum/max on the added colored nodes representing the edges) would have greatly improved the reader understanding of the benefits of processing the dual with respect to an alternative simple solution. \n\nOther comments on the experiments I would like to clarify with the authors:\n\n1. the authors propose just a qualitative analysis on their synthetic dataset for edge reconstruction, I believe showing some quantitative results on this as well would improve the strength of the experimental section.\n\n2. The graph compression experiment in the paper is confusing. What do the authors mean with the relative size of the full graph in Figure 7?\n\nIn conclusion, while the presentation of the core ideas of the paper could be improved and there are a series of items that I would like the authors to address in the final manuscript, I think the manuscript does present some contribution to the field and I’m thus (even if weakly) in favor of its acceptance provided that the authors clarify the issues I highlighted.\n\nOther Minor comments:\n\n\n1) line 92/94, this seems an over statement. As mentioned above, potentially we can simply compute edge-level features by adding for each edge e, a new colored node which is connected to the end points of e and run message passing on this expanded graph. I would rephrase softening the claim.\n2) Figure 3 / 5, compression ratio is never defined in the paper, what do the authors mean with this?\n3) Figure 5, why did the authors show the reconstruction performance of nodes and edges together when they already showed edge reconstruction performance in Figure 3? \n\nI believe it would be clearer if the authors were showing the reconstruction performance of nodes and edges separately to understand the performance of the model  (e.g. in term of accuracy in figure 5 we see an improvement of the baselines wrt figure 3, while the proposed model seem to worsen, is the node-wise accuracy of the baselines at a node level better than the one of the proposed solution? If yes, why?)\n\n4) Citation to https://arxiv.org/abs/1907.10903 is missing, despite the authors compare with it to showing the robustness of the model wrt oversmoothing.\n5) What kind of pooling do the authors use for Hyperdrop without GMT in table 3? I was not able to find that detail anywhere in the paper nor supplementary material. Are the authors using HyperCluster as well in that experiment? \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "EYRm0_eJ3Bc", "reviewer": "Reviewer_xkvv", "summary": "This paper proposes a new edge representation learning model by hypergraph transformation and message passing. Two edge pooling schemes are designed to learn a holistic representation. The proposed model is validated on graph reconstruction, generation, and classification tasks, and the experimental results show the proposed model outperforms the baseline models on several datasets.", "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": "This paper studies an interesting and useful problem, to learn the representation of edge. The proposed idea and method are intuitive. The experiment results are impressive. However, I have a few concerns about this paper.\n(1) Transforming edges to nodes is not very novel, and the strategy is adopted by many existing works, e.g. edge clustering in network community detection. What is the main difference between this paper and the combination of the above transformation and a GCN?\n(2) Does the transformation increases the complexity of message passing, especially for the scale-free networks (few hubs with very high degree)?\n(3) The descriptions of the tasks in the experiments are not clear and may cause misunderstanding. For example, edge reconstruction is to reconstruct the feature of edge actually.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately addressed the potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4.5 hours"}, "extra_text": {}}, {"review_id": "7HiXCmMxz8D", "reviewer": "Reviewer_JU4W", "summary": "This paper is in the area of graph representation learning, and more specifically, they focus on edge representation learning. The proposed method is an edge representation learning framework that is based on Dual Hypergraph Transformation (DHT), that transforms the edges of the original graph into the nodes of a hypergraph and nodes to hyperedges. The dual hyper graph construction allows to apply any off-the-shelf message passing techniques designed for node representations to edge representation. Then, they proposed two novel graph pooling methods for the hypergraph to obtain compact graph-level edge representations; to cluster (HyperCluster) or drop (HyperDrop) edges to obtain holistic graph-level edge representations. They validate the edge representations on various synthetic and molecular datasets for graph representation and generation downstream tasks. When tested on the graph classification task, the proposed method outperforms the state-of-the-art comparison graph polling methods.\n\n-- Edit after the discussion phase: I acknowledge that I have read the authors' response and the other reviews.", "questions": "", "limitations": "", "rating": 7, "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 is well-written and well-structured. The authors work on an interesting problem of edge representation learning and more specifically the propose a framework to construct a hypergraph and apply off-the-shelf message-passing methods from node to edge representations. The related work is dense and covers most important related works. The methodology section (Section 3) contains all details for the proposed edge representation learning method, and justifications with references when needed. The experimental setup is nicely done, it has a good structure with all the necessary details and analyses (including results summarization in Tables and Figures). The authors include edge reconstruction results in the ZINC molecule and synthetic datasets, as well as graph reconstruction results in the ZINC molecule and some examples. They have added the graph compression results figures that shows the relative size of compressed graphs from the proposed method to the node pooling method (GMT). The results on the graph generation task against MolGAN and MARS show that the proposed method outperforms the others. The graph classification results are shown against various datasets and various pooling methods. Overall, the paper discusses some nice ideas regarding the edge representation learning and how to apply message passing techniques for node representation learning to edge representation learning. Also, the authors propose two edge pooling methods and they provide a convincing analysis of an in-depth experimentation they have done that shows the performance improvements.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors discuss the limitations of this work in the paper, they also include a section for this purpose in the Appendix, and there are no concerns for potential negative societal impact. ", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a new edge representation learning model through Dual Hypergraph Transformation. 
Finding good representation of edges remains an under-studied problem and the results of this paper can be considered as progress towards the problem.
 The proposed model outperforms 
baselines on several tasks such asl graph reconstruction, generation, and classification tasks.  
However, the authors should incorporate the salient points of the discussion in the final submission.

Decision: Accept (Poster)