MeGraph: Graph Representation Learning on Connected Multi-scale Graphs
Authors: Honghua Dong
Jiawei Xu
Yu Yang
Rui Zhao
Chun Yuan
Xiu Li
Chris J. Maddison
Lei Han
Venue: Submitted to ICLR 2023 (2023)
Keywords: Hierachical Graph Learning
Multi-scale
Graph Pooling
Graph Neural Networks(GNNs)

Abstract: We present MeGraph, a novel network architecture for graph-structured data. Given any input graph, we create multi-scale graphs using graph pooling. Then, we connect them into a mega graph by bridging inter-graph edges according to the graph pooling results. Instead of universally stacking graph convolutions over the mega graph, we apply general graph convolutions over intra-graph edges, while the convolutions over inter-graph edges follow a bidirectional pathway to deliver the information along the hierarchy for one turn. Graph convolution and graph pooling are two core elementary operations of MeGraph. In our implementation, we adopt the graph full network (GFuN) and propose the stridden edge contraction pooling (S-EdgePool) with adjustable pooling ratio, which are extended from conventional graph convolution and edge contraction pooling. The MeGraph model enables information exchange across multi-scale graphs, repeatedly, for deeper understanding of wide-range correlations in graphs. This distinguishes MeGraph from many recent hierarchical graph neural networks like Graph U-Nets. We conduct comprehensive empirical studies on tens of public datasets, in which we observe consistent performance gains comparing to baselines. Specifically, we establish 5 new graph theory benchmark tasks that require long-term inference and deduction to solve, where MeGraph demonstrates dominated performance compared with popular graph neural networks.

Under review as a conference paper at ICLR 2023
MEGRAPH: GRAPH REPRESENTATION LEARNING ON CONNECTED MULTI-SCALE GRAPHS
Anonymous authors
Paper under double-blind review
ABSTRACT
We present MeGraph, novel network architecture for graph-structured data. Given any input graph, we create multi-scale graphs using graph pooling. Then, we connect them into mega graph by bridging inter-graph edges according to the graph pooling results. Instead of universally stacking graph convolutions over the mega graph, we apply general graph convolutions over grappg edges, while the convolutions over inter-graph graph edges follow a bidirectional pathway to deliver the information along the hierarchy for one turn. Graph convolution and graph pooling are two core elementary operations of MeGraph. In our implementation, we adopt the graph full network (GFuN) and propose the stridden edge contrac- tion pooling (S- (S-EdgePool) with adjustable pooling ratio, which are extended from conventional graph convolution and edge contraction pooling. The MeGraph model enables information exchange across multi-scale graphs, repeatedly, for deeper understanding of wide range correlations in graphs. This distinguishes MeGraph from many recent hierarchical graph neural networks like Graph U- Nets. We conduct comprehensive empirical studies on tens of public datasets, in which we observe consistent performance gains comparing to baselines. Specif- ically, we establish 5 new graph theory benchmark tasks that require long-term inference and deduction to solve, where MeGraph demonstrates dominated per- formance compared with popular graph neural networks.
INTRODUCTION
In real-world applications, many types of data can be naturally organized as graphs, such as social networks, traffic networks and biological data. Recent advances in graph neural networks (GNNs) have inherited the great success of convolutional neural networks (CNNs) from images to deal with graph-structured data. Popular methods include the GCN (Kipf & Welling, 2016), GIN (Xu et al., 2018), 8), GAT (Vaswani et al., 2017) and Graph U-Nets (Gao & Ji, 2019), etc.
Generally, the development of both CNNs and GNNs is co-evolved, and most effective experiences identified in CNNs are also helpful for GNNs. For example, we have witnessed coupled networks for image and graph data, like CNN vs. GCN, attentional CNN vs. GAT (Vaswani et al., 2017), and U-Net (Ronneberger et al., 2015) Graph U-Net (Gao & Ji. 2019), etc.
Instead of directly transferring advances in CNNs to GNNs, we investigate inherent characteristics in graphs and design new architecture accordingly. We use the following example to motivate the story. Consider the problem of identifying the shortest path in a chain graph. Using normal graph convolutions, have stack multiple graph convolutional layers enlarge the receptive field to cover the source and the destination nodes. However, if the architecture could infer from a larger scope, e.g., constructing multi-scale graphs in a hierarchy, the shortest path is easier to be estimated by aggregating and delivering information from multi-level scopes. In addition, a single turn of information aggregation or delivery over the hierarchical structure might not be sufficient, because estimation should be refined and deduced over and over again to achieve sure conclusions. That is, the architecture has to repeat the information exchange across the hierarchy multiple times to identify the shortest path for sure. This example will be investigated in our experiment in Section 4. In fact, there have been several recent GNNs working on hierarchical graph structure. The Graph U-Nets (Gao & Ji, 2019) forms hierarchy by downsampling the graph with iterative convolutions and top-k pooling, and then upsampling the pooled graph with iterative convolutions and unpool- ing operators. However, the U-shaped net only propagates the information for single turn. The GraphFPN (Zhao et al., 2021) builds mappings between the image and graph feature pyramids ac- cording to the superpixel hierarchy, and it applies GNN layers on the hierarchical graph to exchange

---

Under review as a conference paper at ICLR 2023
h
Graph Pyramid
Mega Graph
Intra-graph edges
1
Inter-graph edges
2
Graph pooling
3
Figure I: Illustration for comparing the graph pyramid and the mega graph. The graph pyramid is formed with iterative graph pooling. Different shapes represent the nodes in different scales (heights). The inter-graph edges generated during graph pooling connect the graph pyramid into complete mega graph.
information within the graph pyramid; while the flow of inference still propagates for single pass over a fixed ceneettuaatiieraccccaa-oooeeeee
structure, as shown in Fig. 1 of (Zhao et al., 2021).
In this paper, we provide novel perspective for hierarchical graph representation learning. We use differentiable graph pooling methods to create mult-scale graphs, which were also referred to as the graph pyramid in previous methods (Zhao al., 2021). Conditioning on the graph pooling results, we explicitly connect multi-scale graphs into mega graph according to how the nodes are pooled together (illustrated in Fig. 1). A straightforward way to learn on the mega graph is to adopt the naive message-passinn strategy. which abandons the hierarchical prior knowledge. Instead, we convolve the intra-graph edges and inter-graph edges separately. That is, we stack general graph convolutions over intra-graph edges, while convolutions over inter-graph edges follow bidirec- tional pathway to deliver the information along the hierarchy top-down and then reverse back. This process will be repeated multiple times according to two dimensions, i.c., the height of the graph hierarchy and the depth of stacked layers. To realize the above scheme, we adopt two core elemen- tary operations, graph full network (GFuN) and stridden edge contraction pooling (S-EdgePool), which are extended from conventional graph convolution and edge contraction pooling. We conduct comprehensive experiments tens of public datasets, in which we observe consistent performance gains compared to baselines. Specifically, we establish five new graph theory benchmark datasets that require long-term inference and deduction solve. In these tasks, MeGraph demonstrates dominated performance compared with popular graph neural networks.
Our contributions can be summarized as follows. 1) general usage for graph neural networks. Given the mega graph, we propose a specific network module to enable repeated information exchange across multi-scale graphs. 2) To control the scale of pooled graphs, we design the S-EdgePool operator, which allows variable pooling stride and pooling ratio. 3) We create five new graph theory benchmark tasks, including problems of shortest path, maximum connected component, graph diameter, etc. The MeGraph model achieves obvious improvement on most of the benchmarks compared to popular GNNs.
We propose a novel mega graph structure with
NOTATIONS, BACKGROUNDS AND PRELIMINARIES
Let g = (V,E) be a graph with node set V (of cardinality N") and edge set & (of cardinality Nº). The edge set can be represented as {(S,, tx)]k=1:Ns where sy and t, are the indices of the source and target nodes connected by edge k. We define X as features of graph G, which combination of global (graph-level) features u node features V and edge features E Accordingly, we V represent the features of a specific node vi, and Eg denotes the features of a specific edge (sp: 4.). We may abuse the notations by omitting the superscript G when there is no ambiguity from the contexts.
2.1 GRAPH NETWORK (GN) BLOCK
We follow the graph networks (GN) framework in (Battaglia et al., 2018). Using our notations, GN block takes a graph and features X (u. V, E) as inputs, and the block outputs new features X = (u', V E'). ). A full GN block (Battaglia et al., 2018) contains the following computational steps (where @ each step below indicates an update function that usually a neural network):
1. Update edge features: E/ = (E,, V OE Vi u), Vk E [1...NN..
2. Update node features: V = (p ((Ei)(((E).......... )e..I.........--))) V.. u), Vi E [1...N"], where
D is an edge-to-node aggregation function taking the features of incoming edges inputs.
2

---

Under review as a conference paper at ICLR 2023
Select
Input Graph
InterGraph
Connect
Output
Graph
Reduce
Figure 2: Illustration of graph pooling with SELECT, CONNECT and RRDUCR steps. The SELECT function groups subset of nodes in the input graph to form a new node and connect the subset of nodes with the new node via inter-edges. The CONNECT function maps the edges of the input graph to new edges in the pooled graph. The REDUCE function aggregates features of the input graph according the inter-graph. We only illustrate the reduction node features simplicity.
3. Update global features: u' = (0"p""((E") p"" (V"),, u), where pa- and pm are two global aggregation functions over edge and node features.
Given a fixed graph structure and the consistent input and output formats defined above, GN blocks can be easily applied to compose deep graph networks, A common mncoe-proocsss-dee architecture design adopted in typical graph networks (Battaglia al., 2018; Hamrick et al., 2018) is applying the encoding GN block (GNene), multiple core GN blocks (GNeore) and the decoding GN block dGo) sequentially on inputs Xinput to obtain the outputs Xoutput-
2.2 GRAPH POOLING
Similar to the concept of pooling in CNNs, graph pooling downsamples the graph structure and reduces the corresponding features, while preserving both structural and semantic graphical infor- mation. Following (Grattarola et al., 2022), we define graph pooling as a class of functions POOL that maps graph G = (V, E) with N" nodes and features X to a reduced graph 9 = (V, with Nº nodes and new features X where N S No and x²) POOT.(9 X9).
The POOL function consists of the following steps SELECT, CONNECT and REDUCE:
(g, x SELECT(G, )): و CO
x REDUCE xx (1)
The SELECT function maps the nodes in the input graph to the nodes in the pooled graph. Specifi- cally, it creates R nodes for the pooled graph and connects each node to a subset of nodes Sa C V in the input graph. This forms an undirected bipartite graph 9 = (V, E), where 10 = VU V and (v, ū) & if and only if E Sg. We call this graph & the inter-graph, which is larger graph connecting the nodes in the input graph G and the nodes in the pooled graph G. The SELECT func- tion can generalize to introduce inter-graph features X For example, we can introduce some edge weights for some edge (S,, te) in graph 9 to measure the importance that the node 84 from the input graph contributes to the node 4g in the pooled graph. The CONNECT function rebuilds the edge set between the nodes in Y of the pooled graph 9 according to the original edges in & and the inter- graph edges in غ. The REDUCE function computes the graph features x of graph by aggregating input graph features X according to both the inter-graph 9 and features X
In contrast to the REDUCE function, we further define the EXPAND function in the reversed direction:
x = EXPAND X &. x Note that the inter-graph 9 and features x can be reused when applying REDUCE or EXPAND to any features of graph G or g.
By extending the general SELLECT-REDUCE-COME formulation of the POOL function covers most of the current graph pooling methods, including the recent node clustering pooling and node drop pooling methods (Liu al., 2022). For example, will explain EdgePool (Dichl et al., 2019) under the scope of this formulation in Section 3.3.
framework (Grattarola et al., 2022),
METHODS
The main idea in our approach is that we explicitly connect multi-scale graphs into mega graph. We then apply graph neural networks over the mega graph to enable repeated information exchange across multi-scale graphs. In this section, we first introduce how we obtain and connect the multi- scale graphs using graph pooling methods (Section 3.1). Then, we introduce the MeGraph model, which learns hierarchical graph representation on the mega graph through repeated cross-scale infor- mation exchange (Section 3.2), followed by specific choices of core modules and innovations made therein (Section 3.3). At last, analyse the computational complexity of MeGraph. (Section 3.4).
3

---

Under review as a conference paper at ICLR 2023
Depth
h Inputs
Layer 1
Layer 2
Layer 3
Layer 7
Outs
Graph Features
Intra GN
Inter GN
2
X
X
Pooling
Mee
Layer
x
Readout
Logits
4
Last Layer(s)
Encode
Process
Decode
Figure 3: Illustration of the MeGraph model where means 1. The blue and green circles represent
features of intra- and tierrgraphs, respectively. The mega graph is built using graph pooling during the encode stage. The Mee layer with bidircetional pathways erossing multiple scales is stacked n times during the process stage. There are residual links within the i-th Mee layer for both intra- and inter-graph features from X;- to Xj (blue ones) and from x 1-11n to X (green ones) for all height j. The multi-scale features are read out during the decode stage. The golden inter GN blocks forms hidirectional pathways across multi-scale features.
3.1 CONNECTING MULTI-SCALE GRAPHS INTO A MEGA GRAPH
Similar to the image pyramid (Adelson et al., 1984), a graph pyramid is piled up by multi-scale graphs obtained through iteratively downsampling the smallest one using graph pooling. Formally, according to the image feature pyramid (Lin et al., 2017), we define graph feature pyramid as a set of graphs i-Ah == i=, A and features X == [ A where G1 indicates the original graph, X denotes the initial features, is the height of the graph feature pyramid and (G,, x = POOL(G.-1, X for i > 1.
By iteratively applying the POOL function, we collect the inter-graphs 91. := (9:) (9i) A- and features & = (X& -. (since the highest inter-graph for height Gh-1 instead of Gi),, where (G., X.) SELECT(G, x for i < h. Recalling that SELECT is the first step of the POOL function, the bipartite inter-graph & and features X essentially reveals the relationships between the graphs before and after pooling (see also Section 2.2).
Finally, we wire the graph pyramid Gi-h using the edges in the bipartite graphs 9 resulting in mega graph Mg (MV, ME), where MVV U V; and ME U & - &. We denote MGintra = - 9j as the intra-graph of MG and name the edges therein as the intra-edges. Accordingly, MGunte U G. is referred to as the inter-graph of MG and the corresponding edges called inter-edges. The features XMC of mega graph MG is combination of intra-graph features & and inter-graph features X9.
3.2 THE MEGRAPH MODEI.
The most straightforward way to use the mega graph MG is treating it as an ordinary graph and universally applying graph neural networks like GCNs (Kipf & Welling, 2016) on However, our intuition in proposing the mega graph structure is to facilitate the information exchange across multi- scale graphs, while the above method suffers from long-distance message propagation by ignoring the inherent structure of the mega graph. For example, by applying normal GCNs over the mega graph, the features of the original graph 91 have to be convolved least
times to reach the features of the smallest graph Gn. and vice versa. This is similar to stacking CNNs on a large image, where the pixels at the lefer-left corner and the bottom-right corner are receptive one kernel only at very deep layers.
To overcome this, we propose the MeGraph network. The overall architecture of MeGraph il- lustrated in Fig. 3. As we can observe, the MeGraph network follows the common encode-process- decode architecture design and uses GNs (see Section 2.1) as elementary building blocks. In the grrah GN block, followed by series of
encode stage, the feature embedding is fed into graph pooling operators to construct the mega graph MG and features MS. In the process stage, an elementary component is layer shaped like mirrored E, which is referred the Mee
4

---

Under review as a conference paper at ICLR 2023
Inputs
Vertical Updates
Outputs
Graph Features
Intra GN
Inter GN
Residual
Same
Pathway
3
X
x
Update
Step 1
Step 2
Step3
Figure 4: Illustration of the Mee layer. where i.. means i 1 and j+ means + 1. The blue and green circles represent features of intra- and inter-graphs, respectively. The grey and golden arrows indicate the intra and inter GN blocks, respectively. The cross update exchanges information between consecutive heights using inter GN blocks, detailed in the main text. There are three steps of updates, where the first step updates intra intra-graph features. The second step sequentially applies cross updates from lower to higher levels. The information is accumulated along the pathway and passes to higher levels. The procedure is reversed in the third step.
layer. The process module is composed by stacking the Mee layers for n times. The i-th Mee layer takes the features (XM inputs and outputs (X*) (with residual links (He et al., 2016)) by applying GN blocks in a designated order. In the decode stage, the features (X") are aggregated task-dependent representations using readout functions.
Mee Layer. As we can observe in Fig. 3, the Mee layer contains horizontal flows at each height and vertical bidirectional pathways across multiple scaled graphs. zoom-in structure of the Mee layer is depicted in Fig. 4. At each Mee layer, the messages are passed through one step horizontal flow, i... the features of intra-graphs are fed into a GN block at each height as shown in Step Then, the messages propagate from height I to height h and reverse back, where the features are updated through the intra-edges according to the arrows (called the cross update or XUPD) in Step (height 1 to height h) and Step 3 (reverse back). Within a single Mee layer, the information can be efficiently exchanged across multiple scaled graphs. By stacking the Mee layer into a deeper architecture, the information exchange is repeated for times where is the number of stacked Mee layers.
Formally, let (X = ((xi-1)Stn (Xi-1)S1in) be the inputs of the i-th Mee layer. For simplicity, we omit the superscript of graph identities and rewrite the features of intra- and inter- graphs as (X] "===),,,--- . == (X and (X) "y=,,... A-1 (Xi-1) Then, the updates in Step can be written as X; = GN intra (9), x where X, is the updated features of intra- graph Gj. For the vertical updates in Steps and 3, we define the cross update between consecutive heights j and j + 1 to be a function (X (3,X) = XUPD(J, X,. X,,Xy+1) This function realized by first merging X, (node-wisely) with Xj as X,, applying GN blocks on inter-graph G by X = GN (Gy,X,) and finally retrieving X X,.XI X/+1 and X from XT. We denote this inter
default realization X-Conv. The cross update function can also be realized using the REDUCE and EXPAND operation of POOL (see Section 2.2) by X
REDUCE(C,, X². X,) and X/- EXPAND X.. X1+1), where Gj is the j-th gtter. We denote such realization as X-Pool, which standard for most pooling methods. The intra and inter GN blocks can share parameters among all j's that generalize to different heights, or among all i's that generalize to different depths.
The outputs of the process stage are the updated features (X) 1yji,,, and (X) (x/ A In our implementation, we add residual links from X)-1 to X and from X to X² to provide shortcuts bypassing the entire Mee layer.
3.3 MODULE CHOICE AND INNOVATION
In MeGraph, there are two elementary modules, i.e., the graph pooling operator and the GN block. The MeGraph architecture can adopt any graph pooling method long it belongs to the POOL function family introduced Section 2.2). Also, the choice of the GN block is not limited to the graph convolution layer as used in standard GCN, GIN or GAT.
Graph Pooling, There are a number of commonly used graph pooling methods, including Diff- Pool (Ying et al., 2018), TopKPool (Gao & Ji, 2019), EdgePool (Diehl et al., 2019), etc. Among
5

---

Under review as a conference paper at ICLR 2023
those, EdgePool is promising method because it is trainable, sparse, and adaptable, according to the taxonomy proposed in Grattarola et al. (2022). It also preserves the connectivity in graphs, i.., if two subsets of nodes S₁ and S2 are connected in the input graph, the reduced nodes in and ög are still connected in the pooled graph. However, the pooling ratio (the number of nodes after pooling over the number of nodes before pooling) for applying one EdgePool operator is lower bounded by 50% and not adjustable since EdgePool seeks to only contract edges without overlapping connected nodes. This is inflexible when the original graph (of N nodes) is extremely large, with at least logg . pooling operations to reduce to single node. In this paper, we extend the EdgePool method to deal with arbitrary pooling ratios. We propose the Stridden EdgePool (S- (S-EdgePool) with a vari- able pooling stride within the framework of the POOL function family introduced in Section 2.2. Moreover, we propose an efficient implementation of S-EdgePool (containing EdgePool as a special case) using the disjoint-set data structure (Galler & Fisher, 1964) below.
In the SELECT step, S-EdgePool shares the same computations as in EdgePool to generate learnable edge scores, detailed in Appendix C.I.I. Then, propose a clustering procedure to determine the subset of nodes to be reduced. Let Lv be the identifier of the cluster containing a set of nodes v. Initially, we let v {v} for every single node A contraction of an edge merges a pair of nodes (v, e') connected by this edge (where V E v, o' E v' and v * v'), and thus unifies the v'. That is, once edge connecting
cluster identifiers, i.e., Iv- Iv' Ieaegg and meerge any pair of nodes from two distinct clusters is contracted, we merge the two clusters and unify their identifiers. Edges are visited sequentially by a decreasing order on the edge scores, and contractions are implemented if valid. We set the maximum size of the node clusters to be a parameter Te, where Te 2 degenerates to the case of EdgePool (Dichl et al., 2019). We further introduce the pooling ratio Te to control the minimal number of remaining clusters after edge contractions to be N" * 77- 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 (Galler Fisher, 1964). The detailed procedures of CONNECT, REDUCE and EXPAND functions are provided in Appendix C.1.2. The pseudocode of the entire algorithm is given in Algorithm 2 of Appendix C.1.3.
GN block. In this paper, realize the full GN block (introduced in Section 2.1) as a graph full network (GFuN) layer. A practical difference from the full GN block in (Battaglia et al., 2018) is that deactivate some links in the full GN block to reduce the computational complexity and the number of parameters. More details are available in Appendix C.2. We use GFuN as the basic component because of its excellent flexibility. We compare it with GCN in Appendix E.2.
Encoder and decoder. The MeGraph model can choose most input embedding methods (including positional encodings) and readout functions used in GNNs. Details are Appendix C.3.
3.4 COMPUTATIONAL COMPLEXITY
The overall complexity of the MeGraph model depends on the height h. the number of Mee layers n, and the choices of the modules, as well as the corresponding hyper- parameters.
Let D be the embedding size, V be the number of nodes, and E be the number of edges in the input graph G. The time complexity of S S-Edgepool is OEED+E log E), where OEED) is the complexity of computing edge scores and O E) comes from sorting the edge scores. The dynamic node clustering using disjoint-set is of O (F)) complexity where a aFF)) is a function that grows slower than log(F)) (Tarjan & Van Leeuwen, 1984). The time complexity of GFuN layer is O(V D)) For simplicity, we assume both the pooling ratios of nodes and edges are 7. Then, the total time complexity to build the mega graph MG is O(ED + E log E) n)), where hh-1 n/ < 1/(1 - 11). Similarly, the total time complexity of an Mee layer is O((VD2 + FD) - 1)), which is the same as a normal GNN layer if we regard 1 1/(1 v)) as a constant (e.g.. it is a constant of 2 when 1) = 0.5). In practice, we introduce some variants of MeGrapp to further reduce the time complexity in Appendix C.4.
4 EXPERIMENTS
We conduct comprehensive experiments on both node and graph prediction tasks across a large variety of synthetic and real-world datasets to show the superior performance of the MeGraph model. We also demonstrate the importance of introducing S-EdgePool by ablation studies. Due to space limitations, statistics of the datasets are provided in Appendix B. and the training and implementation details are reported in Appendix D.
6

---

Under review as a conference paper at ICLR 2023
TreeCycle
TreeGrid
1.00
1.00
0.96
0.98
Accuracy
Accuracy
0.92
0.96
0.88
0.94
height=]
heightel
heightm2
2
3
4
5
6
10
0.90
2
5
10
Num Layer
Num Layer
Figure 5: Node classification accuracy (averaged over 10 random repetitions) for MeGraph on TreeCycle (left) and TreeGrid (right) datasets varying the height and the number of Mee layers Clear gaps can be observed among heights 2, and 2 3. Detailed numbers can found Table 10 of Appendix E.3.
4.1 BASELINES
The height h is the key parameter determining the overall architecture of the MeGraph model. When we set h = 1, the MeGraph model reduces to normal GNN over the original graph, which will be treated as reliable baseline. To show the importance of repeated multi-scale information exchange, also compare with the baseline method by setting the number of Mee layers n 1. We also compare with the Graph U-Nets (Gao & Ji, 2019), which is approximately equivalent to U-Shaped variant under the MeGraph architecture. We the GFuN layer as the core GN block in these models.
4.2 SYNTHETIC DATASETS
We first study the effect of the max height h and the number of Mee layers on 4 synthetic datasets introduced by Ying al. (2019), including the BAShape, BACommunity, TrecCycle and TreeGrid. Each dataset contains one graph formed by attaching multiple motifs to base graph. The motif can be a 'house' -shaped network (BAShape, BACommunity), six-node cycle (TreeCycle), or 3-by-3 grid (TreeGrid). The task is to identify the nodes of the motifs in the fused graph.
The
results of TreeCycle and TreeGrid are shown in Fig. 5. We can observe clear gaps among curves of h = 1, h 2 and h 2 3 for all values of n. This indicates that h is crucially important for recognizing the motifs. Similar conclusions can also be drawn in the easier datasets BAShape and BACommunity (Fig. 6 in Appendix E.3).
4.3 GRAPH THEORY BENCHMARK
An important benefit of the MeGraph architecture that it facilitates long-distance inference over graphs. To verify this, we create graph theory benchmark containing 3 graph regression tasks and 2 node regression tasks, for solving which long-distance inference is necessary. The graph regression tasks include Single Source Single Destination Shortest Path (SPsssd), Maximum Con- nected Component of the same color (MCC) and Graph Diameter (Diameter). The node regression tasks are Single Source Shortest Path (SP..) ..) and Eccentricity of nodes (ECC). All these problems are based on artificially generated graphs. Following Corso al. (2020), we use their methods to propose three new methods:
generate undirected and unweighted graphs randomly. In addition, cycle, pesudotree and geographic threshold graphs. We create a dataset for each task and each graph generation method, resulting in total of 55 datasets after filtering out the trivial cases. The de- tails of those tasks and dataset generation can be found in Appendix B.2. As shown in Table 1, the MeGraph model achieves significantly smaller regression loss compared with all the baselines (h = 1, n, 1 and U-Shaped net), even when the baseline methods take more GNN layers.
blation Studies. We first vary the node pooling ratio т) and the maximum cluster size т. of S- EdgePool to evaluate the performance. The ad advantage of a flexible pooling stride is shown in the lower part of Table 1, where the best one achieves almost 4x smaller eтror (l7,, 0.3, T. 4] 0.624 vs. Ir. = 2] 2.337). We further experiment with the X-Pool (see the definition of XUPD in Sec 3.2) variation. The dropped performance ([X-Pe [o-Pool] 1.165 vs. [X-Conv] 0.624) indicates the importance of using GN block for inter-gray -raph updates.
4.4 REAL WORLD DATASETS
Experimental Protocol. In this subsection, evaluate MeGraph public real-world graph benchmarks. To fairly compare MeGraph with the baselines, we use the following experimental protocols. We first report the public baseline results and reproduced standard GCN's results. We

---

Under review as a conference paper at ICLR 2023
Table I: Results on Graph Theory Benchmark, For each task, we report MSE regression loss on test set, averaged over different graph generation methods. Darker blue cells denote better performance. We refer more details to Appendix E.4.
Category
Model
SP SPeedd
MCC
Diameter
SP>>
ECC
Average
n=1
12.
1,377
12.654
25.159
21.522
13.680
Baselines
n=5
4.246
1.093
6.048
13.715
20.287
8.821
(/=1)
n= 10
2.488
1.119
5.812
7.819
20.201
7,481
MeGraph EdgePool (h=55, T==
n= (U-Shaped)
2.683
1.144
5.680
2.801
20.102
6.656
n=1
1.856
0.772
4.801
6.110
14.920
5.662
n=
0.817
0.616
2.6
0.785
6.892
2.337
T
0.648
0,600
0.575
0.501
0.856
0.644
MeGraph
77.0.3
2.33
0.583
0.964
3.984
2.021
1.840
S S-EdgePool
7. =0.33 T-=4
0,584
0.565
0.517
0.475
0,925
0.624
Ablation
0.55. 7
1.103
0.600
0.835
1.331
2.016
1.163
(h=5, n=
7. n.30.3 T (X-Pool)
0.935
0.619
0.734
1.618
2.014
1.165
Table 2: Results on GNN benchmark. 1 denotes the results are reported in (Dwivedi et al., 2020). Regression
tasks are colored with blue. + indicates that smaller numbers are better. Results of classification tasks are colored with green. indicates that larger numbers are better. Darker colors indicate better performance.
Model
ZINC
AQSOL
MNIST
CIFARIO
PATTERN f
CLUSTER
GCNi
0.416 10.006
1.372 10.020
90.120
10.145
54.142
10.394
85. 498 10.045
47.828 11.510
GIN
0.387 10.015
1.894
10.024
96.485
100252
55,255
11.527
85,590
10.011
58.384
200
GATÍ
0.475 20.007
1.441 #0.023
95.535
205
64.223
40.455
75.824
+1 41.823
57.732
+0.323
GatedGCNt
0.435 #0.011
1.352 20.084
97.340
10.143
67.312
#0.311
84.480
10.122
60.404
+0.410
GCN
0.426 10.015
1.397
110 029
90.140
10.100
51,050
10.390
84.672
10.064
47.541
1:09:00
MeGraph (I=1)
0.323 10. 00.002
1.075
10.007
97.570
10.168
69.89 69.890 10.
84 14.845
10.021
58.178
1.0079
MeGraph (x=1)
0.310 10 005
1.038
10.0188
96.867
10.166
68. 68.522 10.239
85. 507
1.0.402
50,396 1.0.882
MeGraph
0.260 =: 005
1.002
20.021
97.860
= 00.
69,925 10.631
86.507 20.067
68.603
=0. 101
McG raphht
0,202 ::0 007
1.002 2: 021
97.860
=0 008
69.925 10.631
86.732 10.023
68.610 1:0 164
then replace GCN layers with GFuN layers (which is equivalent to MeGraph (h 1)) to as 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 other hyper-parameters that only matters for h >> 1, and these pyrer--arameters are referred as the MeGraph hyper syper-parametery. MeGraph (n = 1) also serves as baseline method, which does not enables repeated information exchange. The standard MeGraph uses an uniform prper-parameter setting for all the datasets. We also report the best performance of MeGraph with specifically tuned hyper-parameters in each dataset, denoted as MeGraphbes: Detailed configurations are put in Table in the Appendix.
GNN Benchmark (Dwivedi et al., 2020). We experiment on three types of GNN benchmark datasets, which are chemical data (ZINC and AQSOL), image data (MNIST and CIFARIO) and social network data (PATTERN and CLUSTER). The tasks are regressing certain properties of molecule graphs (graph regression), classifying the super-pixel graphs (graph classification), and recognizing the patterns of nodes clustering nodes (node classification), respectively. More de- tails can be found in their original works. As shown in Table 2, Megraph outperforms the public results reported in (Dwivedi al., 2020) and our two baselines.
Open Graph Benchmark (OGB) (Hu et al., 2020). We choose 10 datasets related to molecular graphs from the graph prediction tasks of OGB, 7 out of which are classification tasks (molhiv, mol- bace, molbbbp, molclintox, molsider, moltox21 and moltoxcast) and the others are regression tasks (molesol, molfreesolv and mollipo). For all datasets, each graph represents a molecular compound. The node features are properties of atoms and the edge features are properties of bonds between atoms. The task of all datasets is to predict some properties of molecule graphs based on their chem- ical structures. As shown in Table 3, Megraph achieves 1% to 3% absolute gains on classification tasks, and about 10% relative gains on regression tasks compared to the bascline MeGraph (h = 1).
TU Datasets (Morris et al., 2020). The results of 10 popular TU datasets are put in Appendix E.
RELATED WORKS
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 (Ron- neberger et al., 2015), FPN (Lin et al., 2017), UNet++ (Zhou al., 2018), and some recent ap-
8

---

Under review as a conference paper at ICLR 2023
Table 3: Results on OGB-G. indicates that the results are reported in (Hu et al., 2020).
Model
molhiv t
molbace t
molbbbp 1
molclintox t
molsider
GCN!
76.06 10.97
79.15 11.44
68.87 1:1.51
91.30 11.73
59.60 1.1.77
GIN
75.58 #1.40
72.97 4:4.00
68.17 4:148
88.14 14 =2.51
57.60 +1.40
GCN
75.40 11.29
76.01
43.31
67.35
40.96
89.62
22.27
58.08 40.78
MeGraph (h=1)
78.54 #1.14
71.77
42.15
67.56
#1.11
89.77 #3.48
58.28 +0.51
MeGraph (n=1)
78.56 +1.02
79.72
+1.21
67.34
+0.98
91.07
#2.21
58,08 +0.59
MeGraph
77.20 #0.88
78.52
42.51
69.57
#:233
92.04
22.19
59.01 +1.45
MeGraphbest
79.20 +1.80
83.52
+0.47
69.57
+2.33
92.06 =1.32
63.43 +1
Model
moltox21 1
moltoxcast 1
molesol |
molfrresoly J
mollipo J
GCN1
75.29 10.69
63.54
10.42
1.114 10.03
2.640
10.23
0.797 1.0.02
GIN
74.91 #0.51
63.41
10.74
1.173 10.05
2.755
=0.34
0.757 +0.01
GCN
75.11 #0.41
64.13
40.52
1.141 #0.02
2.407
=0.15
0.788 +0.01
MeGraph (h=1)
75.89 #0.45
64.49
10.46
1.079 #0.02
2.017
=0.08
0.768 +0.00
MeGraph (w=1)
77.01
20.93
66.89
+1.21
0.896
+0.04
1.892
=0.06
0.730 +0.01
MeGraph
78.11
20.47
67.67
40.53
0.886
00.02
1.876 20.05
0.726 +0.00
MeGraphbest 78.11
10.47
67.90
10.19
0.867 1:002
1.876
00.05
0.688 +0.01
proaches (Yu et al.. 2018; Liu et al., 2018: Lin et al., 2019; Li al., 2020). HRNet (Wang et al., 2020) is similar method compared to MeGraph. HRNet alternates between multi-resolution con- volutions and multi-resolution fusion by stridden convolutions. However, the above methods are developed for image data, and key differences compared to these approaches is that the multi-scale feature fusion in MeGraph is incorporated with the inter-graphs generated by graph pooling, and the fusion process is repeated for multiple times. For graph networks, the GraphFPN (Zhao et al., 2021) builds mappings between the image and graph feature pyramids according to the superpixel hicrar- chy, and it applies GNN layers on the hierarchical graph to exchange information within the graph pyramid. However, the flow of inference still propagates for a single pass over a fixed contextual- hierarchical-conteetuul structure (see Fig. of (Zhao et al., 2021)). Gao & Ji (2019) and Fey et al. (2020) have also explored similar ideas in graph structured data. Our approach shares the general idea of multi-scale information fusion, but the first method that builds mega architecture with graph pooling and GN blocks that achieve efficient multi-scale information exchange in the domain of graph representation learning.
Graph Pooling Methods. Graph pooling is an important part in hierarchical graph representation learning. There have been some traditional graph pooling methods like METIS (Karypis & Kumar, 1998) in early literature. Recently, many learning based graph pooling methods have been proposed, including the DifiPool (Ying et al., 2018), TopKPool (Gao & Ji, 2019), SAG pool (Lee al., 2019), EdgePool (Dichl et al., 2019), MinCutPool (Bianchi et al., 2020), and MEWISPool (Nouranizadeh et al., 2021), etc. In MeGraph, we generalize the EdgePool method as S-EdgePool to build the mega graph, while this operator can be switched to any one of the above mentioned pooling method.
Graph Neural Network (GNN) Layers. The GNN layer is the core module of graph representation learning models. Typical GNNs include the GCN (Kipf& & Welling, 2016), GraphSage (Hamilton et al., 2017), GAT (Veličković et al., 2018; Brody et al., 2021), GIN (Xu et al., 2018), PNA (Corso et al., 2020). MeGraph adopts the full GN block (Battaglia et al., 2018) 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.
6 LIMITATIONS AND FUTURE WORK
The MeGraph model suffers from some limitations. The introduced mega graph architecture in- evitably increases both the number of trainable parameters and tuneable hyper-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 fea- tures in addition to node features, when mapping the input graph to the pooled graph. It is also possible improve MeGraph using adaptive computational steps (Tang et al., 2020). Another direction is to apply some expressive models like Transformers (Vaswani et al., 2017) and Neural Logic Machines (Dong et al., 2018; Xiao et al., 2022) (only) over the pooled small-sized graphs, since these models are computational expensive.

---

Under review as a conference paper at ICLR 2023
7 REPRODUCIBILITY STATEMENT
We will post an anonymous code repository link in an official comment on Openreview. We set the random seed as 2022 for all experiments to enable reproducible results. We provide dataset statistics in Table and details for the proposed graph theory benchmark in Appendix B.2. All details of the and the command
hyper-parameter are reported in Table 5. Configuration of all lines to reproduce the experiments will be included in the code repository.
REFERENCES
Edward H Adelson, Charles H Anderson, James R Bergen, Peter Burt, and Joan M Ogden. Pyramid methods image processing. RCA engineer, 29(6):33-41, 1984.
Réka Albert and Alszrt-LászIó Barabási. Statistical mechanics complex networks. Reviews of modern physics, 74(1):47, 2002.
Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton. Layer normalization. arXiv preprint arXiv: 1607.0640, 2016.
Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint arXiv: / /806.0/261, 2018.
Vinicius Zambaldi,
Filippo Maria Bianchi, Daniele Grattarola, and Cesare Alippi. Spectral clustering with graph neural networks for graph pooling. In International Conference Machine Learning, pp. 874-883. PMLR, 2020.
Shaked Brody, Uri Alon, and Eran Yahav. How attentive are graph attention networks? In Interna- fional Conference on Learning Representations, 2021.
Ting Chen, Song Bian, and Yizhou Sun. Are powerful graph neural nets necessary? a dissection on graph classification. arXiv preprint arXiv: 045599 2019.
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-133 13271, 2020.
Frederik Diehl, Thomas Brunner, Michael Truong Le, and Alois Knoll. Towards graph pooling by edge contraction. In JCMLLL2011 2019 workshop on learning and reasoning with graph-structured data, 2019.
Honghua Dong, Jiayuan Mao, Tian Lin, Chong Wang, Lihong Li, and Denny Zhou. Neural logic machines. In International Conference on Learning Representations, 2018.
Vijay Prakash Dwivedi, Chaitanya K Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv preprint arXiv:2003.00982 2020.
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.
Paul Erdös, Alfréd Rényi, et al. On the evolution of random graphs. Publ, Math. Inst. Hung, Acad. Sci, 5(1):17-60, 1960.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprint arXiv: 2019.
Matthias Fey, Jan-Gin Yuen, and Frank Weichert. Hierarchical inter-message passing for learning on molecular graphs. arXiv preprint arXiv:2006.1217 2020.
Bernard A Galler and Michael J Fisher. An improved equivalence algorithm. Communications of the ACM, 7(5):301-303, 1964.
10

---

Under review as a conference paper at ICLR 2023
Hongyang Gao and Shuiwang Ji. Graph u-nets. In international conference machine learning, pp. 2092-2092. PMLR, 2019.
Daniele Grattarola, Daniele Zambon, Filippo Maria Bianchi, and Cesare Alippi. Understanding pooling in graph neural networks. IEEE Transactions Neural Networks and Learning Systems, 2022.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
Jessica B Hamrick, Kelsey R Allen, Victor Bapst, Tina Zhu, Kevin R McKee, Joshua B Tenen- baum, and Peter W Battaglia. Relational inductive bias for physical construction in humans and 2018.
machines. arXiv preprint 1806.000
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp- 770-778, 2016.
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:221 18 11-1822222 22133, 2020.
Yuanming Hu, Tzu-Mao Li, Luke Anderson, Jonathan Kelan-Kelley, and Frédo Durand. Taichi: a language for perforreffre computation on spatially sparse data structures. ACM Transac- tions on Graphics (TOG), 38(6):201, 2019.
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International conference on machine learning, pp. 448-456. PMLR, 2015.
George Karypis and Vipin Kumar. A fast and high quality multilevel scheme for partitioning irreg- ular graphs. SIAM Journal scientific Computing, 20(1):359 392, 1998.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In ICLR (Poster), 2015. URL http: / / //tp//axvvv///////////e////.aa// org/ /agg//ab//// aabs//112/ 1412. 6980.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. 2016.
Junhyun Lee, Inyeop Lee, and Jaewoo Kang. Self-attention graph pooling. In International confer- ence on machine learning. pp. 37433. PMLR, 2019.
Xiangtai Li, Houlong Zhao, Lei Han, Yunhai Tong, Shaohua Tan, and Kuiyuan Yang. Gated fully fu- sion for semantic segmentation. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pp. 11418- 1425,, 2020.
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 on Computer Vision and Pattern Recognition, pp. 7490-7499, 2019.
Tsung-Yi 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 com- puter vision and pattern recognition, pp. 2117-2125, 2017.
Chuang Liu, Yibing Zhan, Chang Li, Bo Du, Jia Wu, Wenbin Hu, Tongliang Liu, and Dacheng Tao. Graph pooling for graph neural networks: Progress, challenges, and opportunities. arXiv preprint arXiv:2204.072 073211, 2022.
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, pp. 8769-8768, 2018.
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 M.Xiv:0077008663. 2020.
11

---

Under review as a conference paper at ICLR 2023
Amirhossein Nouranizadeh, Mohammadjavad Matinkia, Mohammad Rahmati, and Reza Safabakhsh. Maximum entropy weighted independent set pooling for graph neural networks. arXiv preprint arXhv:2107.014110 2021.
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, high- performance deep learning library. Advances in neural information processing systems, 32, 2019.
Olaf Ronneberger, Philipp Fischer, and Thomas Brox. U-net: Convolutional networks for biomedi- cal image segmentation, In International Conference Medical image computing and computer- Springer, 2015.
assisted intervention, pp.
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 Pro- cessing Systems, 33:15811 1-8222, 2020.
Robert E Tarjan and Jan Van Leewenn. Worst-case analysis of set union algorithms. Journal of the ACM (JACM), 31(2):245-281, 1984.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural informa- tion processing systems, 30, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference Learning Representations, 2018.
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 learn- ing for visual recognition. IEEE transactions on paltern analysis and machine intelligence, 43 (10):3349-3366 2020.
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: graph-centrie, gegfo-tperoommatt package for graph neural networks. arXiv preprint arXiv:1909.01..
2019.
Duncan J WATTS. Networks, dynamics and the small world phenomenon. American Journal of Sociology, 105(2):50-59, 2003.
Guangxuan Xiao, Leslie Pack Kaelbling, Jiajun Wu, and Jiayuan Mao. Efficient training and infer- ence of hypergraph reasoning networks, 2022. URL https: /ttp///wpppeeee.///////// n net/forum? forum? i.d-WKAAkkKGpWN.
Keyulu Xu. Weihua Hu, Jure Leskovec, and Stefanic Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2018
Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hier- archical graph representation learning with differentiable pooling, Advances in neural information processing systems, 31, 2018
Zhitao Ying. Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. Gnnexplainer: Generating explanations for graph neural networks. Advances in neural information processing systems, 32, 2019.
Fisher Yu, Dequan Wang, Evan Shelhamer, and Trevor Darrell. Deep layer aggregation. In Pro- ceedings of the IEEE conference on computer vision and pattern recognition, pp. 2403-2412, 2018.
Gangming Zhao, Weifeng Ge, and Yizhou Yu. Graphfpn: Graph feature pyramid network for object detection. In Proceedings of the IEEE/CVF International Conference Computer Vision, pp. 2763-2772, 2021.
Zongwei Zhou, Md Mahfuzur Rahman Siddiquee, Nima Tajbakhsh, and Jianming Liang. Unet++: A nested u nenet architecture for medical image segmentation. In Deep learning in medical image analysis and mudtimodal learning for clinical decision support, pp. 3-11. Springer, 2018.
12

---

Under review as a conference paper at ICLR 2023
A SUMMARY OF APPENDIX
We present dataset details Section B, method details Section C, implementation and training details in Section D and extra experiment results in Section E.
B DATASET DETAILS
B.1 DATASET STATISTICS AND METRICS
We provide the statistics of all datasets used in our experiments in Table and introduce the evalua- tion 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 (Dwivedi et al., 2020) for evaluation, i.e.. Mcan Absolute Error (MAE) for ZINC and AQSOL. classification accuracy for MNIST and CIFAR1O 10, and balanced classification accuracy for PATTERN and CLUSTER. For OGB Benchmark, we follow the original work (Hu al., 2020) 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 (Chen et al., 2019) and classification accuracy 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 are generated given base graph (V.
Single source single destination shortest path (SP (SPPs a source node E V and destina- tion node E are selected uniform randomly. The feature of each node contains three numbers: (1, whether the node is whether the node is t). The label of graph is the length of shortest path from 8 to t.
A maximum connected component of the same color (MCC): each node of the graph is colored with one 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 the graph the diameter of the graph. The diam- eter of a graph & is the maximum of the set of shortest path distances between all pairs of nodes the graph. The feature each node a uniform number
Single source shortest path (SPs)): source node is selected uniformly randomly. The feature of each node contains two numbers: (1, whether the node is s). The label of each node is the length of the shortest path from s this node.
Graph eccentricity (ECC): the label of each node is node's eccentricity in the graph, which is the maximum distance from to the other nodes. The feature each node is a uniform number 1.
For each task and graph generation method, We generate the dataset by the following steps:
Sample N (number of nodes) from [20, 50), totally 300 graphs. These numbers can be configured.
Use the graph generation method to generate graph of N nodes.
Create graph features and labels according to the task.
We then provide the details about the random graph generation methods we used to create our Graph Theory datasets.
Following Corso et al. (2020), 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 descriptions here for completeness (the percentage after the name is the approximate proportion of such graphs in the mixture setting).
13

---

Under review as a conference paper at ICLR 2023
Table 4: 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 4 synthetic datasets are transductive, where the same graph used for both training and testing. We do not use the node labels as features during the training time. The train-vat val-tst 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
Graphs
Node Feat
Edge Feat
Classes
Task
Reg.
Nodes
Synthetic
BaShape
700
1761
Trans-Node
Synthetic
BaCommunity
1400
3872
Trans-Node
Synthetic
TreeCycle
871
970
Trans-Node
Synthetic
TreeGrid
1231
1705
Trans-Node
GraphThcon
SP send
Graph
GraphTheory
Diameter
300
Graph
TraphTheory
Graph
GhuphThcory
Node
GraphTheory
ECC
Node
GNNBenchmark
ZINC
12000
23.16
49.83
28
Graph
GNNBenchmark
AQSOL
9823
17.57
35.76
65
5
2
Gruph
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 Graph
molhiv
41127
25.51
80.45
3
Graph
OGB Graph
molbace
1513
34,09
107.81
3
Graph
OGB Graph
molbbbp
2039
24.06
75.97
3
2
Graph
OGB Graph
molclintox
1477
26.16
81.93
3
2
Graph
OGB Graph
molsider
1427
33.64
104.36
3
2
Graph
OGB Graph
moltox21
7831
18.57
57.16
3
2
Graph
OGB Graph
moltoxcast
8576
18.78
57.30
3
2
Graph
OGB Graph
molesol
1128
13.29
40.64
3
Graph
OGB Graph
molfrecsoly
642
8.7
25,50
3
Graph
OGB Graph
mollipo
4200
27.04
86.04
Graph
TU
MUTAG
188
17.93
19.79
Graph
TU
NCII
4110
29.87
32.30
37
Graph
TU
PROTEINS
1113
39.06
72.82
4
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
10
3
Graph
TU
RE-B
2000
429.63
497.75
10
2
Graph
TU
RE-MSK
4999
508.52
594.87
10
5
Graph
TU
RE-M12K
11929
391.41
456.89
10
11
Graph
14

---

Under review as a conference paper at ICLR 2023
Erdös-Rényi (ER) (20%) (Erdös et al., 1960): with probability of presence for each edge equal to p. where p independently generated for each graph from 21 1]
Barabási-Albert (BA) (20%) (Albert Barabási, 2002): the number edges for new node is k, which is taken randomly from {1,2, ................................ N 1 for each graph
Grid (5%): m 2d grid graph with = mk and m and & as close as possible
Caveman (5%) (WATTS, 2003): with cliques of size k, with and close as 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 backbone of size b (drawn from U(1,N) and N pendent vertices uniformly connected the backbone
Lobster graphs (10%): with a backbone of size b (drawn from (((,,N), (drawn from W[1, - ) pendent vertices uniformly connected to the backbone, and additional N b-b-p pendent vertices uniformly connected to the previous pendent vertices.
Additional, add three 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 = (0.3le(0.3.N, 0.6.N.. Then m remaining nodes are sampled to parts, where i-th part represents the size of the tree hanging the i-th node on the cycle. The trees are randomly generated with the given size.
Geographic (Geo) graphs: geographic threshold graphs, but with added edges via min- imum spanning tree algorithm, to ensure all nodes are connected. This graph generation method introduced by Battaglia et al. (2018) their codebase 1 We use the geographic threshold / 200 instead of the default value 0 = 1000.
Note that we do not have randomization after the graph generation in Corso al. (2020). There- fore, very long diameter is preserved for some type of graphs.
C METHOD DETAILS
C.I
S-EDGEPOOL
C.1.1 EDGE SCORE GENERATION
Both S-EdgePool and EdgePool methods compute a raw edge score for each edge i using a linear layer:
Fk W (V V. Ex) +
where sę and tu are the source and target nodes of edge V is node features, E is 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:
W exp(rx)/
Σ exp(re<),
and biased by constant 0.5 (Dichl et al., 2019).
hhtp://ghhhiaccm//mmmmmm/gggg nets, the shortest path demo
15

---

Under review as a conference paper at ICLR 2023
C.1.2 CONNECT, REDUCE AND EXPAND
In this subsection, we give the details of CONNECT, REDUCE and EXPAND functions of S-EdgePool.
The CONNECT function rebuilds the edge set & between the nodes in V. As aforementioned, build the pooled graph's nodes according to node clusters. We call this mapping function from node clusters new nodes After that, we 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.
In our experiments, the REDUCE and EXPAND we used are generalized from the method mentioned in Diehl et al. (2019). The REDUCE function computes new node features and edge features We follow their method 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 a disjoint-set data structure. cluster is consist of [Sa] nodes. We define E set of |Sal - 1 edges, where the edges are the selected edges to be contracted in SELECT function and they connecting all nodes a node cluster S..
1+ Ee Wi
C. = V
SSp
Gp
V
vESp
To integrate the edge features between two node clusters, first find all the connected edges be- tween the two node clusters (the edges between node clusters are edges that connect two nodes from different node clusters). Then, use the of all the connected edges' features between the two node clusters as the new edge's features.
The term EXPAND used refers unpooling operation. When unpooling, create inverse mapping of pooled nodes to unpooled nodes.
V
V
Wavg
C.1.3 PSEUDO CODE
The pseudo-code includes two parts, where Algorithm 1 describes how maintain the clusters using a desjoint-set data structure, and Algorithm describes the procedure of S-EdgePool that generates a pooled graph with configurable node pooling ratio and maximum of cluster sizes тe.
C.2 GFUN
We first realize the des Pus &u functions in the full GN block (Sec 2.1 and (Battaglia et al., 2018))
as neural networks:
Eg NN. Eg, Sau Vas u), V NN, E V., u),
(3)
u' = NN, V u)
(4)
respectively, where
(5)
E' (-"((E))
(6)
V (V").
(7)
We further decompose the neural networks according to the features in the function:
NN. (E V .x. V 1 u) NN EE) + NN ce-u, (V.,, + NN
en- (V.2) + NN c4-
(8)
(E, V, = NN. E NN (V;) + NN (u),
(9)
NN. EE, V u) -NN (E') NN, (V') + NNrraal (u)
(10)
16

---

Under review as a conference paper at ICLR 2023
Algorithm 1 Get Cluster Index And Cluster Size of Node (Using disjoint-set data structure) function INITIALIZE DISJOINT SET(graph ((V, 8))
for t E V do
inder []] 0 size/u] =
> the identifier of the cluster the node belongs to
end for end function function FIND INDEX(node v)
index(u) [u] v then
return v
else
indexfu] FIND INDEX(indez(u))
return index(o) [o]
end if
end function
function FIND INDEX AND SizE(node v)
8 FIND INDEX(U)
size(i] return 8
end function
function MERGE(cluster index æ and cluster index y)
size[y] size + sizely]
önder [z] f- index[y]
end function
However, such GN block uses 10 times number of parameters as the standard GCN (Kipf & Welling, 2016) layer when the node, edge and global embedding dimensions all equivalent. In practice, we disable all computations related to global features u, as well as the neural networks NN and We also NN to be Identity.
NN NN
In practice, we use summation function as the aggregator function ,F by default. But other choices like MEAN, MAX, gated summation, attention or their combinations can also be used.
Overall, we call such GN block as graph full network (GFuN) and use the practical setting in our experiments.
C.3 ENCORDER AND DECODER
Encoder. For input embedding, we use Linear layer Embedding layer to embed input features. For example, we follow Dwivedi al. (2020) and use Linear layer on MNIST and CIFARI0 datasets, use Embedding layer on ZINC and AQSOL datasets. For molecular graph in OGB, we use the same embedding method as the original work (Hu et al., 2020). Besides, we can adopt po- sitional encoding methods like Laplacian (Dwivedi et al., 2020) and Random Walk (Dwivedi et al., 2021) to further embed global and local graph structure information. The embedding positional encoding can be combined into (like concatenation, addition, etc.) input features and form new embeddings.
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, first use global pooling functions to aggregate features. We can common global pooling methods like SUM, MEAN, MAX or their combination. After global pool, we use MLP layer(s) generate the prediction.
17

---

Under review as a conference paper at ICLR 2023
Algorithm Strided EdgePool
Input: graph G = (V, edge scores w, node pooling ratio Yee, maximum cluster sizes To- Output: pooled graph 9 = (V, E) and inter graph & = (V,E)
INITIALIZE. DISJOINT SFT(G)
remains <- N E +
N is the number of nodes in graph g Sort the edges according to the edge scores w decreasingly.
for E & do
I; t the two endpoints of the edge e ræ, +- FIND INDEX AND SIZE(x) ry, sy +- FIND INDEX AND SIZE(y)
if Fx * ry and (sx sy S T.) then
MERGF(I, y)
remains + remains if remains S N then break
end if end end for V. V, (...
create empty mapping n from cluster index to nodes for V E V do
if FIND INDEX(() then
create new node 0 n[u]
V + VU (5}
end if
end for
for
E & do
I, < the two endpoints the edge e
T f- FIND INDEX(x))
④ +- n FIND INDEX(
< U ((,,0)
end for
for u E V do
n FIND INDEX(U)]
E غ ((,
end for VU
18

---

Under review as a conference paper at ICLR 2023
C.4 ARCHITECTURE VARIANTS
We can replace some GN blocks within Mee layers as an Identity block to reduce the time com- plexity. We call the height/ j is reserved if the intra GN block of height is not replaced by an Identity block. We prefer to reserve a interval of consecutive heights for the Mee layers. (The inter GN blocks between these heights are remained unchanged while others are replaced as identities) By varying the heights reserved in each Mee layers, we can create a large amount of variants of MeGraph model including U-Shaped, Tridge-Shaped and Staircase- -harpe...-
U-Shaped. This variant similar to Graph U-Net (Gao & Ji, 2019). In this U-Shaped variant, the relationship between the number of layers and height h is
2h 1, and there is only one GN block in each layer. We keep the GN block at height j = for each layer at fist half layers, and + for each layer at later half layers. In the middle layer, only the last height = h = (n - 2 has GN block.
keep the GN block at height j
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 height of to j (where < < h).
Stairease-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 from is like the 'downward' staircase. In each layer of this forms, there are GN blocks at height of j to h (where j = i). The second form is the inverted first form. In each layer i of this second forms, there are GN blocks height of h i (where j = i). The last two forms are the mirror of the first and second forms.
D IMPLEMENTATION AND TRAINING DETAILS
We use PyTorch (Paszke et al., 2019) and Deep Graph Library (DGL) (Wang et al., 2019) to imple- ment our method.
We implement S-EdgePool using DGL, extending from the original implementation of EdgePool in the Pytorch Geometric library (PYG) (Fey & Lenssen, 2019). We did Constant optimization over the implementation to speed up the training and inference of the pooling. We further use Taichi-Lang (Hu et al., 2019) to speed up the dynamic node clustering process of S-EdgePool. The practical running time of MeGraph model with height h > 1 after optimization is about 2h times as 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 to their scores) in the EdgePool and S- S-EdgePool.
We run all our experiments V100 GPUs and M40 GPUs. For training the neural networks, use Adam (Kingma & Ba, 2015) as the optimizer. We report the hyper-parameters of the Megraph in Table 5.
For models using GFuN layer as the core GN block, we find it benefits from using layer norms (Ba al., 2016). However, for models using GCN layer as the core GN block, find it performs best when using batch norms (loffe & Szegedy, 2015).
The code will be made public, along with the configuration of hyper-parameters to reproduce our experiments.
E ADDITIONAL EXPERIMENT RESULTS
E TU DATASETS
TU DATASETS 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 M. REDDIT-BINARY, REDDIT- MULTI-5K and PEDDI--MULTI-IEE
They are all graph classification tasks. For more details of each dataset, please refer to the original work (Morris et al., 2020).
19

---

Under review as a conference paper at ICLR 2023
Table 5: Hlyper-paramest 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 + 1.
Graph
Synthetic Datasets
GNN Benchmark
OGB Benchmark
TU Datasets
hyyper-parametenn
Theory
Benchmark
Repeated Runs
10
5
4
5
for each fold
200 (100 for MNIST, CIFRA10)
100 (200 for ENZYMES)
200 for BA*
300 (200) for MCC)
Epochs per run
100
500 for Tree*
0.002
Learning rate
0.002
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
144
300
128
Edge hidden dim (for GFuN)
128
144
300
128
Num Mee
3
4
layers n
Height h
5
5
3 or
Batch size
32
32
128
32
128
Input embedding
False
True
True
True
True
Mean
Mcan Max
Global pooling
Mean
Mean
Mean
Max
Sum
Dataset split (train:val:test)
Original
Original split
10-fold cross
8:1:1
8:1:1
split
validation
Our Megraph the same network structure and hyper-parameters for the same type of dataset. As shown in Table 6, our Megraph achieves about 1% absolute gain than the h=1 Baselines.
Table 6: Tu Dataset Results Part 1. i means the results taken from Chen et al. (2019) (*: The result of GCN on ENZYMES 100 epoch).
Model
MUTAG 1
NCI1
PROTEINS
D&D f
ENZYMES
Average
GCNT GINT
87.20 25.11
83.65 +1.00
75.65 43.24
79.12 #3.07
66.50 +6.0 78.42
89.40
82.70
76.20 42.88
GCN
92.46 26.55
82.55
+0.99 82.53
77.82 14.62
80.56 +2.40
77
15.39
81.51
MeGraph (h=1)
93.01 -6.40 83
81.32 44.08
81.32
13.17
74.83
13.20
82.60
MeGraph
93.07 26.71
83.99
40.98
81.41
43.10
81.24
22.39
75.17
44486
82,98
MeGraphbest
94.12 =3.02
84.40 +1.11
81.68
43.40
82.00
#2.86
75.17
+44.6
83.47
Model
IMDB-B
IMDB-M f
RE-B 1
RE-MSK
RE-M12K
Average
GCN
76.00
50.33
91.15
L.63
56.47
48.71
64.53
MeGraph (/=l)
68.60 #3.53
51.33
42.23
93.10
11.18
57.47
#2.31
51.56 11.06
64.41
MeGraph
72.40 #2.50
51.27
42.71
93.75
11.2
57.69
#:222
52.03
4:0.86
65,43
MeGraphbent
74.30 #2.97
52.00
+:2.9
93.75
1.22
58.45
#:222
52.13 11001
66.13
20

---

Under review as a conference paper at ICLR 2023
Table 7: Comparison between GCN and GFuN on GNN benchmark.
Model
ZINC +
AQSOL
MNIST 1
CIFARIO
PATTERN 1
CLUSTER
GCN GFuN
0.426 40.015
1.397 20.029
90. 140 20.140
51.050
84.672
20.054
47.541 20.940
0.364 40.003
1.386 #0.024
95.560 20. 61.060 20.500
84.845 20.021
58.178 20.079
Table Comparison between GCN and GFuN on OGB-G.
Model
molhiv 1
molbace
molbbbp f
molclintox 1
molsider
GCN GFuN
75,40 +1.29
76.01 +3.31
67.35
+0.96
89.62 22.27
58.08 #0.78
78.54 11.14
71.77 12.15
67.56 +1.11
89.77 +3.48
58.28 10.51
Model
moltox21 f
moltoxcast
molesol 4
molfreesolv +
mollipo +
GCN GFuN
75.11 40.41 75.89 +0.45
64.13 10.52
1.141
+0.02
2.407 #0.15
0.788 10.01
64.49 +0.46
1.079 +0.02
2.017 #0.08
0.768 +0.00
E.2 GFUN
We show our GFuN results on real-world datasets compared to our reproduced GCN in Table 7, 8 and 9. Both GCN and GFuN have the same hyper-parameters except the batch norm for GCN and layer norm for GFuN as stated in Appendix D.
E.3 SYNTHETIC DATASETS
Figure shows the influence of the height h and the number of Mee layers n for MeGraph model on the BAShape and BACommunity datasets. The trend these easier datasets is similar that TreeCycle and TreeGrid but less significant.
E.4 GRAPH THEORY DATASET
We provide a list of tables (from Table 12 to 22) showing the individual results of Table for each possible graph generation method. Each table contains list of variants of models and 5 tasks. Some graph generation methods and task combinations are trivial so we filter them out.
Table 9: Comparison between GCN and GFuN Tu Dataset.
Model
MUTAG 1
NCT1
PROTEINS 1
D&D1 1
ENZYMES t
Average
GCN
92.46 46.55
82.55 +0.99
77.82 +4.52
80.56 42.40
74.17 45.59
81.51
GFuN
93.01 +7.96
82.80 +1.30
80.60 13.83
82.43 42.60
73.00 45.31
82.37
Model
IMDB-B B 1
IMDB-M t
RE-B t
RE-M5K
RE-MI2K 1
Average
GCN GFuN
76.00 44
50.33 +1.89
91.15 +1.63
56.47 +1.54
48.71 +0.88
64.53
68.90 43.42
51.27 43.22
92.25 +1.12
57.53 +1.31
51.54 11.19
64.30
21

---

Under review as a conference paper at ICLR 2023
BAShape
BACommunity
1,000
1.00
0.996
0.99
Mcturacy
Accuracy
0.992
0.98
0.988
0.97
0.96
heightt
neight-22
3
4
10
Num Layer
Num Layer
Figure 6: Node Classification accuracy for MeGraph model on BAShape (left) and BACommunity (right) datasets, varying the height l and the number of Mee layers n.. A clear gap can be observed between heights and The concrete number of accuracy can be found in Table 11.
Table 10: Node Classification accuracy for MeGraph model TreeCycle (above) and TreeGrid (below).
height
3
5
layer
61.48 26.04
76.59
#4.41
91.48
22.70
98.52
#1.69
97.95
#2.32
98.52
=1.35
67.27
81.59
97.39
11.25
98.98
98.75
11.29
98,86
74.43 23.60
90.80
12.61
98.64 +1.11
99.09
+1.11
98.75
11.56
99.09
=0. 85
4
79.55 24.34
93.41
#2.82
99.20 10.73
99.20 10089
99.66
10.73
99,20
1.69
82.73 24.06
93.41
#1.89
99.43 11.05
99.20 +1.35
99.32
11.16
99.32 =0.56
83.18 #3.51
94.09
#2.02
99.43 10.76
99.09 10.85
99.20 11.69
99,20 =0.89
7
84.43 23.74
94.43
12224
99.89 10.34
99.20 1.00
99.20 10.89
99 06 00.73
84.20 43.82
94.20
12.00
98.98
11.19
99.32 40.75
99.66
50.52
99,20 =0.73
84.43 #3.87
94.20
#2.06
99.77
10.45
99.20
1:002
98.98
#1.07
99.32 0.75
10
84.77
23.98
94.43
12.18
99.32
10.75
98.86 #1.14
99.09
11.67
99.66
height
3
5
layer
79. #3.07
91.13
4:2.01
96.85
+1.11
+1.31 97.18
97. 10 11.45
97.42 11.34
2
89.68 11.76
93.55
11.33
98.31 10.76
97.82 11.14
97.42
11.24
97.98
=0.74
90.81 #1.36
96.13
11.48
97.66
+1.22
98.23 40.94
98.87 10.82
98.39
=0.62
91.53 +1.04
96.69
11.05
98.06 +1.03
+1.01 98.55
98.63
+1.08
97.98 11.15
5
93.95 #1.58
96.13
11.76
98.47 +1.17
98.47 40.92
98.31
97.90
94.35 11.25
96.69 11.46
98.06 +1.03
98.31 41.05
98.15
11.20
98.39 1.20
7
94.76 +1.10
97.02 11.44
98.47 40.84
98.47 41.05
98.71 20.74
98.87 =0.00
8
95.08 20.76
97.02
98.55 +1.24
98.87 40.82
98.47
98.71
94.68 41.09
96.94 11.19
98.47 40.43
98. +1.20
98. 10.89
98.39 1.088
10
94.84 #1.21
96.77 11.20
98.47 +0.92
97.98 +:550
98. 11.02
98.23 1.19
22

---

Under review as a conference paper at ICLR 2023
Table 11: Node Classification accuracy for MeGraph model on BAShape (above) and BACommunity (be-
low).
height
1
3
5
6
layer
98.71 11.00
99.14
1..14
99.86
1:043
99.43
1.070
99.43
10095
99.57 =0.91
2
98.71 #1.00
99.29
#0.96
99.57
#0.91
99.71
#0.57
99.57
#0.91
99.57 =0.91
99.00 10.91
99.43
99.86
10.43
99.86
99.86
10.43
99.86
99.00 #0.91
99.71
#0.37
99.86 #0.13
99.86
+0.43
99.43 #0.95
99.71 =0.57
5
99.00 10.91
99.86
10.43
99.86 10.43
99.86 10.43
99.86 10.43
99,4 =0.95
6
99.00 10.91
99.86
99.86 10.43
99.86
99.86 10.43
99.86
99.00 =0.91
99.86
+0.43
99.86 #0.43
99.86 +0.43
99.86
#0.
99,86 =0.13
8
99.00 10.91
99.86
10.43
99.86 10.43
99.86 10.43
99.71
10.57
99.57 0066
99. 00,00 =0.91
99.86
+0.43
99.57
#0.91
99.57
#0.91
99.57
#0.91
99.57 =0.91
10
99.00 20.91
99.71
10.37
99.57
10.91
99.71
10.57
99.86
10.43
99.43
0.95
height
1
2
3
4
5
6
layer
94.93 +1.30
97.00
11.80
96.93
#1.60
97.00
#1.88
97.21
=1
96.86
-.
97.93 10.87
98.36
10.72
98.79 19.79.. 1.0.4
98.79
1.0.66
98.57
1.055
98.50
1.03
98.07 20.91
98.64
#0.87
98.86
#0.91
98.86
+0.80
98.50
#0.98
98.93
98.21 10.97
98.86
10.65
98.86 1.0.00
98.79
1.0.44
99.00
1.073
99.07 0.64
5
98.50 =0.87
98.86
#0.91
99.07 #0.64
99.21 +0.67
99.14
+0.70
99.00 =0.73
6
98.71
98.64
99.07
99.14 1.0.70
99.07
10.85
99.14
98.29 10.91
98.86 10.65
99.07
10.56
98.79 1.056
98.79
1.072
98.86 0.557
8
98.43 #0.77
99.00 #0.47
99. 14 +0.53
98.93 +0.58
99.14
#0.29
99.14 =0.43
9
98.79
99.07
99.21 10.50
99.00
99.29
10.45
99.36
10
98.86 20.73
98.93 20.80
99.21 +0.87
99.14 14 +0.70
99.00
70.73
99.29 -0.64
Table 12: Graph Theory Benchmark results on Grid graphs, results are obtained using our codebase.
Category
Model
SPored
MCC
Diameter
SP..
ECC
n=1
6,60 #00.441
1.50 10.050
22.49 +1.36
26.74 34.347
20.99 #0.232
Basclines (h=l)
n=5
4.18 70.787
1.29
#0.124
5.04 #1.26
15.54
+a 160
20.32 #0.326
n=10
3.70 #0.422
1.33 #0.100
0.737 #0.116
7.24 #0.243
20.32 #0.422
McGraph EdgePool
n=9 (U-Shaped)
2.12
2.04
2.14
2.01
19.39
n=1
1.19
1.24
6.78
5.34
18.00
(h=5, 72=2)
n=5
0.738
1.11
0.616
0.617
13.3
MeGraph
T
0.361 100.182
1.24 1.0.133
0.382
120
0.442
1:0. 130
0.918
1.0.200
S-EdgePool
7.30.3
4.77 4:2.5
1.33
1:0.661
0,349
1.0.044
5,40
1.0.964
3.59
1:0.354
Ablation (h=5, n=
0.3., m=
0.745 #0.316
1.35
10.168
0,385
180
0.552
4:0. 1-0.118
0.622
4.0.00
0.5.. T-=4
1,61 =0
1.28
10.1388
0.458
#00
1.71
#00.035
1.48
#0.283
0.3.3, 7-=4 (X-Pool)
1,03 #0.365
1.50
#0.142
0.626
#0.216
1.70
#0.118
3.44 #0.991
Table 13: Graph Theory Benchmark results on Tree graphs. results are obtained using our codebase.
Category
Model
SP SPased
MCC
Diameter
SP
ECC
==1
5.21 10.209
1.28 10.050
3.77 11.22
17.16 10.
24.63 10.427
Baselines
(I=1)
5=
3.34 10.375
0.405 10.080
0.504
10..00
7.66 10.325
18.11 11.85
n=10
3.16 1..252
0.338
10.048
0.100
10.059
2.28
10 209
14.93 10.300
McGraph EdgePool
n= (U-Shaped)
3.73 #1.01
1.30
40.092
1.36
20.623
4.21 20
25.53 2..44
n=1
1.62 #0.314
0.846
#0.071
0.725
#0.249
6.99 #0.610
12.27 40.848
(/=5, r2=2)
5
0.83 1..667
0.490
10.118
0.084
10.030
1.27
10.0 442
2.87 1.0. 420
McGraph
r==3
0.599 +0.200
0.483 20.081
0.075
20.012
01.497
+:.
0.429
S-EdgePool
M==0.3
0.868
0.413 10.054
0.142 10.047
0.789 10.000
0.534
m.=033 7.=4
0.615
0.418
0.081
0.440
0.436
Ablation (h=5, n=5)
n.=055 7.=4
1.06
0.424 +0.042
0.214 +0.018
1.20
2.03
M==033 7-=4 (X-Pool)
0.666 11.118
0.596 +0.067
0.182 +0.057
1.22 #0
1.11
23

---

Under review as a conference paper at ICLR 2023
Table 14: Graph Theory Benchmark results Ladder graphs, all results obtained using codebase.
Category
Model
SP SPeeed
MCC
Diameter
SP
ECC
n=1
5,06
1.73
1.17
13.20
20.10
Baselines
n=5
0.692
0.734 #0.106
1.39
5.02
19.81
(h=1)
n=10
0.257
0.691 +0.119
1.55 #0.069
1.60
20.40 +0.996
McGrraph
n= (U-Shaped)
1.03 10.177
1.54 #0.242
0.529 +0.265
1.07 =0.075
17.95 =6.49
EdgePool
==1
0.662 +0. 165
0.866
#0.071
1.57 #:0900
2.18
=: 181
6.61 =1.32
(4=5, r2=2)
5
0.251 10.108
0.753
10.091
0.175 1:0.660
0.321
1:0.058
1.18
746
MeGraph
r
0.296 10.070
0.754
10.086
0.226
10.069
0.228
1.0.021
0.285
1.0.099
S-EdgePool
0.3
0.507 10.204
0.768
10.050
0,156
10.053
0.969 1:0.148
0.787
1:0.099
Ablation
n.=03, n,=4
0.297 113
0.712
20.050
0.095
20.046
0.180
1:0.026
0.225
1:0043
(li5,, n=5)
m.=05, r,=4
0.375 19.
0.656
10.064
0,058
10.019
0.612 2 1:0.101
0.464
1:0.
#.=0.3, ra=4 (X-Pool)
0.442 10.108
0.742 10.047
0,158 10,074
0.710 1.0.066
0.765
1..089
Table 15: Graph Theory Benchmark results on Line graphs, all results are obtained using our codebase.
Category
Model
SPased
MCC
Diameter
SP
ECC
Baselines (h=1)
n=l
30.37
0.458 10.035
21.49 18.84
68.99
10.247
75,46
n=
10.55
0.019
10.004
9.97
46.39
78.49
==10
3.29 #0.813
0.012
#0.003
10.18
+10.5a
35.07 =2.71
77.23 #3.42
McGraph EdgePool
n=9 (U-Shaped)
1.95 #1.11
0.355
#0.080
5.79 #:2.22
2.68 =1.12
74.39 4:1..30
n=1
+0.508
0.056
#0.014
7.62 +4.48
10.13 =2.33
45.19 #8.64
(h=5, 22=
5
0.536 1...49
0.016
10.007
1.0.338
1.06 10.341
1:3.82
MeGraph S-EdgePool
r==3
0.349 +0.206
0.013
#0.003
0.724
20.470
0.339 4:0.
1.15
=:0 267
7==0.3
3.65 #2
0.017 +0.000
1.75 #1.63
13.99 #2.00
7.45
#009899
Ablation (f=5, n=5)
n,=033 7.=4
0,283 #0.072
0.019
+0.006
0.584
#0.337
0.515
#00004
1.27
=1.08
m==055 7-=4
1.81 #0.121
0.022 +0.006
0.711
#0.213
2.64 #0.047
3.77
70.763
m,=033 7==4 (X-Pool)
1.06 #0.510
0,101
#0.016
0.767 #0.522
2.29 #0.472
3.89 =1.02
Table 16: Graph Theory Benchmark results on Caterpillar graphs, all results are obtained using our codebase.
Category
Model
SPeed
MCC
Diameter
SPx
ECC
Baselines
n=1
24.24 +1.67
1.25
#0.082
28.62 #2.65
19.08 208
35.32 #0.462
(h=l)
5=5
8.32 12.10
0.561
20.070
4.59
20.346
9.62
20.357
37.01
11.48
n=10
6.40 20.652
0.630
10.127
5.06 20.449
4.06 10
37.87
13:22
McGraph EdgePool
n== (U-Shaped)
6.66 +1.25
1.39
+0.098
8.64 #3.46
2.63 #0.211
32.18
4:4.80
5.04 +1.03
0.685
#0.077
6.08 +1.40
5.40
20.843
28.52
#:2.16
(h=5, 72=2)
n=5
3.44 +1.13
0.533
#0.064
2.00 +1.28
0.921
10.144
5,20
1:1.7
McGraph
n.=3
2.47 #0.529
0.607
#0.081
0.591
=0.172
0.574
20.074
1.21
#:.1488
S-EdgePool Ablation (7m5,, 5)
10=0.3
3.61 +1.36
0.582
#0.052
0.578
2311
1.69
#00672
1.95
#:0.22
10=0.3 7
1.59 #0.444
0.535
#0.091
0.317
#0.104
0.474
100170
1.32
#0.272
0. m
2.00 10.648
0.514
10.040
1.10
1.0.288
0.986
130
2.11
1:0.766
0.33, m (X-Pool)
1.39 40.478
0.602 10.110
0.736
=:0 2000
1.78 #00.244
3.36
#4.873
Table 17: Graph Theory Benchmark results on Lobster graphs, all results obtained using codebase.
Category
Model
SP SPased
MCC
Diameter
SP
BCC
23.92
1.06 186
11.93 +1.22
38.44 +:00000000 065
40.46
Baselines
(h=1)
5
10.89
0.544 20.087
3.66
20.12 40.105
28.81
n=10
7.35
0.631 40.067
2.59
10.52
28.47
MeGraph EdgePool
n (U-Shaped)
6.20 11.13
1.56
20.217
5.65 11.17
7.06 10.071
29.07 12.59
==1
6.00 =1 .28
0.785 20.062
4.35 +1.51
13.75 +0.676
30.49
22.18
(h=5, r2=2)
5=
1.93 20.861
0.543
20.073
1.07
114
2.05
2:0 398
11.39
=5.43
MeGraph
r==3
2.02 1.0.91
0.447
10.123
0.705
10.133
1.66
1...2% 1,0.270
2.23
1.0.378
S-EdgePool
n.=0.3
6.01 11.52
0.521
10.028
0.707
10.202
3.04
1.0 250
2.70
1.0.112
Ablation (1=5,, n=5)
n.m0.3, 7,
1.90 4:0.49
0.489
10.089
0.671
10.165
1.30
4:0 106
2.62
2:0.89
n.=0.5, 7,
3.27 #4.716
0.451
#0.0900
0.941
#0.324
2.82
#:0
4.04
#000227
n.=0.3, 7.=4 (X-Pool)
2.67 1:0.466
0.494
10.100
1.01
10..99
2.79
1.0 344
4.16
1.0.888
24

---

Under review as a conference paper at ICLR 2023
Table 18: Graph Theory Benchmark results on Cycle graphs, all results are obtained using codebase.
Category
Model
SPodd
MCC
Diameter
SP..
ECC
Baselines
n=1
18.75
0,534
40.022
22.35
#0.149
24.07 40.009
21.47
(h=1)
n=5
3.39 #0.304
0.027
#0,00
25.11
#0.325
12.44
=1.35
21.81
==10
0.352 10.060
0.011
10.003
26.54
11:16
8.65 11.02
24.09 10.380
McGrapp
n= (U-Shaped)
0.964 #0.742
0.251
#0.073
22.27
#3.71
0.910
100121
25.32 #:398
EdgePool
[=1
0.594 #0.212
0.074
#0.029
9.11
11.88
4.07
=: 964
21.53
1:0070
(h=5, T2=2)
n=5
0.060 #0.032
0.014
+0.003
13.44
+6.40
0.103
4:0.016
24.05 #00.204
McGraph
r==3
0.066 10.038
0.015
10.006
0.241
10.049
0.090
1.0.037
0.342 186
S-FdgePool
7.=03
2.45 +0.873
0.015
#0.001
0.709
#0.226
8.36
=00261
0.488
#:0. 267
Ablation (li5,, n=5)
n.=033 n,=4
0.060 10.030
0.019
20.003
0.312
20.236
0.226 1:0.050
0.562 200.00
m==055 ra=4
0,451 10,200
0.014
10.004
0,252
10.124
1,05
1:0 524
4.30 11.00
#.=033, ra=4 (X-Pool)
0.494 10.292
0.096 10.028
0.468
10.220
1.08 10.130
0.860 1.0.02
Table 19: Graph Theory Benchmark results on Pseudotree graphs, all results are obtained using our codchase.
Category
Model
SP
MCC
Diameter
SP..
ECC
Baselines
n=1
1.93 #3.239
1.71 +0.281
2.78 #0.058
6.27 #0.004
4.23 #0.084
(h=l)
5=
0.061 +0.024
0,942
#0.094
1.74 #0.299
1.54 #0.006
4.15 #0.086
n=10
0.037 +0.022
0.775
#0.094
1.84 #0.260
0.126
+:0003
4.06 =0.037
MeGraph EdgePool (h=5, 22=2)
(U-Shaped)
20.229
2.55
1:.148
2.53 10.425
1.26 1:0112
4.14 1:0113
0.404 10.098
1.75
13..33
1.50 10.494
2.25
1. 280
3.97
1002270
0.141 1..022
0,999
10.054
1.16 10.069
0.148
10.034
3.12 1.0.202
McGraph
T
0.130 #0.069
0.912 #0.07a
0.669
#0.080
0.115 #:0015
0.797
#:0,099
S-EdgePool Ablation (fumS, n=5)
7==033
0.048 #0.030
0.839 #0.077
0.758
#0.134
0.246 #0.021
0.838
#:0.023
0.3.3, r==4
0.106 10.054
0,814
10.092
0.663
10.078
0.133 10..22
0.845
1.0. 101
m.0055 m.m4
0.071 10.048
1.03 186
0.583
10.068
0.171 1 1.0.038
0.868
1.0.034
0.3..3 7. (X-Pool)
0,564 10.155
0,966 10.172
0,977
10.054
0.611 1 1:0.055
1.10 0:000
Table 20: Graph Theory Benchmark results on Geo graphs, all results are obtained using our codebase.
Category
Model
SPoed
MCC
Diameter
SP
ECC
Baselines
n=l
5.79 #0.630
0.424 #0.023
11.85 #0.301
12.49
+0.055
14,82 :50.056
(I=l)
n=
1.02 20.772
0.407 20.040
8.37
#0.468
5.10
2: 20.435
14,33 100079
==10
0.304 10.
0.404 10.061
9.41 10.759
0.803
1:0.16
14.33 136
MeGraph EdgePool
n= (U-Shaped)
2.99 10.373
0.549
7.66 11.61
3.38 10.55
12.67 1.0.999
n=1
1.60
0.347
10.17 42.004
4.87
11.91
(h=5, 2==2)
5
0.232
0.273
2.70
0.575
6.92
McGraph
r==3
0.188 +0.100
0,288
#0.020
2.04 #0.226
0.562 18.186
2.42 #0.393
S-FdgePool
7==0.3
1.38 #0.617
0.330
#0.025
4.40 #1.15
1.37
#: 083
5.45 #0.465
Ablation (h=5, n=
M,=0.3 n==4
0,230 #0.070
0.231
20.034
1.99
20.549
0.454
+0.057
2.69
=0. 960
0,=0.5, T-=4
0.374 40.148
0.368
40.043
3.95
#0.319
0.777
+:0
4.61
#0.717
7,=0.3 T-=4 (X-Pool)
1.04 #0.502
0.362
+0.031
2.32
#0.440
2.37
+:0 260
5.08 787
Table 21: Graph Theory Benchmark results on BA graphs, all results are obtained using our codebase.
Category
Model
SPaed
MCC
Diameter
SP..
ECC
x=1
0.004 10.001
2,81 20.142
0.092 =0 021
0.128 10.006
Baselines (I=l)
5
0.007 10.002
3.65
20.680
0.098
1:
0.091 10.011
x= 10
0.011 10.006
3.72
10.378
0.2 10.038
0,080 10.004
McGraph
n=9 (U-shape)
0.060 10.021
1.61
=0.20 -0.233
0.219
20.055
0.115 +0.030
EdgePool
0.006 10.004
2.00
20. 00.338
0.1
1: 020
0.084 20.017
(1=5, 7.=2)
5
0.003 10.001
2.00
10.240
004
1:0 011
0.052 10.010
MeGraph
T.=3
0.007 #0.003
1.77
#0.403
0.089
=0.008
0. 0.126 #0.027
S-EdgePool
7.=0.3
0.013 #0.004
1.67
#0.333
0.084 =00008
0.086 #0.005
Ablation (/=5, n=5)
n.=0.3, T,=4
0.011 +0.005
1.42
=0 252
0.073 =0.015
0.163 #0.007
n.=0.5, T,=4
0.008 10.004
1.71
20.403
0.074
=: 009
0.156 10.021
n,.0.3, T.=4 (X-Pool)
0,009 100.08
1.22
2.0224
0.088 1:0 :20
0.076 10.006
25

---

Under review as a conference paper at ICLR 2023
Table 22: Graph Theory Benchmark results on mixed, ER, Caveman Star graphs, results are obtained using our codehase.
MCC
Category
Model
mix
ER
Caveman
Star
ER
Baselines
n=1
3,46 =00.211
2.91 2002006
0.015
20 004
0.144 #0.031
0.316
20.00a
0.346
#0,006
(h-l)
1:0.961
1:0.00
20
3:0021
0.228
20.008
10.00
R=10
3.51 d00323
3,53
20.375
0.018
500006
0.065
#0.005
0.212
20.008
0.414
10.102
McGraph EdgePool
n=9 (U-Shapod)
1.63 #0.078
1.02 20.128
0.091
=0 028
0.125
#0.082
0.200
20.013
0.272
#0.088
R=l
#0.167
0.749
=0 oce
0.018
=0 00G
0.135
#0.000
0.150
20.011
0.320
#0.071
(/=5, T,=2)
n=5
1.11
0.723
0.017
0.152
0.125
0.345
McGraph
7==3
1.07 #0.034
0.714
=0 c88
0.017
=0 002
0.072
#0.016
0.133
=0.013
0.232 20.035
Pool
==003
0.908 10.153
0.627
20 096
0.026
20 007
0.125
1:0 026
0.128 20.014
0.248 20.012
=,033,
1.10
0.709
0.019
0.073
0.129
0.224
Ablation
(1=5,
n-005, 7.44
1.12 20.219
0.722
=0: 198
0.026
2:0 008
0.058
1:00100
0.147 20.017
0.219 10/012
n,003, 7. (X-Pool)
1.01 #0.186
=0. 078
0.029 =0 007
0.107
#0.021
0.119
20.008
0.213 #0.027
26


Reviews:
[{"review_id": "rKyviBG0h5k", "reviewer": "Reviewer_F7rn", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper presents a novel architecture for graph neural networks called MeGraph.\n\nMeGraph builds on the Select-Reduce-Connect framework for graph pooling (Grattarola et al., 2022). \nIn particular, the Select function of a pooling method implicitly induces a bipartite \"inter-graph\" between the input and output graph. By joining all graphs in the pyramid with the corresponding inter-edges, we obtain a pyramidal \"mega-graph\".\n\nBy applying a specifically designed message-passing scheme (called Mee) to the mega-graphs, the authors allow for long-range communication between nodes and inter-layer communication across the pyramid.\nTo do so, the authors extend the SRC framework with an \"Expand\" function that enables backward communication from higher-level (coarse) layers to lower-level (fine) ones.  \n\nThe authors also propose a novel pooling technique that extends EdgePool by allowing for arbitrary coarsening ratios. \n\nFinally, the authors perform an in-depth experimental analysis on several relevant benchmarks, also introducing 5 new synthetic datasets to explicitly test long-range communication in GNNs. \n\nThe results show that the proposed method outperforms relevant baselines. ", "summary_of_the_review": "The work presents several novel and interesting ideas to improve the performance of graph neural networks (especially concerning long-range communication). The proposed method makes smart use of graph pooling and achieves good results in many diverse experiments. \n\nI recommend acceptance, conditional on the authors addressing the minor concerns that I have raised above. ", "strength_and_weaknesses": "**Strengths**: \n- The paper presents numerous novel ideas related to graph neural networks and, more specifically, graph pooling. \n- The design of the proposed method is well-motivated and validated through an ablation study.\n- The performance improvements are significant and, in certain cases, MeGraph outperforms the baselines by a large margin. \n- The experimental section is very thorough with convincing results. \n\n**Weaknesses**: \n- What is the meaning of the following sentence?\n  > In the process stage, an elementary component is a layer shaped like a mirrored E\n- One of the motivations for the Mee layer is overcoming the need of having multiple GCN steps to enable communication between layers of the pyramid (the naive message-passing strategy). However, because each step in Mee diffuses information between adjacent layers of the pyramid, this issue is not really solved (it's just hidden \"inside\" the layer). Have I misunderstood something? Could a more efficient inter-layer communication be achieved via dense self-attention between all pyramid layers?\n- The Expand function is commonly referred to as \"lifting\" the graph. The authors should either justify why they renamed the function or change the name to \"Lift\" (or something along those lines). \n- While the experimental results are interesting, it is not clear if the baselines reported from other works are comparable to the proposed method (in terms of the number of parameters, number of layers, etc). Can the authors comment on this?\n- Since computational cost is an issue (as commented by the authors in Section 6), the authors should report a comparison of the actual computational times of their architecture compared to the baselines.\n- The color-coding of results in Tables 1, 2, and 3 is unclear since the differences between the results are small and the differences in color are barely perceptible. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "iYZPuCvszz", "reviewer": "Reviewer_nn8y", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a method to create multi-scale graphs using graph pooling. In the process, they construct a mega-graph. Their approach applies graph convolutions to intra-graph edges, while convolutions over inter-graph edges transfer information along the hierarchy. They extend graph convolutions and pooling. Their experimental results include 55 synthetic datasets and 26 real datasets. Their results outperform the chosen baseline algorithms. To share the code, they will share a link in an official comment on OpenReview. The article provides ample detail on the datasets, methods and architectures, implementation, and experimental results in the appendix.", "summary_of_the_review": "The paper presents a novel idea that is sustained on state-of-the-art results with respect to baseline alternatives on a range of synthetic and natural datasets. On top of a detailed description, the authors offer to share their computer code. \nI would invite the authors to edit the manuscript to improve their presentation.", "strength_and_weaknesses": "The paper proposes a novel approach to aggregate graph neural networks. State-of-the-art results on various synthetic and natural datasets, incorporating some novel benchmarks. The authors promise that the code is going to be available. Throughout the article, particularly in the appendix, the authors describe the different aspects of and around their proposal. \n\nThere are some minor editing details, which include:\n***” However, if the architecture could inference from a larger scope, e.g., constructing multi-scale graphs in a hierarchy, the shortest path is easier to be\nestimated by aggregating and delivering information from multi-level scopes.” Infer?\n*** convoluations\n*** SEELCT\n*** Is layer n in Figure 3 missing some symbols because they are white? I am talking about the nodes X_i^{n-???}. This problem also happens to the first column of nodes in Figure 4.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "cI6Yddp-gT-", "reviewer": "Reviewer_AA1h", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies graph representation learning and propose MeGraph that could learn multi-scale graph representation. MeGraph enables information exchange across multi-scale graphs, which distinguishes MeGraph from many recent hierarchical graph neural networks.\nTo achieve this goal, MeGraph first uses graph pooling to create multi-scale graphs, then convolve the intra-graph edges and inter-graph edges separately, and finally adopts graph full network (GFuN) and stridden edge contraction pooling (S-EdgePool) for feature extraction. ", "summary_of_the_review": "This paper is an empirical paper working on graph representation learning. The algorithm studied in this paper is quite complicated, it has many technical details and is very hard to digest. By looking at their ablation study results, I am not convinced how MeGraph could improve the model performance. There are baselines and related methods that need to be compared with given this method is also quite complicated and related to many other existing strategies. The impact and contribution of this paper might not enough to reach the bar of ICLR.", "strength_and_weaknesses": "Cons:\n\n1. The algorithm studied in this paper is quite complicated, it has many technical details and is very hard to digest, and requires massive ablation study. By looking at their ablation study results, I am not confident about which part of the proposed modules could really boost the performance. Although the authors provide massive experiment results in the appendix, I would suggest the authors summarize the main take-home messages in bullet points (e.g., by comparing results A with B we know using module C could roughly improve D percent performance.) Keep in mind to make the religious argument and avoid over-claiming the contributions when conducting an ablation study.\n\n2. The multi-scale graph learning issue in this paper could be very related to jumping knowledge [1] and its follow-up works. According to my understanding, the biggest difference is this paper allows information exchange across multi-scale graphs and a different type of graph convolution operator. I think authors might also need to compare with those types of works, instead of just comparing to vanilla GCN and GIN, to help readers better understand the advantages of this work.\n\n[1] Representation Learning on Graphs with Jumping Knowledge Networks  https://arxiv.org/abs/1806.03536\n\n3. The authors mention many related methods, e.g., Graph U-Net and various pooing methods. These methods are expected to compare with the experiment to understand how much MeGraph gains from these baselines. \n\n4. If possible, please also compare with OGB's node classification baseline methods on node classification datasets such as OGB-Arxiv, and OGB-Products. The algorithm developed for OGB node classification tasks is usually more advanced and more challenging.\n\n5. The impact and contributions of this work might not be enough for ICLR. \nAlthough some new techniques are introduced in this paper, these methods are not fundamental enough, are mostly at the ML engineering aspect, and could have very limited impact in practice.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "G5PvTyhvEh", "reviewer": "Reviewer_M2DM", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a mega graph structure and introduces it to a GNN named MeGraph. MeGraph aims to obtain better node representations by enabling repeated information exchange across multi-scale graphs.  Experimental results are provided to demonstrate the effectiveness of MeGraph.", "summary_of_the_review": "Main concerns of the paper are: (1) The technical contribution of the paper is limited. (2) The expressiveness of the proposed model should be analysed theoretically. (3) Baseline models are weak. Comparisons with SOTA models are needed. (4) MeGraph intensely relies on the graph pooling and the GN layer, which are well-studied and have different options. The discussion on the selection of these components is insufficient.\n\nPost-rebuttal: I appreciate the authors' efforts in providing theoretic proof and additional experimental results, which have partially addressed my concerns. However, my concerns on the limited technical contribution and the lack of extensive experiments for the universality of the framework still remain. I have slightly increased the rating.", "strength_and_weaknesses": "Strengths:\n1. The idea of the paper is straightforward and easy to understand.\n2. Experimental evaluation is performed on various tasks and datasets. \n\nWeaknesses:\n1. The proposed framework is incremental, which limits the technical contribution.\nThe three main components, the graph pooling, the GN layer, and the encode-decode architecture, are all adopted from existing methods.\n\n2. The organization of the paper is poor and should be improved.\nGraph pooling is well-known and widely used in GNNs. There is no need to introduce it in great details. It is suggested to put more details of the proposed method in the main body.\n\n3. The expressiveness power of the proposed method needs further theoretical evaluations.\nThe paper aims to address the inability of a GNN node to observe nodes that are farther away than the number of layers n (so-called the under-reaching problem). This problem was first discussed in [1]. In this work, however, introducing large-scale graph representations to update node representations could aggravate over-squashing. Moreover, from the perspective of graph isomorphism, connecting nodes from different scales could harm the ability of GNN to distinguish non-isomorphic graphs. The authors should analyze how powerful the proposed framework is, in theory, to make sure it addresses the under-reaching problem.\n\n4. Experimental study should be enhanced.\n(1) The proposed method only compares with basic GNNs, such as GCN and GIN. More SOTA methods should be added as baselines. For instance, [2] and [3] also try to extend receptive fields by rewiring the input graph. \n(2) The selection of each component in MeGraph could significantly influence the performance. The discussion on the selection of each component, such as the pooling method and the GN block, is insufficient. \n(3) Since the GN block in the proposed method is realized as a GFuN layer, the authors should report the experimental results of GFuN to clarify the performance improvements that come from the proposed MeGraph.\n\n[1] Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In International Conference on Learning Representations, 2021.\n[2] Topping J, Di Giovanni F, Chamberlain B P, et al. Understanding over-squashing and bottlenecks on graphs via curvature. In International Conference on Learning Representations, 2022.\n[3] Brüel-Gabrielsson R, Yurochkin M, Solomon J. Rewiring with positional encodings for graph neural networks. arXiv preprint arXiv:2201.12674, 2022.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject