MeGraph: Capturing Long-Range Interactions by Alternating Local and Hierarchical Aggregation on Multi-Scaled Graph Hierarchy
Authors: Honghua Dong
Jiawei Xu
Yu Yang
Rui Zhao
Shiwen Wu
Chun Yuan
Xiu Li
Chris J. Maddison
Lei Han
Venue: NeurIPS 2023 poster (2023)
Keywords: Long-Range Interactions
Hierachical Structure
Multi-Scale
Graph Pooling
Graph Neural Networks(GNNs)
TL;DR: A novel MeGraph model that alternates local and hierarchical information aggregation in a multi-scale mega graph shows effectiveness in capturing long-range interactions.

Abstract: Graph neural networks, which typically exchange information between local neighbors, often struggle to capture long-range interactions (LRIs) within the graph. Building a graph hierarchy via graph pooling methods is a promising approach to address this challenge; however, hierarchical information propagation cannot entirely take over the role of local information aggregation. To balance locality and hierarchy, we integrate the local and hierarchical structures, represented by intra- and inter-graphs respectively, of a multi-scale graph hierarchy into a single mega graph. Our proposed MeGraph model consists of multiple layers alternating between local and hierarchical information aggregation on the mega graph. Each layer first performs local-aware message-passing on graphs of varied scales via the intra-graph edges, then fuses information across the entire hierarchy along the bidirectional pathways formed by inter-graph edges. By repeating this fusion process, local and hierarchical information could intertwine and complement each other. To evaluate our model, we establish a new Graph Theory Benchmark designed to assess LRI capture ability, in which MeGraph demonstrates dominant performance. Furthermore, MeGraph exhibits superior or equivalent performance to state-of-the-art models on the Long Range Graph Benchmark. The experimental results on commonly adopted real-world datasets further demonstrate the broad applicability of MeGraph.

MeGraph: Capturing Long-Range Interactions by Alternating Local and Hierarchical Aggregation on Multi-Scaled Graph Hierarchy
Honghua Dong 122,3
Jiawei Xu
Yu Yang 1.4 Rui Zhao
Shiwen Wu
Chun Yuan
Xiu Li
Chris Maddison
Lei Han
Tencent Robotics X
University of Toronto Veccor Institute
TTinggua University
'Hon Kong University of Science and Technology
Abstract
Graph neural networks, which typically exchange information between local neigh- bors, often struggle to capture long-range interactions (LRIs) within the graph. Building graph hierarchy via graph pooling methods is promising approach to address this challenge; however, hierarchical information propagation cannot entirely take over the role of local information aggregation. To balance locality and hierarchy, we integrate the local and hierarchical structures, represented by intra- and inter- anter-graphs respectively, of a multi-scale graph hierarchy into single mega graph. Our proposed MeGraph model consists of multiple layers alternating between local and hierarchical information aggregation the mega graph. Each layer first performs aware pressage-passing on graphs of varied scales via the intra- sirra-graph edges, then fuses information across the entire hierarchy along the bidirectional pathways formed by inter-grae anter-graph edges. By repeating this fusion process, local and hierarchical information could intertwine and complement each other. To evaluate our model, we establish a new Graph Theory Benchmark de- signed to assess LRT capture ability, in which MeGraph demonstrates dominant performance. Furthermore, MeGraph exhibits superior or equivalent performance state-of-the-e models on the Long Range Graph Benchmark. The experimental results on commonly adopted real-world datasets further demonstrate the broad applicability of MeGraph.
1 Introduction
Graph-structured data, such as social networks, traffic networks, and biological data, are prevalent across plethora of real-world applications. Recently, Graph Neural Networks (GNNs) have emerged as powerful tool for modeling and understanding the intricate relationships and patterns present in such data. Most existing GNNs learn graph representations by iteratively aggregating information from individual nodes' local neighborhoods through the message message-passing mechanism. Despite their effectiveness, these GNNs struggle to capture long-range interactions (LRIs) between nodes in the graph. For instance, when employing a 4-layer vanilla GNN on the 9-node (A to /) graph (as shown in Fig. 1), the receptive field of node A is limited to 4-hop neighbors, making the aggregation of information from nodes G, H, and into node A quite challenging. While GNNs could theoretically incorporate information from nodes n-hops away with n-layers of message passing, this often leads to over-smoothing and over-squashing issues [17, 3] when n is large.
"Equal Contribution. Work done while HD, JX and YY are interns Tencent Robotics X. Cooresponding authors, contact honghuad@cs. toronto. edu and 1xhan@tencent. com. Project website and open-source code can be found at https: //sttes.//.te//// google com/viees/negraph.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Graph Pyramid
Mega Graph
Select
Connect
Reduce
IntraEdges
InterEdges
Figure 1: Illustration of the graph pooling operation, graph pyramid, and mega graph. Graph pooling is a downsampling process comprising SELECT, CONNECT, and REDUCE steps. It begins by selecting subsets for grouping and each subset collapses into a new node in the pooled graph. Next, it forms new edges by merging the original ones, and finally calculates the pooled graph's is features. In this graph, nodes A B C, D E P. and G H I are pooled into nodes 1, 2, and 3 respectively, while the edges (B, E) and (C, D) are merged into (1, 2). Graph Pyramid involves multi-scaled graphs derived from iterative graph pooling, with the height indicating different scales and á = 1 symbolizing the original graph. Mega Graph is formed by connecting the graph pyramid using inter-graph edges, which are the by-products of graph pooling.
One mainstream solution to this problem involves constructing multi-scale graph hierarchy through graph pooling methods. Previous efforts, such as Graph UNets [22] and HGNet [47], have attempted to broaden the receptive field using this strategy. They downsample and upsample the graph, aggregating information along the hierarchy. However, hierarchical information propagation cannot take over the role of local information aggregation, To illustrate, consider the graph hierarchy depicted in Fig. 1. The information propagated along the hierarchy from node to nodes D) E, and tends to be similar since they share the common path B-1-X-2. However, in the original graph, node B holds different degrees of importance to nodes D, E, and F as they are 2, 1, and 3 hops away respectively.
To balance the importance of locality and hierarchy, we amalgamate the local and hierarchical structures of a multi-scale graph hierarchy into single mega graph as depicted in Fig. 1, where we refer to the local structure as intra-graph -rrrpggrahhhhh edges and hierarchical structure as inter- gittergraph edges. Based on this mega graph, we introduce our MeGraph model consisting of n Mee layers. Each layer first performs local-aware message- messagg-passing on graphs of varied scales via the intra satra-graph edges and then fuses information across the whole hierarchy along the bidirectional pathways formed by -nter-graph edges. This method enables hierarchically fused information to circulate within local structures and allows locally fused information to distribute across the hierarchy. By repeating this fusion process, local and hierarchical information could intertwine and complement each other. Moreover, to support flexible graph pooling ratios when constructing the multi-scale graph hierarchy, we propose a new graph pooling method S-EdgePool that improves from EdgePool [13].
In our experiments, We first evaluate McGraph's ' capability to capture Long Range interactions (LRIs). We establish a Graph Theory Benchmark comprising four tasks related to shortest paths and one related connected components. MeGraph demonstrates superior performance compared with many competitive baselines. MeGraph also achieves comparable or superior performance than the state-of-the-art on the Long Range Graph Benchmark (LRGB) [17]. In addition, we perform extensive experiments on widely-used real-world datasets that are not explicitly tailored for assessing the capacity to capture LRIs. These include the GNN benchmark [15] and OGB-G datasets [28]. In these tests, MeGraph demonstrates superior equivalent performance compared to the baseline models, suggesting its broad applicability and effectiveness.
The main contributions of this work are summarized as follows: 1) Mega graph and novel architec- ture: we propose the mega graph, a multi-scale graph formed by intra- and inter-graph edges, where the message-passsing over the mega graph naturally balances locality and hierarchy. On this basis, we introduce novel architecture MeGraph, which alternates information aggregation along the intra- and inter-edges of the mega graph. This fusion process intertwines local and hierarchical information, leading to mutual benefits. 2) Hierarchical information fusion: we design a bidirectional pathway to facilitate information fusion among the hierarchies. 3) S-EggePool: we enhance EdgePool into S-EdgePool, allowing an adjustable pooling ratio. 4) Benchmark and Evaluations: we establish a new graph theory benchmark to evaluate the ability of models to capture LRIs. In these evaluations, MeGraph exhibits dominant performance. Additionally, MeGraph achieves new SOTA in one task of LRGB and shows better comparable performance compared with baselines on popular real-world datasets.

---

2 Notations, Backgrounds and Preliminaries
Let 9 E) be graph with node set V (of cardinality N and edge set & (of cardinality Nº). The edge set can be represented as {(k;, I=1:Ne where s and i are the indices of the source and target nodes connected by edge k. We define X as features of graph G, which is a combination of global (graph-level) features u node features V9, and edge features E Accordingly, we use V to represent the features of a specific node vt, and Eg denotes the features of specific edge ($x, tx). We may abuse the notations by omitting the superscript G when there is no context ambiguity.
2.1 Graph Network (GN) Block
We adopt the Graph Network (GN) block design in accordance with the GN framework [6]. In our notation, a GN block accepts a graph G and features X (u, V, E) as inputs, and produces new features X (u', V E'). full GN block [6] includes the following update steps. In each of these steps, Φ denotes an update function, typically implemented as a neural network:
Edge features: E Φf (Eg, V SKy Va t u), Vk [*] Node features: V = 6" (p" ((E) Ne),t, :), Vi, u), Vi E [1, where pr is an aggre-
gation function taking the features of incoming edges inputs.
Global features: u' = 6" "eE"")),,, p""","""""" p"(""("), u), where pa and p"->" are two global aggrega- tion functions over edge and node features.
Given a fixed graph structure 9 and the consistent input and output formats outlined above, GN blocks can be seamlessly integrated construct complex, deep graph networks.
2.2 Graph Pooling
Graph pooling operation downsamples the graph structure and its associated features while ensuring the preservation of structural and semantic information inherent the graph. Drawing from the SRC framework [23], we identify graph pooling as category of functions,POOL, that maps graph g (V,E) E)) with N nodes and features X to reduced graph 9 (V,E) with N nodes and new features X Here, N N and xθ)
The SRC framework deconstructs the POOL operation into SELECT, REDUCE, and CONNECT functions, which encompass most existing graph pooling techniques. We reinterpret these functions in our own notation as follows:
(I) As shown in Fig. the SELECT establishes N nodes for the pooled graph, and each node corresponds to subset of nodes S; C V in the input graph. This creates an undirected bipartite graph 9 = (Ý, E). with 1- = VUV V and (v, ū) E E if and only if v E Sg. We refer to this graph 9 as the inter- graph, a larger graph that links nodes in the input graph 9 with nodes in the pooled graph ğ. The SELECT function can be generalized include inter-graph features X As an example, edge weights can be introduced for some edge (Sx, (x) in graph 9 gauge the importance of node &5. from the input graph contributing node la in the pooled graph.
x0) = SE x9); ğ CONNECT(C, I, X²); x = REDUCE X (9,
The CONNECT function reconstructs the edge set between the nodes in of the pooled graph ğ based on the original edges in & and the inter-graph edges in E. The REDUCE function calculates the graph features X of graph I by aggregating input graph features X taking into account both the inter-graph 9 and features x In a similar vein to the relationship between graph lifting and coarsening, define the EXP EXPAND function for graph features, which serves as the inverse of the REDUCE function: X EXPAND X ,9, X9).
3 Methods
We begin with the introduction of the mega graph (Sec.3.1), which amalgamates the local (intra- edges) and hierarchical (inter-edges) structures of a multi-scale graph hicrarchy into single graph.

---

Depth
Inputs
Layer 1
Layer 2
Layer
Layer
Outs
Graph Features
1
Intra GN
Inter
2
X
Pooling
Mee
Layer
3
x
Readout
Monit
Logits
4
Last Layer(s)
Encode
Process
Deazde
Figure 2: Illustration of the MeGraph model, where n denotes n 1. The blue and green circles represent
features of intra- and inter-graphs, respectively. In this figure, the horizontal and vertical directions represent the interaction among the local structure (intra-graph) and graph hierarchy (inter-graph) respectively. The features intra- and inter-graphs are represented by blue and green circles, respectively. In this figure, the horizontal and vertical directions denote the local structure and graph hierarchy respectively. During the encode stage, the mega graph is constructed using graph pooling. In the process stage. the Mee layer, which features bidirectional pathways across multiple scales, is stacked times. In the decode stage, multi-scale features are read out. The golden inter GN blacks form bidirectional pathways across the whole hierarchy.
Following this, we present the MeGraph model (Sec.3.2), which alternates between the aggregation of local and hierarchical information along the intra- and inter-edges of the mega graph. We then discuss the specific choices made for the core modules of the MeGraph, along with the innovations (S)c.3.3). Finally, we delve into the computational complexity of the MeGraph model (Sec.3.4).
3.1 Connecting Multi-scale Graphs into a Mega Graph
Similar to the concept of an image pyramid [1], graph pyramid is constructed by stacking multi- scale graphs, which are obtained through iterative downsampling of the graph using a graph pooling technique. Formally, in alignment with the definition of an image feature pyramid [39], we define a graph feature pyramid as set of graphs IIA. == fi and their corresponding features x = ( )i=1..... Ah- Here, G1 represents the original graph, X signifies the initial features, h stands for the height, and (G,, x ,, X for i > 1.
By iteratively applying the POOL function, we can collect the inter-graphs فI := Ii A-1 and their features X == (X } A (since there are h inter-graphs for h intra- intra-graphs), where (c;, x SELECT(G, x for i < h. The bipartite inter inter-graph & and its features x² essentially depict the relationships between the graphs before and after the pooling process (see Sec. 2.2).
Finally, as illustrated in Fig. we wire the graph pyramid G1 using the edges found in the bipartite graphs S1sh- This results in a mega graph Mg (MV. where MV Uh_ V. and ME = U2_ & - E, The structure of the mega graph would vary as the graph pooling method trains. We denote MGmura U'_1 G. as the intra-graph of MMG, and refer to the edges therein as intra-edges. Correspondingly, MMGiter = U G is referred to as the inter-graph of MG, with its corresponding edges termed as inter-edges. The features XM of the mega graph MG is combination of intra- -rragg features X and inter -herh features X @
3.2 Mega Graph Message Passing
We introduce the MeGraph architecture, designed to perform local and hierarchical aggregations over the mega graph alternately. As shown in 2 the architecture follows the encode-proces decode design [6. 25] and incorporates GN blocks (refer to Sec. 2. fundamental building blocks.
During the encode stage, initial features are inputted into an intra-graph GN block, which followed by a sequence of graph pooling operations to construct the mega graph MG and its associated features

---

h Inputs
Vertical Updates
Outputs
Graph Features
3
1
Intra GN
2
X
X3
Residual
Same
Pathway
3
4
Cross Update
Step
Step 2
Step
Figure 3: Illustration of the Mee layer, where i- denotes and j+ denotes for j + 1. The blue and green circles represent the features of intra- and inter-grapin respectively. Grey and golden arrows represent the intra and inter GN blocks. The cross-update utilizes inter GN blocks to exchange information between consecutive heights, elaborated in the main text. The Mee layer first aggregates information locally along inter-graph edges. then applies cross-updates sequentially from lower higher levels, accumulating information along the pathway to pass to the higher hierarchy. The process is reversed the last step.
gndgen
(X")MGG In the process stage, the Mee layer, which performs both local and hierarchical information aggregation within the mega graph, is stacked n times. The i-th Mee layer receives (X* (X'-I.MS as input and outputs (X+)MM Through the stacking of Mee layers, deeper architecture created, enabling more profound fusion of local and hierarchical information. Lastly, in the decode stage, the features (X") MM9 are transformed into task- specifcei representations using readout functions.
Mee Layer The Mee layer is designed to aggregate local and hierarchical information within the mega graph. A detailed structure of the Mee layer is depicted in Fig. 3.
For the i-th Mee layer, we consider inputs denoted by (X'-1)MG {(x'~1)9un, (X (Xi For simplicity, we omit the superscript and denote the features of intra- and inter-graphs as (X) (x)."))=
(x and
(X1110114 respectively.
The first step applies GN blocks on intra-graph edges, performing message passing on the local structure graphs at each scale: X = GN ( (;)) Here, X represents the updated intra-graph 9j features.
The second and third steps focus on multi-scale information fusion. The second step applies cross- updates across consecutive heights from 1 to h, while the third step reverses the process, forming bidirectional pathway for the information flow across the hierarchy. The cross- between consec-
utive heights j and j + is denoted by function (X/, X Xj + 1') X-UPD(j, X, X,, X,j + 1). The prime notation indicates the updated value, and residual links [26] are used practice.
This cross-update can be implemented via inter-graph convolution with GN Conv (detailed in App.C.1). Alternatively, it can be realized using the REDUCE and EXPAND AND operations of POOL (refer to Sec.2.2) by X/ = REDUCE Xy. Xj) and X = EXPAND (G,, X X,-1), where G, is the j-th mntergrrah. We denote this implementation as X-Pool.
inter referred to X-
The layer outputs features (X;))=ı,--.A and (X [x)))=_,--_A--1 Residual links [26] can added from X to X and from X to X, empirically, creating shortcuts that bypass GN blocks in the Mee layer. It's worth noting that the intra and inter GN blocks can share parameters across all heights
j to accommodate varying heights, across all Mee layers to handle varying layer numbers.
3.3 Module Choice and Innovation
MeGraph incorporates two fundamental modules: the graph pooling operator and the GN block. This architecture can accommodate any graph pooling method from the POOL function family (refer to Sec. 2.2). Furthermore, the GN block is not strictly confined to the graph convolution layer found in standard GCN, GIN, GAT.
Graph Pooling, There are a number of commonly used graph pooling methods, including Diff- Pool [62], TopKPool [22], EdgePool [13], etc. We opt for EdgePool due its simplicity, efficiency,
5

---

and ability to naturally preserve the graph's 's connectivity through edge contraction. However, edge contraction is applied only the edges in a specific maximal matching of the graph's nodes [13], thereby setting a lower limit of 50% to the pooling ratio T)-- This constraint implies that minimum of logg N pooling operations is required to reduce a graph of N nodes to a single node, To address this limitation, we propose the Stridden EdgePool (S-EdgePool), which allows for variable pooling stride.
The principle behind S-EdgePool involves dynamically tracking the clusters of nodes created by the contraction of selected edges. Similar to EdgePool, edges are processed in descending order based on their scores. When an edge is contracted, if both ends do not belong to the same node cluster, the two clusters containing the endpoints of the edge merge. The current edge can be contracted if the resulting cluster contains no more than T, nodes after this edge's 's contraction. The iteration stops prematurely once a pooling ratio, T]. achieved. During pooling, each node cluster is pooled as a new node. When = 2, S-EdgePool reverts to the original EdgePool. The algorithm's 's details and pseudocode are available in App. C.2.
For efficiency, we employ the disjoint-set data structure to dynamically maintain the node clusters, which has a complexity of ((Ea(E)) where E the number of edges and (EE) is function that grows slower than logí E) [50]. The total time complexity of S-EdgePool is equivalent to EdgePool and is calculated as O+E log E). where D the embedding size, OEED) from computing edge scores and O E log E) from sorting the edges.
GN block. The full GN block, introduced in Sec. 2.1, is implemented a graph full network (GFuN) layer. This layer exhibits a highly configurable within-block structure, enabling to express a variety of other architectures (see Sec. 4.2 of [6]), like GCN, GIN, GAT, GatedGCN. Thus, modifying the within-block structure of GFuN is akin to plugging in different GNN cores. Further details can be found in App. C.3.
Encoder and decoder. Most preprocessing methods (including positional encodings and graph rewiring), encoding (input embedding) and decoding (readout functions) schemes applicable to GNNs can also be applied to MeGraph. We give implementation details in App. C.4.
3.4 Computational Complexity and Discussion
The overall complexity of the MeGraph model is contingent the height h, the number of Mee layers n, the chosen modules, and the corresponding hyperparameters. Let D be the embedding size, V the number of nodes, and E the number of edges in the input graph G. The time complexity of S-Edgepool is O [ED+ D log E), and that of a GFuN layer is O(VD++D)) Assuming both the pooling ratios of nodes and edges are n, the total time complexity to construct the mega graph MG becomes O(ED + E log E)/(1 - n)), where >h-1 17² < 1/(1 - -)) Similarly, the total time complexity of an Mee layer is O(VVD2 ED)/(1 n)). This complexity is equivalent a typical GNN layer if we consider 1/(1 7) constant (for instance, it is constant of 2 when 17 0.5).
Theoretically, when using the same number of layers, MeGraph is better capturing LRIs than standard message-passing GNNs owning to the hierarchical structure (see App. D. for details). On the other hand, MeGraph can degenerate into standard peessag-ppassing GNNs (see App. D.2 for details), indicating it should not perform worse than them on other tasks.
Experiments
We conduct extensive experiments to evaluate the MeGraph's 's ability to capture long-range interactions (LRIs) and its performance in general graph learning tasks.
4.1 Experimental Settings
Baselines. We compare MeGraph model to three baselines as follows: 1) MeGraph /=1 variant does not use the hierarchical structure and falls back standard GNNs. 2) MeGraph n=1 variant gives up repeating information exchange over the mega graph. 3) Graph U-Nets [22] uses a U-shaped design and only traverses the multi-scale graphs once.
Due to page limits, statistics of the datasets are provided in App. B. hyper-parametent are reported in Table 9, and the training and implementation details reported in App. E.

---

Table I: Results on Graph Theory Benchmark (medium size). For each task, we report the MSE regression loss on test set, averaged over different graph generation methods. Darker blue cells denote better performance and the bold denotes the best one. We provide detailed results on each type of graphs in App. F.7.
Category
Model
SPadd
MCC
Diameter
SPer
ECC
Average
n=1
11.184
1.504
11.781
22.786
20.133
13 13.478
Baselines
n=5
3.898
1.229
5.750
12.354
18.971
8.440
(/=l)
n=10
2.326
1.264
5.529
7.038
18.876
7.006
MeGraph (1=5)
n=1
1.758
0.907
4.591
5.554
14.030
5.368
EdgePool (r,=2)
n=5
0.790
0.767
2.212
0.712
6.593
2.215
vg=3
0.660
0.747
0.719
0,459
0.942
0.705
MeGraph
10.3.3
2.225
0.778
1.061
3.591
2.009
1.933
S S-EdgePool
10.0.3. 7,=4
0.615
0.702
0.651
0.434
0,975
0.675
Variants
=0.5.5 T-=4
1.075
0.769
0.945
1.204
1.992
1.197
(h=5, 5=
=0.3., 7 (X-Pool)
0.935
0.751
0.864
1.462
2,003
1.203
=.33. 7 (w/o pw)
0.632
0.730
0.864
0.765
2.334
1.065
Graph-UNets
1.118
1.008
2.031
1.166
2.584
1.581
Table 2: Results Graph Theory Benchmark (large size).
Category
Model
SPasd
MCC
Diameter
SP
ECC
Average
Baseline
h=1.n=
328.014
39.4772
189.577
324.033
219.746
220.169
MeGraph
h=5 ha5,n=55mmm003...e
23.8963
16.8321
19.2185
14.9676
44.9234
23.9676
Graph-UNets
101.009
30.3711
39.8708
100.070
75.1185
69.2879
Table 3: Results LRGB [17]. numbers taken from corresponding papers. All methods around 500K
parameters for fair comparison. cessagg-passing-heee -aased models have 5 layers, while the Transformer-haser models have 4 layers [17]. PE indicates positional encoding, which makes easier to distinguish different nodes.
Methods
Use PE
Peptide-func f
Peptide-struct
GCN [17]
59.30 20.23
0.3496 +0.0013
GINE [17]
55,43 20.78
0.3547
#0.0015
GatedGCN [17]
58.64 20.77
0.3420
#0.0013
GatedGCN+RWSE [17]
60.69 10.35
0.3357 10.0006
GuteGGCN+RWSE++N [10]
66.85 1..62
0.2529 1:0.0099
Transformer+LapPE [17]
63.26 11.26
0.2529 10.0016
SAN+LapPE [17]
63.84 1122
0,2683 +0.0043
SAN+RWSE [17]
64.39
0.2545
10.0012
GPS [46]
65.35 +0.41
0,2500 +0.0005
MGT+WavePE [43]
68.17 #0.61
0.2453 +0.0025
GNN-AK+ [27]
64,80 +0.89
0.2736
#0.0007
SUN [27]
67.30 70.78
0.2498
+0.0008
GraphTrans+ [27]
63.13 #0.39
0.2777
=0.0025
GINE+PE [27]
64.05 10.77
0.2780
10.0021
GINE-MLP WWE-MML-MMiierHP [27]
69.21 4.054
0.2485
0.00004
MeGraph (h=9,n=1)
67.52 20.78
0.2557
- 000011
MeGraph (b=9,n=4)
69.45 +0.77
0.2507
- 0009
4.2 Perfomance on LRI Tasks
To test MeGraph's ability to capture long-range interactions, establish Graph Theory Benchmark. of which four tasks related to shortest path distance, i.e.. Single Source Shortest Path (SPx)) Single Source Single Destination Shortest Path (SP Graph Diameter (Diameter) and Eccentricity of nodes (ECC); and task related to connected component, i.e., Maximum Connected Component of the same color (MCC). To generate diversified undirected and unweighted graphs for each task, adopt the ten methods used in PNA [12] and add four new methods: cycle graph, pseudotree, SBM, and geographic threshold graphs. The details of the dataset generation can be found in App. B.2.
As depicted in Table the MeGraph model with h=5, n=5 significantly outperforms both the h=1 and n=1 basclines in terms of reducing regression error across all tasks. It is worth noting that even

---

Table 4: Results on GNN benchmark. Regression tasks are colored with blue. + indicates that smaller numbers are better. Classification tasks colored with green. indicates that larger numbers are better. Darker colors indicate better performance, denotes the results are reported in [15].
Model
ZINC
4
MNIST f
CIFARIO
PATTERN 1
CLUSTER t
GCN
0,416 10.006
1.372 10.020
90.120
10.145
54,142
10.394
85,498
10.00 04.445
47.828
11.510
GIN
0.387 10.015
1.894
10.024
96,485
10.252
55.255
11.527
85,590
10.011
58.384
10.236
GATI
0.475 +0.007
1.441 +0.023
95.535
#0.205
64.223
#0.455
75.824
#1.823
57.732
+0.323
GatedGCNt
0.435 +0.011
1.352 +0.034
97.340
+0.143
67.312
#0.311
84,480 =0 122
60.404
#0.419
Graph-UNets
0,332 20.010
1.063
$0.018
97.130
20.227
68.567
4:0 =0.339
86,257
#0.078
50.371
40,243
MeGraph (h=1)
0.323 100002
1.075
1:0.07
97.570
10.168
69,890
1:0 209
84, 84.845 1:0 021
58.178 1.0079
MeGraph (n=1)
0.310 10.005
1.038
10.018
96. 867 10.187
68.522
10 239
85.507
1.0 402
50.396
10.082
MeGraph
0,260 10.005
1.002
10.021
97.860
10,098
69.925
1.0 63.331
86.507
10.067
68. 50.
10, 101
0.202 +0.007
1.002 +00021
97.860 #0.008
69.925
=:0 631
86.732 = 20.023
68.610
+0. 164
Table 5: Results on OGB-G. i indicates that the results are reported in [28].
Model
molhiv f
molbace f
molbbbp 1
molclintox f
molsider 1
GCN1
76.06 +0.97
79.15 11.44
68.87 =1.51
91.30 +1.73
59.60 =1.77
GIN
75.58 +1.40
72.97 #4.00
68.17 =1.48
88. 14 +2.51
57.60 =1.40
Graph-UNets
79.48 +1.06
81.09 1..6
71.10 =0.52
91.67 1166
59.38 +0.03
MeGraph (h=1)
78.54 +1.14
71.77
+2.15
67.56
11.11
89.77 +3.48
58.28 =0.51
MeGraph (n=1)
78.56 +100
79.72
+1.24
67.34
=0.98
91.07
#2.21
58.08 +0.09
MeGraph
77.20 +0.88
78.52
#2.51
69.57
=2.33
92.04
12.19
59.01
11.45
MeGraphbest
79.20 11.00
83.52
+0.47
69.57 #2.33
92.06 1.33
63.43 11.10
Model
moltox21 f
moltoxcast t
molesol
molfreesolv 4
mollipo 4
GCN
75.29 +0.09
63.54
#0.42
1.114 =0.03
2.640 +0.23
0.797
=0.02
GIN
74.91 #0.51
63.41 #0.74
1.173 =0.05
2.755 +0.34
0.757 =0.01
Graph-UNets
77.85
+0.81
66.49
#0.45
1.002 =0.04
1.885 +0.07
0.716 #0.01
MeGraph (h=l)
75.89
+0.45
64.49
#0.46
1.079 =0.02
2.017
+0.08
0.768 +0.00
MeCraph (n=1)
77.01
+0.93
66.89
+1.21
0.896
=0.04
1.892 40.06
0.730
#0.01
MeGraph
78. 11 +0.47
67.67
+0.53
0.886
=0.02
1.876
+0.05
0.726 10.00
MeGraphbest
78.11 10.47
67.90
10.19
0.867 00.0
1.876 40.05
0.688 10.01
the /=5,, n=1 baseline outperforms the h=1, n=10 baseline, indicating that adopting a multi-scale graph hierarchy is crucial in these tasks. The improvement is also substantial when compared with our reproduced Graph-UNets using S-EdgePool (MMeGraph] 0.675 vs. [Graph UNets] 1 1.581). ). The improvements are more significant when the size of graphs becomes larger (as shown in Table 2). These results collectively demonstrate the superior ability of MeGraph to capture LRIs.
Furthermore, we evaluated MeGraph model and compared it with other recent methods the Long Range Graph Benchmark (LRGB) [17] that contains real-world tasks that require capturing LRIs. As depicted in Table 3, the h=9, n=4 variant of MeGraph achieves superior results the Peptide-func task, and comparable performance on the Peptide-struce struct task, relative to state-of-the-an models. It is worth noting that the 1 variant already surpasses other methods except the recent MLP-Mixer [27] in the Peptide-fune task.
4.3 Generality of MeGraph
To verify the generality of MeGraph model, we evaluate MeGraph on widely adopted GNN Bench- mark [15], Open Graph Benchmark [28] and TU Dataset [42]. Results on TU Datasets are available in App. F.3. In addition to the standard model that shares prrper-prramters in similar tasks, we also report MeGraphbest with specifically tuned hyperr-aarameters for each task.
GNN Benchmark. We experiment on chemical data (ZINC and AQSOL), image data (MNIST and CIFAR10) and social network data (PATTERN and CLUSTER). As shown in Table 4, MeGraph outperforms the three baselines by a large margin, indicating the effectiveness of repeating both the local and hierarchical information aggregation.
Open Graph Benchmark (OGB). We choose 10 datasets related to molecular graphs from the graph prediction tasks of OGB. The task of all datasets is to predict some properties of molecule graphs
8

---

TreeCycle
TreeGrid
1.00
1.00
0.96
0.98
0.88
0.94
0.84
0.92
0.80
0.76
0.88
0.72
0.68
0.84
0.64
0.82
0.60
0.80
10
6
Num Layer
Num Layer
EdyoRool he2
Random
hw1
Exdgehoo hrd
Lotorein hrdd
Randdr h-3
EdgelPol h-
Loutoein hi-3
Random h-
Figure 4: Node classification accuracy (averaged over 10 random repetitions) for MeGraph (left) and TreeGrid (right) datasets by varying the number of Mee layers the height h, and the graph pooling methods (EdgePool, Louvain, Random). Clear gaps can be observed among heights 1, 2. and 3 for EdgePool and Louvain [8] methods, while the accuracy is almost invariant among different heights for randomized pooling.
TreeCycle
based on their chemical structures. As shown in Table 5, MeGraph outperforms the 1=1 baseline by large margin, suggesting that building a graph hierarchy is also essential molecule graphs. The performance of MeGraph, = 1 baseline, and the reproduced Graph U-Nets are comparable. This observation may be because the information obtained from multi-hop neighbors offers only marginal improvements compared to the information aggregated hierarchically.
4.4 Ablation Study
Hierarchy vs. Locality. We study the impact of the height h and the number of Mee layers four synthetic datasets introduced in [61], which are BAShape. BACommunity, TreeCycle, and TreeGrid. Each dataset contains one graph formed by attaching multiple motifs base graph. The motif can be a 'house" -shape network (BAShape, BACommunity), six-node cycle (TreeCycle), or 3-by-3 grid (TreeGridd) The task is to identify the nodes of the motifs in the fused graph.
As shown in Fig. 4, we can observe clear improvements in performance as the height and the number of layers increase when using EdgePool. Although increasing height shows better improvements, both hicrarchy and locality are indispensable in TreeCycle and TreeGrid tasks. In App. F.5, we show that the conclusion also holds on BAAShape and BACommunity datasets, except that the accuracy already saturated with height h = 2. The significance of integrating locality with hierarchy is also demonstrated in the CLUSTER task, presented in Table 4. Here, MeGraph reaches 68.6% accuracy, which is markedly higher than the 50.4% accuracy achieved by both the n=1 baseline and Graph-UNets.
Varying the Pooling Method. We varied the graph pooling with two non-learnable pooling methods, Louvain [8] and Random. On the TreeCycle and TreeGrid datasets, depicted in Fig. 4, Louvain achieves comparable accuracy to EdgePool, while MeGraph using random pooling matches the performance of the h variant of MeGraph. These observations indicate that: I) well-structured hierarchy crafted by suitable graph pooling methods enhances MeGraph's 's ability to harness hierarchi- cal information; and 2) despite the disruption from randomly constructed hierarchy, the MeGraph model effectively taps into the local structure of the original graph (also discussed in App. D.2).
We further studied the impact of the node pooling ratio The and the maximum cluster size To in S-EdgePool by perturbing these parameters. As indicated in Table 1, the best variant 70,, achieved regression error about 3x smaller (0.675) compared to the original EdgePool (r.=2 with an error of 2.215). This suggests the benefit of having a flcxible pooling stride. Moreover, the mega graph produced by S-EdgePool can vary significantly with different parameters. In App. F.2, visualized the resulting graph hicrarchy to illustrate the difference between different S-EdgePool variants. However, irrespective of the parameter set used, MeGraph consistently outperforms h 1 baselines. This suggests that MeGraph exhibits robustness against different architectures of the mega graph.
Varying GN Block. We varied the aggregation function of the GN block as attention (w/ ATT) and gated function (w/ GATE). We observe similar results as in Sec. 4.2 and 4.3, verifying the robustness of MeGraph towards different types of GN blocks. Detailed results can found in Tables 16, and 18 in App. F.6.

---

Changing cross update function (X-UPD). The unpool operation is frequently used by other hier- archical architectures that build upon graph pooling. As illustrated in Table we substituted the X-Conv implementation with the X-Pool implementation of X-UPD, which resulted in performance decline from 0.675 to 1.203 (smaller is better). This finding suggests that other hierarchical GNNs might also benefit from replacing the unpool operation with a convolution over the inter-graph edges.
Disabling bidirectional pathway. We verify the effectiveness of the bidirectional pathway design by replacing steps 2 and of the Mee layer as a standard message-passing along the inter-graph edges (denoted w/o pw). As shown in Table 1, the performance degrades from 0.675 1.065 (smaller is better), which indicates the contribution of the bidirectional pathway.
5 Related Work
Long-Range Interactions (LRIs). Various methods have been proposed to address the issue of LRIs, including making the GNNs deeper [40]. Another way is to utilize attention and gating mechanism. including GAT [52]. jumping knowledge (JK) network [59], incorporating Transformer structures [35, 60. 56, 46] and MLP-Mixer [27]. Another line of research focuses on multi-scale graph hierarchy using graph pooling methods [62, 22, 47], or learning representation based on subgraphs [5, 66]. Recently, Long Range Graph Benchmark [17] has been proposed to better evaluate
models' ability to capture LRIs.
Feature Pyramids and Multi-Scale Feature Fusion. Multi-scale feature fusion methods on image feature pyramids have been widely studied in computer vision literature, including the U-Net [48], FPN [39], UNet++ [67], and some recent approaches [63, 41, 38, 37J. HRNet [53] a similar method compared to MeGraph. HRNet alternates between multi-resolution convolutions and multi-resolution fusion by stridden convolutions. However, the above methods are developed for image data. The key difference compared to these approaches is that the multi-scale feature fusion in MeGraph is along the inter-graph edges, which is not as well structured as the pooling operation in image data. For graph networks, the GraphFPN [65] builds a graph feature pyramid according to the image feature pyramid and superpixel hierarchy. It applies GNN layers on the hierarchical graph to exchange information within the graph pyramid. Existing works [22, 20, 47, 30] have also explored similar ideas in graph- structured data. Our approach aligns with the broader concept of multi-scale information fusion, but it is the first method that builds mega graph using graph pooling operations and alternates local and hierarchical information aggregation.
Graph Pooling Methods. Graph pooling is an important part of hierarchical graph representation
learning. There have been some traditional graph pooling methods like METIS [32] in early liter- ature. Revently, many sotriing-based graph pooling methods have been proposed, including the DiffPool [62], Topk [22], SAG pool [36], EdgePool [13], MinCutPool [7], Structpool [64], and MEWISPool [44], etc. In this work, we utilize S S-EdgePool improved from EdgePool to build the mega graph, while this module can be substituted with any of the abooe-menntoone pooling methods.
Graph Neural Network (GNN) Layers. The GNN layer is the core module of graph representation learning models. Typical GNNs include the GCN [34], GraphSage [24], GAT [52, 9], GIN [58], PNA [12]. MeGraph adopts the full GN block [6] by removing part of links in the module as an elementary block, and similarly this can be replaced by any one of the popular GNN blocks.
Limitations and Future Work
The MeGraph model suffers from some limitations. The introduced mega graph architecture inevitably increases both the number of trainable parameters and tuneable syper-parameters. The flexible choices of many modules in MeGraph post burdens on tuning the architecture on specific datasets. For future research, MeGraph encourages new graph pooling methods to yield edge features in addition to node features, when mapping the input graph to the pooled graph. It is also possible to improve MeGraph using adaptive computational steps [49]. Another direction is to apply some expressive but computationally expensive models like Transformers [51] and Neural Logic Machines [14, 57] (only) over the pooled small-sized graphs.
A Acknowledgements
We thank Qizheng He for the discussions on the Graph Theory Dataset, Kirsty You for improving the illustrations, and Jiafei Lv and the Maddison group for their helpful discussions or feedback on the paper draft; This work was supported by the STI 2030-Major Projects under Grant 202 4000044444
10

---

References
[1] Edward H Adelson, Charles Anderson, James R Bergen, Peter J Burt, and Joan M Ogden. Pyramid methods in image processing. RCA engineer, 29(6):33 1984.
[2] Réka Albert and Albert-Lászie Barabási. Statistical mechanics of complex networks. Reviews of modern physics, 74(1):47, 2002.
[3] Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In International Conference on Learning Representations, 2020.
[4] Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E. Hinton, Layer normalization, arXiv preprint arXiv: (600::607.44400 2016.
[5] Jinheon Back, Minki Kang, and Sung Ju Hwang. Accurate learning of graph representations with graph multiset pooling. In International Conference on Learning Representations.
[6] Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinicius Zambaldi. Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, al. Relational inductive biases, deep learning, and graph networks. arXiv preprint arXiv:1806.0126: 2018.
[7] Filippo Maria Bianchi, Daniele Grattarola, and Cesare Alippi. Spectral clustering with graph neural networks for graph pooling. In International Conference on Machine Learning, pages 874-883, PMLR, 2020.
[8] Vincent D Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre. Fast unfolding of communities in large networks. Journal of statistical mechanics: theory and experiment, 2008(10):P10008, 2008
[9] Shaked Brody, Uri Alon, and Eran Yahav. How attentive are graph attention networks? In International Conference on Learning Representations, 2021.
[10] Chen Cai, Truong Son Hy, Rose Yu, and Yusu Wang. On the connection between mpnn and graph transformer. arXiv preprint arXiv:2301.11956 2023.
[11] Ting Chen, Song Bian, and Yizhou Sun. Are powerful graph neural nets necessary? dissection on graph classification. arXiv preprint arXiv: 99059945597 2019.
[12] Gabriele Corso, Luca Cavalleri. Dominique Beaini, Pietro Liō, and Petar Veličkovié. Principal neighbourhood aggregation for graph nets. Advances in Neural Information Processing Systems, 33:13260- 13271, 2020.
[13] Frederik Dichl, Thomas Brunner, Michael Truong Le, and Alois Knoll. Towards graph pooling by edge contraction. In ICML 2019 workshop on learning and reasoning with graph-structured data, 2019.
[14] Honghua Dong, Jiayuan Mao, Tian Lin, Chong Wang, Lihong Li, and Denny Zhou. Neural logic machines. In International Conference on Learning Representations, 2018.
[15) Vijay Prakash Dwivedi, Chaitanya K Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv preprint arXiv:2003.00982. 2020.
[16] Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph neural networks with learnable structural and positional representations. In International Conference on Learning Representations, 2021.
[17] Vijay Prakash Dwivedi, Ladislav Rampasek, Mikhail Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, and Dominique Beaini. Long range graph benchmark. In Thirty-sixth Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2022.
[18) Paul Erdös, Alfréd Rényi, al. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad, Sci, 5(1):17-60, 1960.

---

[19] Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprint vrXiv:1903.00 02428, 2019.
[20] Matthias Fey, Jan-Gin Yuen, and Frank Weichert. Hierarchical inter-message passing for learning molecular graphs. arXiv preprint arXhv:2006.1211 2020.
[21] Bernard A Galler and Michael Fisher. An improved equivalence algorithm. Communications of the ACM, 7(5):301-303, 1964.
[22] Hongyang Gao and Shuiwang Ji. Graph u-nets. In international conference on machine learning. pages 2083-2092. PMLR, 2019.
[23] Daniele Grattarola, Daniele Zambon, Filippo Maria Bianchi, and Cesare Alippi. Understanding pooling in graph neural networks. IEEE Transactions Neural Networks and Learning Systems, 2022.
[24] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
[25] Jessica B Hamrick, Kelsey R Allen, Victor Bapst, Tina Zhu, Kevin R McKee, Joshua B Tenenbaum, and Peter W Battaglia. Relational inductive bias for physical construction in humans and machines. arXiv preprint arXiv:1806.01203. 2018.
[26] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and paltern recognition, pages 770-778, 2016.
[27] Xiaoxin He, Bryan Hooi, Thomas Laurent, Adam Perold, Yann LeCun, and Xavier Bresson. A generalization of vit/mlp-mixer to graphs, 2022.
[28] 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. Advances in neural information processing systems, 33:22118-2211 2020.
[29] Yuanming Hu, Tzu-Mao Li, Luke Anderson, Jonathan Kelley,,lley,, and Frédo Durand. Taichi: a language for high- perforrrffe computation on spatially sparse data structures. ACM Transac- tions on Graphics (TOG), 38(6):201, 2019.
[30] Truong Son Hy and Risi Kondor. Multiresolution equivariant graph variational autoencoder. Machine Learning: Science and Technology, 4(1):01503,, 2023.
[31] Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International conference on machine learning, pages 448-456. PMLR, 2015.
[32] George Karypis and Vipin Kumar. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on scientific Computing, 20(1):359-392, 1998.
[33] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In ICLR (Poster), 2015.
[34] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. 2016.
[35] Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létoureau,, and Prudencio Tossou. Rethinking graph transformers with spectral attention. Advances in Neural Information Pro- cessing Systems, 34:21618 226882,21999211 2021.
[36] Junhyun Lee, Inyeop Lee, and Jaewoo Kang. Self-attention graph pooling, In International conference on machine learning, pages 3734-3743. PMLR, 2019.
[37] Xiangtai Li, Houlong Zhao, Lei Han, Yunhai Tong, Shaohua Tan, and Kuiyuan Yang. Gated fully fusion for semantic segmentation. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pages 14418-1425, 2020. 2020.
12

---

[38] Di Lin, Dingguo Shen, Siting Shen, Yuanfeng Ji, Dani Lischinski, Daniel Cohen-Or, and Hui Huang. Zigzagnet: Fusing top-down and bottom-up context for object segmentation. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pages 7490-7499, 2019.
[39] Tsung-Y Yi Lin, Piotr Dollár, Ross Girshick, Kaiming He, Bharath Hariharan, and Serge Belongie. Feature pyramid networks for object detection. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 2117-2125, 2017.
[40] Meng Liu, Hongyang Gao, and Shuiwang Ji. Towards deeper graph neural networks. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, pages 338-348, 2020.
[41] Shu Liu, Lu Qi, Haifang Qin, Jianping Shi, and Jiaya Jia. Path aggregation network for instance segmentation. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 8759-8768, 2018.
[42] Christopher Morris, Nils M Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs arXiv preprint arXiv:2007.08663 2020.
[43] Nhat Khang Ngo. Truong Son Hy, and Risi Kondor, Multiresolution graph transformers and wavelet positional encoding for learning long-range and hierarchical structures. The Journal of Chemical Physics, 159(3), 2023.
[44] Amirhossein Nouranizadeh, Mohammadjavad Matinkia, Mohammad Rahmati, and Reza Safabakhsh. Maximum entropy weighted independent set pooling for graph neural networks. arXiv preprint urXiv:2107.01410 2021.
[45] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, tigh-performanc deep learning library. Advances in neural information processing systems, 32, 2019.
[46] Ladislav Rampášek, Mikhail Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini. Recipe for a general, powerful, scalable graph transformer. arXiv preprint arXiv:2205. 12454, 2022.
[47] Ladislav Rampášek and Guy Wolf. Hicrarchical graph neural nets can capture long-range interactions. In 2021 IEEE 31st International Workshop on Machine Learning for Signal Processing (MLSP), pages 1 1-6. IEEE, 2021.
[48] Olaf Ronneberger, Philipp Fischer, and Thomas Brox. U-net: Convolutional networks for biomedical image segmentation. In International Conference on Medical image computing and computer-assisted intervention, pages 234-241. Springer, 2015.
[49] Hao Tang, Zhiao Huang, Jiayuan Gu, Bao-Liang Lu, and Hao Su. Towards scale-invariant graph-related problem solving by iterative homogeneous gnns, Advances in Neural Information Processing Systems, 33: 151 1-15822, 2020.
[50] Robert E Tarjan and Jan Van Leeuwen. Worst-case analysis of set union algorithms. Journal of the ACM (JACM), 3 ((2):245-28)) 1984.
[51] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. Advances in neural information processing systems, 30, 2017.
[52] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
[53] Jingdong Wang, Ke Sun, Tianheng Cheng, Borui Jiang, Chaorui Deng, Yang Zhao, Dong Liu, Yadong Mu, Mingkui Tan, Xinggang Wang, et al. Deep high-resolution representation learning for visual recognition. IEEE Iransactions on pattern analysis and machine intelligence, 43(10):3349-3364 2020.
13

---

[54] Minjie Wang, Da Zheng, Zihao Ye, Quan Gan, Mufei Li, Xiang Song, Jinjing Zhou, Chao Ma, Lingfan Yu, Yu Gai, Tianjun Xiao, Tong He, George Karypis, Jinyang Li, and Zheng Zhang. Deep graph library: A graph-centric, highly-performant package for graph neural networks. arXiv preprint 15, 2019.
[55] Duncan J WATTS, Networks, dynamics and the small world phenomenon. American Journal of Sociology, 105(2):50-555 2003.
[56] Zhanghao Wu, Paras Jain, Matthew Wright, Azalia Mirhoseini, Joseph E Gonzalez, and Ion Stoica. Representing long-range context for graph neural networks with global attention. Advances in Neural Information Processing Systems, 34:13266-13279 2021.
[57] Guangxuan Xiao, Leslie Pack Kaelbling, Jiajun Wu, and Jiayuan Mao. Efficient training and inference of hypergraph reasoning networks, 2022.
(58) Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2018.
[59] Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning graphs with jumping knowledge networks. In International conference on machine learning, pages 5453-5462. PMLR, 2018.
[60] Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie- Yan Liu. Do transformers really perform badly for graph representation? Advances in Neural Information Processing Systems, 34:28877-28888, 2021.
[61] Zhitao Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitik, and Jure Leskovec. Gnnexplainer: Generating explanations for graph neural networks. Advances in neural information processing systems, 32, 2019.
[62] Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hierarchical graph representation learning with differentiable pooling. Advances in neural information processing systems, 31, 2018.
[63] Fisher Yu, Dequan Wang, Evan Shelhamer, and Trevor Darrell. Deep layer aggregation. In Proceedings of the IEEÉ conference on computer vision and pattern recognition, pages 2403- 2412, 2018.
[64] Hao Yuan and Shuiwang Ji. Structpool: Structured graph pooling via conditional random fields.
In Proceedings of the 8th International Conference on Learning Representations, 2020.
[65] Gangming Zhao, Weifeng Ge, and Yizhou Yu. Graphfpn: Graph feature pyramid network for object detection. In Proceedings of the IEEE/CVF International Conference on Computer Vision pages 2763-2772, 2021.
[66] Lingxiao Zhao, Wei Jin, Leman Akoglu, and Neil Shah. From stars to subgraphs: Uplifting any gnn with local structure awareness. In International Conference on Learning Representations.
[67] Zongwei Zhou, Md Mahfuzur Rahman Siddiquee, Nima Tajbakhsh, and Jianming Liang. Unet++: A nested u-net architecture for medical image segmentation. In Deep learning in medical image analysis and multimodal learning for clinical decision support, pages 3-11. Springer, 2018
14

---

Appendix
Table of Contents
A Code and Reproducibility
16
B Dataset Details
16
B.1 Dataset Statistics and Metrics
16
Graph Theory Benchmark
C Method Details
18
C.I Cross Update Function
................................
18
C.2 S-EdgePool
19
C,3 GFuN
20
C.4 Encorder and Decoder
21
Architecture Variants
22
D Theoretical Discussions
22
D.1 Smaller Number of Aggregation Steps for Capturing Long- Range Interactions
22
D.2 MeGraph degenerate standard GNNs
22
E
Implementation and Training Details
23
F
Additional Experiment Results
23
F.1
Experimental Protocol
23
F22
Visualization
24
F3
Other Real-Wrold Datasets
24
F.4
GFuN
24
F55
Synthetic Datasets
25
F6
Varying GN block
25
F7
Graph Theory Dataset
27
15

---

A Code and Reproducibility
The code along with the configuration of typer-parameters to reproduce our experiments can be found at
com/dhh190 1999 2995///
We set the random seed as 2022 for all experiments to enable reproducible results. We provide dataset statistics in Table 6 and details for the proposed graph theory benchmark in Appendix B.2. Details of the
are reported in Table Configuration all peerm-rreetters and the command lines reproduce the experiments have been included in the code repository.
B
Dataset Details
B.1 Dataset Statistics and Metries
We provide the statistics of all datasets used in our experiments in Table and introduce the evaluation metrics for each dataset.
For Synthetic datasets, we use classification accuracy (ACC) as the evaluation metric. We use Mean Square Error (MSE) as the evaluation metric for all datasets in our Graph Theory Benchmark. For GNN Benchmark, we follow the original work [15] for evaluation, i.c., Mean Absolute Error (MAE) for ZINC and AQSOL, classification accuracy for MNIST and CIFAR10, and balanced classification accuracy for PATTERN and CLUSTER. For OGB Benchmark, we follow the original work [28] and use the ROC-AUC for classification tasks and Root Mean Square Error (RMSE) for regression tasks. For TU datasets, we follow the setting used by [11] and use classification accuracy as the evaluation metric.
B.2 Graph Theory Benchmark
In this section, we provide the details about the tasks and how the graph features and the labels generated given a base graph g = (V,
Single source single destination shortest path ssPs) a source node s e and a destination node t E V are selected uniform randomly. The feature of each node v contains three numbers: (1, whether the node v is 8, whether the node u is t). The label of a graph the length of the shortest path from to t.
A maximum connected component of the same color (MCC): each node of the graph is colored with of three colors. The feature for each node is the one-hot representation of its color. The label of graph is the size of the largest connected component of the same color for each color.
Graph diameter (Diameter): the label of the graph is the diameter of the graph. The diameter of graph G is the maximum of the set of shortest path distances between all pairs of nodes in the graph. The feature of each node is a uniform number 1.
Single source shortest path (SPss): : source node is selected uniformly randomly. The feature each node contains two numbers: (I, whether the node is s). The label of each node is the length of the shortest path from to this node.
Graph eccentricity (ECC): the label of each node e is node's eccentricity in the graph, which is the maximum distance from v to the other nodes. The feature of each node is uniform number 1.
For each task and graph generation method, We generate the dataset by the following steps:
Sample N (number of nodes) from interval with total number of graphs. These numbers can be configured. For the medium size setting, the interval is [20, 50), a total of 300 graphs. For the large size setting, the interval [100, 200), total of 500 graphs.
Use the graph generation method to generate a graph of N nodes.
Create graph features and labels according to the task.
16

---

Table The statistics of the datasets used in experiments. Some statistics (like the average number of edges) of the Graph Theory datasets may vary depending on different random graph generation methods. The regression tasks are marked with v in separate column. The tasks of synthetic datasets are transductive, where the same graph is used for both training and testing. We do not use the node labels as features during the training time. The train-val-test split is over nodes. All other datasets in the table are inductive, where the testing graphs do not occur during training, and the train-val-test split is over graphs.
Avg
Avg # Edges
Collection
Dataset
Node Feat
Edge Feat
Task
Reg.
Graphs
Classes
Nodes
Synthetic Synthetic
BaShape
700
1761
Trans-Node
BaCommunity
1400
3872
10
Trans-Node
Synthetic
TreeCyele
871
970
Trans-Node
Synthetic
TreeGrid
1231
1705
Trans-Node
GraphTheory
SPoed
300
35.0
Graph
GraphTheory
Diameter
300
35.0
Graph
TreprTh
MCC
300
35.0
Graph
GraphTheor
SP..
300
35.0
Node
GraphTheory
ECC
300
35.0
Node
LRGB
Peptides-func
15535
150.94
307.30
Gruph
LRGB
Peptides-struct
15535
150.94
307.30
Graph
GNNBenchmark
ZINC
12000
23.16
49.83
28
Graph
GNNBenchmark
AQSOL
9823
17.57
35.76
65
Graph
GNNBenchmark
MNIST
70000
70.57
564.53
10
Graph
GNNBenchmark
CIFARIO
60000
117.63
941.07
Graph
GNNBenchmark
PATTERN
14000
118.89
6078.57
Node
GNNBenchmark
CLUSTER
12000
117.20
4301.72
Node
OGB Gruph
molhiv
41127
25.51
80.45
Graph
OGB Graph
molbace
1513
34,09
107 (07.81
Graph
OGB Graph
molbbbp
2039
24.06
75.97
Graph
OGB Graph
molelintox
1477
26.16
81.93
2
Graph
OGB Graph
molsider
1427
33.64
104.36
2
Graph
OGB Graph
moltox21
7831
18.57
57.16
2
Graph
OGB Graph
moltoxcast
8576
18.78
57.30
Graph
OGB Graph
molesol
1128
13:29
40.64
Graph
OGB Graph
molfreesolv
642
8.7
25.50
Graph
OGB Graph
mollipo
4200
27.04
86.04
Graph
TU MUTAG
188
17.93
19.79
7
Graph
TU
NCTI
4110
29.87
32.30
37
Graph
TU
PROTEINS
1113
39.06
72.82
Graph
TU
D&D
1178
284.32
715.66
89
Graph
TU
ENZYMES
600
32.63
62.14
21
Graph
TU
IMDB-B
1000
19.77
96.53
10
2
Graph
TU
IMDB-M
1500
13.00
65.94
Graph
TU
RE-B
2000
429.63
497.75
Graph
TU
RE-MSK
4999
508.52
594.87
Graph
TU
RE-M12K
11929
391.41
456.89
Graph
17

---

We then provide the details about the random graph generation methods we used to create our Graph Theory datasets.
Following [12], we continue to use undirected and unweighted graphs from a wide variety of types. We inherit their 10 random graph generation methods and quote their deseriptions here for completeness (the percentage after the name is the approximate proportion of such graphs in the mixture setting).
Erdös-Rényi (ER) (20%) [18]: with a probability of presence for each edge equal to p. where is independently generated for each graph from 2/ 1]
Barabási-Albert (BA) (20%) [2]: the number of edges for a new node k, which taken N 7--1 }} for each graph
randomly from { .,.,,... .....,,''
Grid (5%): m x 2d grid graph with N = mk and m and & as close as possible
Caveman (5%) [55]: with cliques of size k. with m and close possible
Tree (15%): generated with power-law degree distribution with exponent 3
Ladder graphs (5%)
Line graphs (5%)
Star graphs (5%)
Caterpillar graphs (10%): with a backbone of size b (drawn from 4(11,)) and N - b pendent vertices uniformly connected to the backbone
Lobster graphs (10%): with a backbone of size b (drawn from U(1, p (drawn from U[1, b)) pendent vertices uniformly connected to the backbone, and additional N -bb-p pendent vertices uniformly connected the previous pendent vertices.
Additional, add three more graph generation methods:
Cycle graphs
Pseudotree graphs: A tree graph plus additional edge. The graph is generated by first generating a cycle graph of size m sample(0.3N, 0.6.N.. Then m remaining nodes are sampled to m parts, where i-th part represents the size of the tree hanging on the i-th node on the cycle. The trees are randomly generated with the given size.
Stochastic Block Model (SBM) graphs: graphs with clusters. We randomly sample the size of each block to be random from (5, 15), and the probability edge within the block to be random from (0.3, 0.5) and those for other edges to be random from (0.005, 0.01). To make all the tasks well-defined, we filtered out the unconnected graphs during the generation.
Geographic (Geo) graphs: geographic threshold graphs, but with added edges via minimum spanning tree algorithm, to ensure all nodes are connected. This graph generation method introduced by [6] in their codebase We use the geographic threshold 200 instead of the default value 1000.
Note that we do not have randomization after the graph generation as in [12]. Therefore, very long diameter preserved for some type of graphs.
C Method Details
C.1
Cross Update Function
The cross update function (X,, X'y x/41) = X-UPD(j, X3, X541) perform information ex- change in consecutive hierarchies.
The X-Com realization contains the following steps:
1. Merge the node features of X, and Xj+1 with the inter-graph feature X,, results in X,-
2. Apply GN blocks on inter-graph Φj: X = GNL. inter (Ộ), X²).
3. Retrieve X and X from the node features of inter- inter-graph features X/.
hhupss/githubbccm//eepmm//e/ee nets, the shortest path demo
18

---

C.2 S-EdgePool
In this subsection, we introduce the details of S-EdgePool. We first introduce the score generation method, then give details about the SELECT, CONNECT, REDUCE and EXPAND functions, and lastly provide pseudocode the algorithm.
C.2.1 Edge Score Generation
Both S-EdgePool and EdgePool methods compute a raw edge score ry for each edge k using a linear layer:
W ,V I
Ex)
where Sę and iy are the source and target nodes edge k, is node features. edge features, W and b are learned parameters. The raw edge scores are further normalized by a local softmax function over all edges of node:
Wx = exp(Tx)/
Σ
exp(re);
and biased by a constant 0.5 [13].
C.2.2 Select, Connect, Reduce and Expand
SELECT step. S-EdgePool shares the same computations as in EdgePool to generate learnable edge scores, as detailed above. Then, we use a clustering procedure to determine the subset of nodes to be reduced.
Let Iv be the identifier of the cluster containing set nodes v. Initially, we let v {u} for every single node v. A contraction of an edge merges pair of nodes (v, v") connected by this edge (where E v, o' E v'v and v + v'), and thus unifies the cluster identifiers. i.e., Iv Iv- I and V Vmerge- v Uv'. That is, once an edge connecting any pair of nodes from two distinct clusters is contracted, we merge the two clusters and unify their identifiers. Edges are visited sequentially by decreasing order on the edge scores, and contractions are implemented if valid. We set the maximum size of the node clusters to be parameter Te, where Te 2 degenerates to the case of EdgePool [13]. We further introduce the pooling ratio 77 to control the minimal number of remaining clusters after edge contractions to be N 1Ju. Contractions that violate the above two constraints are invalid and will be skipped. Both parameters control the number of nodes in the pooled graph. In our implementation, the cluster of nodes is dynamically maintained using the disjoint-set data structure [21].
Then each node cluster collapses into new node e of the pooled graph (i.e. Sa = {u|4 = i}), with inter-graph edges connect the nodes in the cluster the new node
CONNECT step. The CONNECT function rebuilds the edge set & between the nodes in V. As aforemen- tioned, we build the pooled graph's 's nodes according to node clusters. We call this mapping function from node clusters to nodes c2n. After that, build the pooled graph's edges following three steps: First, for all edges in the original graph, we find out the corresponding node cluster(s) of its two endpoints (using disjoint-set's find index operation). Then, we find out the corresponding new nodes by using the mapping function n. Last, we add new edge between the new nodes.
REDUCE and EXPAND step. The REDUCE and EXP AND are generalized from the method mentioned in [13]. The REDUCE function computes new node features and edge features. We follow their method to compute new node features by taking the sum of the node features and multiplying it by the edge score. Specifically, we generalize the computation between two nodes to a node cluster. The node clusters are maintained with disjoint-set data structure and cluster Sg consists of [Se] nodes. We define Ege as set of [Sa] 1 edges, where the edges are the selected edges to be contracted in the SELECT step. Then,
+ Ee We
Cp
Sa
V.-
G5
V
v
19

---

To integrate the edge features between two node clusters, we first find all the connected edges between the node clusters (the edges between node clusters are edges that connect nodes from different node clusters). Then, we use the sum of all the connected edges' features between the two node clusters as the new edge's features.
The EXPAND function is also referred as umpool operation. It computes node features of the input graph v given the node features of the pooled graph Va as following:
V
V
GF
C.2.3 Pseudo Code
The pseudo-code includes two parts, where Algorithm 1 describes how to maintain the clusters using a disjoint-set data structure, and Algorithm describes the procedure of S-EdgePool that generates pooled graph & with configurable node pooling ratio To and maximum of cluster sizes Te-
Algorithm 1 Get Cluster Index And Cluster Size of Node (Using disjoint-set data structure)
function InitalizeeDisjonnSeetrrrahp G(V,E))
for U E V do index[u] (the identifier of the cluster the node belongs to end for end function function FindIndex(node v) if index(v) [v] then
return else
index[u] FindIndex(indeer())) return inder[v]
end if end function
function FindIndexAAnSSizenndnd v)
< FindIndex(r)
sice[(] return 8
end function
function MERGE(cluster index v, cluster index y)
sizely) +- size[x] sizely]
indez [z] + index
end function
C.3 GFuN
We first realize the de, &v, 6u functions in the full GN block (Sec 2.1 and [6]) neural networks:
Eg NN, Ex sus V tup u),
(2)
V = NN, E. V., u),
(3)
u' NN, V u),
respectively, where
E ( [EEg
(5)
E'
E
(6)
V
(7)
We further decompose the neural networks according to the features in the function:
(E, V Axx Ve,, u) NN EE) + NN ce-u, (V.,) + NNc.mm (Vr.) + NN
(u).
NN, V., u) = NN E NN (V:) + NN..-.(u)
(9)
NN. (E', V u) -NN, E') NN (V') + N.V N.V (u)
(10)
20

---

Algorithm 2 Strided EdgePool
input graph (V, edge scores w, node pooling ratio Ye. maximum cluster sizes To- output pooled graph 9 = (V,E) and inter graph (V, E)
InitializeDisjointSee((
remains + No {NV is the number nodes in graph G & + Sort the edges & according to the edge scores w decreasingly.
for e E & do
2, y the two endpoints of the edge
rz, s - FindindexAndSiie(er
ry, sy < FindIndexAAndizzed
if ræ * ry and (sx + sy S Ta) then
Merge( y)
remains +- remains 1 if remains S No To then
break end if end if' end for V.E, V.E.VE V.& 0..000000
create empty mapping c2n from cluster index to nodes for v VE V do if FindIndex(1)
then
create new node ; c2n(v] = 10 <- (0) end if
end for
for E 3 do
E,Y y f- the two endpoints of the edge
f c2n FindIndex(x:))
ÿ - c2n (FindIndexx)))
E + E u {(., ;)}
end for
for E V do
6- (2nnFFnndndeex()) E
end for V- VUD
However, such GN block uses 10 times the number of parameters the standard GCN [34] layer when the node, edge and global embedding dimensions are all equivalent. In practice, we disable all computations related global features u, well the neural networks NN and NN NNe-mg- We also set NN, to be Identity.
In practice, we use the summation function as the aggregator function pf by default. But other choices like MEAN, MAX, gated summation, attention or their combinations can also used.
Overall, we call such GN block as graph full network (GFuN).
C.4 Encorder and Decoder
Encoder. For input embedding, we use the Linear layer or Embedding layer to embed input features. For example, we follow [15] and use the Linear layer on MNIST and CIFARIO datasets, and use the Embedding layer on ZINC and AQSOL datasets. For the molecular graph in OGB, we use the same embedding method as in the original work [28]. Besides, we can adopt positional encoding methods like Laplacian [15] and Random Walk [16] to further embed global and local graph structure information. The embedding of positional encoding can combined into (like concatenation, addition, etc.) input features and form new embeddings.
21

---

Decoder. We can freely choose from the multi-scale features computed during the process stage as inputs to the decoder module. Empirically, we use the features on the original graph for prediction in all experiments. For node-level tasks, we apply a last GNN layer on the original graph to get logits for every node. For graph-level tasks, we first use global pooling functions to aggregate features. We can use common global pooling methods like SUM, MEAN, MAX, or their combination. After the global pool, we use MLP layer(s) to generate the prediction.
C.5 Architecture Variants
We can replace some GN blocks within Mee layers as an Identity block to reduce the time complexity. We call the height j reserved if the intra GN block of height is not replaced by an Identity block. We prefer to reserve an interval of consecutive heights for the Mee layers. (The inter GN blocks between these heights remain unchanged while others are replaced as identities) By varying the heights reserved in each Mee layers, we can create a large number of variants of MeGraph model including U-Shaped, Seidge-Shapel and Staircase- -haree..
U-Shaped. This variant is similar to Graph U-Net [22]. In this U-Shaped variant, the relationship between the number of layers n and height h is layer. We keep the GN block at height = i for each layer at the first half layers and keep the GN block height; j = n i ++1 1 for each layer at the later half layers. In the middle layer, only the last height j = h = -n- 1)/2 has a GN block.
2h + and there is only one GN block in each
Bridge-Shaped. In this variant, all GN blocks are combined like arch bridge. Describe in detail, in the first and last layers, there are GN blocks in each height. In other layers, there are GN blocks at height of 1 to (where < h).
Staircase-Shaped. There are four forms in this variant, and the number of layers n is equal to the height h in all forms. The first form is like the 'downward' staircase. In each layer i of this form, there are GN blocks at the height of j to (where j = i). The second form the inverted first form. In each layer i of this second form, there are GN blocks at height of to h i 1 (where i). The last two forms are the mirror of the first and second forms.
D Theoretical Discussions
D.1 Smaller Number of Aggregation Steps for Capturing Long-Range Interactions
We rephrase the analysis provided in [47] as following:
We analyze the number of aggregation steps required to capture long-range interactions between nodes in the original graph while assuming the node representation capacity is large enough.
Standard message- pressage-passing GNNs require aggregation steps to capture long-range interactions of n hops away, therefore requiring a stack of layers, which could be expensive when is large.
We also assume the height of the hierarchy large enough so that all nodes of the original graph pooled into single node. In that case, the information aggregation along the hierarchy captures all pairs of LRIs into the embedding of the single node. Which means the number of aggregation steps of MeGraph is h. When
adopt a pooling method that coarsens the graph at least half, h is at most O Olog((VV)) where [V] is the number of nodes of the input graph. Therefore, the height is significantly smaller than the diameter of the graph (which could be O(V))) in most cases.
D.2 MeGraph degenerate to standard GNNs
MeGraph can learn a gating function (within the X-UPD function) that only reserves the features of the same scale while performing cross-scale information exchanging. In that case, there will be no information exchange across multi-scale graphs, and features other than those in the original scale will not be aggregated. We provide proof sketch below, while the results of the random pooling method ablation study in Sec. 4.4 also provide empirical evidence.
The cross update function (X), X/, X1+1) = X-UPD(j, X,, Xj+1). There is a residual function applied here, and we assume it implemented as gated residual: X" =
Proof:
where is the sigmoid function and a, 3 are learnable parameters. Theoremetically, it is possible that
22

---

Table 7: Running time (s) for one epoch the GNN benchmark. See Sec. E for more implementation details.
ZINC
AQSOL
CIFARIO
MNIST
PATTERN
CLUSTER
Megraph 5)
25.69
20.22 1.67
336.63 51.74
307.23 38.60
101.52 9.21
69.65
Megraph (h 1) 2.41
6.52
Table 8: Running time (s) for one epoch on the OGBG datasets. See Sec. E for more implementation details.
molhiv
molbace
molbbbp
molclintox
molsider
Megraph (h 5)
393.42
14.70 1.43
20.36
14.03 1.26
14.12
Megraph (h = 1)
22.50
1.58
1.41
moltox21
moltoxcast
molesol
molfreesoly
mollipo
Megraph (h = 5)
70.15
78.77
11.68 0.76
6.24
44.77
Megraph 1)
5.27
8.17
0.41
2.77
(a)) = and o (3) after training. In that case, Xÿ¹ Xj, which means Xj is not changed over steps 2 and 3 of the Mee layer. Therefore, X = GN (ntra (G x;-)), this is equivalent to a simple GNN layer that X = GN X as Xi is the features of the original graph and GNintrr is GNN layer. Therefore. MeGraph degenerates standard message-passe paaaggggg GNNs in this case.
E Implementation and Training Details
We use PyTorch [45] and Deep Graph Library (DGL) [54] to implement our method.
We implement S- S-EdgePool using DGL, extending from the original implementation of EdgePool in the Pytorch Geometric library (PYG) [19]. We did Constant optimization over the implementation to speed up the training and inference of the pooling. We further use Taichi- LLng [29] to speed up the dynamic node clustering process of S-EdgePool. The practical running time of MeGraph model with height h after optimization is about 2h times the h baseline. This is still slower than the theoretical computational complexity due to the constant in the implementation and the difficulty of paralleling the sequential visitation of edges (according their scores) in the EdgePool and S-EdgePool. This process could be further speed up by implementing the operations with the CUDA library. We provide the practical running time for h > and h 1 in GNN benchmark and OGB-G datasets in Tables and 8. The speed is slower than the theoretical one partially due to the pooling ratio of edges being larger than the nodes, making the number of edges decrease slowly over the hierarchy. To further speed up, we could use the variants of MeGraph introduced in App. C.5 by skipping some computation modules.
We run all our experiments on V100 GPUs and M40 GPUs. For training the neural networks, we use Adam [33] the optimizer. We report the syper-parameter: of the Megraph in Table 9.
For models using GFuN layer as the core GN block, we find benefits from using layer norms [4]. However, for models using GCN layer as the core GN block, we find it performs best when using batch norms [31].
F Additional Experiment Results
F1
Experimental Protocol
We evaluate MeGraph on public baselines, we use the following experimental protocols. We first report the public baseline results and our reproduced standard GCN's results. We then replace GCN layers with GFuN layers (which is equivalent to MeGraph (h 1)) to serve another baseline. We tune the hyper-parameters (such as learning rate, dropout rate and the readout global pooling method, etc.) of MeGraph (h = 1) and choose the best configurations. We then run other diversely configured MeGraph candidates by tuning
graph benchmarks. To fairly compare MeGraph with the
23

---

Table 9: Hyper-paramete parameters of the standard version of MeGraph for each dataset. It is worth noting that the total number of GNN layers is equals to one plus the number of Mee layers as n +
Graph Theory Benchmark
Synthetic Datasets
LRGB Benchmark
GNN Benchmark
TU Datasets
Hyper-paramene parameters
Benchmark
Repeated Runs
10
5
4
4
for each fold
200 (100 for MNIST, CIFRA10)
100 (200 for ENZYMES)
200 for BA*
300
Epochs per run
200
100
500 for Tree*
(200 for MCC)
0.002
Learning rate
0.002
0.001
0.001
0.001
0.002
(0.005 for MCC)
Weight decay
0.0005
0.0005
0
0.0005
0.0005
Node hidden dim
64
128
160
144
300
128
Edge hidden dim (for GFuN)
64
128
160
144
300
128
Num Mee
3
2
layers n
Height h
9
5
or 5
Batch size
32
32
128
128
Input embedding
False
True
True
True
True
True
Mean
Mean
Mean Max
Global pooling
Mean
Max
Mean
Mean
Max Sum
Sum
Dataset split
Original
Original split
Original split
10-fold cross
8:1:1
8:1:1
(train:val:tett)
split
validation
other ppeer-parmmttrs that only matters for / > 1, and these MeGraph hyper-panne parammaraesrrss Detailed configurations are put in Table 9 in App. E.
are referred to as the
F.2
Visualization
We plotted the graph hierarchies discovered by MeGraph in the shortest path tasks of Graph Theory Benchmark. Figure 5, the S-EdgePool with 7. 0.3, T, 4 well preserves the structure of the graph after pooling, while the S-FdgePool with 7, 0.3 (no cluster size limit) sometimes pooled too many nodes together, breaking the graph structure. The former S-FdgePool leads to better performance as indicated in Table 1. We also plot the hierarchy for SBM-generated graphs in Figure indicating that EdgePool can handle graphs that naturally contains clusters of different size.
F33 Other Real-Wrold Datasets
TÜ dataset consists of over 120 datasets of varying sizes from wide range of applications. We choose 10 datasets, of which are molecule datasets (MUTAG, NCII, PROTEINS, D&D and ENZYMES) and the other are social networks (IMDB-B, IMDB-M, REDDIT-BINARY REDDIT- MULTI-5K and REDDIT-MULTI-I2K; They are all graph classification tasks. For more details of each dataset, please refer the original work [42].
Our Megraph uses the same network structure and pprammprrseeters for the same type of dataset. As shown in Table 10, our Megraph achieves about 1% absolute gain than the h Baselines.
E4 GFuN
We show our GFuN results real-world datasets compared to our reproduced GCN in Table 11, 12 and 13. Both GCN and GFuN have the same layer norm for GFuN as stated in Appendix E.
except the batch norm for GCN and

---

Figure 5: The visualization of the resulting graph hierarchy of MeGraph. Each row is graph hierarchy, and the nodes with the same color in the same graph in the same cluster and pooled into single node in the next hicrarchy. The 1st, 3rd hierarchies use S- Poog with n. 0.3, T. and the 2nd and 4th hicrarchies S-EdgePool with n) = 0.3. The graph in the 1st and 2nd hierarchies is generated by the 'lobster' method, the graph in the 3rd and 4th hierarchies is generated by the 'geo" method. The task is to compute the length of the shortest path between two nodes.
Figure 6: The graph hierarchy visualization, using S-FdgePool with n) 0.3, T. = 4 (left two figures) and Louvain pooling (right two figures) the same SBM generated graph. The task is the shortest path.
E.5 Synthetic Datasets
Figures 7 and show the influence of the height h and the number of layers n for MeGraph model on the BAShape and BACommunity datasets. The trends are similar while less significant casier datasets BAShape and BACommunity.
F.6 Varying GN block
We vary the aggregation function of the GN block as attention (w/ ATT) and gated function (w/ GATE). We observe similar results in Sec. 4.2 and 4.3, verifying the robustness of MeGraph over different GN blocks. Results are shown in Tables 16, 17 and 18.
25

---

Table 10: Results on Tu Dataset. means the results taken from [11] ( The result of GCN on ENZYMES 100 epoch).
Model
MUTAG f
NCI1
PROTEINS 1
D&D1
ENZYMES t
Average
GCN!
87.20 #5.11
83.65
75.65 #3.24
79.12 #3.07
66.50 #6.91*
78.42
GIN
89.40 +5.00
82.70 +1.70
76.20 #2.80
GCN
92.46 16.56
82.55
20.99
77.82 4-4.52
80.56
1
74.17
25.39
81.51
MeGraph (h=l)
93.01 +6.83
82.53
+1.99
81.32 44.08
81.32
13.17
74.83
43:20
82.60
MeGraph
93.07
83.99
81.41
81.24
#2.39
75.17
82.98
MeGraphpest
94.12 4.500
84.40 1:.11
81.68
1:3.4
82.00
2:288
75.17
4:4.86
83.47
Model
IMDB-B 1
IMDB-M f
RE-B 1
RE-MSK 1
RE-MI2K 1
Average
GCN
76.00 43.44
50.33
+1.89
91.15
+1.63
56.47
#1.54
48.71
20.88
64.53
MeGraph (h=1)
68.60 43.53
51.33
+2.23
93.10 11.16
57.47
12.31
51.56
+1.06
64.41
MeGraph
72.40 2:880
51.27
22.71
93.75
+1.25
57.69
+2.22
52.03
20.86
65.43
MeGraphnest
74.30 2.997
52.00
1:2.49
93.75
1.25
58.45
1.2.2
52.13 11.01
66.13
Table 11: Comparison between GCN and GFuN on GNN benchmark.
Model
ZINC 1
AQSOL J
MNIST
CIFARIO f
PATTERN
CLUSTER
GCN
0.426 +0.015
1.397 40.029
90.140
=0.140
51.050 +0.300
84.672
=0.054
47.541 #0.940
GFuN
0.364 10.003
1.386 20.024
95.560
=0.19
61.060 +0.500
84.845
=0 0.0021
58. 58.178 20.079
MeGraph (h=1)
0.323 +0.002
1.075
#0.007
97.570
=0.168
69.890
20.200
84.845
=0.021
58. 188177 #0.079
MeGraph
0,260 +0.005
1.002 +0.021
97.860
=0.008
69.925
+0.631
86.507
=0.067
68. 68.603 #0.101
Table 12: Comparison between GCN and GFuN on OGB-G.
Model
molhiv f
molbace
molbbbp f
molclintox f
molsider 1
GCN
75.40 11.29
76.01 #3.31
67.35
:0.96
89.62 22.27
58.08 20.78
GFuN
78.54 41.14
71.77 #2.15
67.56 #1.11
89.77 #3.48
58.28 #0.51
MeGraph (h=1) MeGraph
78.54 11.14
71.77
#2.15
67.56
#1.11
89.77
1:3488
58.28
10.51
77.20 40.88
78.52
#2.51
69.57
#2.33
92.04
#2.19
59.01
#1.45
Model
moltox21 f
moltoxcast f
molesol
molfreesoly |
mollipo 4
GCN
75.11 +0.41
64.13 #0.52
1.141
+0.02
2.407
=0.15
0.788 =0.01
GFuN
75.89 40.45
64.49 +0.46
1.079 +0.02
2.017
=0.08
0.768 =0.00
MeGraph (/=1)
75.89 40.45
64,49
+0.46
1.079
+0.02
2.017
0.008
0.768 #:0.00
MeGraph
78.11 #0.47
67.67
+0.3
0.886
+0.02
1.876
00.05
0.726
=:0.0
Table 13: Comparison between GCN and GFuN on Tu Dataset.
Model
MUTAG
NCII
PROTEINS t
D&D f
ENZYMES f
Average
GCN
92.46 +6.55
82.55 +0.99
77.82 +1.52
80.56 +2.40
74.17 +5.39
81.51
GFuN
93.01 17.96
82.80 1.30
80.60
13.83
82.43 4:2.00
73.00 15.31
82.37
Model
IMDB-B 1
IMDB-M f
RE-B f
RE-M5K 1
RE-M12K 1
Average
GCN GFuN
76.00 43.44
50.33 +1.89
91.15 #1.63
56.47 +1.54
48.71 20.88
64.53
68.90 13.42
51.27 133.2
92.25 11.12
57.53 11.31
51.54 11.19
64.30
26

---

TreeCycle
TreeGrid
1.00
1.00
0.98
Accuracy
0.08
0.94
0.84
0.92
neightt
0.90
10
Num Layer
Num Layer
Figure 7: Node Classification accuracy MeGraph model on TreeCycle (left) TreeGrid (right) datasets,
varying the height and the number of Mee layers n.. A clear gap can be observed between heights 1, 2 and 2 3. The concrete number of accuracy can be found in Table 14.
BAShape
BACommunity
1.000
1.00
0.996
0.99
Accuracy
Accuracy
0.98
haiight-3
heighti
helgte
0.980
0.95
2
3
4
10
10
Num Layer
Num Layer
Figure 8: Node Classification accuracy for MeGraph model BAShape (left) and BACommunity (right) datascts, varying the height h and the number Mee layers n. A clear gap can be observed between heights and
The concrete number of accuracy can be found in Table 15.
F.7 Graph Theory Dataset
We provide list of tables (from Table 19 30) showing the individual results of Table for each possible graph generation method. Each table contains a list of variants of models and tasks. Some graph generation methods and task combinations trivial filter them out.
27

---

Table 14: Node Classification accuracy for MeGraph model on TreeCycle (above) and TreeGrid (helow).
height
3
5
layer
61.48 26.04
76.59
1:441
91.48
12.70
98.52
11.69
97.95
1:232
98.52
1.35
67.27 #6.91
81.59
#4.03
97.39
#1.25
98.98
+.091
98.75
#1.29
98.86
=1.14
74.43 13.60
90.80
42.61
98.64
11.11
99.09
11.11
98.75
11.56
99.09
=0.85
4
79.55 14.34
93.41
12.82
99.20
10.73
99.20
10.89
99.66
10.73
99.20
82.73 #4.06
93.41
#1.89
99.43
#1.05
99.20
+1.35
99.32
#1.16
99.32 =0.56
6
83.18 23.51
94.09
4:200
99.43
10.76
99.09
4:085
99.20 11.69
99.20) =0.89
7
84.43 13.74
94.43
::224
99.89 10.34
99.20 11.02
99.20 10.89
99 99.66
84.20 #3.82
94.20
#2.00
98.98
#1.19
99.32 +0.73
99.66
#0.52
99,20 =0.73
9
84.43 #3.87
94.20
:2206
99.77
10.45
99.20
11.02
98.98
11.07
99.32 00.75
10
84.77
13.98
94.43
12.18
99.32
10.75
98.86
11.14
99.09
11.67
99.66 0.52
height
3
5
layer
79.11 #3.07
91.13
#2.01
96.85 +1.11
97.18
+1.31
97.10
+1.45
97.42 =1.31
2
89.68 #1.76
93.55
+1.33
98.31 #0.76
97.82 +1.14
97.42
#1.21
97.98
90.81 11.36
96.13
1.44
97.66
11.22
98.23
10.94
98.87
10.82
98.39 00.6
4
91.53 #1.01
96.69
+1.05
98.06 +1.03
98.55 +1.01
98.63
#1.08
97.98 =1.15
5
93.95 #1.58
96.13
#1.76
98.47 #1.17
98.47 #0.92
98.31
#0.81
97.90
94.35 11.25
96.69 11.46
98.06 11.03
98.31 11.05
98.15
11.20
98.39 1.20
7
94.76 #1.10
97.02 #1.41
98.47 #0.84
98.47 #1.05
98.71
#0.71
98.87 =0.90
8
95.08
97.02
98.55 11.24
98.87
98.47
10.92
98.71
94.68 11.00
96.94 11.19
98.47 10.43
98.15 11.20
98.15 10.89
98.39 1.08
10
94.84 #1.21
96.77 #1.20
98.47 #0.92
97.98 +1.50
98.15 #1.02
98.23 1.19
Table 15: Node Classification accuracy for MeGraph model on BAShape (above) and BACommunity (below).
height
3
5
layer
98.71 11.00
99.14
1.14
99.86
1.0.43
99.43
10.70
99.43
1.0.55
99.57
00.9
98.71 =1.00
99.29
+0.96
99.57
10.91
99.71
+0.57
99.57
10.91
99.57
=0.91
99.00 20.91
99.43
10.96
99.86
1.0.43
99.86
10.43
99.86
1.0.3
99,86 0..33
4
99.00 10.91
99.71
10.37
99.
10.43
10.43 99.86
99,43
10.95
99.71
0.57
99.00 20.91
99.86
+0.43
99.86 +0.43
99.86
+0.43
99.86
40.43
99,43 =0.95
6
99.00 10.91
99,86
10.43
99.86 10.43
99.86 10.43
99.86
1..43
99,86 0.43
7
99.00 10.91
99.86
10.43
99.86 10.43
99.86 10.43
99.86
10.43
99 99,86 00.4
99.00 =0.91
99.86
+0.43
99.86
+0.43
99.86
+0.43
99.71
10.57
99.57 =0.65
9
99.00 10.91
99,86
10.43
99.57
10.91
99.57
10.91
99.57
1.0.1
99.57 0.91
10
99.00 10.91
99.71
10.37
99.57
10.91
99.71
10.57
99.86
10.43
99. 99.43 0.95
height
3
5
layer
94.93 +1.30
97.00
+1.80
96.93
+1.60
97.00
+1.88
97.21
#1.70
96.86 11.67
97.93
98.36
98.79
1:046
98.79
98.57
1:055
98.50
98.07 40.91
98.64
10.87
98.86
1.0.1
98.86
10.80
98.50
10.98
98.93
0.80
4
98.21 20.97
98.86
+0.65
98.86 +0.80
98.79
+0.64
99.00 +0.73
99.07 =0.64
98.50 20.87
98.86
99.07
99.21
99.14 10.70
99,00
98.71 20.83
10.87 98.64
99.07 10.64
99.14 1.077
99.07 10.85
99,14 00.70
7
98.29 20.91
98.86
40.65
99.07 +0.36
98.79 40.56
98.79 +0.72
98.86 =0.57
8
98.43 20.77
99.00
99. 14 10.53
98.93
99.14 10.29
99.14
98.79 40.79
99.07
10.56
99.21 10.50
99.00 10.73
99.29 10.45
99,36 0.50
10
98.86 20.73
98.93 40.80
99.21 +0.87
99. 14 40070
99.00 20.73
99.29 20.64
28

---

Table 16: Comparison results of MeGraph with ATT and GATE on Graph Theory Benchmark.
Category
Model
SPeadd
MCC
Diameter
SPas
ECC
h
2,990 #3.411
3.346
#3.228
44,41
#336.3
16,39 #13.37
29.04
=27.00
MeGraph W. ATT
5
0.594
#0.903
1.706
+1.400
3.256
#2.956
1.018 #1.071
14.80
#:7.00
I/ = 0.3, 76
0.749 +1:131
1.128
+0.794
4.430
441.20
0.640
+0.833
5.649
#41400
4.144 14.191
0.908
10.5034
6.343
17.152
13.94 112.78
19.73
1:9.47
MeGraph W. GATE
5
0,809
0.660
1:0.001
2.506
1:2 839
0.669
7.508
17.508
0.3, 7o
0.602
#00622
0.599 +0.520
0,544
4:0.40
0.342 +0.193
0.859
20.712
Table 17: Comparison results of MeGraph with ATT and GATE on GNN Benchmark.
ZINC
AQSOL
CIFARTO
MNIST
PATTERN
CLUSTER
MeGraph w. ATT (A 1)
0,4258 #0.0054
1.1421 #0.0270
69.890 #0.200
97.570 10.
78.232
50.527
59,497
20.207
MeGraph ATT [h = 5)
0.3637 20.01dd
1,0767 #0.0166
69.925
#0.031
97.860
#0.008
83.798
86.86
68.930
#68.76
HeGraph w. GATE [h=
0,3336 #0,0066
1.0766 #1.050
64.200
#0.086
96.812
200.20
85.391
20.029
59.321
#0.20 200
NeGraph GATE (h-
0.2897 20.0291
1.0240 +0.0008
64.935
#0.520
97.290 +0.140
86.611
=0.041
67.122
#3.323
Table 18: Comparison results of MeGraph with ATT and GATE on OGB-G.
Model
molhiv f
molbace
molbbbp f
molclintox t
molsider 1
MeGraph w. ATT (h 1)
77.33 #0.78
74.83
#4.87
64.74 #1.14
86.34 #1.04
58.12
=0.53
MeGraph w. ATT (h- 5)
77.15 +1.37
76.13
#3.85
68.68 #2.07
87.17
20.76
58.03
=1.58
MeGraph w. GATE
76.35 10.70
76.36
#1.35
65.97
#1.98
87.12
20.74
58.11
1122
MeGraph W. GATE (h- = 5)
78.14 20.91
78.90 #1.29
66.53 #0.74
89.02 22.56
59.58 11.88
Model
moltox21
moltoxcast f
molesol
molfreesolv 4
mollipo
MeGraph w. ATT (h- = 1)
75.88 20.64
64.65
#0.39
1.091 +0.030
2.318
=0.089
0.790 +0.012
MeGraph w. ATT (h- 5)
76.71 #0.98
66.98
+0.70
1.007
400617
2.065
15.151
0.736 +.0023
MeGraph GATE (h- 1)
75.30
40.43
64.34
#0.02
1.064
40.015
2.191
#0.008
0.766 +:0008
McGraph W. GATE
5)
76.91 20.25
66.78 10.13
1.003 =0.086
2.048
10.199
0.700 +0.014
Table 19: Graph Theory Benchmark results on Grid graphs, results are obtained using our codebase.
Category Model
SP
MCC
Diameter
SP
ECC
Baselines
n=1
6,60 #0.541
1.50 +0.050
22.49 +1.36
26.74 #0.347
20.99
+0.282
(/=l)
n=5
4.18 10.737
1.29 10.124
5.04
11.26
15.54
10.155
20.32
10.126
n=10
3.70 #0.422
1.33 10.100
0.737
40.136
7.24
40.243
20.32
40.422
McGraph(h=S)
n=1
1.19 #0.486
1.24 10.164
6.78 #1.95
5.34 +0.265
18.00 +0.910
EdgePool(7,=2)
n=5
0.738 10.322
1.11 10.043
0.616
10.310
0.617
10.0099
13.3 =3.31
T,=3
0.361 #0.182
1.24 #0.113
0.382
#0.120
0.442
40. 130
0.918
#0.220
MeGraph
1,=0.3
4.77 12.50
1.33 10.161
0.349
10.074
5,40 10.954
3.59 10.354
S- S-FdgePool
=00.3, T==4
0.745 #0.316
1.35 10.168
0.385
10.180
0.552
11.113
0.622 10.100
Variants
m,50,5 7,24
1.61 #:0.994
1.28
10.138
0.458
+00220
1.71 4:0.55
1.48 #:0.283
(h=5, n=
0,=033, T-=4 (X-Pool)
1.03 10.385
1.50
14.142
0.626
10.216
1.70
10. 185
3.44 100991
n,0033 T (w/o pw)
0.616 +0.194
1.66
+0 +0.083
0.361
+0.147
0.678
13.139
1.70 4004885
Graph-UNets
0.969 10.643
2.18
#0.381
0.111 #0.091
0.773 40.086
0.548 40.181
Table 20: Graph Theory Benchmark results on Tree graphs. All results are obtained using our codebase.
Category
Model
SP SPoed
MCC
Diameter
SP..
ECC
Basclines
w=1
5,21 :0: 200
1.28
20.050
3.77 11:22
17.16 =0. 168
24.63
20.127
(fx1))
5=
3.34
10.375
0.40S
10.080
0.504
10.109
7.66
10.325
18.11 11.85
n=10
3.
20.252
0.338
20.046
0.100
#0.060
2.28
+0. 209
14.93
=0.800
McGraph(h=5)
n=1
1.62
#0.314
0.846
=0.071
0.725 #0.249
6.99
#0.010
12.27
=0.843
EdgePook(.=2)
n=
0.83 1.0.60000 L.0.677
0.490
100.
0.084 10.000
1.27
140.442
2.87
.10.420
r.=3
0.599 20,200
0.483
20.081
0.075
20.012
0.497
20.121
0.429
10.105
McGraph
=0:33
0.868 #0.230
0.413
=0.054
0.142 #0.047
0.789
=0.092
0.534
=00074
S-EdgePool Variants
V. =030.3 n.m4
0.615 10.209
0.418
10.024
0.081 10.017
0.440
100106
0.436
L.0.997
Ge -..5. 7
1.06 10.3327
0.424
10.042
0,214 10.018
1.20 1:0.128
2.03
110. 100507
(l==5, n=5)
V. =0.33 7.24 (X-Pool)
0.666 10.118
0.596
::0000 067
0.182
10.05
1.22
1: 281
1.11 ::0 122
=0333, 7, (w/ pw)
0.771 10.141
050 0.455
0.124
10.002
0.700
10. 100
1.07
Graph- UNets
A=5,n=000 0033 m.
0.873 10.247
0.667
11.00000 043
0.804 10.284
0.606 120.23
1.00 110 201
29

---

Table 21: Graph Theory Benchmark results on Ladder graphs, all results are obtained using our codebase.
Category
Model
SPood
MCC
Diameter
SP..
ECC
Baselines
w=l
5.06 +0.330
1.73 =0.
1.17 20.149
13,20 +0. 126
20. 10 #0.583
(/=l))
n=5
0.692 10. 204
0.734 10.106
1.39
20.098
5.02 20.876
19.81
20.000
x=10
0.257 +0.078
0.691
#0.119
1.55
#0.069
1.60
+0.194
20.40
#0.995
McGraph(h==)
n=1
0.662 10.165
0.866
#0.071
1.57
#0.992
2.18
40.181
6.61
#1.32
EdgePool(r:=2)
n=5
0.251 10. 108
0.753
1:0091
0.175
1: 180
0.321
20.008
1.18
::0
n.=3
0.296 10.070
0.754
10.086
0.226
10 069
0,228
10.021
0.285
1.0009
McGraph
0,507 20.204
0.768
#:0050
0.156
=:0
0,969
148
0.787
1:0.009
S S-EdgePool
W==0.3 0.3, m,=4
0.297 10. 113
0.712
1:0009
0.095
1:0 048
0.180
10:026
0.225
1:0044
Variants
0. n==4
0.375 #0.190 196
0.656
#0.064
0.058
=00 018
0.612
10.191
0.464
#0.121
(1=5, n=5)
0,=033 n,=4 (X-Pool)
0.442 #0.
0.742 :0.047
0.158
074
0.710 #0:076
0.765
+00089
n=003, 7-44 (w/o pw)
0.245
0.682
0.106
0.271
0.618
Graph-UNets
Am5,m=0..g. =
10.11
0.797 10.138
008
0.287 10.020
0.230
10.054
Table 22: Graph Theory Benchmark results Line graphs, all results obtained using our codebase.
Category
Model
SP sndd
MCC
Diameter
SP..
ECC
Baselines
x=1
30.37 #1.41
0.458
#0.035
21.49 #8.84
68.99
20.247
75.46
(I==)
n=5
10.55 42.40
0.019
9.97
46.39
78.49
n=10
3.29 #0.813
0.012
#0.003
10.18 #10.58
35.07
77.23
#3.42
MeGraph(h=5)
==1
1.45 +0.598
0.056 #0.014
7.62 #4.43
10.13 #2.38
45.19
EdgePPol(r.=2))
w=5
0.536
0.016 20.007
0.611
1.06 20:34)
14,12 13.82
Tz=3
0.349 10. 206
0.013 10.003
0.724 479
0.339 10.102
1.15
287
McGraph
7.
3.65
0.017
1.75
13.99
7.45
S-FdgePool
n,=0.3, n,
0.283 20.072
0.019
0.584
0.515
20:064
1.27 11:06
Variants
n= 0.. T==4
1.81 #0.121
0.022 #0.008
0.711 #0.213
2.64 +0.047
3.77
=00 768
(h=5, n=5)
n.-03 7,=4 (X-Pool)
1.06 #0.510
0.101
#0.016
0.767
=00.22
2.29 #0.472
3.89 +1.02
M,UU.3 n2=4 (wfo pw)
0.377 10.106
0.022 +00007
1.19 11.17
1.12 20.115
3.34
::0.904
Graph-UNcts
h=5.m=9.9 3
0.426 228
0.062 #0.008
2.89
0.767 10.120
4.78 #1.94
Table 23: Graph Theory Benchmark results on Caterpillar graphs, all results are obtained using our codebase.
Calegory
Model
SPood
MCC
Diameter
SP..
ECC
Baselines
n=1
24.24 11.57
1.25
10.082
28.62 12.55
19.08 10.208
35.32 10.462
(h=1)
n=5
8.32 #2.10
0.561
20.070
4.59
#0.346
9.62
#0.357
37.01 #1.48
n=10
6.40 40.602
0.630
#0.127
5.06 40.409
4.06 #002977
37.87
#:3.2
MeGraph(A=5)
n=1
5.04 11.00
0.685
10.077
6.08
11.40
5.40 L.0844
28.52
12.16
EdgePool(1.=2)
n=5
3.44 +1.13
0.533
#0.064
2.00 +1
0.921 10.149
5.20
=1.57
r.=3
2.47 10.529
0.607
1:00881
0.591
0.574 1.0.033
1.21
1:0. 148
McGraph
=0=03
3.61 +1.36
0.582
=0.052
0.578
=0.231
1.69 =0.672
1.95
+:0.322
S SdEggeoool
m.=0.3. n.
1.59 10.444
0.535
1.0091
0.317
100.00
0.474 10.170
1.32
1.0.772
Variants
=0=55, n.=4
2.00 40.048
0.514
=0.040
1.10 20.268
0.986
10.130
2.11
2:0706
(1=5, n=
=.333, n.=4 Pool)
1.39 10.478
0.602
110
0.736
1:0.30
1.78 1:0.25
3.36
1.0.873
=0.33, n.=4 (w/o pw)
1.82 40.627
0.628
+0.093
0.604
=0.0067
0.797
+0 200
2.25
+00.30
Graph-UNets
1=5,,==0,y=003,7--
1.57 40.670
0.679
20.008
3.18 40.583
0.976 20.220
3.83 =1.06
30

---

Table 24: Graph Theory Benchmark results on Lobster graphs, all results are obtained using our codebase.
Category
Model
SPasdd
MCC
Diameter
SP
ECC
Baselines
w=l
23.92 #0.310
1.06 =0 100
11.93 +1.52
38.44 #0.005
40.46
+0.350
(/=1)
n=5
10.89 #1.47
0,544 =0.007
3.66
#0.424
20.12 10.105
28.81
#1.14
==10
7.35 12.50
0.631
10.067
2.59
10.517
10.52
10.610
28.47
1.165
MeGraph(It=5
w=l
6.00 11.82
0.785
#0.062
4.35 #1.51
13.75 #0.075
30.49
#2.18
EdgePool(7,
n=5
1.93 #0.861
0.543
#0.073
1.07 #0.114
2.05 +0.388
11.39
#3.43
n==3
2,02 10.791
0.447
10.123
0.705
10. 133
1.66
10.270
2.23
1.0.378
MeGraph
1=
6.01 11.52
0.521
#0.028
0.707
=0 202
3.04
+0.250
2.70
2:02112
S- S-EdgePool
m= n,=4
1.90 10.449
0.489
1:0.069
0.671
1: 185
1.30
2:0. 106
2.62
1:0 240840
Variants
0= n==4
3.27 #0.716
0.451
#0.000
0,941
=0 524
2.82 +0.808
4.04
=: 527
(hm5, mm
0.mU. n, (X-Pool)
2.67 1.04866
0.494
10.109
10.194
10.343
4.16
1.. 886
4,003, n-=4 (w/o pw)
1.85
0.473
0.892
1.77
4.33
Graph-UNets
h= =0.
4.85 +1.48
0.782 #0.026
#0.361
2.96 +0.448
4,25 =0 544
Table 25: Graph Theory Benchmark results Cycle graphs, all results obtained using codebase.
Category
Model
SPaddd
MCC
Diameter
SP
ECC
Baselines
==1
18.75 #0.066
0.534 #0.022
22.35
149
24.07
#0.009
21.47 #0.060
(I=l)
n=5
3.39 40.304
0.027 20.001
25.11
325
12.44
=1 .5
21.81 10.102
n=10
0.352 #0.060
0.011
26.54
8.65 #1.02
24.09
MeGraph(h=5)
am1
0.594 10. 212
0.074
10.029
9.11 11.88
4.07 10.364
21.53 10.070
ErgePool(r=22)
n=5
0.060 20.033
0.014
20.003
13.44 16.40
0.103 20:016
24.05 #0.904
r==3
0.066 +0.086
0.015
#0.006
0,241
=:0 049
0.090 #0.087
0.342 #0.188
MeGraph
q.m0.3
2.45 10.873
0.015
10.001
0.709
226
10.261
0.488 1..267
S S-FdgePool
1=0.33 n==4
0.060 20.030
0.019 20.003
0.312
236
0.226
2:0000
0.562 20.200
Variants
n.005. n,
0,451
0.014
0.252
1.05
1.0524
4.30
(1=5, n=5)
n=0.3, T-=1 (X-Pool)
0.494
0.096
0.468
+00.22 220
1.08 +0.130
0.860 #0.292
n.m033 n.=4 (wlo pw)
0.159
0.017 1.0008
1.23 1.0928
0.461 1:0.188
8.26 1:3.0
Graph-UNets
km5, 3.3
0.144 10.073
0.035 10.010
3.21 10.893
0.439
5.91 11:31
Table 26: Graph Theory Benchmark results on Pseudotree graphs. all results are obtained using our codebase.
Category
Model
SP eodd
MCC
Diameter
SP..
ECC
w=1
1.93
1,71
2.78 10.098
6.27 10.004
4,23 10.004
Baselines
(h=1)
n=5
0.061 #0.024
0.942
20.094
1.74 #0.209
1.54 +0.006
4.15 =0.088
==10
0.037 #0.022
0.775
20.004
1.84 20.260
0.126 20.038
4.06 200007
(eGraph(h=3)
w=1
0. 4.40
1.75
1.50 10.494
2.25 100280
3.97 .10
EdgePool(r.
n=5
0.141 10.022
0.999
10.054
1.16 10.069
0.148 10.034
3.12 1.0.00
0.130 #0.0669
0.912
=0.073
0.669
0.115
0.797
McGraph
n.=0.3
0.048 #0.080
0.839
#0.077
0.758
184
0.246
#0.021
0.838 #0.003
S S-EdgePool
n.=0.33 n.=4
0.106 10.054
0.814
100092
0.663
1.0.00 1..006
0.133
10.028
0.845 100100
Variants
0,=055 n2=4
0.071 20.048
1,03
=0. 188
0.583 ::0 065
0.171
=0.038
0.868
+0.004
(1=5,, x=5)
n,30.,, n.=4 (X-Pool)
0.564 11. 155
0.966
1:0.172
0,977
1:0 054
0.611
11.000
1.10 :10.008
n.=03,, n,=4 (w/o pw)
0.080 +0.033
0.971
#0.072
0.956 =0 230
0.276
+0.017
1.13
=:0 821
Graph-UNets
h= =0333
0.467 20.005
1.09 =: 072
1.71 20.395
0.721 20.000
2.25
::0.527
31

---

Table 27: Graph Theory Benchmark results on Geo graphs, results are obtained using our codebase.
Category
Model
SPowe
MCC
Diameter
SP.-
ECC
Basclines
==1
5.79 $0.630
0.424
20.023
11.85 =0 301
12.49 #0 03-035
14.82
20.006
(k=1)
n=5
1.02 #0.772
0.407
#0.040
#0.468
5.10 +0.485
14.33
#0.079
==10
0.304 +0.122
0.404
#0.061
9.41
#0.780
0.803
#0.
14.33
#0.130
MeGraph((=5)
w=1
1.60 #0.580
0.347
20.033
10.17
22:04
4.87
20.777
11.91
20.451
EdgcPool
n=5
0.232 +0.061
0.273 #0.018
2.70
#0.268
0.575
+0. 10.127
6.92
#2.36
T.=3
0.188 10.100
0.288
1.00000
2,04
10.225
0.562
1.0. 186
2,42
10.333
McGraph
1,=0.3
1.38 20.617
0.330 10.025
4,40 11.15
1.37
20.083
5.45
::0 465
S-EdgePool
4,=.33 -
0.230 10.070
0.231 10.034
1.0549
10.057
2.69
100.38
Variants
0=005 r==1
0.374
0.368
#0.043
3.95 #0.319
0.777
=0
(h=5, 5=
n.003. n, (X-Pool)
1.04
0,362
2.32
2.37
5,08
n.0.3. T-=4 (w/ pw)
0.233 #0.046
0.261 #0.033
2.58 #0.617
1.09
40
4.85
=:0 80.800
Graph-UNets
1.49
0.400 =0.020
4.63
2.42
7.36
Table 28: Graph Theory Benchmark results on SBM graphs, all results are obtained using our endehase.
Category
Model
SPoedd
MCC
Diameter
SP.c
ECC
Baselines
n=1
1.14 20.084
3.28 10.135
3.05 10.171
1.43
20.020
3.47 1:0.026
(h=1)
n=5
0.420 20.018
3.14 #0.131
2.77 40.388
0.100
20.050
3.18 4:0009
k=10
0.704 10.284
3.29 10.063
2.70 10.235
0.012 10.000
2.97 1..051
McGraph(h=5)
n=1
0,786 #0.145
2.79 #0.226
2,49
0.547 +0.058
3.35
EdgePool(7.=2) 2)
n=5
0.525
2.88
2.37
0.058
3.01
rz=3
0.783 14.149
2,80 17.
2.16 4:0.4
0.076 1.0.64
1.98 1.0.497
McGraph
0.=0.3
1.16 13.
3.51 #0.312
2.03 #00.29
0.058 #0.027
1.86 #:0.096
S-FdgePool
0==033, n==4
0.926 20.087
2.62 17.179
1.99
+00200
0.062 #0.027
1.57 2:0206
Variants
0.=0.5 T
0.798 #0.255
3.14 #0.234
2.05 +:0.378
0.063 #0.013
1.70 4:0.049
(h=5, n=5)
m,=0.3, T.=4 (X-Pool)
0.935 40.106
2.60
#0.374
2.16
2:0.204
0.056 #0.014
1.87
1:0.113
0,=0.3, T-=4 (w/o pw)
0,788 10.063
2.52 10.100
1.38
101.31
0.484 10.063
2.21
1.0.189
Graph-UNets
A=0,m=0.,,=033,72-
1.51 19.
3.57 #0.509
1.96 2:0.200
1.71 11.
2.77 #:0. 160
Table 29; Graph Theory Benchmark results BA graphs, all results obtained using codebase.
Category
Model
SP sool
MCC
Diameter
SP..
Baselines (f=1)
0.004 10
10.142
0.092 10
0.128 10 00e
5=
0.007
3.65
0.098
0.091
==10
0.01
3.72 20.376
0.122
0.080 =0
MeGraph(I=5)
w=1
0.006 10 004
2:03560
0.101
10 .20
0.084 10 017
n=5
0.003
2.00
0.104
0.052 1.
T,=3
0.007 20. 003
1.77
20.403
0.089 40.008
0.126 +00002
McGraph
7.=0.3
0.013
1.67 #0.333
0.084
+0.000
0.086
S-EdgePool
m0.3. r.
0.011
1.42
0.073
0.163 110.
Variants
n==0.5 +2=4
0.008 20.000
1.71 20.408
0.074
0.166 =: 021
(f=5, n=5)
n=0033 7, (X-Pool)
0.009 #0.003
1.22 #0.242
0.088 +0.021
0.076 #-0.006
n.003 72=4 (w/o pw)
0.009 =0. 303
1.42 +: 209
0.068 +0.017
0.068 +0.017
Graph-UNets
A=5 m4
0.024 009
2.84 20.777
0.091 #0.01
0.1 20 #0.0227
32

---

Table 30: Graph Theory Benchmark results mixed, ER, Caveman and Star graphs, all results obtained using our codebase.
MCC
ECC
Category
Model
ER
Caveman
Star
mix
ER
Baselines
#0.211
#00206
0.015
#0.004
0.144
=0.051
0.316 =0.000
0.346
20.006
(h=1)
n=5
3.29 20:201
3.35 40.206
0.014
20.005
0.078
0.228
0.289 20.00s
n=10
3.51 10.305
3.53 10.375
0.018
00.008
20.000 0.065
0.212
20.000
0.414
10.102
McGraph((k=))
sa.eer
0.018
20.005
20.011
0.320
Fdge
n=5
1.11 19.34
0.723 .0.073
0.017
00.000
0,052
10.017
0.125 10.010
0.345 20.061
T,=3
1.07 10000
0.714
20.030
0.017
10.002
0.072
10.016
0.137
20.013
0.232
20.035
McGraph
00.0.3
0.908
0.627
0.026
0.125
0.128
0.248
S-EdgePool
MN=0.3, ram4
1.10 #0.065
0.709
=0.092
0.019
20.004
0.073
=0.012
0.129 =0.000
0.224 20.053
Variants
0.026
0.219
(l=5, n=5)
W=0.3, 7,44 (X Pool)
1.01 1:0.108
0.838
20.078
0.029
10.007
0.107
1..021
0.119 20.000
0.213 20.027
N.-033 m. (wfo pw)
100000
003
10.0
20.006
Graph Graph-UNets
1,06
0.859
0.041
0.057
0,153
0.34 510.135
33


Reviews:
[{"review_id": "6Xf1B7IcjT", "reviewer": "Reviewer_NF28", "summary": "This paper proposes MeGraph, a GNN architecture that interleaves local and hierarchical structural information in a graph at multiple-scales, to capture long-range interactions (LRI). The authors propose S-EdgePool that generalizes EdgePool by allowing more than two nodes to be clustered in order to achieve a desired pooling ratio. Using graph pooling, they build a \"mega graph\", which includes inter-edges connecting nodes at one height to the corresponding super-nodes at the next height. Furthermore, they propose a message passing scheme based on \"MeeLayers\", which first propagates information locally at each height, then propagates upwards and then backwards in the hierarchy. A complexity analysis is provided. Authors conduct an extremely extensive set of experiments on graph theory benchmarks, 10 standard LRI tasks plus three others proposed in the paper, LRGB, GNN benchmarks and OGB. Results show the superior performance of MeGraph in comparison with GCN, GIN, GAT, GatedGCN, Graph U-Net and a large variety of baselines specific to LRGB. An ablation study demonstrates gains from larger height and number of layers, as well as some other components of the method.", "questions": "Q1. While perturbation-based graph explainability frameworks can be applied with MeGraph, they would not provide immediate insights into how the hierarchy comes into play. Is there any graph explainability frameworks suitable for this task or are there fundamental challenges in deriving explanations for outputs predicted by MeGraph?\nQ2. Was there a particular reason not to include a comparison with HGNet?\nQ3. Does S-EdgePool tend to create groups of nodes with roughly the same size? If so, how would the performance of MeGraph be affected in graphs where clusters of different sizes arise naturally?", "limitations": "Yes, the authors have discussed some obvious limitations in Section 6.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "S1. The paper investigates a fundamental problem: how to capture longe-range interactions in a graph using GNNs without incurring over-smoothing or over-squashing issues. \nS2. The proposed solution is clean, well-justified and introduces some novel components (e.g., S-EdgePool, MeeLayer).\nS3. The proposed solution matches or exceeds the performance of reference methods in a large variety of diverse benchmarks.\nS4. Excellent presentation; writing is very clear despite the sophistication of the method.\nS5. Extremely extensive set of experiments (9 out of 16 pages in the appendix contain additional tables/plots).\nS6. Code and details of the experimental setup allow great reproducibility.", "weaknesses": "W1. There is no discussion regarding the hierarchies discovered by MeGraph for specific datasets/tasks, which could shed some light into the way the method is working.\nW2. HGNet also builds a multi-scale hierarchy via graph pooling and was shown to slightly outperform Graph U-Net, but is not included in the comparisons.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your invaluable reviews. We provide point-by-point responses below.\n>1. [W1] There is no discussion regarding the hierarchies discovered by MeGraph for specific datasets/tasks, which could shed some light into the way the method is working. [Q3] Does S-EdgePool tend to create groups of nodes with roughly the same size? If so, how would the performance of MeGraph be affected in graphs where clusters of different sizes arise naturally?\nThanks for your suggestion, we plotted the graph hierarchies discovered by MeGraph in the shortest path tasks of Graph Theory Benchmark, in Figure 2 of the attached pdf (in Overall Response).\n\nFor the S-EdgePool with $\\eta_v=0.3, \\tau_c=4$ (The 1st, 3rd, and 5th hierarchy), the size of the clusters are roughly the same size (as the cluster size is restricted as at most 4), and the structure of the graph is well preserved after pooling. For the S-EdgePool with $\\eta_v=0.3$ (no cluster size limit), the size of the resulting cluster could vary, depending on the structure of the graph. In dense graphs (e.g. generated by the 'geo' method, 4th hierarchy in Figure 2 of the attached pdf), the size of the resulting cluster could be very large while leaving some node forms a cluster alone. The former S-EdgePool leads to better performance as indicated in Table 1.\n\nMeGraph still performs well when clusters of different sizes arise naturally. We use Stochastic Block Model (SBM) to generate graphs with clusters of different sizes to illustrate.  In Table R2, MeGraph with S-EdgePool still shows comparable or better performance compared to the baselines. Moreover, as shown in Figure 3 of the attached pdf, S-EdgePool preferentially performs clustering in the clusters of the original graph. For reference, we also show the Louvain pooling result in the right part of Figure 3, which can be regarded as a natural clustering in the original graph.\n\n>2. [W2] HGNet also builds a multi-scale hierarchy via graph pooling and was shown to slightly outperform Graph U-Net, but is not included in the comparisons. [Q2] Was there a particular reason not to include a comparison with HGNet?\n\nThanks for your question. We thought HGNet has a similar architecture as Graph U-Net and could have similar issues, and therefore we didn't compare ours with HGNet. As suggested, we have included the comparison with HGNet, and the results are provided in Table R3 in **Overall Response** and Tables R4 and R5 below. It can be seen that MeGraph achieves better or comparable results than both Graph U-Nets and HGNet, where MeGraph achieves the best performance in most tasks (the best one is bolded in the table).\n\n*Table R4*: GNN Benchmark results (Corresponding to Table 3)\n| dataset |        ZINC         |        AQSOL        |       MNIST        |      CIFAR10       |      PATTERN       |      CLUSTER       |\n| :------ | :-----------------: | :-----------------: | :----------------: | :----------------: | :----------------: | :----------------: |\n| MeGraph | **0.2597 ± 0.0053** | **1.0017 ± 0.0210** | **97.860 ± 0.098** | **69.925 ± 0.631** | **86.507 ± 0.067** | **68.603 ± 0.101** |\n| U-Net   |   0.3320 ± 0.0103   |   1.0629 ± 0.0182   |   97.130 ± 0.227   |   68.567 ± 0.339   |   86.257 ± 0.078   |   50.371 ± 0.243   |\n| HGNet   |   0.4743 ± 0.0032   |   1.1192 ± 0.0101   |   90.122 ± 1.012   |   60.122 ± 0.428   |   69.448 ± 0.021   |   35.514 ± 0.046   |\n\n*Table R5*: OGB-G results (Corresponding to Table 4)\n| dataset |      molhiv      |     molbace      |     molbbbp      |    molclintox    |     molsider     |\n| :------ | :--------------: | :--------------: | :--------------: | :--------------: | :--------------: |\n| MeGraph |   77.20 ± 0.88   |   78.52 ± 2.51   |   69.57 ± 2.33   | **92.04 ± 2.19** |   59.01 ± 1.45   |\n| U-Net   | **79.48 ± 1.06** | **81.09 ± 1.66** | **71.10 ± 0.52** |   91.67 ± 1.69   | **59.38 ± 0.63** |\n| HGNet   |   77.96 ± 1.10   |   72.49 ± 0.93   |   70.26 ± 1.79   |   85.90 ± 0.90   |   58.91 ± 0.98   |\n\n| dataset |     moltox21     |    moltoxcast    |      molesol      |    molfreesolv    |      mollipo      |\n| :------ | :--------------: | :--------------: | :---------------: | :---------------: | :---------------: |\n| MeGraph | **78.11 ± 0.47** | **67.67 ± 0.53** | **0.886 ± 0.024** |   1.876 ± 0.058   |   0.726 ± 0.006   |\n| U-Net   |   77.85 ± 0.81   |   66.49 ± 0.45   |   1.002 ± 0.036   |   1.885 ± 0.069   |   0.716 ± 0.014   |\n| HGNet   |   77.85 ± 0.12   |   65.93 ± 0.61   |   0.924 ± 0.020   | **1.870 ± 0.056** | **0.706 ± 0.014** |\n\n>3.[Q1] While perturbation-based graph explainability frameworks can be applied with MeGraph, they would not provide immediate insights into how the hierarchy comes into play. Is there any graph explainability frameworks suitable for this task or are there fundamental challenges in deriving explanations for outputs predicted by MeGraph?\n\nThanks for your question. We think perturbation-based graph explainability frameworks like GNNExplainer [57] could still be used. As explained in Section 3.2 Mega Graph Message Passing, we can regard the Mee layer as performing message passing over the mega graph. Though the mega graph keeps changing during the training stage, it will be fixed during testing time. Therefore, we can treat the mega graph as a standard graph and use GNNExplainer to explain the outputs predicted by MeGraph. The explanation would be a subgraph of the mega graph, containing the hierarchy information.\n"}, {"review_id": "cGR5CXsISX", "reviewer": "Reviewer_Y5z6", "summary": "In summary, the paper proposes a mechanism to learn on graph in a multiscale and hierarchical manner. This is one of the approaches that can address the long-range problem, in which the graph has a large diameter, i.e. the length of maximum shortest paths between all pairs of nodes is long, in graph learning.\n\nGiven the following strengths and weaknesses, I vote this paper in the borderline. There are certainly more works to do.", "questions": "N / A", "limitations": "I have written about other limitations of this work in the \"Weaknesses\" section. \n\nI think the authors should extend the Graph Theory Benchmark further. For example, the graphs should be much larger, it is interesting to see how each method behaves on a very large and very long-range graphs in terms of efficiency and efficacy. In particular, since this work is about multiscale representation of a graph, the benchmark should have Stochastic Block Model (SBM) or some graphs with clustering or hierarchical patterns.\n\nIf the benchmark is sophisticated enough, the authors can submit to the data & benchmark track. Recently, there is a separate track for data & benchmark in main ML conferences.", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I believe this paper asks the right question: Long-range problem in graph learning is certainly important. Existing GNNs based on the conventional message passing have severe limitations with long-range graphs (i.e. graphs with \"long\" maximum shortest paths). The reason is message passing only allows exchanging of information among neighboring nodes, and consequently we would need many layers / iterations of message passing (one can argue that the number of layers needed is proportional to the size of the graph) so that two distant nodes can reach each other. However, it is computationally infeasible to have many layers for large graphs and it will cause the problem of over-smoothing and potentially other problems with gradients and training. \n\nTherefore, we need a method that allows distant nodes can exchange information via a small number of hops. Constructing a hierarchical and multiscale structure is one of the reasonable choices.", "weaknesses": "* Novelty: The long-range problem has attracted increasing attention from the graph learning community. There are similar ideas / works about multiscale and hierarchical structure learning being developed in parallel with this work.\n\nFor example, this work \"Multiresolution equivariant graph variational autoencoder\" https://iopscience.iop.org/article/10.1088/2632-2153/acc0d8/pdf proposed a similar multiscale / multiresolution method, but the construction of the hierarchy is done via a flexible learning-to-cluster algorithm in data-driven manner. The follow-up paper \"Multiresolution Graph Transformers and Wavelet Positional Encoding for Learning Long-Range and Hierarchical Structures\" https://arxiv.org/pdf/2302.08647.pdf (accepted at Journal of Chemical Physics) proposed an extension with Graph Transformers and a new positional encoding motivated from multiresolution analysis and wavelet theory, that can efficiently learn long-range and hierarchical graphs.\n\nFurthermore, a recent ICML 2023 paper \"On the Connection Between MPNN and Graph Transformer\" https://arxiv.org/pdf/2301.11956.pdf suggested that a simple method of adding a virtual node (i.e. a node connecting to all other nodes) can significantly boost the performance of the conventional message passing for the long-range graphs. This work has theoretical analysis that proves the equivalence between adding a virtual node and graph transformer.\n\n* Theoretical analysis: The paper got rejected from ICLR 2023 https://openreview.net/forum?id=Oz0npxjLAsI. One of the main reasons is the lack of theoretical analysis in analyzing the expressive power of their proposal. I suggest the authors to investigate theoretically their proposed model.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your invaluable reviews. We provide point-by-point responses below.\n>1. Novelty: The long-range problem has attracted increasing attention from the graph learning community. There are similar ideas / works about multiscale and hierarchical structure learning being developed in parallel with this work.\n\nThanks for pointing out these related works. Indeed, our work understands graphs beyond multiscale and hierarchical structure learning, and the key idea of our work and that of these works differ.\n* As stated in the abstract, the key idea of our work is to integrate the local and hierarchical structures of a multi-scale graph hierarchy into a single mega graph, and we proposed a MeGraph model that consists of multiple layers **alternating between local and hierarchical information aggregation on the mega graph**.\n* According to [B1], \"The key idea of MGVAE is learning to construct a series of coarsened graphs along with a hierarchy of latent distributions in the encoding process while learning to decode each latent into the corresponding coarsened graph at every resolution level\". MeGraph is different from MGVAE as it explicitly builds a mega graph upon the graph hierarchy and alternates local and hierarchical information aggregation on that, which is not seen in MGVAE. The targets are also different where MGVAE aims to generate graphs and MeGraph aims to capture both local and long-range interactions.\n* MGT [B2] first obtains a graph representation using GPS [42], builds substructures using the same clustering method as in [B1], and then applies Transformers on the substructures. The original graph and the substructures form a hierarchy of 2 layers. This method, based on a graph transformer, is a different way of capturing long-range interactions compared to ours. The WavePE [B2] also contains multiresolution information but is from the perspective of positional encoding.\n* MPNN+VN [B3] mainly focuses on proving the equivalence between adding a virtual node and graph transformer. Adding a virtual (root) node can be regarded as a very special case of our MeGraph architecture when the graph pooling module pools all nodes into a single node.\n\nMoreover, both MGT+WavePE [B2] and MPNN+VN [B3] conducted experiments in the Peptides-func dataset, while their results are inferior compared to ours (MGT+WavePE is 68.17% [B2], GatedGCN+RWSE+VN is 66.85% [B3], where MeGraph is 69.45%).\n\nWe would include the discussions and their experimental results in our revision.\n\n[B1] Hy, T. S., & Kondor, R. (2023). Multiresolution equivariant graph variational autoencoder. Machine Learning: Science and Technology, 4(1), 015031.\n\n[B2] Ngo, N. K., Hy, T. S., & Kondor, R. (2023). Multiresolution graph transformers and wavelet positional encoding for learning long-range and hierarchical structures. The Journal of Chemical Physics, 159(3).\n\n[B3] Cai, C., Hy, T. S., Yu, R., & Wang, Y. (2023). On the connection between mpnn and graph transformer. arXiv preprint arXiv:2301.11956.\n\n>2. Theoretical analysis: The paper got rejected from ICLR 2023. One of the main reasons is the lack of theoretical analysis in analyzing the expressive power of their proposal. I suggest the authors to investigate theoretically their proposed model.\n\nWe had provided supplementary theoretical explanations for the expressive power of MeGraph during that response period, and the reviewer appreciated our previous efforts. The according analysis is also provided in Appendix D.2 in the current submission. This explanation is also empirically supported by the results of using random poolings, which are provided in the Graph Poolings Ablation part of the **Overall Response**.\n\nIn Appendix D.1, we have also rephrased the analysis provided in [43], which shows hierarchical architectures like MeGraph require a much smaller number of aggregation steps ($O(\\log(|V|))$) for capturing long-range interactions than standard message-passing GNNs ($O(|V|)$).\n\n[43] Ladislav Rampášek and Guy Wolf. Hierarchical graph neural nets can capture long-range interactions. In 2021 IEEE 31st International Workshop on Machine Learning for Signal Processing (MLSP), pages 1–6. IEEE, 2021.\n\n>3. I think the authors should extend the Graph Theory Benchmark further. For example, the graphs should be much larger, it is interesting to see how each method behaves on a very large and very long-range graphs in terms of efficiency and efficacy. In particular, since this work is about multiscale representation of a graph, the benchmark should have Stochastic Block Model (SBM) or some graphs with clustering or hierarchical patterns.\n\nThanks for your suggestion. We have created another version of our Graph Theory Benchmark. For each graph generation method, the generated dataset contains 500 graphs, and each graph contains 100 to 200 nodes. We also add a new graph generation method Stochastic Block Model (SBM). The generation details and the results are shown in the **Overall Response**.\n"}, {"review_id": "xREoyaiZRn", "reviewer": "Reviewer_qUTa", "summary": "The authors propose a novel methodology for capturing long-range interactions in graph-based learning models, that is based on mult-scale graph construction and merging. Specifically, following the Select-Reduce-Connect framework [1], the authors introduce a novel pooling method called Edgepool  that enables refinement of the original graph structure in an arbitrary continuum. They then perform graph pooling in order to create multi-scale graph instances of the original graph, and merge the inter-graph and intra-graph connections through the proposed MeGraph framework. \n\nThe authors perform extensive experimentation to over 10 datasets. They, also, show a limited (compared with the number of trainable parameters) ablation study on four synthetic datasets. They, also, propose a rather novel benchmark, called Graph Theory Benchmark (testing properties: graph diameter, single source shortest path, graph eccentricity, maximum connected component), where they evaluate the prediction capabilities of their model. The results suggest a solid performance of MeGraph framework for tasks that require both shallow and deeper architectures.\n\n[1] Daniele Grattarola, Daniele Zambon, Filippo Maria Bianchi, and Cesare Alippi. Understanding pooling in graph neural networks. IEEE \n Transactions on Neural Networks and Learning Systems, 2022.", "questions": "1. Can the authors pose any theoretical motivations on why the combination of SRC framework with the MeGraph framework can contribute to more effectively capture long-range interactions?\n\n", "limitations": "1. As I mentioned, I think that there is a lack of theoretical motivation for the choice of the model's modules. It would be quite helpful to provide any information on positive benefits of the SRC framework,as well as the representations obtained from the intra-graph and inter-graph interactions. \n2. The computational complexity is dependent on the choice of pooling methods, and encoder-decoder methods (as well as the message passing steps). It would be quite interesting to investigate on any potential improvement that would balance the increased parameter space with the training time. \n3. The written text can be further be clarified. The complex architecture of MeGraph requires a clear, and easy-to-follow description, so that the readers can grasp its mechanics.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The proposed framework is fairly novel. It shows some dependencies on previous frameworks (i.e. SRC framework needed for graph pooling).\n2. The idea and methodology of the hierarchical pooling and merging, although it's not new (e.g. DiffPool), its quite interesting and intuitive for the problem of capturing long-range interactions.\n3. The extensive experimentations to a broad set of datasets suggest a strong performance of the MeGraph framework. \n4. There is a newly introduced benchmark, called Graph Theory Benchmark that can be used for various methods of evaluation. \n5. The written text is fairly clearly written. However, it can be improved, mainly due to the fact that it's hard to follow the main contribution section. A more clear summarization of the contributions (methodology, and experimentation) would significantly improve the clarity of the paper.\n6. The problem that MeGraph is approaching is quite important, mainly due to the known incapabilities of various graph neural network architectures to perform on par in deeper settings.", "weaknesses": "1. I am concerned about the computational complexity of the model. It seems that in the average case the combined computational cost of pooling, merging, and message passing is high, with respect to simple graph neural network models. The authors propose some variants to alleviate the high computational complexity, however it becomes more unclear how each one of the choices impact the behavior of the model. It seems (based on Tables 2, 4 ) that either the best performance comes from the computationally heavy variant of MeGraph or that there is no clear impact of the model choices. \n2. The model consists of a high number of trainable parameters, and module choices. Although I value the effort of the authors for an ablation study, I think that a further investigation of the parameters of the modules ( especially with respect to the encoder-decoder choices, and the graph pooling methods) would be quite helpful.\n3. There is no safe conclusion that long-range interactions can be captured because of the multi-scale method that the authors propose rather than the increased parameter space in MeGraph. The lack of any theoretical insight on why the specific choices contribute to capturing long-range interactions hinders convincing the reader that the multi-scale approach is appropriate for LRI.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your invaluable reviews. We provide point-by-point responses below.\n\n>0. The authors propose some variants to alleviate the high computational complexity, however it becomes more unclear how each one of the choices impact the behavior of the model. It seems ...\n\nWe'd like to clarify that, when discussing methods to reduce time complexity in L215, we are referring to the variants described in Appendix C.5, not those in the baseline section (h=1 and n=1). The variants from Appendix C.5 primarily replace certain GN blocks with the Identity function to decrease time complexity. These include U-Shaped, Bridge-Shaped, and Staircase-Shaped structures and we present their running speed on the treecycle dataset in Table R7. To prevent confusion, we'll make necessary revisions.\n\nThe h=1 and n=1 variants serve as baselines (refer to L224-226). Comparing the MeGraph model to its h=1 variant underscores the significance of using hierarchical (multi-scale) structures. When comparing the MeGraph model to its n=1 variant, it demonstrates the value of repeated information exchange throughout the mega graph hierarchy. We selected these two variants as baselines because it allows for fair comparisons by ensuring identical hyper-parameters, as detailed in Appendix F.1.\n\n>1. I am concerned about the computational complexity of the model. It seems that in the average case the combined computational cost of pooling, merging, and message passing is high, with respect to simple graph neural network models.\n\nIn Section 3.4 (L213), we demonstrated the theoretical complexity of the MeGraph framework which is $1/(1−\\eta)$ times that of a standard GNN. Here, $\\eta$ is the ratio of the graph size before and after pooling. Notably, when $\\eta \\le 0.5$, $1/(1−\\eta) \\le 2$, suggesting the overall complexity is at most double that of the GNN when the graph size is halves for each pooling.\n\nHowever, in practice, the pooling method often targets the node ratio, but the edge ratio might be higher. To illustrate, we present the node and edge counts in a graph hierarchy from the synthetic treecycle dataset, using a randomized graph pooling method with a $\\eta_v=0.3$ node pooling ratio:\n\n*Table R6*: Node and edge counts across hierarchies for a sample graph in the treecycle dataset.\n|count|h=1|h=2|h=3|\n|-|-|-|-|\n|intra-nodes|871|261|78|\n|intra-edges|972|964|850|\n|inter-nodes|1132|339|/|\n|inter-edges|1742|522|/|\n\nThe edge count decreases at a slower rate compared to the node count. Furthermore, the overhead of inter-conv becomes nonnegligible when the edge and node counts are similar. We present the running times for edgepool and random-pool for heights 1 to 3 when $n=3$:\n\n*Table R7*: Training time (s) per epoch for various methods with n=3 layers on the treecycle dataset.\n|method|h=1|h=2|h=3|h=3 X-Pool|h=3 bridge|h=3 staircase|\n|-|-|-|-|-|-|-|\n|edgepool|0.026|0.068|0.127|0.078|0.098|0.081|\n|random  |0.026|0.056|0.111|0.064|0.087|0.070|\n\nTo speed up, we can employ the X-Pool variant (refer L167) which approximately doubles the speed, but at a potential performance cost, as shown in the ablation study on cross update functions (L317). As discussed in Appendix C.5, substituting some GN blocks with identity functions can reduce runtime. The running times of two such variants (bridge and staircase) are displayed above, offering noticeable speed improvements. We leave exploring the balance between speed and performance in future studies.\n\n>2.a They show a limited ablation study on four synthetic datasets.\n\nWe'd like to clarify that our ablation study is not limited to four synthetic datasets ([L280] Hierarchy vs. Locality), but also covers the Graph Theory Benchmark (for [L300] Varying S-EdgePool, [L314] Changing cross update function, [L319] Disabling bidirectional pathway) and real-world datasets (for [L310] Varying GN Block).\n\n>2.b ..., I think that a further investigation of the parameters of the modules ( especially with respect to the encoder-decoder choices, and the graph pooling methods) would be quite helpful.\n\nThanks for your suggestions. As clarified above, we have conducted ablation studies on the graph pooling methods. We adjusted the hyper-parameters $\\tau_c$ and $\\eta_v$ for S-EdgePool and displayed MeGraph's performance with various poolings in Table 1. As stated in L309, irrespective of the pooling variant used, MeGraph consistently outperforms h = 1 baselines, suggesting the robustness of MeGraph against different structures of the mega graph.\n\nWe implemented Louvain pooling [B0] and a random pooling that assigns nodes to a random cluster. The ablation study results for these new graph pooling methods are shown in the **Overall Response**.\n\nFor shared components and hyper-parameters in standard GNNs and MeGraph, including encoders and decoders, their choices could influence model performance and the optimal choices are typically task-specific. As detailed in Appendix F.1 (Experimental Protocol), we first optimized the hyper-parameters for GFuN and selected the best configurations for each task. The effects of this tuning are seen in the performance differences between MeGraph(h=1) and GFuN, as shown in Tables 3, 4, 9 and 10-12. We will update Tables 10-12 accordingly.\n\n>3. Can the authors pose any theoretical motivations on why the combination of SRC framework with the MeGraph framework can contribute to more effectively capture long-range interactions?\n\nAs discussed in Appendix D.1 (L714), hierarchical architecture like MeGraph provides a much smaller number of aggregation steps ($O(\\log(|V|))$) for capturing long-range interactions than standard message-passing GNNs ($O(|V|)$).\n\n>4. A more clear summarization of the contributions would significantly improve the clarity of the paper. ... The complex architecture of MeGraph requires a clear, and easy-to-follow description, so that the readers can grasp its mechanics.\n\nThanks for your suggestion. We will revise accordingly to make the text clearer.\n"}]

Author rebuttal:
# Overall Response
We thank all reviewers for the consistently positive feedback and invaluable reviews. We provide point-by-point responses below by commenting on each of your reviews.

We report the following new results as suggested by the reviewers.
* As suggested by Reviewer Y5z6, we created another version of the Graph Theory Benchmark with larger graphs, and also include a new random graph generation method Stochastic Block Model (SBM).
* As suggested by Reviewer qUTa, we performed an ablation study on new graph pooling methods.
* As suggested by Reviewer NF28, we visualized the graph hierarchy discovered by MeGraph in the Graph Theory Benchmark. We compared two versions of S-EdgePool and found that the one that leads to better performance also better preserves the graph structure after pooling, suggesting the potential correlation.

For clarity in the response, we use Lxx to refer to Line xx in our submitted manuscript, e.g. L35 means Line 35.

## Larger Graphs in Graph Theory Benchmark
We created another version of our Graph Theory Benchmark. For each graph generation method, the generated dataset contains 500 graphs and each graph contains 100 to 200 nodes. For clarity in the response, we refer this version to as 'large' and the original version as 'medium', respectively.

We also add a new graph generation method Stochastic Block Model (SBM). We randomly sample the size of each block to be random from (5, 15), and the probability of edge within the block to be random from (0.3, 0.5) and those for other edges to be random from (0.005, 0.01). To make all the tasks well-defined, we filtered out the unconnected graphs during the generation.

The results are shown in Tables R1-R3 below.
* As shown in Table R1, the MeGraph model significantly outperforms the h=1 version and the Graph-UNets. The conclusion still holds (in Table R3) after adding the SBM graph generation method.
* Table R2 shows the results on the SBM-generated graphs only, where the shortest path among nodes is usually short as the nodes in the same block are usually well connected. In such graphs, Graph-UNets failed to identify local paths which standard GNNs (h=1 setting) can identify. This result matches our argument in our Introduction ([L35] hierarchical information propagation cannot take over the role of local information aggregation). In contrast, MeGraph performs comparable to or better than standard GNNs (h=1 setting).

*Table R1*: Graph Theory Benchmark (large version, averaged over different graph generation methods, excluding SBM generation):
|Category|Model|SP<sub>sssd</sub>|MCC|Diameter|SP<sub>ss</sub>|ECC|
|-------|----|----------------|---|-------|-------------|----|
|Megraph|$h=1,n=5$|360.813|34.865|208.490|360.017|237.996|
|Megraph|$h=5,n=5,\eta_v=0.3,\tau_c=4$|26.280|14.619|21.100|16.622|48.626|
|U-Net|$h=5,n=9,\eta_v=0.3,\tau_c=4$|110.998|28.052|43.794|110.998|81.322|


*Table R2*: Graph Theory Benchmark (large version, SBM generation only)
|Category|Model|SP<sub>sssd</sub>|MCC|Diameter|SP<sub>ss</sub>|ECC|
|-------|-----|---------------|-----|-------|-------------|-----|
|Megraph|$h=1,n=5$|0.023|104.048|0.4486|0.173|0.7500|
|Megraph|$h=5,n=5,\eta_v=0.3,\tau_c=4$|0.059|47.816|0.4033|0.078|0.4919|
|U-Net|$h=5,n=9,\eta_v=0.3,\tau_c=4$|1.117|62.839|0.6390|1.722|0.6770|

*Table R3*: Graph Theory Benchmark (large version, averaged over different graph generation methods, including SBM generation)
|Category|Model|SP<sub>sssd</sub>|MCC|Diameter|SP<sub>ss</sub>|ECC|
|-------|-----|-----------------|-------|-------|-------------|-------|
|Megraph|$h=1,n=5$|328.014|39.4772|189.577|324.033|219.746|
|Megraph|$h=5,n=5,\eta_v=0.3,\tau_c=4$|**23.8963**|**16.8321**|**19.2185**|**14.9676**|**44.9234**|
|U-Net|$h=5,n=9,\eta_v=0.3,\tau_c=4$|101.009|30.3711|39.8708|100.070|75.1185|
|HGNet[43]|$h=5,n=9,\eta_v=0.3,\tau_c=4$|413.793|45.188|299.189|420.884|359.354|

## Graph Poolings Ablation
We implemented the Louvain pooling [B0] and a random pooling method that assigns nodes to a random cluster. We conduct an ablation study for these two graph pooling methods on the treecycle and treegrid dataset, the results are illustrated in Figure 1 of the attached pdf.

For the random pooling, the hierarchical information becomes useless, and the MeGraph still achieves accuracy that is similar to the standard GNNs (h=1 variant), which supports our discussion in Appendix D.2 (MeGraph can degenerate to standard GNNs).

For Louvain pooling on the treecycle dataset, performance is marginally improved compared to EdgePool. This might be because the fixed clustering from the Louvain algorithm is better suited for this task compared to EdgePool. Such observations indicate the MeGraph architecture's robustness across various reasonable pooling methods.

[B0] Fast unfolding of communities in large networks, Vincent D Blondel, Jean-Loup Guillaume, Renaud Lambiotte, Renaud Lefebvre, Journal of Statistical Mechanics: Theory and Experiment 2008(10), P10008 (12pp)

## Plot Graph Hierarchy
We plotted the graph hierarchies discovered by MeGraph in the shortest path tasks of Graph Theory Benchmark, in Figures 2 and 3 of the attached pdf. In Figure 2, the S-EdgePool with $\eta_v=0.3, \tau_c=4$ well preserves the structure of the graph after pooling, while the S-EdgePool with $\eta_v=0.3$ (no cluster size limit) sometimes pooled too many nodes together, breaking the graph structure. The former S-EdgePool leads to better performance as indicated in Table 1. We also plot the hierarchy for SBM-generated graphs in Figure 3, indicating that EdgePool can handle graphs that naturally contains clusters of different size.


Meta-review: In graph representation learning, message passing allows exchanging of information among neighboring nodes in order to create node representations. Gathering the information from distant parts of a graph, however, may need many message passing layers. Unfortunately, if many such layers are applied on large graphs, the node embeddings tend to a steady-state convergence (over-smoothing), which, combined with backpropagation over many layers creates difficulties computing accurate gradients.

Therefore, there is a desire for a method that allows distant nodes to exchange information via a small number of layers in the neural network. One such research direction constructs hierarchical multiscale graphs that facilitate the communication between distant nodes in the graph via iterative graph pooling. The basic ideas of iterative graph pooling are well known.

This work proposes a new way to propagate the messages through these multiscale graphs. The reviewers believe this method, while considering a well-understood concept, is a worthy addition to the existing literature on this research direction.
Decision: Accept (poster)