Repository navigation
fix(kg): build the PageRank adjacency once for a graph dict, not per node - #1844
Conversation
…node _get_filtered_neighbors called build_adjacency(graph, directed=True) for every node of a plain graph dictionary, so neighbour resolution cost O(N * (N + E)). calculate_pagerank now builds it once before the node loop and passes it in through an optional adjacency argument; scores are unchanged. Fixes semantica-agi#1842.
|
ⓘ Qodo reviews are paused because the subscription is no longer active. Ask your workspace admin to reactivate the subscription to resume reviews. Manage billing |
PR Summary by QodoBuild dict-graph PageRank adjacency once per calculation
AI Description
Diagram
High-Level Assessment
Files changed (3)
|
Code Review by Qodo🐞 Bugs (0) 📘 Rule violations (0) 📎 Requirement gaps (0)
Great, no issues found!Qodo reviewed your code and found no material issues that require reviewTip of the day💡 Did you know, you can route each severity your way: inline, summary, both, or drop |
|
One heads-up: this touches the same lines in |
pkupt
left a comment
There was a problem hiding this comment.
Verified against #1842. The dict-graph adjacency is now built once before the node loop and reused, and the adjacency=None default keeps the old behavior for the non-dict paths and for direct callers of _get_filtered_neighbors. I confirmed main still rebuilds it per node at centrality_calculator.py:660 and :748, so the merged #1770 did not already cover this and the fix is still needed.
I ran the new test here: 2 passed.
One non-blocking note: the reuse only applies when graph is a plain dict; a networkx graph still walks graph.neighbors(node) per node. That path is already cheap and outside #1842, but if that loop ever shows up hot for networkx graphs it would be a separate change.
The branch is behind main, so it needs a rebase before it merges. Nothing else from me.
Sameer6305
left a comment
There was a problem hiding this comment.
✅ Approve
This PR correctly fixes #1842.
The problem was that PageRank on plain graph dictionaries rebuilt the adjacency structure once per node, causing unnecessary O(N × (N + E)) work.
The PR fixes this by:
- building the adjacency once before the PageRank node loop;
- reusing that adjacency for each
_get_filtered_neighbors()call; - retaining
adjacency=Noneas the fallback so direct callers and non-dict/networkx paths preserve their existing behavior; - adding regression coverage for adjacency reuse and node-label behavior;
- documenting the performance fix in the CHANGELOG.
Review findings:
- The adjacency is now built exactly once for dict graphs.
- PageRank results and error behavior were unchanged across multiple graph sizes, node-ID types, and filtering cases.
- No new hidden O(N²) work was introduced.
- No mutation/staleness, recursion, infinite-loop, security, or data-loss issues were found.
- The regression test correctly fails against the base implementation and passes with the fix.
- The existing
relationship_typesedge-scan cost is outside this PR and is not introduced by the change.
Validation:
- 20 targeted tests passed.
- 26 relevant tests passed on a trial merge with
origin/main. - Trial merge was clean.
Approved.
Description
PageRank on a plain graph dict called build_adjacency once per node, so a 30-node graph built the adjacency 30 times. It is now built once before the node loop and passed to _get_filtered_neighbors, which still builds it itself when called without one.
Type of Change
Related Issues
Fixes #1842
Changes Made
Testing
python -m build)Test Commands
Ran the two pytest files above on the committed HEAD: 20 passed. The new test fails at the base commit (30 calls, expected 1). Build, black and isort were not run, so those stay unticked.
Documentation
Breaking Changes
Breaking Changes: No
Checklist
Additional Notes
Checklist items not ticked were not run on this HEAD.