Implementation of Vertex Similarity algorithm (Blondel's Similarity Measure)
private final int M, N;


It's Java. Albeit M and N may get big, you should use camelcase (small initial letters) for non-constant fields. Maybe something like width and height? Or rows and colums, or m and n, if you insist.

public Matrix(double[][] data) {
    M = data.length;
    N = data[0].length;
    this.data = new double[M][N];
    for (int i = 0; i &lt; M; i++)
        for (int j = 0; j &lt; N; j++)
                this.data[i][j] = data[i][j];
}


Either make the method non-public or check arguments, especially check that each row has the same length. Apart from this, the inner loop could be replaced by

this.data[i] = data[i].clone();





  What I want feedback on is memory efficiency, to not make new matrices as much as possible.


Matrix firstProduct = Y.times(Sk).times(X.transpose());


Here you're creating an new matrix, while a view of the original would do (albeit probably slower). You could instead define a timesTransposed operation and have the full speed without any allocations. That's pretty simple and you can test it nicely using the existing operations.

Matrix totalProduct = firstProduct.plus(secondProduct);


Here you can avoid allocations by implementing the equivalent of +=. It surely doesn't make you code more readable, but sometimes that's the price for efficiency.

An operation like *= could get pretty complicated for matrices (and is rather impossible for non-square matrices, so lets forget it).



    double[][] data = totalProduct.transpose().data;
    Sk = new Matrix(normalizeByRows(data)).transpose();


Here, you're refusing to use objects and I really can't why. normalizeByRows should be a method (either modifying an existing matrix or creating a new one; choose what you need, but be careful with naming).



// This is the actual algorithm.


So don't put it in main. Make a method, name it properly and save yourself that comment.