Challenges

A) Graph Signal Processing 

B) Graph Neural Networks

• Limited Bandwidth: GNNs are low-pass graph filters which ignore information that would be valuable at the middle and high frequencies. Graph signal processing, which uses the spectral decomposition of the graph Laplacian matrix to build a function of frequency (eigenvalue) and defines it as a graph filter, is the foundation of the study of GNNs. By designing the filter function appropriately, the filter can be interpreted in the spatial domain, allowing for the aggregation of information from a node’s multi-hop neighborhood to update its feature. There is a tendency to build GNNs only in the spatial domain without considering their spectral properties for efficiency, generality, and flexibility. But, this fact may result in spatial-designed GNNs that only consider low frequency information of graph signals, thereby ignoring potentially useful middle and high frequency bands. In practice, spectral GNNs and spatial GNNs can be distinguished.

• Scaling GNNs:  Scaling GNNs to large-scale graphs remains a significant challenge, which limits their practical application in large-scale application settings. In practice, data are independent, and the parameters are optimized by mini-batch gradient descent. But, the recursive neighbor aggregation scheme used in GNNs requires a full-graph gradient descent approach during the training step. This fact reaches in important computational and memory costs, particularly when training GNNs on large-scale graphs. The strategies to address the scalability issues can be classified into two categories: Sampling-based methods and decoupling-based methods. Sampling-based methods construct mini-batches for training by selecting nodes from the graph. Node-wise, layer-wise, and subgraph sampling strategies are generally the three categories into which sampling-based techniques are classified. However, due to the unavoidable loss of edges during sampling, this approach can lead to a significant loss of information. Decoupling-based methods  eliminate nonlinear transformations between consecutive layers, resulting in a reduction in expressive power. Sampling-based methods and decoupling-based methods, which are primarily intended for spatial GNNs, essentially employ low-pass filters as its graph filter function, ignoring middle and high frequency information.

• Over-Smoothing: GNNs have better experimental results in the shallow layer case, and instead do not work well in the deep layer case. This is due to the fact that during the GNNs training process, the hidden layer representation of each node tend to converge to the same value as the number of layers increases. This phenomenon is called over-smoothing (Zhao et al., 2020).

• Over-Squashing: Over-squashing is a more recent and less understood problem than over-smoothing. A graph learning problem has long-range dependencies when the outputs of GNNs depend on features of interacting distant nodes. In that scenario, information from non-adjacent nodes should be propagated through the network without distortion. This phenomenon is called over-squashing (Alon et al., 2021).

C) Graph Spectral Clustering

References

L. Zhao, L. Akoglu, "PairNorm: Tackling oversmoothing in GNNs",  International Conference on Learning Representations, ICLR 2020, 2020.

U. Alon, E. Yahav, "On the bottleneck of graph neural networks and its practical implications", International Conference on Learning Representations, ICLR 2021, 2021.