We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Maximum Entropy Approach to Massive Graph Spectrum Learning with Applications.
- Authors
Granziol, Diego; Ru, Binxin; Dong, Xiaowen; Zohren, Stefan; Osborne, Michael; Roberts, Stephen
- Abstract
We propose an alternative maximum entropy approach to learning the spectra of massive graphs. In contrast to state-of-the-art Lanczos algorithm for spectral density estimation and applications thereof, our approach does not require kernel smoothing. As the choice of kernel function and associated bandwidth heavily affect the resulting output, our approach mitigates these issues. Furthermore, we prove that kernel smoothing biases the moments of the spectral density. Our approach can be seen as an information-theoretically optimal approach to learning a smooth graph spectral density, which fully respects moment information. The proposed method has a computational cost linear in the number of edges, and hence can be applied even to large networks with millions of nodes. We showcase the approach on problems of graph similarity learning and counting cluster number in the graph, where the proposed method outperforms existing iterative spectral approaches on both synthetic and real-world graphs.
- Subjects
SIGNAL frequency estimation; MAXIMUM entropy method; LANCZOS method; ENTROPY; SPECTRAL energy distribution
- Publication
Algorithms, 2022, Vol 15, Issue 6, p209
- ISSN
1999-4893
- Publication type
Article
- DOI
10.3390/a15060209