[BUG] Spectral Matching divide by zero

[maberrospi]

Description: I am trying to use spectral matching to get correspondence between nodes in graphs of different sizes. As per the documentation, I create sparse adjacency matrices, followed by an affinity matrix, which is then passed to the spectral matching function. I get 3 RunTimeWarnings as follows:

*\Lib\site-packages\numpy\linalg\linalg.py:2582: RuntimeWarning: overflow encountered in multiply
  s = (x.conj() * x).real
*\Lib\site-packages\pygmtools\numpy_backend.py:279: RuntimeWarning: divide by zero encountered in divide 
  v = np.matmul(v, (1 / n).reshape((batch_num, 1, 1)))
*\Lib\site-packages\pygmtools\numpy_backend.py:279: RuntimeWarning: invalid value encountered in matmul  
  v = np.matmul(v, (1 / n).reshape((batch_num, 1, 1)))

To Reproduce Unfortunately I don't have an exact example to add with data but I will provide the bare bones.

import pygmtools as pygm
import numpy as np
# Get the node feature matrices
g1_node_feat_matrix = get_node_feat_matrix() # shape: [n1,n_features] (e.g. [32,64])
g2_node_feat_matrix = get_node_feat_matrix() # shape: [n2,n_features] (e.g. [48,64])

# Get the edge feature matrices
g1_edge_feat_matrix = get_edge_feat_matrix() # shape: [e1,n_features] (e.g. [100,7])
g2_edge_feat_matrix = get_edge_feat_matrix() # shape: [e2,n_features] (e.g. [132,7])

# Assume we have adjacency matrix and transform it to sparse
A1, _ = pygm.utils.dense_to_sparse(A1)
A2, _ = pygm.utils.dense_to_sparse(A2)

# Change data types to conserve memory
g1_node_feat_matrix = g1_node_feat_matrix .astype("float16")
g2_node_feat_matrix = g2_node_feat_matrix .astype("float16")
g1_edge_feat_matrix = g1_edge_feat_matrix .astype("float16")
g2_edge_feat_matrix = g2_edge_feat_matrix .astype("float16")
A1 = A1.astype("int16")
A2 = A2.astype("int16")

# Build the affinity matrix
K = pygm.utils.build_aff_mat(
    g1_node_feat_matrix, g1_edge_feat_matrix, A1, g2_node_feat_matrix, g2_edge_feat_matrix, A2
)

# Run spectral matching
# n1 and n2 are the number of nodes in g1 and g2 respectively
S = pygm.sm(K, n1=n1, n2=n2) # error!

# Use sinkhorn to get doubly-stochastic matrix
S = pygm.sinkhorn(S, dummy_row=True, max_iter=iter, tau=tau)

Environment:

• OS: Windows-11
• Python Version: 3.12.2
• Pygmtools Version: 0.5.2
• Environment report: Windows-11-10.0.22631-SP0 Python 3.12.2 | packaged by conda-forge | [MSC v.1937 64 bit (AMD64)] NumPy 1.26.4 SciPy 1.13.0 pygmtools 0.5.2 Torch 2.2.2 Paddle not installed Jittor not installed No GPU found. If you are using GPU, make sure to install pynvml: pip install pynvml

Additional context FYI. The sinkhorn algorithm column and row sums return NaN. I am sorry I could not provide reproducible code and hope this is enough. Looking forward to your reply.

[rogerwwww]

Hi, thanks for using our toolkit. By looking at your error message, can you please check if your K is all-zero?

[maberrospi]

Hi, thanks for your quick response!

K using edge weights returned from edge_to_sparse function (following documentation): K using custom edge features: K using custom edge features zoomed in:

It seems in both cases K is sparse but is not zero everywhere. Note that both cases result in the same error.

[rogerwwww]

Another possibility might be the values in your K matrix is too large. Please try normalizing them to 0-1

[maberrospi]

I normalized K (min-max norm) and the error disappears in most cases. I have a case where I still get it but I suppose it might be an error of mine. Thank you for your help!

[rogerwwww]

Good to know! No worries.

I am closing this issue and please feel free to reopen it if the error still exists.