TY - GEN

T1 - A Spectral Representation of Networks

T2 - 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2022

AU - Jin, Shengmin

AU - Tian, Hao

AU - Li, Jiayu

AU - Zafarani, Reza

N1 - Funding Information:
We propose representing a network with a 3D spectral path: a path connecting the spectral moments of a network to the expected spectral moments of its subgraphs. We demonstrate the interpretability of spectral paths. We show the utility of spectral paths in network visualization, network identification and distinguishing cospectral graphs. To the best of our knowledge, this is the first study to explore spectral moments of subgraphs and study the relationship between spectral moments of subgraphs and those of the whole network. Limitations( ) and Future Work. For a graph of nodes, there are subgraphs of size . When is around 2, the number of subgraphs is the largest. Hence, one may consider taking different numbers of samples to estimate the expected moments. In our experiments on real-world networks, we take 20 samples for each sampling proportion, and the standard deviation of spectral moments is often less than 5%. In the future, we aim to study the distribution of spectral moments of subgraphs. Acknowledgements. This research was supported in part by the National Science Foundation under award CAREER IIS-1942929.
Publisher Copyright:
© 2022 ACM.

PY - 2022/8/14

Y1 - 2022/8/14

N2 - Network representation learning has played a critical role in studying networks. One way to study a graph is to focus on its spectrum, i.e., the eigenvalue distribution of its associated matrices. Recent advancements in spectral graph theory show that spectral moments of a network can be used to capture the network structure and various graph properties. However, sometimes networks with different structures or sizes can have the same or similar spectral moments, not to mention the existence of the cospectral graphs. To address such problems, we propose a 3D network representation that relies on the spectral information of subgraphs: the Spectral Path, a path connecting the spectral moments of the network and those of its subgraphs of different sizes. We show that the spectral path is interpretable and can capture relationship between a network and its subgraphs, for which we present a theoretical foundation. We demonstrate the effectiveness of the spectral path in applications such as network visualization and network identification.

AB - Network representation learning has played a critical role in studying networks. One way to study a graph is to focus on its spectrum, i.e., the eigenvalue distribution of its associated matrices. Recent advancements in spectral graph theory show that spectral moments of a network can be used to capture the network structure and various graph properties. However, sometimes networks with different structures or sizes can have the same or similar spectral moments, not to mention the existence of the cospectral graphs. To address such problems, we propose a 3D network representation that relies on the spectral information of subgraphs: the Spectral Path, a path connecting the spectral moments of the network and those of its subgraphs of different sizes. We show that the spectral path is interpretable and can capture relationship between a network and its subgraphs, for which we present a theoretical foundation. We demonstrate the effectiveness of the spectral path in applications such as network visualization and network identification.

KW - network representations

KW - spectral graphs

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

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

U2 - 10.1145/3534678.3539433

DO - 10.1145/3534678.3539433

M3 - Conference contribution

AN - SCOPUS:85137148834

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

SP - 698

EP - 708

BT - KDD 2022 - Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining

PB - Association for Computing Machinery

Y2 - 14 August 2022 through 18 August 2022

ER -