Empowering Deep Learning on Graphs: Tackling Over-smoothing and Over-squashing = 그래프 기반 딥러닝 강화: 오버스무딩과 오버스쿼싱 문제 해결

다국어 초록 (Multilingual Abstract)

Graphs are ubiquitous data structures, prevalent from e-commerce platforms to complex molecular structures, abstracting the rich interactions between individual entities. The increasing reliance on graph-structured data in diverse real-world applications necessitates the development of effective representations for graph nodes. Recent advancements in deep learning on graphs, particularly through Graph Neural Networks (GNNs), have led to significant breakthroughs in various fields by enabling the learning of these representations. However, deep learning on graphs still faces fundamental challenges.
Firstly, GNNs operate by propagating information through the connected neighborhood structure of the graph. While increasing the number of GNN layers allows for the capture of higher-order neighborhood information, this iterative aggregation process can lead to the over-smoothing problem, where the representations of different nodes become increasingly similar and lose their distinctiveness. This phenomenon can be understood by viewing the diffusion process inherent in GNNs.
Secondly, real-world graphs often contain critical long-range dependencies and interactions. Nodes in these graphs face limitations in effectively receiving information from distant nodes due to the over-squashing problem. Over-squashing arises as a bottleneck, where a node's fixed-dimensional feature vector must compress an exponentially growing amount of information originating from its expanding receptive field in deeper layers.

This thesis proposes novel approaches to tackle these two critical issues: over-smoothing and over-squashing. To mitigate over-smoothing, we propose new architectures for both GNNs and Transformers. For GNNs, we draw inspiration from reaction-diffusion equations to design a novel layer incorporated into our proposed method, GREAD, which prevents feature convergence by balancing smoothing and sharpening. We also explore over-smoothing in the context of Transformers, interpreting their self-attention mechanism as a graph filter, and propose Graph Filter-based Self-Attention as a novel mechanism to alleviate this problem in Transformer models.
To address over-squashing in GNNs, we present two distinct methods. Recognizing limitations in existing graph rewiring techniques, our first method, PANDA, introduces an expanded width-aware message passing framework designed to overcome topological bottlenecks and over-squashing. Our second method, Fractal-Inspired Message Passing with Fractal Nodes, uses a fractal concept to improve message passing and enhance the expressive power of GNNs, thereby facilitating more effective propagation of global information and mitigating the decay of signal propagation associated with over-squashing.

As the scale and complexity of global data continue to grow, the relationships abstracted by graph structures are becoming increasingly complex. The research presented in this thesis aims to develop more effective graph representations and enhance the scalability of deep learning models by effectively addressing over-smoothing and over-squashing. This will enable these models to process complex graph relationships more efficiently and make a positive impact across a wide range of domains.

국문 초록 (Abstract)

그래프는 전자상거래부터 분자 구조에 이르기까지 어디에나 존재하며, 개별 노드 간의 상호작용을 추상화합니다. 그래프 구조 데이터를 기반으로 하는 다양한 실제 애플리케이션은 그래프 노드의 효과적인 표현을 필요로 합니다. 최근 그래프에 대한 딥러닝은 다양한 휴리스틱 접근법을 통해 그래프 표현을 학습함으로써 다양한 분야에서 획기적인 발전을 이루었습니다. 그러나 그래프 딥러닝은 몇 가지 근본적인 과제에 직면합니다. 첫째, 그래프 신경망(GNN)은 연결된 이웃(neighborhood)을 통해 정보를 전파합니다. GNN 계층의 수를 늘리면 고차 이웃을 포착할 수 있지만, 이러한 반복적인 전파는 노드 표현이 이웃 간에 구분되지 않는 오버스무딩(over-smoothing) 문제를 야기합니다. 둘째, 실제 그래프는 종종 중요한 장거리 상호작용을 포함합니다. 노드는 오버스쿼싱(over-squashing) 문제로 인해 멀리 떨어진 노드로부터 정보를 수신하는 데 한계에 직면합니다. (over-squashing) 문제는 고정 차원 벡터가 멀리 떨어진 이웃으로부터 기하급수적으로 증가하는 정보의 병목 현상이 되는 문제입니다.

본 논문에서는 1) 오버스무딩(over-smoothing)와 2) 오버스쿼싱(over-squashing) 문제를 해결하기 위한 접근 방식들을 제안합니다. 먼저, 물리 관점에서 그래프 신경망을 열 확산 과정으로 바라보고 오버스무딩을 해결하기 위한 동기를 갖습니다. 반응-확산 방정식에서 영감을 받아 새로운 그래프 신경망 아키텍처를 제안하여 오버스무딩 문제를 완화합니다. 또한, 우리는 트랜스포머의 셀프 어텐션을 그래프로 해석하고 오버스무딩가 트랜스포머에도 있다는 것을 소개하고 이 문제를 완화하기 위한 새로운 자기 주의 메커니즘을 제안합니다. 오버스쿼싱의 경우, 기존의 재배선 방법들이 무분별하게 엣지를 추가하여 기존 그래프 구조를 손상하는 문제를 지적하며 시작합니다. 우리는 노드 너비 확장을 통해 오버스쿼싱 문제를 해결하는 새로운 그래프 신경망 아키텍처를 설계합니다. 또한, 우리는 프랙탈 개념에서 영감을 받아, 장거리 상호작용을 위해 오버스쿼싱을 완화하면서 더 전역적인 정보를 전파시킬 수 있도록하는 방법을 설계합니다.

전세계적으로 수집하는 데이터의 규모와 다양성이 증가함에 따라, 개별 노드 간의 관계는 규모와 복잡성 측면에서 2차적으로 증가합니다. 이 연구들은 그래프에서 더 나은 표현을 개발하고 딥러닝의 확장성을 향상시킴으로써 이러한 관계를 효과적으로 처리하고 광범위한 영역에 걸쳐 긍정적인 영향을 미치는 것을 목표로 합니다.

목차 (Table of Contents)

• List of Figures vi
• List of Tables ix
• Abstract xiii
• 1 Introduction 1
• 1.1 Motivation and Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
• 1.1.1 The Over-smoothing Problem . . . . . . . . . . . . . . . . . . . . . . . 1
• 1.1.2 The Over-squashing Problem . . . . . . . . . . . . . . . . . . . . . . . 2
• 1.1.3 Two Distinct Challenges . . . . . . . . . . . . . . . . . . . . . . . . . 2
• 1.2 Thesis Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
• 1.2.1 Addressing Over-smoothing . . . . . . . . . . . . . . . . . . . . . . . . 2
• 1.2.2 Addressing Over-squashing . . . . . . . . . . . . . . . . . . . . . . . . 3
• 1.3 Impact and Significance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
• 1.4 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
• 2 Over-smoothing I 5
• 2.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
• 2.2 Preliminaries & Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . 7
• 2.2.1 Reaction-Diffusion Equations . . . . . . . . . . . . . . . . . . . . . . . 7
• 2.2.2 Graph Neural Networks . . . . . . . . . . . . . . . . . . . . . . . . . . 8
• 2.2.3 Neural Ordinary Differential Equations (NODEs) . . . . . . . . . . . 9
• 2.3 Proposed Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
• 2.3.1 Overview of GREAD . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
• 2.3.2 Soft Adjacency Matrix Generation . . . . . . . . . . . . . . . . . . . . 10
• 2.3.3 Reaction-diffusion Layer . . . . . . . . . . . . . . . . . . . . . . . . . . 11
• 2.3.4 Training Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
• 2.3.5 Comparison with GNNs . . . . . . . . . . . . . . . . . . . . . . . . . . 13
• 2.4 Computational Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
• 2.5 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
• 2.5.1 Node Classification on Real-world Datasets . . . . . . . . . . . . . . . 14
• 2.5.2 Over-smoothing and Dirichlet Energy . . . . . . . . . . . . . . . . . . 17
• 2.5.3 Different Homophily Levels . . . . . . . . . . . . . . . . . . . . . . . . 22
• 2.5.4 Training Time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
• 2.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
• 2.7 Appendix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
• 2.7.1 Search Space of Hyperparameter . . . . . . . . . . . . . . . . . . . . . 25
• 2.7.2 Best Hyperparameters in Section 2.5.1 . . . . . . . . . . . . . . . . . . 25
• 3 Over-smoothing II 29
• 3.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
• 3.2 Background & Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
• 3.2.1 Self-Attention in Transformers . . . . . . . . . . . . . . . . . . . . . . 32
• 3.2.2 Self-Attention and Graph Convolutional Filter . . . . . . . . . . . . . 32
• 3.2.3 Over-smoothing in GCNs and Transformers . . . . . . . . . . . . . . . 33
• 3.3 Graph Filter-based Self-Attention Layers . . . . . . . . . . . . . . . . . . . . 34
• 3.4 Properties of GFSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
• 3.5 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
• 3.5.1 Experiments on Natural Language Understanding . . . . . . . . . . . 38
• 3.5.2 Experiments on Causal Language Modeling . . . . . . . . . . . . . . . 39
• 3.5.3 Experiments on Vision Transformers . . . . . . . . . . . . . . . . . . . 39
• 3.5.4 Experiments on Graph-level Tasks . . . . . . . . . . . . . . . . . . . . 40
• 3.5.5 Experiments on Automatic Speech Recognition . . . . . . . . . . . . . 41
• 3.5.6 Experiments on Code Classification . . . . . . . . . . . . . . . . . . . 43
• 3.6 Discussion on Runtime Overheads . . . . . . . . . . . . . . . . . . . . . . . . 44
• 3.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
• 3.8 Appendix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
• 3.8.1 Oversmoothing and Additional Visualizations . . . . . . . . . . . . . . 46
• 3.8.2 Analysis of Frequency Responses with Visualizations . . . . . . . . . . 47
• 3.8.3 Frequency Analyses in the Singular Value Domain . . . . . . . . . . . 47
• 3.8.4 Matrix Polynomial vs. Graph Fourier Transform . . . . . . . . . . . . 49
• 3.8.5 Proof of Theorem 3.3.1 . . . . . . . . . . . . . . . . . . . . . . . . . . 49
• 3.8.6 Proof of Theorem 3.4.1 . . . . . . . . . . . . . . . . . . . . . . . . . . 50
• 3.8.7 Implementation of GFSA . . . . . . . . . . . . . . . . . . . . . . . . . 51
• 3.8.8 Comparison with Actual and Approximated High-order Terms . . . . 51
• 3.8.9 Natural Language Understanding . . . . . . . . . . . . . . . . . . . . 52
• 3.8.10 Sensitivity to K . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
• 3.8.11 Causal Language Modeling . . . . . . . . . . . . . . . . . . . . . . . . 54
• 3.8.11.1 Detailed Experimental Settings . . . . . . . . . . . . . . . . . 54
• 3.8.11.2 Sensitivity to K . . . . . . . . . . . . . . . . . . . . . . . . . 55
• 3.8.12 Image Classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
• 3.8.12.1 Detailed Experimental Settings . . . . . . . . . . . . . . . . . 55
• 3.8.12.2 FLOPs & Throughput . . . . . . . . . . . . . . . . . . . . . . 55
• 3.8.12.3 Sensitivity to K . . . . . . . . . . . . . . . . . . . . . . . . . 56
• 3.8.12.4 Additional Comparison with SOTA Models . . . . . . . . . . 57
• 3.8.12.5 Additional Experiments with Guo et al. [1]’s setting . . . . . 57
• 3.8.13 Automatic Speech Recognition . . . . . . . . . . . . . . . . . . . . . . 58
• 3.8.13.1 Detailed Experimental Settings . . . . . . . . . . . . . . . . . 58
• 3.8.13.2 Training Curve . . . . . . . . . . . . . . . . . . . . . . . . . . 61
• 3.8.14 Graph-level Tasks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
• 3.8.14.1 Detailed Experimental Settings . . . . . . . . . . . . . . . . . 61
• 3.8.15 Code Defect Detection . . . . . . . . . . . . . . . . . . . . . . . . . . 62
• 3.8.15.1 Detailed Experimental Settings . . . . . . . . . . . . . . . . . 62
• 3.8.15.2 Case Study . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
• 3.8.15.3 Code Clone Detection . . . . . . . . . . . . . . . . . . . . . . 64
• 3.8.15.4 Time Complexity and Empirical Runtime Analysis . . . . . . 65
• 3.8.16 Inference Time Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . 68
• 3.8.17 Results of the Strategy for Efficiency . . . . . . . . . . . . . . . . . . 70
• 3.8.18 GFSA in Linear Transformers . . . . . . . . . . . . . . . . . . . . . . 71
• 4 Over-squashing I 72
• 4.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
• 4.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
• 4.2.1 Message Passing Neural Networks . . . . . . . . . . . . . . . . . . . . 76
• 4.2.2 Over-squashing Problem . . . . . . . . . . . . . . . . . . . . . . . . . 76
• 4.3 Proposed Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
• 4.3.1 Motivation and Design Rationale . . . . . . . . . . . . . . . . . . . . . 78
• 4.3.2 Expanded Width-Aware Message Passing . . . . . . . . . . . . . . . . 78
• 4.3.3 Properties of PANDA . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
• 4.4 Why Does PANDA Mitigate Over-squashing? . . . . . . . . . . . . . . . . . 81
• 4.5 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
• 4.6 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
• 4.7 Limitations and Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . 91
• 4.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
• 4.9 Appendix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
• 4.9.1 Signal Propagation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
• 4.9.2 Dirichlet Energy and Over-smoothing . . . . . . . . . . . . . . . . . . 92
• 4.9.3 Graph Centrality Metrics . . . . . . . . . . . . . . . . . . . . . . . . . 92
• 4.9.4 Experimental Details for Graph Classification . . . . . . . . . . . . . 93
• 4.9.5 Experiments on Node Classification . . . . . . . . . . . . . . . . . . . 94
• 4.9.6 Experiments on Long Range Graph Benchmark . . . . . . . . . . . . 96
• 5 Over-squashing II 98
• 5.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
• 5.2 Background & Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
• 5.3 Fractal-Inspired Message Passing with Fractal Nodes . . . . . . . . . . . . . 102
• 5.4 Properties and Effectiveness of Fractal Nodes . . . . . . . . . . . . . . . . . 105
• 5.4.1 Why Fractal Nodes Improve Message Passing . . . . . . . . . . . . . . 105
• 5.4.2 Model Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
• 5.4.3 Comparison with Prior Work . . . . . . . . . . . . . . . . . . . . . . . 107
• 5.5 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
• 5.5.1 Analysis on Over-squashing (Q1) . . . . . . . . . . . . . . . . . . . . . 108
• 5.5.2 Expressive Power of Fractal Nodes (Q2) . . . . . . . . . . . . . . . . . 109
• 5.5.3 Experiments on Graph Benchmarks (Q3) . . . . . . . . . . . . . . . . 110
• 5.5.4 Runtime Comparison (Q4) . . . . . . . . . . . . . . . . . . . . . . . . 112
• 5.5.5 Ablation, Sensitivity, and Additional Studies . . . . . . . . . . . . . . 113
• 5.6 Limitations and Future Directions . . . . . . . . . . . . . . . . . . . . . . . . 114
• 5.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
• 5.8 Appendix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
• 5.8.1 Proof of Theorem 5.3.1 . . . . . . . . . . . . . . . . . . . . . . . . . . 114
• 5.8.2 Theoretical Analyses . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
• 5.8.2.1 Effective Resistance with Fractal Nodes . . . . . . . . . . . . 116
• 5.8.2.2 Proof of Theorem 5.4.1 . . . . . . . . . . . . . . . . . . . . . 116
• 5.8.2.3 Proof of Theorem 5.4.2 . . . . . . . . . . . . . . . . . . . . . 117
• 5.8.2.4 Total Resistance Analysis . . . . . . . . . . . . . . . . . . . . 118
• 5.8.3 Implementation Details . . . . . . . . . . . . . . . . . . . . . . . . . . 119
• 5.8.4 Fractal Structure and Node Centrality . . . . . . . . . . . . . . . . . . 120
• 5.8.5 Detailed Discussion on Section 5.5.2 . . . . . . . . . . . . . . . . . . . 121
• 5.8.6 Experimental Details on Graph-level Tasks . . . . . . . . . . . . . . . 123
• 5.8.6.1 Dataset Description . . . . . . . . . . . . . . . . . . . . . . . 123
• 5.8.6.2 Hardware Specifications and Libraries . . . . . . . . . . . . . 124
• 5.8.6.3 Setup & Hyperparameters . . . . . . . . . . . . . . . . . . . 124
• 5.8.7 Experimental Details on Large-scale Node Classification . . . . . . . . 126
• 5.8.7.1 Implementation for Node Classification . . . . . . . . . . . . 126
• 5.8.7.2 Dataset Description . . . . . . . . . . . . . . . . . . . . . . . 126
• 5.8.7.3 Setup & Hyperparameters . . . . . . . . . . . . . . . . . . . 127
• 5.8.8 Scalability Analysis of of Fractal Node . . . . . . . . . . . . . . . . . . 128
• 5.8.9 Ablation, Sensitivity and Additional Studies . . . . . . . . . . . . . . 128
• 5.8.9.1 Impact of HPF . . . . . . . . . . . . . . . . . . . . . . . . . . 128
• 5.8.9.2 Impact of type of ω(ℓ)_c . . . . . . . . . . . . . . . . . . . . . . 130
• 5.8.9.3 Comaprison to Graph Rewiring Methods . . . . . . . . . . . 130
• 5.8.9.4 Comaprison to Virtual Node Methods . . . . . . . . . . . . . 130
• 5.8.9.5 Sensitivity to C . . . . . . . . . . . . . . . . . . . . . . . . . 130
• 5.8.9.6 Additional Results on All-layer Fractal Node Message Passing130
• 5.8.10 Effective Resistance and Signal Propagation . . . . . . . . . . . . . . 133
• 5.8.11 Distribution Analysis of Subgraph Size Ratio . . . . . . . . . . . . . . 136
• 5.8.12 Connection to Renormalization Techniques . . . . . . . . . . . . . . . 142
• 5.8.13 Different Partitioning Algorithms . . . . . . . . . . . . . . . . . . . . 142
• 6 Conclusion 145
• References 147
• 국문요약 167