{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T02:42:54Z","timestamp":1787452974435,"version":"build-2736575974"},"reference-count":27,"publisher":"MDPI AG","issue":"6","license":[{"start":{"date-parts":[[2022,6,15]],"date-time":"2022-06-15T00:00:00Z","timestamp":1655251200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Oxford-Man institute"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.3390\/a15060209","type":"journal-article","created":{"date-parts":[[2022,6,15]],"date-time":"2022-06-15T01:39:54Z","timestamp":1655257194000},"page":"209","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Maximum Entropy Approach to Massive Graph Spectrum Learning with Applications"],"prefix":"10.3390","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3169-2081","authenticated-orcid":false,"given":"Diego","family":"Granziol","sequence":"first","affiliation":[{"name":"Machine Learning Research Group, University of Oxford, Eagle House, Walton Well Rd, Oxford OX2 6ED, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Binxin","family":"Ru","sequence":"additional","affiliation":[{"name":"Machine Learning Research Group, University of Oxford, Eagle House, Walton Well Rd, Oxford OX2 6ED, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xiaowen","family":"Dong","sequence":"additional","affiliation":[{"name":"Machine Learning Research Group, University of Oxford, Eagle House, Walton Well Rd, Oxford OX2 6ED, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Stefan","family":"Zohren","sequence":"additional","affiliation":[{"name":"Machine Learning Research Group, University of Oxford, Eagle House, Walton Well Rd, Oxford OX2 6ED, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1959-012X","authenticated-orcid":false,"given":"Michael","family":"Osborne","sequence":"additional","affiliation":[{"name":"Machine Learning Research Group, University of Oxford, Eagle House, Walton Well Rd, Oxford OX2 6ED, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9305-9268","authenticated-orcid":false,"given":"Stephen","family":"Roberts","sequence":"additional","affiliation":[{"name":"Machine Learning Research Group, University of Oxford, Eagle House, Walton Well Rd, Oxford OX2 6ED, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2022,6,15]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Mislove, A., Marcon, M., Gummadi, K.P., Druschel, P., and Bhattacharjee, B. (2007, January 24\u201326). Measurement and analysis of online social networks. Proceedings of the 7th ACM SIGCOMM Conference on Internet Measurement, San Diego, CA, USA.","DOI":"10.1145\/1298306.1298311"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Flake, G.W., Lawrence, S., and Giles, C.L. (2000, January 20\u201323). Efficient identification of web communities. Proceedings of the Sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Boston, MA, USA.","DOI":"10.1145\/347090.347121"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1145\/1232722.1232727","article-title":"The dynamics of viral marketing","volume":"1","author":"Leskovec","year":"2007","journal-title":"ACM Trans. Web"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"814","DOI":"10.1038\/nature03607","article-title":"Uncovering the overlapping community structure of complex networks in nature and society","volume":"435","author":"Palla","year":"2005","journal-title":"Nature"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"026704","DOI":"10.1103\/PhysRevE.64.026704","article-title":"Spectra of \u201creal-world\u201d graphs: Beyond the semicircle law","volume":"64","author":"Farkas","year":"2001","journal-title":"Phys. Rev. E"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Cohen-Steiner, D., Kong, W., Sohler, C., and Valiant, G. (2018, January 19\u201323). Approximating the Spectrum of a Graph. Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, London, UK.","DOI":"10.1145\/3219819.3220119"},{"key":"ref_7","unstructured":"Lov\u00e1sz, L. (2022, June 13). Eigenvalues of Graphs. Available online: https:\/\/web.cs.elte.hu\/~lovasz\/eigenvals-x.pdf."},{"key":"ref_8","unstructured":"Chung, F.R. (1997). Spectral Graph Theory, American Mathematical Soc.. Number 92."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"8577","DOI":"10.1073\/pnas.0601602103","article-title":"Modularity and community structure in networks","volume":"103","author":"Newman","year":"2006","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1007\/s11222-007-9033-z","article-title":"A tutorial on spectral clustering","volume":"17","year":"2007","journal-title":"Stat. Comput."},{"key":"ref_11","unstructured":"Kolla, A., Koutis, I., Madan, V., and Sinop, A.K. (2018). Spectrally Robust Graph Isomorphism. arXiv."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Takahashi, D.Y., Sato, J.R., Ferreira, C.E., and Fujita, A. (2012). Discriminating different classes of biological networks by analyzing the graphs spectra distribution. PLoS ONE, 7.","DOI":"10.1371\/journal.pone.0049949"},{"key":"ref_13","unstructured":"Pineau, E. (2019). Using Laplacian Spectrum as Graph Feature Representation. arXiv."},{"key":"ref_14","unstructured":"Biggs, N., Lloyd, E., and Wilson, R. (1976). Graph Theory 1736-1936, Oxford University Press."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Granziol, D., Ru, B., Zohren, S., Dong, X., Osborne, M., and Roberts, S. (2019). MEMe: An Accurate Maximum Entropy Method for Efficient Approximations in Large-Scale Machine Learning. Entropy, 21.","DOI":"10.3390\/e21060551"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1137\/130934283","article-title":"Approximating spectral densities of large matrices","volume":"58","author":"Lin","year":"2016","journal-title":"SIAM Rev."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"1075","DOI":"10.1137\/16M1104974","article-title":"Fast Estimation of tr(f(A)) via Stochastic Lanczos Quadrature","volume":"38","author":"Ubaru","year":"2017","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"ref_18","unstructured":"Cover, T.M., and Thomas, J.A. (2012). Elements of Information Theory, John Wiley & Sons."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Amari, S.I., and Nagaoka, H. (2007). Methods of Information Geometry, American Mathematical Soc.","DOI":"10.1090\/mmono\/191"},{"key":"ref_20","unstructured":"Banerjee, A. (2008). The Spectrum of the Graph Laplacian as a Tool for Analyzing Structure and Evolution of Networks. [Ph.D. Thesis, Leipzig University]."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Fitzsimons, J., Granziol, D., Cutajar, K., Osborne, M., Filippone, M., and Roberts, S. (2017, January 18\u201322). Entropic Trace Estimates for Log Determinants. Proceedings of the Joint European Conference on Machine Learning and Knowledge Discovery in Databases, Skopje, Macedonia.","DOI":"10.1007\/978-3-319-71249-9_20"},{"key":"ref_22","unstructured":"Golub, G.H., and Meurant, G. (1994). Matrices, moments and quadrature. Numerical Analysis 1993, CRC Press."},{"key":"ref_23","unstructured":"Akemann, G., Baik, J., and Di Francesco, P. (2011). The Oxford Handbook of Random Matrix Theory, Oxford University Press."},{"key":"ref_24","unstructured":"Feier, A.R. (2012). Methods of Proof in Random Matrix Theory. [Ph.D. Thesis, Harvard University]."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1007\/BF02579329","article-title":"The eigenvalues of random symmetric matrices","volume":"1","year":"1981","journal-title":"Combinatorica"},{"key":"ref_26","unstructured":"Leskovec, J., and Krevl, A. (2022, June 13). SNAP Datasets: Stanford Large Network Dataset Collection. Available online: http:\/\/snap.stanford.edu\/data."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"036104","DOI":"10.1103\/PhysRevE.74.036104","article-title":"Finding community structure in networks using the eigenvectors of matrices","volume":"74","author":"Newman","year":"2006","journal-title":"Phys. Rev. E"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/6\/209\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T23:31:41Z","timestamp":1760139101000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/6\/209"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,15]]},"references-count":27,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2022,6]]}},"alternative-id":["a15060209"],"URL":"https:\/\/doi.org\/10.3390\/a15060209","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,6,15]]}}}