[chapter 5] Possible error in LabelPropagation and LabelSpreading

[amarzullo24]

In the notebook 02_Shallow_embeddings.ipynb the rows of the matrix returned by glp.predict_proba(G) are not summing to 1 (as expected, since each row should be a probability assigment over two classes).

I think the issue is due to the fact that the probability distributions are not explicitly normalized at each iteration. In the iterative update step within your while loop, there should be a normalization step after computing the new Y:

while it < self.max_iter and c_tool > self.tol:
    Y = A * Y_prev  # Matrix multiplication for label propagation
    Y = Y / Y.sum(axis=1, keepdims=True)  # Normalize rows to sum to 1

Furthermore, I think the hadamard product (*) there is not intended. Instead, it should be a matrix multiplication. Therefore the final code should be:

while it < self.max_iter and c_tool > self.tol:
    Y = A @ Y_prev  # Matrix multiplication for label propagation
    Y = Y / Y.sum(axis=1, keepdims=True)  # Normalize rows to sum to 1

Both in the GraphLabelPropagation and in the GraphLabelSpreading class

[deusebio]

Yes, it makes sense. Thanks @amarzullo24 for this!

[deusebio]

Just a small point, I believe the * and @ are doing the same thing, as * when applied to matrices falls back to matrix multiplication.

I have tested this using the following code:

DD = np.random.rand(8,8)

assert (inv(DD) @ nx.to_numpy_matrix(G) - inv(DD)*nx.to_numpy_matrix(G)).sum().sum() == 0

[amarzullo24]

@deusebio once the PR is closed, can you please update Figure 5.8 with probabilities summing to 1?