Local Vertex Colouring Graph Neural Networks

2024-03-10 · Shouheng Li, Dongwoo Kim, Qing Wang

In recent years, there has been a significant amount of research focused on expanding the expressivity of Graph Neural Networks (GNNs) beyond the Weisfeiler-Lehman (1-WL) framework. While many of these studies have yielded advancements in expressivity, they have frequently come at the expense of decreased efficiency or have been restricted to specific types of graphs. In this study, we investigate the expressivity of GNNs from the perspective of graph search. Specifically, we propose a new vertex colouring scheme and demonstrate that classical search algorithms can efficiently compute graph representations that extend beyond the 1-WL. We show the colouring scheme inherits useful properties from graph search that can help solve problems like graph biconnectivity. Furthermore, we show that under certain conditions, the expressivity of GNNs increases hierarchically with the radius of the search neighbourhood. To further investigate the proposed scheme, we develop a new type of GNN based on two search strategies, breadth-first search and depth-first search, highlighting the graph properties they can capture on top of 1-WL. Our code is available at https://github.com/seanli3/lvc.

📄 PDF Abstract BibTeX arXiv:2403.06080

Code (1)

seanli3/lvc 공식 구현 pytorch

Graph Colouring Meets Deep Learning: Effective Graph Neural Network Models for Combinatorial Problems

2019-03-11 · Henrique Lemos, Marcelo Prates, Pedro Avelar, Luis Lamb

Deep learning has consistently defied state-of-the-art techniques in many fields over the last decade. However, we are just beginning to understand the capabilities of neural learning in symbolic domains. Deep learning a…

Deep Learning Graph Neural Network

Generating a Graph Colouring Heuristic with Deep Q-Learning and Graph Neural Networks

2023-04-08 · George Watkins, Giovanni Montana, Juergen Branke

The graph colouring problem consists of assigning labels, or colours, to the vertices of a graph such that no two adjacent vertices share the same colour. In this work we investigate whether deep reinforcement learning c…

Deep Reinforcement Learning Graph Neural Network Q-Learning reinforcement-learning+1

Graph Colouring Problem Based on Discrete Imperialist Competitive Algorithm

2013-08-17 · Hojjat Emami, Shahriar Lotfi

In graph theory, Graph Colouring Problem (GCP) is an assignment of colours to vertices of any given graph such that the colours on adjacent vertices are different. The GCP is known to be an optimization and NP-hard probl…

valid

Learning Vertex Convolutional Networks for Graph Classification

2019-02-26 · Lu Bai, Lixin Cui, Shu Wu, Yuhang Jiao 외

In this paper, we develop a new aligned vertex convolutional network model to learn multi-scale local-level vertex features for graph classification. Our idea is to transform the graphs of arbitrary sizes into fixed-size…

Classification General Classification Graph Classification

Vertex-Frequency Graph Signal Processing: A review

2019-12-26

Graph signal processing deals with signals which are observed on an irregular graph domain. While many approaches have been developed in classical graph theory to cluster vertices and segment large graphs in a signal ind…