Adaptive Monte Carlo Search for Conjecture Refutation in Graph Theory

• URL: http://arxiv.org/abs/2306.07956v2
• Date: Tue, 27 Jun 2023 21:20:41 GMT
• Title: Adaptive Monte Carlo Search for Conjecture Refutation in Graph Theory
• Authors: Valentino Vito and Lim Yohanes Stefanus
• Abstract summary: Conjecture-refuting algorithms attempt to refute conjectures by searching for counterexamples to those conjectures. This study proposes a novel conjecture-refuting algorithm, referred to as the adaptive Monte Carlo search (AMCS) algorithm.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph theory is an interdisciplinary field of study that has various applications in mathematical modeling and computer science. Research in graph theory depends on the creation of not only theorems but also conjectures. Conjecture-refuting algorithms attempt to refute conjectures by searching for counterexamples to those conjectures, often by maximizing certain score functions on graphs. This study proposes a novel conjecture-refuting algorithm, referred to as the adaptive Monte Carlo search (AMCS) algorithm, obtained by modifying the Monte Carlo tree search algorithm. Evaluated based on its success in finding counterexamples to several graph theory conjectures, AMCS outperforms existing conjecture-refuting algorithms. The algorithm is further utilized to refute six open conjectures, two of which were chemical graph theory conjectures formulated by Liu et al. in 2021 and four of which were formulated by the AutoGraphiX computer system in 2006. Finally, four of the open conjectures are strongly refuted by generalizing the counterexamples obtained by AMCS to produce a family of counterexamples. It is expected that the algorithm can help researchers test graph-theoretic conjectures more effectively.

Related papers

• CayleyPy RL: Pathfinding and Reinforcement Learning on Cayley Graphs [0.0]
  This paper is the second in a series of studies on developing efficient artificial intelligence-based approaches to pathfinding on large graphs. We present a novel combination of a reinforcement learning approach with a more direct diffusion distance approach from the first paper. We provide strong support for the OEIS-A186783 conjecture that the diameter is equal to n(n-1)/2 by machine learning and mathematical methods.
  arXiv  Detail & Related papers  (2025-02-25T21:53:41Z)
• Causal Discovery over High-Dimensional Structured Hypothesis Spaces with Causal Graph Partitioning [0.742246975663779]
  Causal discovery allows us to infer mechanisms as sets of cause and effect relationships in a generalized way. We show our algorithm achieves comparable accuracy and a faster time to solution for biologically-tuned synthetic networks and networks up to $104$ variables.
  arXiv  Detail & Related papers  (2024-06-10T15:08:14Z)
• A Differentially Private Clustering Algorithm for Well-Clustered Graphs [6.523602840064548]
  We provide an efficient ($epsilon,$delta$)-DP algorithm tailored specifically for such graphs. Our algorithm works for well-clustered graphs with $k$ nearly-balanced clusters.
  arXiv  Detail & Related papers  (2024-03-21T11:57:16Z)
• A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near Neighbor Graph [51.880164098926166]
  Graph-based algorithms have demonstrated state-of-the-art performance in the nearest neighbor search (NN-Search) problem. There exists a practice-to-theory gap in the graph-based NN-Search algorithms. We present theoretical guarantees of solving NN-Search via greedy search on ANN-Graph for low dimensional and dense vectors.
  arXiv  Detail & Related papers  (2023-03-10T21:18:34Z)
• The Dynamics of Riemannian Robbins-Monro Algorithms [101.29301565229265]
  We propose a family of Riemannian algorithms generalizing and extending the seminal approximation framework of Robbins and Monro. Compared to their Euclidean counterparts, Riemannian algorithms are much less understood due to lack of a global linear structure on the manifold. We provide a general template of almost sure convergence results that mirrors and extends the existing theory for Euclidean Robbins-Monro schemes.
  arXiv  Detail & Related papers  (2022-06-14T12:30:11Z)
• From Width-Based Model Checking to Width-Based Automated Theorem Proving [8.131328180219962]
  We introduce a general framework to convert a large class of width-based model-checking algorithms into algorithms that can be used to test the validity of graph-theoretic conjectures. Our framework is modular and can be applied with respect to several well-studied width measures for graphs, including treewidth and cliquewidth.
  arXiv  Detail & Related papers  (2022-05-23T01:56:52Z)
• Partial Counterfactual Identification from Observational and Experimental Data [83.798237968683]
  We develop effective Monte Carlo algorithms to approximate the optimal bounds from an arbitrary combination of observational and experimental data. Our algorithms are validated extensively on synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2021-10-12T02:21:30Z)
• Graphon based Clustering and Testing of Networks: Algorithms and Theory [11.3700474413248]
  Network-valued data are encountered in a wide range of applications and pose challenges in learning. We present two clustering algorithms that achieve state-of-the-art results. We further study the applicability of the proposed distance for graph two-sample testing problems.
  arXiv  Detail & Related papers  (2021-10-06T13:14:44Z)
• Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms [71.62575565990502]
  We prove that the generalization error of an optimization algorithm can be bounded on the complexity' of the fractal structure that underlies its generalization measure. We further specialize our results to specific problems (e.g., linear/logistic regression, one hidden/layered neural networks) and algorithms.
  arXiv  Detail & Related papers  (2021-06-09T08:05:36Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  We introduce a novel learning problem for dense subgraph discovery. We first propose a edge-time algorithm that obtains a nearly-optimal solution with high probability. We then design a more scalable algorithm with a theoretical guarantee.
  arXiv  Detail & Related papers  (2020-06-24T11:37:33Z)
• Stochastic Flows and Geometric Optimization on the Orthogonal Group [52.50121190744979]
  We present a new class of geometrically-driven optimization algorithms on the orthogonal group $O(d)$. We show that our methods can be applied in various fields of machine learning including deep, convolutional and recurrent neural networks, reinforcement learning, flows and metric learning.
  arXiv  Detail & Related papers  (2020-03-30T15:37:50Z)

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.