Neural Online Graph Exploration

• URL: http://arxiv.org/abs/2012.03345v2
• Date: Tue, 6 Apr 2021 12:47:00 GMT
• Title: Neural Online Graph Exploration
• Abstract summary: We study the problem of Online Graph Exploration, the online version of the Traveling Salesperson Problem. We reformulate graph exploration as a reinforcement learning problem and apply Direct Future Prediction to solve it. This is the first attempt to solve online graph exploration in a data-driven way.
• Score: 65.49668396771239
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Can we learn how to explore unknown spaces efficiently? To answer this question, we study the problem of Online Graph Exploration, the online version of the Traveling Salesperson Problem. We reformulate graph exploration as a reinforcement learning problem and apply Direct Future Prediction (Dosovitskiy and Koltun, 2017) to solve it. As the graph is discovered online, the corresponding Markov Decision Process entails a dynamic state space, namely the observable graph and a dynamic action space, namely the nodes forming the graph's frontier. To the best of our knowledge, this is the first attempt to solve online graph exploration in a data-driven way. We conduct experiments on six data sets of procedurally generated graphs and three real city road networks. We demonstrate that our agent can learn strategies superior to many well known graph traversal algorithms, confirming that exploration can be learned.

Related papers

• GraphTOP: Graph Topology-Oriented Prompting for Graph Neural Networks [66.07512871031163]
  "Pre-training, adaptation" scheme pre-trains powerful Graph Neural Networks (GNNs) over unlabeled graph data.<n>In the adaptation phase, graph prompting modifies input graph data with learnable prompts while keeping pre-trained GNN models frozen.<n>We propose the first **Graph** **T**opology-**O**riented **P**rompting (GraphTOP) framework to effectively adapt pre-trained GNN models for downstream tasks.
  arXiv  Detail & Related papers  (2025-10-25T22:50:12Z)
• Graph Prompting for Graph Learning Models: Recent Advances and Future Directions [75.7773954442738]
  "Pre-training, adaptation" scheme first pre-trains graph learning models on unlabeled graph data in a self-supervised manner.<n> graph prompting emerges as a promising approach that learns trainable prompts while keeping the pre-trained graph learning models unchanged.
  arXiv  Detail & Related papers  (2025-06-10T01:27:19Z)
• A Survey of Large Language Models for Data Challenges in Graphs [40.430960706806665]
  Graphs are a widely used paradigm for representing non-Euclidean data, with applications ranging from social network analysis to biomolecular prediction.<n>While graph learning has achieved remarkable progress, real-world graph data presents a number of challenges that significantly hinder the learning process.<n>Recently, Large Language Models (LLMs) offer the potential to tackle these challenges by leveraging rich semantic reasoning and external knowledge.
  arXiv  Detail & Related papers  (2025-05-24T02:38:14Z)
• Online Network Inference from Graph-Stationary Signals with Hidden Nodes [31.927912288598467]
  We present a novel method for online graph estimation that accounts for the presence of hidden nodes. We then formulate a convex optimization problem for graph learning from streaming, incomplete graph signals.
  arXiv  Detail & Related papers  (2024-09-13T12:09:09Z)
• Knowledge Probing for Graph Representation Learning [12.960185655357495]
  We propose a novel graph probing framework (GraphProbe) to investigate and interpret whether the family of graph learning methods has encoded different levels of knowledge in graph representation learning. Based on the intrinsic properties of graphs, we design three probes to systematically investigate the graph representation learning process from different perspectives. We construct a thorough evaluation benchmark with nine representative graph learning methods from random walk based approaches, basic graph neural networks and self-supervised graph methods, and probe them on six benchmark datasets for node classification, link prediction and graph classification.
  arXiv  Detail & Related papers  (2024-08-07T16:27:45Z)
• Continual Learning on Graphs: Challenges, Solutions, and Opportunities [72.7886669278433]
  We provide a comprehensive review of existing continual graph learning (CGL) algorithms. We compare methods with traditional continual learning techniques and analyze the applicability of the traditional continual learning techniques to forgetting tasks. We will maintain an up-to-date repository featuring a comprehensive list of accessible algorithms.
  arXiv  Detail & Related papers  (2024-02-18T12:24:45Z)
• State of the Art and Potentialities of Graph-level Learning [54.68482109186052]
  Graph-level learning has been applied to many tasks including comparison, regression, classification, and more. Traditional approaches to learning a set of graphs rely on hand-crafted features, such as substructures. Deep learning has helped graph-level learning adapt to the growing scale of graphs by extracting features automatically and encoding graphs into low-dimensional representations.
  arXiv  Detail & Related papers  (2023-01-14T09:15:49Z)
• Graph Learning and Its Advancements on Large Language Models: A Holistic Survey [37.01696685233113]
  This survey focuses on the most recent advancements in integrating graph learning with pre-trained language models. We provide a holistic review that analyzes current works from the perspective of graph structure, and discusses the latest applications, trends, and challenges in graph learning.
  arXiv  Detail & Related papers  (2022-12-17T22:05:07Z)
• Automatic Relation-aware Graph Network Proliferation [182.30735195376792]
  We propose Automatic Relation-aware Graph Network Proliferation (ARGNP) for efficiently searching GNNs. These operations can extract hierarchical node/relational information and provide anisotropic guidance for message passing on a graph. Experiments on six datasets for four graph learning tasks demonstrate that GNNs produced by our method are superior to the current state-of-the-art hand-crafted and search-based GNNs.
  arXiv  Detail & Related papers  (2022-05-31T10:38:04Z)
• Data Augmentation for Deep Graph Learning: A Survey [66.04015540536027]
  We first propose a taxonomy for graph data augmentation and then provide a structured review by categorizing the related work based on the augmented information modalities. Focusing on the two challenging problems in DGL (i.e., optimal graph learning and low-resource graph learning), we also discuss and review the existing learning paradigms which are based on graph data augmentation.
  arXiv  Detail & Related papers  (2022-02-16T18:30:33Z)
• Online Graph Learning in Dynamic Environments [5.222057229549077]
  This paper focuses on learning graphs in the case of sequential data in dynamic environments. For sequential data, we develop an online version of classic batch graph learning method.
  arXiv  Detail & Related papers  (2021-10-11T06:24:30Z)
• Second-Order Pooling for Graph Neural Networks [62.13156203025818]
  We propose to use second-order pooling as graph pooling, which naturally solves the above challenges. We show that direct use of second-order pooling with graph neural networks leads to practical problems. We propose two novel global graph pooling methods based on second-order pooling; namely, bilinear mapping and attentional second-order pooling.
  arXiv  Detail & Related papers  (2020-07-20T20:52:36Z)

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.