[NS][Lab_Seminar_240710]Improving Graph Networks through Selection-based Convolution.pptx

Improving Graph Networks through Selection-based Convolution

1. Improving Graph Networks through Selection-based Convolution Tien-Bach-Thanh Do Network Science Lab Dept. of Artificial Intelligence The Catholic University of Korea E-mail: os fa19730 @catholic.ac.kr 202 4/07/10 David Hart et al. WACV 2024

2. Introduction GNN used to learn with irregular data that can be represented with graph structures GCN employ neighborhood aggregation functions Use attention or other metrics to determine how much to weight incoming node features during aggregation [5, 43, 44] Use MLP within aggregation steps themselves [8, 45, 51] Applications: 3D geometry, social networks, chemical structures Limitation: GCNs often ignore intrinsic relationships among nodes [5] Shaked Brody, Uri Alon, and Eran Yahav. How attentive are graph attention networks? In International Conference on Learning Representations, 2022 [43] Yunsheng Shi, Zhengjie Huang, Shikun Feng, Hui Zhong, Wenjing Wang, and Yu Sun. Masked label prediction: Unified message passing model for semi-supervised classification. In Zhi-Hua Zhou, editor, Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, pages 1548–1554. International Joint Conferences on Artificial Intelligence Organization, 8 2021. Main Track. [44] Petar Vel i ckovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph Attention Networks. International Conference on Learning Representations, 2018 [8] Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Lio, and Petar Velickovic. Principal neighbourhood aggregation for graph nets. Advances in Neural Information Processing Systems, 33:13260–13271, 2020 [45] Yue Wang, Yongbin Sun, Ziwei Liu, Sanjay E Sarma, Michael M Bronstein, and Justin M Solomon. Dynamic graph CNN for learning on point clouds. Acm Transactions On Graphics (tog), 38(5):1–12, 2019 [51] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019

3. Introduction Different Kinds of Intrinsic Relationships Spatial (Direction, Distance) Temporal (Dynamic Graphs) Edge Properties Multimodal Data User Specified

4. Introduction Selection-based Graph Convolution Allow for intrinsic relationships to be preserved by preprocessing the edges of the graph into multiple groups that called selections Each selection has its own unique learned weights in the graph network

5. Introduction Standard vs Selection-based Graph Convolution Standard Graph Convolution Multiply each neighbor by the same weight and then apply a permutation-invariant function May have fixed edge weights between 0 and 1 May have learned edge weights between 0 and 1 (using mechanisms like attention) Lose intrinsic relationship information, have to be encoded as node features and learned on

6. Introduction Standard vs Selection-based Graph Convolution Selection-based Graph Convolution Partition the edges into groups called selections as a preprocessing step Multiply neighbors by a unique weight based on its assigned selection The edge weights are learned for each selection, can be positive or negative, and can be different for each channel Keep intrinsic relationships information, leading to faster convergence and better performance

7. Motivation Need for preserving intrinsic relationships in graphs Limitations of attention-based and local-kernel approximation methods

8. Method Adding Selection to Graph Convolution result feature vector at source node for next layer vector of source features for node i target feature vector for node j in neighbor learnable weights Define selection function that assigns the edge between node i and adjacent node j Denote set of all possible selection values as S = {0, 1, 2, …, s max } such that = s ∊ S

9. Method General Formulation Message passing scheme for all convolution-based graph networks: differentiable functions with possible learned weights differentiable and permutation-invariant aggregation function To incorporate selection, use the same summation over selection weights

10. Method Different Kinds of Selection Functions Spatial Distance Time Property Combinations Custom Designed

11. Selection Function for Graphs Directional Selections Given edge between 2 nodes in graph, the original selection function determines the cardinal/ordinal direction that the edge most closely aligns with where x i , s j are the spatial coordinates of nodes i and j and Dk is list of the unit vectors for 8 different directions of interest Limitations Ambiguous rotation can affect directional selection, makes it ineffective

12. Selection Function for Graphs Distance Selections Purpose: account for spatial distance between nodes in graph Mechanism: edges are grouped into bins based on distance between connected nodes number of desired bins maximum distance between nodes

13. Selection Function for Graphs Combined Selection Functions Any of described selection functions can be combined to increase usability Eg: directional selection combine with distance selection for increased performance number of possible selections for

14. Experiments Spatial Graph Classification

15. Experiments Traffic Prediction

16. Experiments Traffic Prediction

17. Experiments Molecular Property Prediction

18. Experiments Advantages of Selection-Based Convolution Maintain intrinsic relationships Outperforms attention-based networks Requires fewer parameters

19. Conclusion Presented a technique for adding intrinsic graph relationships into GCN (spatial data) Selection can improve a variety of networks and outperformed attention -based networks Improve performance of SOTA graph networks or perform comparably with smaller networks Can be used and extended by others to incorporate intuitive relational information into graph networks