## 3 Distributed Estimation of Laplacian Spectrum
### Retrieving the Non-Zero Laplacian Eigenvalues  
As stated before, the set of eigenvalues deriving from the Algorithm 1, denoted \(\mathcal{S}_{1}\), composing of the set of non-zero distinct Laplacian eigenvalues \(\mathcal{S}_{2}\). Let \(\hat{x}_{i}\) be the final consensus value reconstructed by \(\hat{x}_{i}=\hat{x}_{i}(h)=\frac{1}{N}\sum_{i=1}^{N}x_{i}(0)\) and the iteration scheme of the finite-time average consensus is implemented as in (1). Following the idea of the Proposition 3 in [27], we step-by-step assume to leave one element of the \(\mathcal{S}_{1}\), then, the remaining elements of this set are used to reconstruct \(\hat{x}_{i}(h)\). If \(\hat{x}_{i}=\hat{x}_{i}(h)\) is satisfied, then the left element is not the expected Laplacian eigenvalue. Hence, we can eliminate it out of the set \(\mathcal{S}_{1}\). Otherwise, the left element is one of non-zero distinct eigenvalues. We restore it in the set \(\mathcal{S}_{1}\) and marked as an element in the set \(\mathcal{S}_{2}\). Now, the procedure is continued with another element to the end. The distributed non-zero Laplacian eigenvalues are described in Algorithm 2. ```
1. Initialization: * Number of nodes \(N\), tolerance \(\epsilon\), initial input-output pairs \(\{x_{i}(0),\pi_{i},i=1,2,\ldots,N\}\), where \(\pi=\frac{1}{N}\sum_{i=1}^{N}x_{i}(0)\) is retrieved from a standard average consensus algorithm. * Each node \(i,i=1,\ldots,N\) initializes: 1. random stepsizes \(\alpha_{t,i}(0)\) for \(t=1,\ldots,h=N-1\). 2. random Lagrange multipliers \(\beta_{t,i},\eta_{t,i}\), for \(t=1,\ldots,h\) and \(\lambda_{i},\lambda_{QP,i}\). 3. Semi-positive definite matrices \(\Sigma_{t}\in\Re^{N}\), learning rates \(b\), penalty parameters \(\rho,c,\mu\). * Set \(k=0\);
2. Repeat: * Set \(k:=k+1\), * Solving decouple NLP problem (7) for \(t=1,\ldots,h=N-1\): * Propagate Lagrange multipliers \(\beta_{t,i}[k]\) for \(t=h,\ldots,2\) and \(i=1,\ldots,N\): 1. Set \(\delta_{h,i}[k]=\beta_{t,i}[k]\). 2. \(\delta_{t-1,i}[k]=\delta_{t,i}[k]+\alpha_{t,i}[k]\sum_{j\in\mathcal{N}_{i}}( \delta_{t,j}[k]-\delta_{t,i}[k])\). * Finite-time average Consensus steps: \[x_{t,i}[k]=x_{t-1,i}[k]+\alpha_{t,i}[k]\sum_{j\in\mathcal{N}_{i}}(x_{t-1,j}[k] -x_{t-1,i}[k]).\] * Propagate the error \(e_{t,i}[k]\) by setting \(e_{h,i}[k]=\mathbf{x}_{h,i}[k]-\pi_{i}[k]\): \[e_{t-1,i}[k]=e_{t,i}[k]+\alpha_{t,j}\sum_{j\in\mathcal{N}_{i}}(e_{t,j}[k]-e_{t, i}[k]).\] * Update \(\alpha_{t,i}\) for \(t=1,\ldots,h\): \[\alpha_{t,i}[k+1] =\alpha_{t,i}[k+1]-b\sum_{j\in\mathcal{N}_{i}}(\alpha_{t,j}[k]- \alpha_{t,i}[k])\] \[-b\lambda_{i}-b\rho[k]\sum_{j=1}^{N}\Sigma_{t}(i,j)(\alpha_{t,j}[k]-y_{t, j}[k])\] \[+b\sum_{j\in\mathcal{N}_{i}}(x_{t-1,j}[k]-x_{t-1,i}[k])\delta_{t,i}[k]\] \[+b\sum_{j\in\mathcal{N}_{i}}(x_{t-1,j}[k]-x_{t-1,i}[k])e_{t,j}[k]\] **Algorithm 1** ALADIN-based Laplacian eigenvalues estimation

* Update NLP Lagrange multipliers \(\beta_{t,i}\) for \(t=1,\ldots,h\) by (16). * Stopping criteria: if \(\|\sum_{t=1}^{h}(\boldsymbol{\alpha}_{t}-\mathbf{y}_{t})\|\leq\epsilon\) and \(\|\sum_{t=1}^{h}\boldsymbol{\alpha}_{t}^{T}\mathbf{L}\boldsymbol{\alpha}_{t} \|\leq\epsilon\) are simultaneously satisfied, then stop the optimization procedure. * Compute Gradient, Jacobian matrices, and Hessian matrices as in (8)-(10), respectively. * Solving the coupling QP problem (11) via solving the linear Equation (19) to define \(\Delta\alpha_{t,i}^{*}[k],\lambda_{QP,i}^{*}[k]\). * Update \(\lambda,\hat{g}_{t,i}\): 1. \(\lambda_{i}[k+1]=\lambda_{QP,i}^{*}[k]\) 2. \(\hat{g}_{t,i}[k]=\alpha_{t,i}[k+1]+\Delta\alpha_{t,i}^{*}[k]\) 3. Projecting \(\hat{g}_{t,i}[k]\) onto the constraint \(\mathcal{C}\) by solving an ADMM-based optimization subproblem (20) to derive \(y_{t,i}[k+1]\)
```
1. Input: set of stepsizes, obtaining form Algorithm 1\(\mathcal{S}_{1}\), the input-output pairs \(\{\mathbf{x}_{i}(0),\bar{\mathbf{x}}_{i}\}\), \(i=1,\ldots,N\), the threshold \(\epsilon\). 2. Set \(\mathcal{S}_{2}=\emptyset\), \(\mathcal{S}=\mathcal{S}_{1}\). 3.