A graph is a form which can efficiently represent the structured data. It is already conventional tool used in wide range of domains, from bioinformatics and pharmacology to social network and network system. In this thesis we aim to develop unsupervised and supervised frameworks for graph representation learning by combining the methods from spectral graph theory. Eigenvalues and the heat kernel are an important component from spectral graph theory that describes graph structure and the flow of information through the edges in the graph. First, the proposed unsupervised framework is developed using spectral distributions from the eigenvalues and heat kernels on graphs. These two components are carried out for graph comparison with the optimal transport like method, Gromov-Wasserstein discrepancy. The framwork is suitable for graph representation in that it satisfies three graph properties, permutation-invariance, structural-adaptivity and scale-adaptivity. Additionally, we introduce approximation for Gromov-Wasserstein discrepancy to boil down the computational complexity for large-scale graph comparison. The experiments on the benchmark datasets, including molecules, proteins and scientific collaboration, are conducted to validate the performance in graph classification task. We further investigate the samples in real-world graphs and check whether similar graphs selected from the proposed method is actually similar and the dissimilar graphs are dissimilar.
Second, we propose a supervised graph representation learning method with graph neural networks. The model incorporates the heat kernel in graph convolution and satisfies the graph properties. Usually diffusion rate in the heat kernel is selected with trial-error. However, we substitute the diffusion rate to learnable parameter so that the model can decide the diffusion rate and the heat kernel is decided subsequently. Moreover, heat kernel trace normalization is suggested to enhance the discernability of the model on regular graphs. It complements the problem of representing non-isomorphic regular graphs the same in conventional graph convolution method. Multi-head heat kernels are applied to the model to further learn the comprehensive local and global structure of the graph. We experiment on benchmark datasets and show competitive performance on graph classification against baseline methods and verify whether the multi-head heat kernel improves the performance. Additionally, we analyze the heat kernels in the model to identify that learned heat kernels in real-world graphs utilizes local and global structure from the heat kernels.
