function M = metriclearning(graph,kernel,lambda,d)
%
% METRICLEARNING : Graph inference by kernel metric learning
%
% Copyright 2007, Jean-Philippe Vert
%
% USAGE:
% M = metriclearning(graph,kernel,lambda,d)
%
% graph is the nxn adjacency matrix
% kernel is the pxn kernel submatrix (p>n)
% lambda is the regularization parameter
% d is the dimension of the projection
%
% See details in Vert and Yamanishi, "Supervised graph inference", NIPS
% 2004.

% Compute the Laplacian of the graph
n = size(graph,1);
p = size(kernel,1);
L = graph - diag(diag(graph));
L = diag(L*ones(n,1)) - L;

% Center the kernel matrices wrt to the first n points (training set)
u1 = eye(p);
u1(:,1:n) = u1(:,1:n) - ones(p,n)/n;
Kv = u1 * kernel * (eye(n)-ones(n,n)/n);

% Solve the generalized eigenvalue problem
[alpha,mu] = eig(L*Kv(1:n,:) + lambda*eye(n) , Kv(1:n,:));

% Sort the alpha's by increasing eigenvalue and keep only the d smallest
% eigenvectors
[m,i] = sort(diag(mu));
alpha = alpha(:,i(1:d));

% Normalize to unit RKHS norm
alpha = alpha .* ( ones(n,1) * (diag(alpha'*Kv(1:n,1:n)*alpha).^(-0.5))' );

% Project all points onto the new basis
f = Kv * alpha;

% Compute all pairwise distances in the new metrics
M = f * f'; %inner products
M = ones(p,1)*diag(M)' + diag(M)*ones(1,p) - 2*M;