The spectral properties of traditional (dyadic) graphs, where an edge connects exactly two vertices, are widely utilized in different applications. These spectral properties are closely connected to the structural properties of dyadic graphs. We generalize such connections and characterize higher-order networks by their spectral information. We first split the higher-order graphs by their orders into several uniform hypergraphs. For each uniform hypergraph, we extract the corresponding spectral information from the transition matrices of carefully designed random walks. From each spectrum, we compute the first few spectral moments and use all such spectral moments across different orders as the higher-order graph representation. We will show that these moments not only clearly indicate the return probabilities of random walks but are also closely related to various higher-order network properties such as degree distribution and clustering coefficient. Extensive experiments show the utility of this new representation in various settings.
@inproceedings{tian2025representinghigherorder,
title = {Representing Higher-Order Networks with Spectral Moments},
author = {Hao Tian and Shengmin Jin and Reza Zafarani},
year = {2025},
keywords = {conference},
booktitle = {Proceedings of the 29th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD)},
address = {Sydney, Australia},
abstract = {The spectral properties of traditional (dyadic) graphs, where an edge connects exactly two vertices, are widely utilized in different applications. These spectral properties are closely connected to the structural properties of dyadic graphs. We generalize such connections and characterize higher-order networks by their spectral information. We first split the higher-order graphs by their orders into several uniform hypergraphs. For each uniform hypergraph, we extract the corresponding spectral information from the transition matrices of carefully designed random walks. From each spectrum, we compute the first few spectral moments and use all such spectral moments across different orders as the higher-order graph representation. We will show that these moments not only clearly indicate the return probabilities of random walks but are also closely related to various higher-order network properties such as degree distribution and clustering coefficient. Extensive experiments show the utility of this new representation in various settings.},
}