Gradual Weisfeiler-Leman: Slow and Steady Wins the Race

• URL: http://arxiv.org/abs/2209.09048v1
• Date: Mon, 19 Sep 2022 14:37:35 GMT
• Title: Gradual Weisfeiler-Leman: Slow and Steady Wins the Race
• Authors: Franka Bause and Nils M. Kriege
• Abstract summary: Weisfeiler-Leman algorithm aka color refinement is fundamental for graph learning and central for successful graph kernels and graph neural networks. We propose a framework for gradual neighborhood refinement, which allows a slower convergence to the stable coloring. Our approach is used to derive new variants of existing graph kernels and to approximate the graph edit distance via optimal assignments.
• Score: 4.416484585765029
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The classical Weisfeiler-Leman algorithm aka color refinement is fundamental for graph learning and central for successful graph kernels and graph neural networks. Originally developed for graph isomorphism testing, the algorithm iteratively refines vertex colors. On many datasets, the stable coloring is reached after a few iterations and the optimal number of iterations for machine learning tasks is typically even lower. This suggests that the colors diverge too fast, defining a similarity that is too coarse. We generalize the concept of color refinement and propose a framework for gradual neighborhood refinement, which allows a slower convergence to the stable coloring and thus provides a more fine-grained refinement hierarchy and vertex similarity. We assign new colors by clustering vertex neighborhoods, replacing the original injective color assignment function. Our approach is used to derive new variants of existing graph kernels and to approximate the graph edit distance via optimal assignments regarding vertex similarity. We show that in both tasks, our method outperforms the original color refinement with only moderate increase in running time advancing the state of the art.

Related papers

• PF-GNN: Differentiable particle filtering based approximation of universal graph representations [20.544160526945234]
  Graph Neural Networks (GNNs) are known to be limited in expressive power by the 1-WL color-refinement test for graph isomorphism. In this work, we propose to make GNNs universal by guiding the learning process with exact isomorphism solver techniques. Our algorithm is end-to-end differentiable, can be applied with any GNN as backbone and learns richer graph representations with only linear increase in runtime.
  arXiv  Detail & Related papers  (2024-01-31T11:26:03Z)
• How to guess a gradient [68.98681202222664]
  We show that gradients are more structured than previously thought. Exploiting this structure can significantly improve gradient-free optimization schemes. We highlight new challenges in overcoming the large gap between optimizing with exact gradients and guessing the gradients.
  arXiv  Detail & Related papers  (2023-12-07T21:40:44Z)
• Generating a Graph Colouring Heuristic with Deep Q-Learning and Graph Neural Networks [5.620334754517149]
  We investigate whether deep reinforcement learning can be used to discover a competitive construction for graph colouring. Our proposed approach, ReLCol, uses deep Q-learning together with a graph neural network for feature extraction. We demonstrate that reinforcement learning is a promising direction for further research on the graph colouring problem.
  arXiv  Detail & Related papers  (2023-04-08T15:41:01Z)
• Deep Manifold Learning with Graph Mining [80.84145791017968]
  We propose a novel graph deep model with a non-gradient decision layer for graph mining. The proposed model has achieved state-of-the-art performance compared to the current models.
  arXiv  Detail & Related papers  (2022-07-18T04:34:08Z)
• Evolutionary Algorithm for Graph Coloring Problem [0.0]
  The graph coloring problem (GCP) is one of the most studied NP-HARD problems in computer science. In our paper, we start with the theoretical upper bound of chromatic number, that is, maximum out-degree + 1. In the process of evolution some of the colors are made unused to dynamically reduce the number of color in every generation.
  arXiv  Detail & Related papers  (2021-11-17T12:16:57Z)
• A deep learning guided memetic framework for graph coloring problems [15.426481600285724]
  We present a new framework which combines a deep neural network with the best tools of "classical" metaheuristics for graph coloring. A study of the contribution of deep learning in the algorithm highlights that it is possible to learn relevant patterns useful to obtain better solutions to this problem.
  arXiv  Detail & Related papers  (2021-09-13T13:17:41Z)
• Joint Graph Learning and Matching for Semantic Feature Correspondence [69.71998282148762]
  We propose a joint emphgraph learning and matching network, named GLAM, to explore reliable graph structures for boosting graph matching. The proposed method is evaluated on three popular visual matching benchmarks (Pascal VOC, Willow Object and SPair-71k) It outperforms previous state-of-the-art graph matching methods by significant margins on all benchmarks.
  arXiv  Detail & Related papers  (2021-09-01T08:24:02Z)
• Adapting Stepsizes by Momentumized Gradients Improves Optimization and Generalization [89.66571637204012]
  textscAdaMomentum on vision, and achieves state-the-art results consistently on other tasks including language processing. textscAdaMomentum on vision, and achieves state-the-art results consistently on other tasks including language processing. textscAdaMomentum on vision, and achieves state-the-art results consistently on other tasks including language processing.
  arXiv  Detail & Related papers  (2021-06-22T03:13:23Z)
• Time Complexity Analysis of Randomized Search Heuristics for the Dynamic Graph Coloring Problem [15.45783225341009]
  We study the dynamic setting where edges are added to the current graph. We then analyze the expected time for randomized searchs to recompute high quality solutions.
  arXiv  Detail & Related papers  (2021-05-26T13:00:31Z)
• Multilayer Graph Clustering with Optimized Node Embedding [70.1053472751897]
  multilayer graph clustering aims at dividing the graph nodes into categories or communities. We propose a clustering-friendly embedding of the layers of a given multilayer graph. Experiments show that our method leads to a significant improvement.
  arXiv  Detail & Related papers  (2021-03-30T17:36:40Z)
• Sequential Graph Convolutional Network for Active Learning [53.99104862192055]
  We propose a novel pool-based Active Learning framework constructed on a sequential Graph Convolution Network (GCN) With a small number of randomly sampled images as seed labelled examples, we learn the parameters of the graph to distinguish labelled vs unlabelled nodes. We exploit these characteristics of GCN to select the unlabelled examples which are sufficiently different from labelled ones.
  arXiv  Detail & Related papers  (2020-06-18T00:55:10Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.