# Maximum Entropy Approach to Massive Graph Spectrum Learning with Applications
## 8 EGS for Estimating Cluster Number  
It is known from spectral graph theory [10] that the multiplicity of the 0 eigenvalue of the Laplacian (and the normalised Laplacian) is equal to the number of connected components in the graph. For a small number of inter-cluster connections between \(k\) clusters, we expect (by matrix perturbation theory) the \(k\) smallest eigenvalues to be close to 0. This leads to the so-called eigengap between the \(k\)-th and \(k+1\)-th eigenvalue which is used as a heuristic to detect number of clusters in a graph [10]. Here, we first make the above argument about eigenvalues precise in the following theorem.  
Theorem 8.2: _The normalised Laplacian eigenvalue, perturbed by adding a single edge between nodes \(v_{1}\) and \(v_{m+1}\) from two previously disconnected clusters \(A\) and \(B\), is bounded to first order by_  
\[\bigg{|}\frac{1}{\sqrt{d_{1}d_{a}}}+\frac{1}{\sqrt{d_{m+1}d_{b}}}-\frac{2}{ \sqrt{d_{1}d_{m+1}}}\bigg{|}, \tag{15}\]  
_where \(d_{i}\) denotes the degree of node \(v_{i}\), \(1/\sqrt{d_{a}}=\sum_{g\in N(v_{1})}1/\sqrt{d_{g}}\) and similarly \(1/\sqrt{d_{b}}=\sum_{g\in N(m+1)}1/\sqrt{d_{g}}\), where \(\sum_{g\in N(v_{1})}\) denotes the sum over all nodes connecting to node \(v_{1}\)._  
Proof.: Using Weyl's bound on Hermitian matrices  
\[\Delta\lambda_{i}=|\lambda_{i}^{\prime}-\lambda_{i}|\leq||\mathbf{L}_{\text{ norm}}^{\prime}-\mathbf{L}_{\text{norm}}||_{2}\leq||\mathbf{L}_{\text{ norm}}^{\prime}-\mathbf{L}_{\text{norm}}||_{F} \tag{16}\]  
where \(\lambda_{i}\) and \(\lambda_{i}^{\prime}\) are the \(i\)-th eigenvalue of the normalised graph Laplacian \(\mathbf{L}_{\text{norm}}\) and \(\mathbf{L}_{\text{norm}}^{\prime}\) for graph \(G\) and its perturbed version \(G^{\prime}\), respectively, and \(||\cdot||_{2}\) and \(||\cdot||_{F}\) denote the matrix 2-norm and Frobenius norm, respectively. By definition that the \(ij\)-th entry of \(\mathbf{L}_{\text{norm}}\) is that of \(\mathbf{L}\) divided by \(\sqrt{d_{i}d_{j}}\), we have  
\[\Delta\mathbf{L}_{\text{norm}}=\sum_{g\in(g,1)}\bigg{(}\frac{1} {\sqrt{d_{1}d_{g}}}-\frac{1}{\sqrt{(d_{1}+1)d_{g}}}\bigg{)}-\frac{2}{\sqrt{d_ {1}d_{m+1}}}\] \[\qquad\qquad+\sum_{g\in(g,m+1)}\bigg{(}\frac{1}{\sqrt{d_{m+1}d_{ g}}}-\frac{1}{\sqrt{(d_{m+1}+1)d_{g}}}\bigg{)},\]  
to first order in the binomial expansion. We hence prove the result.  
Corollary 1: _For two clusters in which nodes have an identical degree \(d\gg 1\), connected by a single inter-cluster link, the zero eigenvalue is perturbed (to first order) by at most \(\Delta\lambda_{0}=\frac{1}{d}\)._  
Remark 3: _For \(E\) inter-cluster connections, our bound scales as \(E/d\) and hence the intuition of a small change in the 0 eigenvalue holds if the number of edges between clusters is much smaller than the degree of the nodes within the clusters._  
For the case of large sparse graphs, where only iterative methods such as the Lanczos algorithm can be used, the same arguments from Section 3 apply. This is because the Dirac delta functions are now weighted, and to obtain a reliable estimate of the eigengap, one must smooth the spectral delta functions. We would expect a smoothed spectral density plot to have a spike near 0, and the moments of the spectral density to encode this information, and the mass of this peak to be spread. We hence look for the first spectral minimum in the EGS and calculate the number of clusters as shown in Algorithm 3. We conduct a set of experiments to evaluate the effectiveness of our spectral method in Algorithm 3 for learning the number of clusters in a network, where we compare it against the Lanczos algorithm with kernel smoothing on both synthetic and real-world networks.