Learning Hierarchical Representations of Graphs using Neural Network Techniques

Jain, Mausam and Balasubramanian, Vineeth N (2017) Learning Hierarchical Representations of Graphs using Neural Network Techniques. Masters thesis, Indian Institute of Technology Hyderabad.

Text
CS15MTECH11009.pdf - Submitted Version
Restricted to Registered users only until 2 July 2020.
Download (2MB) | Request a copy

Abstract

For a long time, the preferred machine learning algorithms for doing graph classification have been kernel based. The reasoning has been that kernels represent an elegant way to handle structured data that cannot be easily represented using numerical vectors or matrices. An important reason for the success of kernel methods, is the kernel trick, which essentially replaces computing the feature representation, with a call to a kernel function, thus saving computation and memory cost. For some of the most successful kernels in the graph domain however, such as graphlets, this is not feasible, and one must compute the entire feature distribution in order to obtain the kernel. The main motivation for this work is that latent dimension vector representation of network nodes and network itself are helpful in many tasks like node classification, community detection etc. by allowing their direct use in ML algorithms like SVM and Regression techniques. Also, real-world networks like Youtube and Facebook have millions of nodes in their representation graphs which demand scalable solutions to study them. On the other hand, language modelling has successfully exploited the power of Deep Learning in recent years which motivated representation learning for nodes in the graph. In this work, we present a novel method to learn latent vector representations for sub-structures in any large graph and also the graph itself, motivated by current Deep Learning and Graph Kernels advancements. These vector representations encode semantic sub-structure dependencies in continuous vector space, which can then be leveraged in Machine Learning algorithms for tasks such as graph classification, link prediction, community detection, clustering and anomaly detection. Our method exploits the neighbourhood information of sub-structures in the graph to learn representations using state-of-the- art language modelling techniques in unsupervised manner. We derive a novel concept of hierarchical embedding for graphs, which can represent a any graph in terms of hierarchy of sub-structures and can derive rich multi-level embedding of the graph. Along with deep learning techniques, we also use edit-distance similarity measure between sub-structures to learn their vector embeddings and compare all these resuls with the previous work (This report has a turnitin score of 0.27).

[error in script]

IITH Creators: