Handling Over-Smoothing and Over-Squashing in Graph Convolution With Maximization Operation.

Area of Science:

• Artificial Intelligence
• Machine Learning
• Graph Neural Networks

Background:

• Graph convolutional networks (GCNs) have shown success but struggle with over-smoothing and over-squashing, limiting long-distance node information modeling.
• Existing solutions using linear combinations of neighborhood features offer only a trade-off between these two problems.

Purpose of the Study:

• To introduce a novel graph convolution operation, Maximization-based Graph Convolution (MGC), designed to effectively address over-smoothing and over-squashing.
• To develop an efficient, linear-complexity approximated model for large-scale graph learning using MGC.

Main Methods:

• MGC employs an elementwise maximizing operation, unlike linear combinations, to aggregate information from various neighborhood powers.
• An efficient approximation of MGC is developed to enable scalability for large graph datasets.

Main Results:

• Theoretical and empirical analyses confirm MGC's effectiveness in handling over-smoothing and over-squashing.
• Extensive experiments demonstrate MGC's competitive performance, scalability, and efficiency, even on graphs with over 100 million nodes.
• The proposed models achieve strong results with lower computational complexity compared to existing methods.

Conclusions:

• MGC presents a simple yet effective solution to fundamental limitations in GCNs.
• The developed MGC models are suitable for large-scale graph learning tasks, offering improved performance and efficiency.