Abstract

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

Challenge: Capturing Long-Range Interactions

Local-aware message-passing GNNs struggle to capture LRIs.
The receptive field is limited (illustrated for node A, for different local message passing steps).

From Multi-scaled Graph to Mega Graph

Most existing hierarchical methods like Graph U-Nets [1] and HGNet [2] successfully enlarged the nodes’ receptive fields by building the hierarchy. They downsample the graph by performing Graph poolings that consist of SELECT, CONNECT, and REDUCE steps. It forms a Graph Pyramid which involves multi-scaled graphs derived from iterative graph pooling, with the height indicating different scales.

However, such hierarchy-focused structures failed to keep multiple rounds of local aggregation in the same granity.

Instead, we propose to view the graph hierarchy as a single mega graph, where

- Nodes: the nodes from graphs of each scale.
- IntraEdges: edges within graphs of each scale, the local connections.
- InterEdges: edges between graphs of consecutive scales, the hierarchical connections.

Message passing over such mega graph performs both local and hierarchical information aggregations.

Basic Notations

Mega Graph Message Passing

We proposed the MeGraph model to dynamically build the mega graph and perform specialized message passing on that. The overall architecture is illustrated below, where blue and green circles represent features of intra- and inter-graphs, respectively.

In this figure, the horizontal and vertical directions represent the interaction among the local structure (intra-graph) and graph hierarchy (inter-graph) respectively. MeGraph consists of three parts:

Encoding: Apply (differentiable) graph poolings to construct the mega graph.
Processing: Stack Mee layer n times to repeat both local and hierarchical information aggregation.
Decoding: Transform the resulting features into task-specific representations using readout functions.

Alternating Local and Hierarchical Aggregation

The Mee layer performs both local and hierarchical information aggregation. We design a bidirectional pathway (powered by residual connections) to facilitate the hierarchical information aggregation process. The detailed architecture is illustrated below, where the grey and golden arrows represent the intra and inter-GN blocks.

Steps of Mee layer (rightward, downward, and upward in the figure direction):

Performs message passing on the local structure of graphs at each scale using intra-GN blocks (weights can be shared among different scales).
Applies cross-updates sequentially from lower to higher levels, accumulating information along the pathway to pass to the higher hierarchy. The cross-update utilizes inter-GN blocks to exchange information between consecutive heights.
Reversed direction of Step 2.

Graph Pooling Choices and Improvements

There are many graph pooling methods, we mainly use EdgePool [3] for our experiments due to its simplicity and ability to preserve the graph’s connectivity.

However, EdgePool only allows merging two nodes in the pooling, limiting the pooling ratio (η) for the node to ≥50%. We further propose Strided-EdgePool (S-EdgePool) to overcome this, which dynamically tracks the clusters of nodes created by the contraction of selected edges without increasing the time complexity.

Experiments

We established a Graph Theory Benchmark for LRIs

5 tasks related to graph theory (e.g. shortest path distance)
14 random graph generation methods (e.g. random tree graph)
Sizes: Medium (300 graphs, 20 <= |V| <= 50), Large (500 graphs, 100 <= |V| <= 200)

The MeGraph model significantly outperforms the no-hierarchy and hierarchy-based baselines in both medium and large settings.

The comparison among S-EdgePool variants also suggests the importance of allowing a customizable pooling ratio (η) and pooling stride (τ, the maximal number of nodes to be merged).

We achieved better or comparable performance than previous SOTA on LRGB [4]

MeGraph shows generality on widely adopted real-world benchmarks

Ablation Study

The figure shows the node classification accuracy for MeGraph on two synthetic datasets (TreeCycle and TreeGrid).

By varying the number of Mee layers n and the height h:
- Increasing height shows better improvements than increasing the number of layers.
- Both hierarchy and locality are indispensable.
By varying the graph pooling methods (EdgePool, Louvain, Random):
- A well-structured hierarchy crafted by suitable graph pooling methods enhances MeGraph’s ability to harness hierarchical information.
- Despite the disruption from a randomly constructed hierarchy, the MeGraph model effectively taps into the local structure of the original graph.

Conclusions

MeGraph excels in Long-Range Interaction (LRI) tasks and shows generality over widely adopted GNN benchmarks, affirming the essential role of both local and hierarchical structures.
MeGraph demonstrates robust improvement over the baselines, across various graph pooling methods and GN block choices.
The mega graph offers a novel viewpoint to the plain graph and leads to a natural way of repeating local and hierarchical information fusion.

For more details, please read our paper.

Cite Us By

@inproceedings{dong2023megraph,

title={MeGraph: Capturing Long-Range Interactions by Alternating Local and Hierarchical Aggregation on Multi-Scaled Graph Hierarchy},

author={Dong, Honghua and Xu, Jiawei and Yang, Yu and Zhao, Rui and Wu, Shiwen and Yuan, Chun and Li, Xiu and Maddison, Chris J and Han, Lei},

booktitle={Thirty-seventh Conference on Neural Information Processing Systems},

year={2023}

}

References

[1] Hongyang Gao and Shuiwang Ji. Graph u-nets. In international conference on machine learning, pages 2083–2092. PMLR, 2019.

[2] Ladislav Rampášek and Guy Wolf. Hierarchical graph neural nets can capture long-range interactions. In 2021 IEEE 31st International Workshop on Machine Learning for Signal Processing (MLSP), pages 1–6. IEEE, 2021.

[3] Frederik Diehl, Thomas Brunner, Michael Truong Le, and Alois Knoll. Towards graph pooling by edge contraction. In ICML 2019 workshop on learning and reasoning with graph-structured data, 2019.

[4] Vijay Prakash Dwivedi, Ladislav Rampasek, Mikhail Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, and Dominique Beaini. Long range graph benchmark. In Thirty-sixth Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2022.