Skip to content

fix(kg): build the PageRank adjacency once for a graph dict, not per node - #1844

Merged
Sameer6305 merged 2 commits into
semantica-agi:mainfrom
drakeo338:claude/1842-fix
Oct 4, 2026
Merged

Sameer6305 merged 2 commits into
semantica-agi:mainfrom
drakeo338:claude/1842-fix

Conversation

@drakeo338

Copy link
Copy Markdown
Contributor

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

  • Bug fix (non-breaking change which fixes an issue)
  • New feature (non-breaking change which adds functionality)
  • Breaking change (fix or feature that would cause existing functionality to not work as expected)
  • Documentation update
  • Performance improvement
  • Code refactoring

Related Issues

Fixes #1842

Changes Made

  • Build the adjacency once in the PageRank loop for dict graphs
  • Optional adjacency argument on _get_filtered_neighbors
  • New test plus a CHANGELOG line

Testing

  • Tested locally
  • Added tests for new functionality
  • Package builds successfully (python -m build)

Test Commands

# Build the package
pip install build
python -m build

# Optional: Run your own tests
pytest tests/kg/test_centrality_pagerank_adjacency_reuse.py tests/kg/test_centrality_pagerank_node_labels.py

# Optional: Format code
black semantica/
isort semantica/

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

  • Updated relevant documentation
  • Added code examples if applicable
  • Updated API reference if adding new APIs
  • Updated cookbook if adding new examples
  • No documentation changes needed

Breaking Changes

Breaking Changes: No

Checklist

  • My code follows the project's style guidelines
  • I have performed a self-review of my code
  • I have commented my code, particularly in hard-to-understand areas
  • My changes generate no new warnings
  • Package builds successfully

Additional Notes

Checklist items not ticked were not run on this HEAD.

…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-code-review

Copy link
Copy Markdown

ⓘ Qodo reviews are paused because the subscription is no longer active. Ask your workspace admin to reactivate the subscription to resume reviews. Manage billing

@qodo-free-for-open-source-projects

Copy link
Copy Markdown

PR Summary by Qodo

Build dict-graph PageRank adjacency once per calculation

🐞 Bug fix 🧪 Tests 📝 Documentation 🕐 10-20 Minutes

Grey Divider

AI Description

• Build outgoing adjacency once per dict-graph PageRank calculation instead of once per node.
• Preserve neighbor filtering and standalone helper behavior through an optional prebuilt adjacency.
• Add regression tests and document the performance fix.
Diagram

graph TD
G["Graph input"] --> D{"Plain dict?"} -->|yes| A["Shared adjacency"] --> F["Filtered neighbors"] --> M["Sparse matrix"] --> P["PageRank scores"]
D -->|no| N["Graph neighbors"] --> F
Loading
High-Level Assessment

Prebuilding adjacency at the PageRank call site is the simplest way to reuse it for one calculation without introducing a persistent cache or changing non-dict handling. The helper retains its existing behavior when no adjacency is supplied.

Files changed (3) +70 / -4

Bug fix (1) +21 / -4
centrality_calculator.pyReuse dict-graph adjacency across PageRank nodes +21/-4

Reuse dict-graph adjacency across PageRank nodes

• Builds directed adjacency once before the PageRank node loop for dict graphs and passes it to neighbor resolution. The helper accepts optional prebuilt adjacency but still builds its own when called without one.

semantica/kg/centrality_calculator.py

Tests (1) +46 / -0
test_centrality_pagerank_adjacency_reuse.pyCover adjacency build count and PageRank score behavior +46/-0

Cover adjacency build count and PageRank score behavior

• Asserts that a 30-node dict graph triggers one adjacency build. Also checks score normalization, a relative ranking, and the node set when relationship-type filtering is used.

tests/kg/test_centrality_pagerank_adjacency_reuse.py

Documentation (1) +3 / -0
CHANGELOG.mdDocument the PageRank adjacency performance fix +3/-0

Document the PageRank adjacency performance fix

• Records the repeated-adjacency issue, its complexity impact, the fix, and the new regression test under Fixed.

CHANGELOG.md

@qodo-free-for-open-source-projects

Copy link
Copy Markdown

Code Review by Qodo

🐞 Bugs (0) 📘 Rule violations (0) 📎 Requirement gaps (0)

Grey Divider

Great, no issues found!

Qodo reviewed your code and found no material issues that require review

Grey Divider

Tip of the day
💡 Did you know, you can route each severity your way: inline, summary, both, or drop

More tips ↗ | Customize Qodo ↗ | Qodo docs ↗

Grey Divider

Qodo Logo

@pkupt

pkupt commented Oct 1, 2026

Copy link
Copy Markdown
Collaborator

One heads-up: this touches the same lines in calculate_pagerank as #1770, so whichever of the two lands second will need a rebase in that function. The changes do different jobs, #1770 is about mass normalisation and the max_iterations behaviour on a DiGraph, so they should sit fine next to each other. If yours lands first I'll rebase mine on top of it; if mine goes in first, your side is a small rebase since the adjacency build just moves above the loop. Building the adjacency once outside the node loop is the right call either way.

@pkupt pkupt left a comment

Copy link
Copy Markdown
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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
Sameer6305 self-requested a review October 4, 2026 18:23

@Sameer6305 Sameer6305 left a comment

Copy link
Copy Markdown
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

✅ 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=None as 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_types edge-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.

@Sameer6305
Sameer6305 merged commit f87998d into semantica-agi:main Oct 4, 2026
12 checks passed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

perf(kg): calculate_pagerank on graph dicts rebuilds adjacency once per node (O(N²))

3 participants