MGNNI: Multiscale Graph Neural Networks with Implicit Layers

Juncheng Liu, Bryan Hooi, Kenji Kawaguchi, Xiaokui Xiao

Introduction

Implicit Graph Neural Networks (IGNNs) have emerged as a powerful alternative to standard message-passing GNNs. By defining node representations as the equilibrium of a fixed-point equation rather than a sequence of discrete layers, IGNNs theoretically offer "infinite depth" with constant memory cost. However, this theoretical promise often fails in practice when tasks require long-range reasoning.

The Convergence-Range Tradeoff

The primary limitation of existing IGNNs lies in their stability requirements. To ensure that the iterative solvers used to find the fixed point actually converge, these models employ a contraction factor ($\gamma < 1$). This factor creates a fundamental tradeoff: while it ensures stability, it also causes the influence of distant nodes to decay exponentially.

The norm of the change of equilibrium decays exponentially as nodes get further apart, illustrating the limited effective range of standard IGNNs.

As shown in the figure above, the "effective range" of a standard IGNN is surprisingly small. Even with a high contraction factor, the signal from a node 20 hops away may vanish into numerical noise, rendering the "infinite depth" claim practically irrelevant for tasks requiring long-distance information propagation.

MGNNI: Multiscale Implicit Layers

To overcome this range limitation, the authors propose MGNNI (Multiscale Graph Neural Networks with Implicit Layers). The core innovation is to move beyond simple 1-hop message passing within the implicit framework.

Multiscale Propagation

Instead of relying solely on the normalized adjacency matrix $S$, MGNNI utilizes powers of the matrix, $S^m$. By setting $m > 1$, a single iteration of the implicit solver can propagate information across $m$ hops. This effectively "multiplies" the model's reach without compromising the convergence stability of the underlying solver. If a standard IGNN can see 20 hops, an MGNNI with scale $m=4$ can theoretically see 80 hops with the same convergence stability.

Parallel Architectures and Attention

MGNNI runs multiple implicit propagation modules in parallel, each operating at a different scale (e.g., $M = \{1, 4, 8\}$). To combine these different resolutions, the model employs a learnable attention mechanism. This allows the network to adaptively determine which scale is most relevant for each node, which is particularly useful in graphs with complex, non-uniform topologies.

Experimental Evaluation

The effectiveness of MGNNI was tested across several benchmarks, focusing on its ability to handle long-range information and heterophilic graph structures.

Long-Range Reasoning

On synthetic "Chains" datasets, where the goal is to classify nodes based on information located many hops away, MGNNI demonstrated significant robustness. While the performance of standard IGNNs and explicit GNNs drops sharply as the chain length increases, MGNNI maintains high accuracy by leveraging its multiscale "jumps."

MGNNI maintains superior accuracy on long-range synthetic tasks compared to baselines as the distance (chain length) increases.

Heterophilic and Inductive Tasks

The model also achieved state-of-the-art results on real-world heterophilic datasets (like Chameleon and Squirrel) and the PPI dataset. In heterophilic graphs, where immediate neighbors often belong to different classes, the ability to look further into the neighborhood is critical for finding relevant structural patterns. MGNNI's attention-based fusion of multiple scales proved superior to single-scale baselines, outperforming the next best implicit model (EIGNN) by nearly 8% on the Squirrel dataset.

Conclusion

MGNNI addresses a critical flaw in implicit GNNs by identifying and mitigating the convergence-range tradeoff. By introducing multiscale propagation and adaptive fusion, it transforms the theoretical "infinite depth" of implicit layers into a practical tool for long-range graph reasoning, setting new performance standards across both synthetic and real-world benchmarks.

Summary updated

Abstract

Recently, implicit graph neural networks (GNNs) have been proposed to capture long-range dependencies in underlying graphs. In this paper, we introduce and justify two weaknesses of implicit GNNs: the constrained expressiveness due to their limited effective range for capturing long-range dependencies, and their lack of ability to capture multiscale information on graphs at multiple resolutions. To show the limited effective range of previous implicit GNNs, we first provide a theoretical analysis and point out the intrinsic relationship between the effective range and the convergence of iterative equations used in these models. To mitigate the mentioned weaknesses, we propose a multiscale graph neural network with implicit layers (MGNNI) which is able to model multiscale structures on graphs and has an expanded effective range for capturing long-range dependencies. We conduct comprehensive experiments for both node classification and graph classification to show that MGNNI outperforms representative baselines and has a better ability for multiscale modeling and capturing of long-range dependencies.
BibTeX
@inproceedings{liu2022mgnni,
  author = {Juncheng Liu and Bryan Hooi and Kenji Kawaguchi and Xiaokui Xiao},
  title = {{MGNNI: Multiscale Graph Neural Networks with Implicit Layers}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=SMdL04IqSGu},
}
Figure