Research On Key Technologies Of Graph Mining Via Quantum Walks

Quantum computing conducts the computation using quantum mechanics.As an important part of quantum computation,the quantum walk is the random walk based on quantum mechanics.Quantum walks are expert in mining information,thus being widely used in diverse quantum algorithms.Quantum walks are drawing growing attention from academics and industries,becoming the leading technology in computer science.Graph mining aims to learn information in graphs,which is a significant part of data mining.However,graph mining methods need to promote information capturing so that they can obtain comprehensive information from sophisticated networks.Benefitted from quantum mechanics and information capturing,quantum walks have made a breakthrough in methods like graph search and graph isomorphism algorithms,and are definitely promising techniques for graph mining.From both the level of basic theoretical algorithms and the level of practical application methods,this thesis studies the key graph mining methods based on quantum walks.This thesis applies quantum walks to key graph mining methods,using the characteristic of quantum walks to satisfy the requirement of algorithms.This thesis optimizes the information capturing of related methods,thus providing developing directions for both quantum computing and graph mining.The main contributions of this thesis are listed as follows:(1)Node proximity estimation based on quantum walksNode proximity studies the local structural similarity between nodes.Fundamental to graph mining methods,it is widely used in similarity estimation.This thesis analyzes the diffusion process of biased quantum walks,discover the Diminishing Effect and the Returning Effect,and propose QSIM for node proximity.QSIM faithfully reveals the firstorder and the second-order proximity,and is superior to other methods in experimental studies.(2)Node embedding via quantum-walk-based node proximityNode embedding aims to embed densely-connected nodes into similar vectors so that node proximity is maximumly preserved.Based on QSIM,this thesis proposes QNE for node embedding.QNE firstly conducts the node sampling on the QSIM proximity for the mid-representation of nodes and then learns embeddings by the neural network.QNE uses QSIM for comprehensive node proximity,and adds the non-linear layer to the neural network in order to capture non-linear structures.QNE performs better than current methods in many applications,including node classification,node clustering,and visualizations.(3)Community detection via quantum-walk-based node proximityCommunity detection aims to cluster densely connected nodes into communities,which is widely used in sociological and biological studies.This thesis presents QCOM,which computes the pairwise node similarity from the QSIM proximity and conducts the spectral clustering for community detection.QCOM validates the effectiveness of QSIM for capturing node proximity and local information from the perspective of downstream community detection,and achieves a better performance in experiments.(4)A quantum-walk-based graph isomorphism method for regular graphsGraph isomorphism judges whether two graphs are topologically the same and the isomorphism mapping reveals the equivalency between nodes.Current quantum-walkbased methods usually fail symmetric graphs like regular graphs,so this thesis presents Iso Marking to solve this problem.Based on quantum walks that can effectively capture structural equivalency,Iso Marking reduces the symmetry of graphs by marking nodes.It also validates whether the current bijection is consistent with existing ones,which makes the mapping more reliable.Compared with other methods,Iso Marking performs better on both ordinary graphs and regular graphs.(5)Role embedding based on quantum walksDistinct from ordinary node embedding,role embedding aims to embed role-similar nodes into similar representations,even if those nodes are far from each other.Current methods usually fail to capture global role information.From the capability of quantum walks for capturing structural equivalency,this thesis studies the effectiveness of quantum walks for capturing role information,and propose RED to capture both global and local role information via quantum walks and to generate the entire role embedding.RED can overcome the locality to embed far role-similar nodes into similar vectors,and enjoys a better performance in many applications like role detection.