Some thoughts after using Panther/Panther++

I finally had a chance to take both for a spin, and I found a few small surprises/inconsistencies:

• Looking at the paper again, the sample size formula uses C(T, 2) where T is the number of nodes in a path. The way we're generating paths, we're calling math.comb(path_length, 2), but path_length is the edge count, not the node count, this means we're missing sample paths (C(5,2) = 10 vs C(6,2) = 15).
  • The fix would be a simple t_choose_2 = math.comb(path_length + 1, 2).
• Because index_map is populated only with nodes that appear in at least one sampled path, for a disconnected graph with a sufficiently small R, you can get a KeyError if you try to access a node that was never visited (index_map[vi]).
  • I think the likelihood of hitting this is pretty low since we remove isolates in panther_similarity and we have a guard against isolates on panther_vector_similarity, but it's an easy fix of just index_map.get(source, set())
  • I'm also wondering whether we should handle isolates in panther_vector_similarity (as we do in panther_similarity) instead of refusing. A graph like {0-1, 0-2, 3(isolated)} with source=0 is perfectly valid for similarity computation.
• Per the paper, we probably want math.ceil instead of int -- this "off-by-one" has a negligible impact in practice, but I missed that the formula for R is giving a lower bound.
• In #4400, I said

Note: I didn't reuse the epsilon parameter because for a sufficiently small graph, that value could be 1.0, which I think would be entirely too large for a reasonable epsilon.

But on L1942, I do use it... We could potentially decouple it from the sampling epsilon with something like

neighbor_distances = np.maximum(neighbor_distances, np.finfo(float).eps)

• Docstring issue in panther_similarity

So, for k = 5, a dictionary of top 4 nodes and their similarity scores will be returned.

As of #4400, it actually does return k.

• I'm wondering if we want more param validation in _prepare_panther_paths since it's possible to get OverflowErrors and ZeroDivisionErrors. Perhaps something like (with the right error classes)

 if path_length < 2:
     raise nx.NetworkXError("path_length must be >= 2")
 if not (0 < delta < 1):
     raise nx.NetworkXError("delta must be in (0, 1)")
 if eps is not None and eps <= 0:
     raise nx.NetworkXError("eps must be positive")
 if c <= 0:
     raise nx.NetworkXError("c must be positive")

• In panther_similarity, for small dense graphs where all similarity scores are equal, np.argpartition can exclude the source node from the top k+1 partition, and pop(source) removes nothing, yielding k+1 results. I think we just need a guard like

 top_k_with_val.pop(source, None)
 if len(top_k_with_val) > k:
     sorted_items = sorted(top_k_with_val.items(), key=lambda x: x[1], reverse=True)
     top_k_with_val = dict(sorted_items[:k])