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.

本研究提出了一种新的猜想反驳算法，名为 AMCS 算法，通过修改蒙特卡洛树搜索算法获得，旨在更有效地帮助研究人员测试图论猜想，并在多项图论猜想中得到了较好的应用。

自适应蒙特卡罗搜索在图论猜想证伪中的应用

Adaptive Monte Carlo Search for Conjecture Refutation in Graph Theory

Graph convolutional network (GCN) is generalization of convolutional neural
network (CNN) to work with arbitrarily structured graphs. A binary adjacency
matrix is commonly used in training a GCN. Recently, the attention mechanism
allows the network to learn a dynamic and adaptive aggregation of the
neighborhood. We propose a new GCN model on the graphs where edges are
characterized in multiple views or precisely in terms of multiple
relationships. For instance, in chemical graph theory, compound structures are
often represented by the hydrogen-depleted molecular graph where nodes
correspond to atoms and edges correspond to chemical bonds. Multiple attributes
can be important to characterize chemical bonds, such as atom pair (the types
of atoms that a bond connects), aromaticity, and whether a bond is in a ring.
The different attributes lead to different graph representations for the same
molecule. There is growing interests in both chemistry and machine learning
fields to directly learn molecular properties of compounds from the molecular
graph, instead of from fingerprints predefined by chemists. The proposed GCN
model, which we call edge attention-based multi-relational GCN (EAGCN), jointly
learns attention weights and node features in graph convolution. For each bond
attribute, a real-valued attention matrix is used to replace the binary
adjacency matrix. By designing a dictionary for the edge attention, and forming
the attention matrix of each molecule by looking up the dictionary, the EAGCN
exploits correspondence between bonds in different molecules. The prediction of
compound properties is based on the aggregated node features, which is
independent of the varying molecule (graph) size. We demonstrate the efficacy
of the EAGCN on multiple chemical datasets: Tox21, HIV, Freesolv, and
Lipophilicity, and interpret the resultant attention weights.

该论文提出了一种基于边注意力的多关系图卷积网络 (EAGCN) 模型，可用于多个化学数据集中学习化合物的属性，通过设计边注意力字典以及在不同分子中查找该字典以形成每个分子的注意力矩阵，进而实现对不同分子大小的聚合节点特征预测的独立性。