GraphFSA: A Finite State Automaton Framework for Algorithmic Learning on Graphs

• URL: http://arxiv.org/abs/2408.11042v1
• Date: Tue, 20 Aug 2024 17:49:47 GMT
• Title: GraphFSA: A Finite State Automaton Framework for Algorithmic Learning on Graphs
• Authors: Florian Grötschla, Joël Mathys, Christoffer Raun, Roger Wattenhofer,
• Abstract summary: GraphFSA is designed to learn a finite state automaton that runs on each node of a given graph. We test GraphFSA on cellular automata problems, showcasing its abilities in a straightforward algorithmic setting. As our main application, we then focus on learning more elaborate graph algorithms.
• Score: 18.95453617434051
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Many graph algorithms can be viewed as sets of rules that are iteratively applied, with the number of iterations dependent on the size and complexity of the input graph. Existing machine learning architectures often struggle to represent these algorithmic decisions as discrete state transitions. Therefore, we propose a novel framework: GraphFSA (Graph Finite State Automaton). GraphFSA is designed to learn a finite state automaton that runs on each node of a given graph. We test GraphFSA on cellular automata problems, showcasing its abilities in a straightforward algorithmic setting. For a comprehensive empirical evaluation of our framework, we create a diverse range of synthetic problems. As our main application, we then focus on learning more elaborate graph algorithms. Our findings suggest that GraphFSA exhibits strong generalization and extrapolation abilities, presenting an alternative approach to represent these algorithms.

Related papers

• G-Retriever: Retrieval-Augmented Generation for Textual Graph Understanding and Question Answering [61.93058781222079]
  We develop a flexible question-answering framework targeting real-world textual graphs. We introduce the first retrieval-augmented generation (RAG) approach for general textual graphs. G-Retriever performs RAG over a graph by formulating this task as a Prize-Collecting Steiner Tree optimization problem.
  arXiv  Detail & Related papers  (2024-02-12T13:13:04Z)
• MGNet: Learning Correspondences via Multiple Graphs [78.0117352211091]
  Learning correspondences aims to find correct correspondences from the initial correspondence set with an uneven correspondence distribution and a low inlier rate. Recent advances usually use graph neural networks (GNNs) to build a single type of graph or stack local graphs into the global one to complete the task. We propose MGNet to effectively combine multiple complementary graphs.
  arXiv  Detail & Related papers  (2024-01-10T07:58:44Z)
• The Graph Lottery Ticket Hypothesis: Finding Sparse, Informative Graph Structure [18.00833762891405]
  Graph Lottery Ticket (GLT) Hypothesis: There is an extremely sparse backbone for every graph. We study 8 key metrics of interest that directly influence the performance of graph learning algorithms. We propose a straightforward and efficient algorithm for finding these GLTs in arbitrary graphs.
  arXiv  Detail & Related papers  (2023-12-08T00:24:44Z)
• Can Language Models Solve Graph Problems in Natural Language? [51.28850846990929]
  Large language models (LLMs) are increasingly adopted for a variety of tasks with implicit graphical structures. We propose NLGraph, a benchmark of graph-based problem solving simulating in natural language.
  arXiv  Detail & Related papers  (2023-05-17T08:29:21Z)
• Learning Graph Algorithms With Recurrent Graph Neural Networks [8.873449722727026]
  We focus on a recurrent architecture design that can learn simple graph problems end to end on smaller graphs and then extrapolate to larger instances. We use (i) skip connections, (ii) state regularization, and (iii) edge convolutions to guide GNNs toward extrapolation.
  arXiv  Detail & Related papers  (2022-12-09T15:42:22Z)
• Synthetic Graph Generation to Benchmark Graph Learning [7.914804101579097]
  Graph learning algorithms have attained state-of-the-art performance on many graph analysis tasks. One reason is due to the very small number of datasets used in practice to benchmark the performance of graph learning algorithms. We propose to generate synthetic graphs, and study the behaviour of graph learning algorithms in a controlled scenario.
  arXiv  Detail & Related papers  (2022-04-04T10:48:32Z)
• Automated Graph Machine Learning: Approaches, Libraries, Benchmarks and Directions [58.220137936626315]
  This paper extensively discusses automated graph machine learning approaches. We introduce AutoGL, our dedicated and the world's first open-source library for automated graph machine learning. Also, we describe a tailored benchmark that supports unified, reproducible, and efficient evaluations.
  arXiv  Detail & Related papers  (2022-01-04T18:31:31Z)
• Automated Machine Learning on Graphs: A Survey [81.21692888288658]
  This paper is the first systematic and comprehensive review of automated machine learning on graphs. We focus on hyper- parameter optimization (HPO) and neural architecture search (NAS) for graph machine learning. In the end, we share our insights on future research directions for automated graph machine learning.
  arXiv  Detail & Related papers  (2021-03-01T04:20:33Z)
• Learning Graph Structure With A Finite-State Automaton Layer [31.028101360041227]
  We study the problem of learning to derive abstract relations from the intrinsic graph structure. We show how to learn these relations end-to-end by relaxing the problem into learning finite-state automata policies. We demonstrate that this layer can find shortcuts in grid-world graphs and reproduce simple static analyses on Python programs.
  arXiv  Detail & Related papers  (2020-07-09T17:01:34Z)
• Learning to Solve Combinatorial Optimization Problems on Real-World Graphs in Linear Time [12.43303621344215]
  We develop a new framework to solve any optimization problem over graphs without expert knowledge. Our method trains a graph neural network using reinforcement learning on an unlabeled training set of graphs. We demonstrate our approach on both NP-hard problems with optimality gaps close to 1, and show that our method is able to generalize well.
  arXiv  Detail & Related papers  (2020-06-06T01:35:45Z)
• Unsupervised Graph Embedding via Adaptive Graph Learning [85.28555417981063]
  Graph autoencoders (GAEs) are powerful tools in representation learning for graph embedding. In this paper, two novel unsupervised graph embedding methods, unsupervised graph embedding via adaptive graph learning (BAGE) and unsupervised graph embedding via variational adaptive graph learning (VBAGE) are proposed. Experimental studies on several datasets validate our design and demonstrate that our methods outperform baselines by a wide margin in node clustering, node classification, and graph visualization tasks.
  arXiv  Detail & Related papers  (2020-03-10T02:33:14Z)

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.