# Help with inferring Network topology from Spectral templates

I am trying to use matlab and YALMIP to solve a graph learning problem of recovering eigenvalues from the eigenvectors of the covariance of sampled graph signal data. This is to implement the algorithm in https://graphex.mit.edu/sites/default/files/documents/2017_Poster_Segarra.pdf. A better explanation is their paper https://ieeexplore.ieee.org/document/7990048. My objective is to estimate the Adjacency matrix. I have tried different versions of the constraints and other troubleshooting, but lambda is always NaN or very small, and estimated_A is also very small, so interpreted as 0. This is my first time working through this kind of optimization problem and I appreciate any assistance. Thank you.

My code is

% Generate a random network with 100 nodes
N = 100;
G = gsp_sensor(N);
A = G.A;
D = diag(sum(A, 2));
L = D - A;   % Laplacian matrix

% Generate observed graph signals
X = sin(rand(N, N));

% Diffuse graph signals using the heat equation
alpha = .5;
X_diff = zeros(N, N);
for t = 1:N
X_diff(:, t) = (eye(N) - alpha * L) * X(:, t);
end

% Compute sample covariance matrix
C = (X_diff * X_diff') / N;

% Extract spectral templates by computing the eigenvectors and eigenvalues of the sample covariance matrix
[V, D] = eig(C);

% Formulate optimization problem with YALMIP
A_est = sdpvar(N, N, 'full');  % Unknown graph shift operator (Laplacian matrix)
lambda = sdpvar(N, 1);       % Unknown eigenvalues

options = sdpsettings('verbose', 2, 'solver', 'sedumi');
% Define the objective function (minimize L1 norm of A)
objective = norm(A_est(:), 1);

% Set up the constraints
constraints = [A_est == V * diag(lambda) * V', A_est == A_est', diag(A_est) == zeros(N, 1), A_est >= 0, sum(A_est, 2) ==1];

% Define objective function
objective = norm(A_est(:), 1);

% Solve SDP problem using YALMIP
sol = solvesdp(constraints, objective, options);

disp(value(A_est));
disp(value(lambda));


I am currently not able to even reproduce the assumption that the eigenvectors of the graph shift operator (adjacency matrix) are equal to the eigenvectors of the signal covariance matrix.

% Define the size of the matrix
N = 5;

% Create a symmetric simple graph GSO (Adjacency matrix)
A = zeros(N);  % Initialize
for i = 1:N-1
for j = i+1:N
A(i, j) = 1;
end
end
A = A + A';  % Make symmetric

% Compute eigenvectors of the GSO
[VA, ~] = eig(A);

% Generate white signals: N signals of length N
X = randn(N, N);  % White signals have a covariance matrix that is the identity matrix

% Apply the eigenvectors as a filter to the white signals
X_filtered = VA * X;

% Compute the covariance matrix of the filtered signals
C = cov(X_filtered');

% Compute eigenvectors of the signal covariance matrix
[VC, ~] = eig(C);

% Compare eigenvectors (This will be qualitative. For quantitative, consider using norms or inner products)
disp('Eigenvectors of A:');
disp(VA);
disp('Eigenvectors of C:');
disp(VC);

• What have you already done to debug your script? Commented Dec 4, 2023 at 18:41
• Hi Wolfgang, so far I have deleted and tried to modify the constraints, I have also tried to use the eigenvectors of the original A and L matrixes. The best I have gotted is an all-ones lambda vector and a trivial matrix with ones in the diagonal. Commented Dec 4, 2023 at 21:14
• Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer.
– Community Bot
Commented Dec 5, 2023 at 12:44
• Have you solved this problem? I am currently looking for a reproduction code for this paper. Commented Dec 28, 2023 at 9:32
• I haven't been able to create a sucessful algorithm to reporduce their results, and I am also having issues with creating data that matches their assumption: that the eigenvectors of the GSO are the same as the eigenvectors of the signal covariance matrix. Commented Jan 28 at 15:25