Research And Application Of Structural Graph Embedding Algorithm Based On Spectral Domain

Graph is a common data form and is widely used in many fields,which is often used to model the complex interactions between different entities.In recent years,with the rapid development of artificial intelligence technology,more and more researchers have tried to employ graph embedding methods to extract some valuable information from the graph.The goal of graph embedding is to embed each node in the graph into positions in the low-dimensional vector space,with preserving important information of the node as much as possible during the embedding process.In this paper we focus on the structural graph embedding algorithm.We aim to preserve the structural information of nodes during the embedding process,so that the structurally similar nodes are close to each other in the vector space,while the nodes with different structures are far away from each other,and distances between embedding vectors can reflect the structural difference between the corresponding nodes in the original graph.Previous structure embedding algorithms are usually carried out in the spatial domain of the graph,taking advantage of nodes and edges to extract structural information.However,these methods usually need manual annotation of structural features,so it is difficult to be applied to large-scale graphs.Moreover,such methods will lose a lot of information by recording a few quantitative descriptors of the complex structure.In this paper we propose a structural graph embedding algorithm based on spectral domain of the graph.At first,the complex structural information in the spatial domain can be decomposed into some components in the spectral domain through the graph fourier transform,and different components correspond to different information in the graph.At the same time,in order to highlight the importance of structural features in the local neighborhood of nodes,we employ the spectral graph wavelet transform to find the local area around the node,which uses transform basis function with attenuation.Then we obtain the distribution of wavelet coefficients by performing wavelet transformation on pulse signal at nodes.We discuss the close relation between wavelet coefficients and structures in theory.Then,from the point of view of the spatial domain,we prove that when the kernel function of wavelet transform is the heat kernel,the transformation of pulse signal on the node can be regarded as simulating the process of heat diffusion in the spatial domain.By placing a heat source at the node and observing the heat diffusion at different time in the graph,we can extract the structural information in different areas in the graph.In order to precisely characterize the structures,we construct a hierarchical representation of the area where the node is located,then characterize the structural information of each layer separately.Then we propose the multi-scale structural embedding algorithm based on the idea.Compared to the single scale,the multi-scale embedding can extract more structural information in the graph.This paper theoretically proves that nodes with similar topological structures will have similar embedding vectors,even if these nodes may be far away from each other in the graph.And the embeddings can be used to distinguish those nodes with obviously different structures.In this way,the embedding vector can be used as a quantitative representation of the irregular structure of the node,which provides a lot of help for downstream machine learning tasks.In experimental part we demonstrate that our structural embedding method can effectively extract the structural information of nodes,and achieves the state-of-the-art results in different experiments.