Goal-directed graph construction using reinforcement learning
- URL: http://arxiv.org/abs/2001.11279v4
- Date: Wed, 27 Oct 2021 12:54:35 GMT
- Title: Goal-directed graph construction using reinforcement learning
- Authors: Victor-Alexandru Darvariu, Stephen Hailes, Mirco Musolesi
- Abstract summary: We formulate the construction of a graph as a decision-making process in which a central agent creates topologies by trial and error.
We propose an algorithm based on reinforcement learning and graph neural networks to learn graph construction and improvement strategies.
- Score: 3.291429094499946
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Graphs can be used to represent and reason about systems and a variety of
metrics have been devised to quantify their global characteristics. However,
little is currently known about how to construct a graph or improve an existing
one given a target objective. In this work, we formulate the construction of a
graph as a decision-making process in which a central agent creates topologies
by trial and error and receives rewards proportional to the value of the target
objective. By means of this conceptual framework, we propose an algorithm based
on reinforcement learning and graph neural networks to learn graph construction
and improvement strategies. Our core case study focuses on robustness to
failures and attacks, a property relevant for the infrastructure and
communication networks that power modern society. Experiments on synthetic and
real-world graphs show that this approach can outperform existing methods while
being cheaper to evaluate. It also allows generalization to out-of-sample
graphs, as well as to larger out-of-distribution graphs in some cases. The
approach is applicable to the optimization of other global structural
properties of graphs.
Related papers
- Towards Graph Foundation Models: The Perspective of Zero-shot Reasoning on Knowledge Graphs [14.392577069212292]
We introduce SCORE, a unified graph reasoning framework that effectively generalizes diverse graph tasks using zero-shot learning.
We evaluate SCORE using 38 diverse graph datasets, covering node-level, link-level, and graph-level tasks across multiple domains.
arXiv Detail & Related papers (2024-10-16T14:26:08Z) - GraphGLOW: Universal and Generalizable Structure Learning for Graph
Neural Networks [72.01829954658889]
This paper introduces the mathematical definition of this novel problem setting.
We devise a general framework that coordinates a single graph-shared structure learner and multiple graph-specific GNNs.
The well-trained structure learner can directly produce adaptive structures for unseen target graphs without any fine-tuning.
arXiv Detail & Related papers (2023-06-20T03:33:22Z) - Bures-Wasserstein Means of Graphs [60.42414991820453]
We propose a novel framework for defining a graph mean via embeddings in the space of smooth graph signal distributions.
By finding a mean in this embedding space, we can recover a mean graph that preserves structural information.
We establish the existence and uniqueness of the novel graph mean, and provide an iterative algorithm for computing it.
arXiv Detail & Related papers (2023-05-31T11:04:53Z) - 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) - A Complex Network based Graph Embedding Method for Link Prediction [0.0]
We present a novel graph embedding approach based on the popularity-similarity and local attraction paradigms.
We show, using extensive experimental analysis, that the proposed method outperforms state-of-the-art graph embedding algorithms.
arXiv Detail & Related papers (2022-09-11T14:46:38Z) - Revisiting Adversarial Attacks on Graph Neural Networks for Graph
Classification [38.339503144719984]
We present a novel and general framework to generate adversarial examples via manipulating graph structure and node features.
Specifically, we make use of Graph Class Mapping and its variant to produce node-level importance corresponding to the graph classification task.
Experiments towards attacking four state-of-the-art graph classification models on six real-world benchmarks verify the flexibility and effectiveness of our framework.
arXiv Detail & Related papers (2022-08-13T13:41:44Z) - Graph Pooling for Graph Neural Networks: Progress, Challenges, and
Opportunities [128.55790219377315]
Graph neural networks have emerged as a leading architecture for many graph-level tasks.
graph pooling is indispensable for obtaining a holistic graph-level representation of the whole graph.
arXiv Detail & Related papers (2022-04-15T04:02:06Z) - A Robust and Generalized Framework for Adversarial Graph Embedding [73.37228022428663]
We propose a robust framework for adversarial graph embedding, named AGE.
AGE generates the fake neighbor nodes as the enhanced negative samples from the implicit distribution.
Based on this framework, we propose three models to handle three types of graph data.
arXiv Detail & Related papers (2021-05-22T07:05:48Z) - GraphOpt: Learning Optimization Models of Graph Formation [72.75384705298303]
We propose an end-to-end framework that learns an implicit model of graph structure formation and discovers an underlying optimization mechanism.
The learned objective can serve as an explanation for the observed graph properties, thereby lending itself to transfer across different graphs within a domain.
GraphOpt poses link formation in graphs as a sequential decision-making process and solves it using maximum entropy inverse reinforcement learning algorithm.
arXiv Detail & Related papers (2020-07-07T16:51:39Z)
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.