Learning to compute the metric dimension of graphs

Highlights：

• A data structure is proposed to store the resolving relations of graphs, on which the greedy repair policy for solving the MDP is developed.

• A hybrid approximate algorithm for solving the MDP is established, which combines graph neural networks and greedy repair policy. By designing specific reward function related to the background of the MDP, the policy gradient algorithm is used to learn the extraction of graph metric base.

• Complex networks and random graphs are established, on which the advantages and disadvantages of different graph neural network architectures in learning the metric base of graphs are compared. Moreover, the computational accuracy of graph neural networks and the effect of greedy repair policy are analyzed respectively. Furthermore, the convergence of graph neural networks, the characteristics of the data structure and the complexity of the hybrid approximate algorithm are all considered.

摘要

•A data structure is proposed to store the resolving relations of graphs, on which the greedy repair policy for solving the MDP is developed.•A hybrid approximate algorithm for solving the MDP is established, which combines graph neural networks and greedy repair policy. By designing specific reward function related to the background of the MDP, the policy gradient algorithm is used to learn the extraction of graph metric base.•Complex networks and random graphs are established, on which the advantages and disadvantages of different graph neural network architectures in learning the metric base of graphs are compared. Moreover, the computational accuracy of graph neural networks and the effect of greedy repair policy are analyzed respectively. Furthermore, the convergence of graph neural networks, the characteristics of the data structure and the complexity of the hybrid approximate algorithm are all considered.