Graph Construction Logic Problems in k-NN Graph Building

[zhiqing0205]

Summary

I've discovered two potential issues in the graph construction process within utils/graph_utils.py that may be affecting the effectiveness of the add_label_edges and rewire_edges operations. I would appreciate your insights on these observations.

Problem 1: Label-Based Edge Addition Not Effective

Location: build_knn_graph_from_features() function, add_label_edges section

Issue: The current logic for adding label-based edges appears to be adding duplicate edges that get removed during deduplication, resulting in no actual new edges being added to the graph.

Details:

• The code correctly identifies nodes with the same labels
• However, it then filters these nodes to only include those already in the k-nearest neighbors (valid_neighbors = [j for j in same_label if j in knn_neighbors])
• Since these neighbors are already connected by the initial k-NN construction, adding edges between them creates duplicates
• After deduplication with edge_list = list(set(edge_list)), no new edges are actually added

Evidence: Added debugging counters show that label_based_add_success_cnt is typically 0 or very low compared to label_based_add_cnt.

Problem 2: Edge Rewiring Ineffective Due to Zero Similarities

Location: build_knn_graph_from_features() function, rewire_edges section

Issue: The rewiring logic attempts to connect nodes with the same labels that are NOT in the k-nearest neighbors, but the similarity calculation assigns 0 to all such nodes, preventing any rewiring.

Details:

• The code correctly identifies same-label nodes not in the current neighbors
• However, when computing similarities: sims = [1.0 - dists[i, np.where(inds[i, :] == j)[0][0]] if j in inds[i, :] else 0.0 for j in same_label]
• All nodes not in inds[i, :] (the k-NN list) get similarity 0.0
• The condition if i < j and sims[idx] > 0.0: then prevents any edges from being added
• Result: rewired_count consistently remains 0

Suggested Discussion Points

1. For Problem 1: Should we modify the logic to add edges between same-label nodes that are NOT already in the k-NN connections?

2. For Problem 2: Should we compute actual feature-based similarities for same-label nodes outside the k-NN list, rather than defaulting to 0?

3. Overall: Are these operations intended to work as currently implemented, or might there be a different approach to achieve the desired graph connectivity improvements?

Impact

These issues may be affecting:

• Graph homophily and clustering properties
• Model performance on classification tasks
• The effectiveness of the fuzzy rule learning process

I would be grateful for any guidance on whether these observations are correct and how we might address them to improve the graph construction process.

Thank you for your time and consideration.

[zhiqing0205]

[zhiqing0205]

Moreover, the number of edges constructed here does not match the edge count reported in Table 2 of Appendix A.1 of the paper.