Seyede Fateme Mousavi (MS)

My role: Supervisor

Master Thesis Title: Hierarchical Graph Embedding in Vector Space, 2015

Abstract
Graph-based representations have an effective and extensive usage in pattern recognition due to represent properties of entities and binary relations at the same time. But a major drawback of graphs is lack of basic and essential mathematical operations required in many algorithms of pattern recognition. To overcome this problem, graph embedding in vector space enables classical statistical learning algorithms to be used on graph-based input patterns by providing a feature vector for each graph. Different graph embedding methods have been proposed in the literature, consist of three large families based on dissimilarity, graph probing and graph spectra. However, the problem of finding convenient vector representations for graphs is not an easy task. There are two issues concerning with embedding methods. Firstly, embedding procedures should not be done by costly operations. Secondly, extracted features should preserve graph information particularly structural details as possible. Present thesis introduces two frameworks to compromise between the embedding time and the ability of preserving information of the embedding method. The main idea is to use the advantages of the hierarchical architecture in the graph domain. The first framework creates a pyramid from different scales of the input graph using a summarization algorithm. Embedding the multi scales of this pyramid provides global features beside the local ones and it causes the embedding method be able to show the missing graph information. Moreover, the embedding time can be decreased by smaller size of the graph in the lower levels. The second framework separates input graph into its components to improve its analysis. The missing information during the summarization procedure can be kept into two detail graphs. As a result, original graph can be reconstructed by a summarized graph and its corresponding details. Then, embedding can be done with feature extraction from different scales and details of graph. Also, for decreasing the embedding time, a discriminant tree introduced based on divide and conquer method. Experiments investigate a selected method of each family for embedding different graph levels. The main achievement of this evaluation is that regardless of the selected embedding method, the proposed hierarchical frameworks have high capability to improve accuracy and time in the classification problems.
 

Keywords: Pattern recognition, Graph embedding, Graph classification, Hierarchical
architecture, Graph pyramid, Graph details.

publication:

https://www.sciencedirect.com/science/article/pii/S003132031630200X