Network embedding techniques have been widely and successfully used in network-based applications such as node classification and link prediction. However, an ideal representation of a network should be both informative for prediction and be easy to interpret by users. In this paper, we introduce a spectral embedding method for a network, its Spectral Point, which is basically the truncated spectral moments of a network. We mathematically prove that spectral moments have close relationship with network structure (e.g. number of triangles and squares) and various network properties (e.g. degree distribution, clustering coefficient and network connectivity). Using spectral points, we introduce a visualizable and bounded 3D embedding space, where user can characterize different networks such as special graphs (e.g., cycles), or real-world networks from different categories (e.g., social or biological networks). We demonstrate that spectral points can be used for network identification (i.e., what network is this subgraph sampled from?) and the truncated spectral moments do not lose much predictive power.
@inproceedings{shengmin2020spectral,
title = {The Spectral Zoo of Networks: Embedding and Visualizing Networks with Spectral Moments},
author = {Shengmin Jin and Reza Zafarani},
year = {2020},
keywords = {conference},
booktitle = {Proceedings of the 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD)},
abstract = {Network embedding techniques have been widely and successfully used in network-based applications such as node classification and link prediction. However, an ideal representation of a network should be both informative for prediction and be easy to interpret by users. In this paper, we introduce a spectral embedding method for a network, its Spectral Point, which is basically the truncated spectral moments of a network. We mathematically prove that spectral moments have close relationship with network structure (e.g. number of triangles and squares) and various network properties (e.g. degree distribution, clustering coefficient and network connectivity). Using spectral points, we introduce a visualizable and bounded 3D embedding space, where user can characterize different networks such as special graphs (e.g., cycles), or real-world networks from different categories (e.g., social or biological networks). We demonstrate that spectral points can be used for network identification (i.e., what network is this subgraph sampled from?) and the truncated spectral moments do not lose much predictive power.},
pdf = {files/2020-KDD-Zoo.pdf},
}