Maximum entropy approach to massive graph spectrum learning with applications
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 ba...
| Main Authors: | , , , , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
MDPI
2022
|
| _version_ | 1797108175878488064 |
|---|---|
| author | Granziol, D Ru, B Dong, X Zohren, S Osborne, M Roberts, S |
| author_facet | Granziol, D Ru, B Dong, X Zohren, S Osborne, M Roberts, S |
| author_sort | Granziol, D |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-07T07:25:50Z |
| format | Journal article |
| id | oxford-uuid:80fb33ca-42fe-444c-84c3-e8ba896235d8 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T07:25:50Z |
| publishDate | 2022 |
| publisher | MDPI |
| record_format | dspace |
| spelling | oxford-uuid:80fb33ca-42fe-444c-84c3-e8ba896235d82022-11-17T15:21:32ZMaximum entropy approach to massive graph spectrum learning with applicationsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:80fb33ca-42fe-444c-84c3-e8ba896235d8EnglishSymplectic ElementsMDPI2022Granziol, DRu, BDong, XZohren, SOsborne, MRoberts, SWe 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. |
| spellingShingle | Granziol, D Ru, B Dong, X Zohren, S Osborne, M Roberts, S Maximum entropy approach to massive graph spectrum learning with applications |
| title | Maximum entropy approach to massive graph spectrum learning with applications |
| title_full | Maximum entropy approach to massive graph spectrum learning with applications |
| title_fullStr | Maximum entropy approach to massive graph spectrum learning with applications |
| title_full_unstemmed | Maximum entropy approach to massive graph spectrum learning with applications |
| title_short | Maximum entropy approach to massive graph spectrum learning with applications |
| title_sort | maximum entropy approach to massive graph spectrum learning with applications |
| work_keys_str_mv | AT granziold maximumentropyapproachtomassivegraphspectrumlearningwithapplications AT rub maximumentropyapproachtomassivegraphspectrumlearningwithapplications AT dongx maximumentropyapproachtomassivegraphspectrumlearningwithapplications AT zohrens maximumentropyapproachtomassivegraphspectrumlearningwithapplications AT osbornem maximumentropyapproachtomassivegraphspectrumlearningwithapplications AT robertss maximumentropyapproachtomassivegraphspectrumlearningwithapplications |