Research On Multi-Constrained Dynamic Graph Path Query

Graphs are a kind of data structure which model a set of objects(nodes)and their relationships(edges).As a common type of graphs,dynamic graphs have been receiving more and more attention in the field of graphs in recent years.Dynamic graphs can be used to model time-series data,as objects and relationships in dynamic graphs can change.Recently,with the development of Internet and technology,people can obtain more detailed data to build dynamic graphs,and this brings new challenges to the path query problem of dynamic graphs,i.e.,how to quickly find temporal paths that satisfy users' requirements in large-scale dynamic graph.In order to solve the problem,this paper mainly studies multi-constrained dynamic graph path query,hoping to improve the query speed and ensure the accuracy of the searching results.Multi-constrained dynamic graph path query not only needs to ensure the accuracy and optimality of query results,that is,to ensure the query result is a better solution and meets the needs of users.At the same time,the efficiency of the query needs to be guaranteed,which means the query should be fast and efficient,and the user does not need to wait for a long time.However,in order to ensure the accuracy of query results,the existing methods often use traversal-based path searching methods.These methods often take a lot of time to obtain the optimal solution when applied to large-scale dynamic graphs,and they do not have good applicability in real life.In the paper,we build a new kind of path query models that based on reinforcement learning.This model transforms multi-constrained dynamic graph path queries into reinforcement learning problems,and uses the idea of Monte Carlo tree search for modeling.In addition,a replay memory mechanism is designed to improve the efficiency of the query.As there are correlations between different paths,the features of the visited paths are extracted using the graph embedding techniques and stored in the replay memory.The path features in the replay memory are used to filter unvisited paths,thus the accuracy on the searching of large-scale dynamic graphs can be improved.In this paper,the above models are experimentally verified on ten real datasets such as YouTube,Facebook,and Twitter,and compared with the latest existing methods.Ex-perimental results show that the efficiency and effectiveness of this method are better than existing methods.The proposed model has certain help for multi-constrained dynamic graph path query application,and have certain reference value for related work.