# Maximum Entropy Approach to Massive Graph Spectrum Learning with Applications
## 4 An Information-Theoretically Optimal Approach to Estimating Massive Graph Spectrum
### Stochastic Trace Estimation  
The intuition behind stochastic trace estimation is that we can accurately approximate the moments of \(\lambda\) with respect to the spectral density \(p(\lambda)\) by using computationally cheap matrix-vector multiplications. The moments of \(\lambda\) can be estimated using a Monte-Carlo average,  
\[n\,\mathbb{E}_{p}(\lambda^{m})=\mathbb{E}_{\mathbf{v}}(\mathbf{v}^{T}\mathbf{ X}^{m}\mathbf{v})\approx\frac{1}{d}\sum_{j=1}^{d}\mathbf{v}_{j}^{T}\mathbf{X}^{m} \mathbf{v}_{j}, \tag{6}\]  
where \(\mathbf{v}_{j}\) is any random vector with zero mean and unit covariance and \(\mathbf{X}\) is an \(n\times n\) matrix whose eigenvalues are \(\{\lambda_{i}\}_{i=1}^{n}\). This enables us to efficiently estimate the moments in \(\mathcal{O}(d\times m\times n_{\text{nz}})\) for sparse matrices (where \(n_{\text{nz}}\) is the number of non-zero entries in the matrix), where \(d\times m\ll n\). We use these as moment constraints in our entropic graph spectrum formalism to derive the functional form of the spectral density. Examples of this in the literature include [17; 21]. The algorithm for learning the graph Laplacian moments is summarised in Algorithm 1.  
```
1:Input: Normalised Laplacian \(\mathbf{L}_{\text{norm}}\), number of probe vectors \(d\), number of moments, required \(m\)
2:Output: Moments of normalised Laplacian \(\{\mu_{i}\}\)
3:for\(i\) in \(1,..,d\)do
4: Initialise random vector \(\mathbf{z}_{i}\in R^{1\times n}\)
5:for\(j\) in \(0\)do
6:\(\mathbf{z}_{j}=\mathbf{z}_{i}\)
7:\(\rho_{j}=\mathbf{z}_{i}\)\(\mathbf{z}_{j}^{T}\mathbf{z}_{j}^{\prime}\)
8:endfor
9:for\(j\) in \(1,..,m\)do
10:\(\mathbf{z}_{j}=\mathbf{L}_{\text{norm}}\mathbf{z}_{j}\)
11:\(\rho_{j}=\mathbf{z}_{i}\)\(\mathbf{z}_{j}^{T}\mathbf{z}_{j}^{\prime}\)
12:endfor
13:endfor
14:\(\mu_{i}=1/d\times\sum_{j=1}^{d}\rho_{ij}\)
```  
**Algorithm 1** Learning the Graph Laplacian Moments via Stochastic Trace Estimation (STE)Comment on the Lanczos Algorithm  
In the state-of-the-art iterative algorithm Lanczos Lanczos (1961), the tri-diagonal matrix \(\mathbf{T}^{m\times m}\) can be derived from the moment matrix \(\mathbf{M}^{m\times m}\), corresponding to the discrete measure \(d\alpha(\lambda)\) satisfying the moments \(\mu_{i}=v^{T}X^{i}v=\int\lambda^{i}d\alpha(\lambda)\) for all \(i\leq m\)([PERSON] et al., 2018) and hence it can be seen as a weighted Dirac approximation to the spectral density matching the first \(m\) moments. The weight given on every Ritz eigenvalue \(\lambda_{i}^{\prime\prime}\) (the eigenvalues of the matrix \(\mathbf{T}^{m\times m}\)) is the square of the first component of the corresponding Ritz vector (\(\phi_{i}\)), i.e., \({\left[\phi_{i}\right]}^{2}\), hence the approximated spectral density can be written as,  
\[\frac{1}{n}\sum_{i}^{n}\delta(\lambda-\lambda_{i})\approx\sum_{i}^{m}w_{i} \delta(\lambda-\lambda_{i}^{\prime\prime})=\sum_{i}^{m}\phi_{i}[1]^{2}\delta( \lambda-\lambda_{i}^{\prime\prime}). \tag{7}\]  
As we will further discuss in this paper, whilst this approximate spectral density respects the moment information of the original matrix, in practice as this spectral density is discrete, it must be smoothed. This smoothing neither respects moment nor bound information (for example the matrix may be positive definite). We hence expect a method which respects such information when relevant to provide superior performance, this is the subject of enquiry of this paper.