Deep depth-based representations of graphs through deep learning networks

摘要

Graph-based representations are powerful tools in structural pattern recognition and machine learning. In this paper, we propose a framework of computing the deep depth-based representations for graph structures. Our work links the ideas of graph complexity measures and deep learning networks. Specifically, for a set of graphs, we commence by computing depth-based representations rooted at each vertex as vertex points. In order to identify an informative depth-based representation subset, we employ the well-known k-means method to identify M dominant centroids of the depth-based representation vectors as prototype representations. To overcome the burdensome computation of using depth-based representations for all graphs, we propose to use the prototype representations to train a deep autoencoder network, that is optimized using Stochastic Gradient Descent together with the Deep Belief Network for pretraining. By inputting the depth-based representations of vertices over all graphs to the trained deep network, we compute the deep representation for each vertex. The resulting deep depth-based representation of a graph is computed by averaging the deep representations of its complete set of vertices. We theoretically demonstrate that the deep depth-based representations of graphs not only reflect both the local and global characteristics of graphs through the depth-based representations, but also capture the main structural relationship and information content over all graphs under investigations. Experimental evaluations demonstrate the effectiveness of the proposed method. (C) 2018 Elsevier B.V. All rights reserved.