Entropic Spectral Learning for Large-Scale Graphs
This work addresses a domain-specific problem for researchers and practitioners in graph analysis, offering an incremental improvement in spectral approximation methods.
The paper tackled the problem of approximating graph spectra for large graphs where eigen-decomposition is infeasible, showing that kernel smoothing loses moment information and proposing a Maximum Entropy-based method that matches moments exactly and is positive, with experiments demonstrating its effectiveness and superiority over existing approaches on synthetic and real-world networks.
Graph spectra have been successfully used to classify network types, compute the similarity between graphs, and determine the number of communities in a network. For large graphs, where an eigen-decomposition is infeasible, iterative moment matched approximations to the spectra and kernel smoothing are typically used. We show that the underlying moment information is lost when using kernel smoothing. We further propose a spectral density approximation based on the method of Maximum Entropy, for which we develop a new algorithm. This method matches moments exactly and is everywhere positive. We demonstrate its effectiveness and superiority over existing approaches in learning graph spectra, via experiments on both synthetic networks, such as the Erdős-Rényi and Barabási-Albert random graphs, and real-world networks, such as the social networks for Orkut, YouTube, and Amazon from the SNAP dataset.