Fix Laplacian calculation in spectral partitioning #2568
Conversation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
…dsai#2507)" This reverts commit deff995.
…to fix-sparse-utilities
|
Also partially answers #379, though we may want additional testing beyond what is provided here. |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
These changes enable the use of the new Lanczos solver for spectral partitioning. This solver gives the correct eigenvalues in some cases where the old solver did not, but a previous attempt to introduce this led to a downstream breakage because the Laplacian was not being calculated correctly in the spectral partitioning logic.
In this PR, we introduce a new
compute_graph_laplacianfunction to correctly generate a new CSR matrix representing the graph Laplacian of the input CSR-formatted adjacency matrix. This resolves #2419. This function is used in the spectral partition function to obtain the correct partitioning using the new Lanczos solver. This eliminates all internal uses ofcomputeSmallestEigenvectors, the old Lanczos implementation, which should allow it to be removed after a deprecation cycle for downstream consumers. This will in turn allow us to resolve #313.Note that the originally-reported breakage from the previous attempt to switch to the new Lanczos solver was used to create the test confirming correct functionality of the current PR.
This PR is marked as a bugfix because it unblocks usage of the corrected Lanczos implementation. It is based on and requires PR #2541, and it will be marked as draft until that PR is merged.