TY - GEN

T1 - The Spectral Zoo of Networks

T2 - 26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2020

AU - Jin, Shengmin

AU - Zafarani, Reza

N1 - Publisher Copyright:
© 2020 ACM.

PY - 2020/8/23

Y1 - 2020/8/23

N2 - Network embedding methods have been widely and successfully used in network-based applications such as node classification and link prediction. However, an ideal network embedding should not only be useful for machine learning, but interpretable. We introduce a spectral embedding method for a network, its Spectral Point, which is basically the first few spectral moments of a network. Spectral moments are interpretable, where we prove their close relationships to 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 for all possible graphs, in which one can characterize various types of 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 that by using just the first few moments one does not lose much predictive power.

AB - Network embedding methods have been widely and successfully used in network-based applications such as node classification and link prediction. However, an ideal network embedding should not only be useful for machine learning, but interpretable. We introduce a spectral embedding method for a network, its Spectral Point, which is basically the first few spectral moments of a network. Spectral moments are interpretable, where we prove their close relationships to 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 for all possible graphs, in which one can characterize various types of 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 that by using just the first few moments one does not lose much predictive power.

KW - graph spectrum

KW - network embedding

KW - network representation

KW - network visualization

KW - spectral graph theory

UR - http://www.scopus.com/inward/record.url?scp=85089543552&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85089543552&partnerID=8YFLogxK

U2 - 10.1145/3394486.3403195

DO - 10.1145/3394486.3403195

M3 - Conference contribution

AN - SCOPUS:85089543552

T3 - Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

SP - 1426

EP - 1434

BT - KDD 2020 - Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

PB - Association for Computing Machinery

Y2 - 23 August 2020 through 27 August 2020

ER -