# Maximum Entropy Approach to Massive Graph Spectrum Learning with Applications
## 3 Motivation for a New Method to Approximate and Compare Graph Spectra  
For large sparse graphs with millions, or billions, of nodes, learning the exact spectrum using eigen-decomposition is unfeasible due to the \(\mathcal{O}(n^{3})\) cost. Powerful iterative methods (such as the Lanczos algorithm, kernel polynomial methods, Chebyshev/Taylor approximations, the Haydock method and many more), which only require matrix-vector multiplications and hence have a computational cost scaling with the number of non-zero entries in the graph matrices, are often used. There is extensive literature documenting the performance of these methods. Ref. [16] states that the [PERSON] algorithm is significantly more accurate than other methods (including the kernel polynomial methods), followed by the Haydock method. Ref. [17] shows that the convergence of the Lanczos algorithm is twice that of the Chebyshev approximation. Hence given the superior theoretical guarantees and empirical performance of the Lanczos algorithm, we employ it as a sole baseline against our MaxEnt method. The [PERSON] algorithm [17] approximates the graph spectrum with a sum of weighted Dirac delta functions, closely matching the first \(m\) moments (where \(m\) is the number of iterative steps used, as detailed in Section 4.1) of the spectral density:  
\[p(\lambda)=\frac{1}{n}\sum_{i=1}^{n}\delta(\lambda-\lambda_{i})\approx\sum_{i= 1}^{m}w_{i}\delta(\lambda-\lambda_{i}), \tag{2}\]  
where \(\sum_{i=1}^{m}w_{i}=1\), and \(\lambda_{i}\) denotes the \(i\)-th eigenvalue in the spectrum. This can be seen as an \(m\)-moment matched discrete approximation to the spectral density of the graph. However, such an approximation is undesirable because natural divergence measures between densities, such as the information-based relative entropy, i.e., the KL divergence \(\mathcal{D}_{\text{KL}}(p||q)\in(0,\infty)\)[18; 19], can be infinite for densities that are mutually singular. The use of the Jensen-Shannon divergence simply re-scales the divergence into \(\mathcal{D}_{\text{JS}}(p||q)\in(0,1)\). The Argument against Kernel Smoothing  
To alleviate these limitations, practitioners typically generate a smoothed spectral density by convolving the Dirac mixture of spectral components with a smooth kernel \(k_{\sigma}(\lambda-\lambda_{i})\)[12; 20], often a Gaussian or Cauchy [20] to facilitate visualisation and comparison. The smoothed spectral density, with reference to Equation (2), thus takes the form:  
\[ \begin{split}\tilde{p}(\lambda)&=\int k_{\sigma}( \lambda-\lambda^{\prime})p(\lambda^{\prime})d\lambda^{\prime}\\ &=\int k_{\sigma}(\lambda-\lambda^{\prime})\sum_{i=1}^{m}w_{i} \delta(\lambda^{\prime}-\lambda_{i})d\lambda^{\prime}\\ &=\sum_{i=1}^{m}w_{i}k_{\sigma}(\lambda-\lambda_{i})\end{split}  \tag{3}\]  
We make some assumptions regarding the nature of the kernel function, \(k_{\sigma}(\lambda-\lambda_{i})\), in order to prove our main theoretical result about the effect of kernel smoothing on the moments of the underlying spectral density. Both of our assumptions are met by (the commonly employed) Gaussian kernel. The kernel function \(k_{\sigma}(\lambda-\lambda_{i})\) is supported on the real line \([-\infty,\infty]\). The kernel function \(k_{\sigma}(\lambda-\lambda_{i})\) is symmetric and permits all moments. The m-th moment of a Dirac mixture \(\sum_{i=1}^{m}w_{i}\delta(\lambda-\lambda_{i})\), which is smoothed by a kernel \(k_{\sigma}\) satisfying Assumptions 1 and 2, is perturbed from its unsmoothed counterpart by an amount \(\sum_{i=1}^{m}w_{i}\sum_{j=1}^{r/2}\binom{r}{2j}\mathbb{E}_{k_{\sigma}(\lambda )}(\lambda^{2j})\lambda_{i}^{m-2j}\), where \(r=m\) if \(m\) is even and \(m-1\) otherwise. \(\mathbb{E}_{k_{\sigma}(\lambda)}(\lambda^{2j})\) denotes the 2j-th central moment of the kernel function \(k_{\sigma}(\lambda)\). Proof.