create new generator that returns a random k-lift of a d-regular graph

[sean-chernov]

This module implements a k-lift construction using random permutations for a given d-regular base graph. It supports applications in network topology design, such as the Xpander architecture, where high spectral expansion is desired.

[dschult]

Can you make this PRs title/subject line informative?

[sean-chernov]

Title updated. Regrarding the tests, I had a problem with my pre commit, that I now fixed. I will update the files and sorry for this (my first time contributing)

[sean-chernov]

Hi! Just a friendly reminder to take a look at this PR when you get the chance. Let me know if there’s anything I should adjust or clarify. Thanks!

[sean-chernov]

Updated this PR to address the previous comments. The function has been moved to the generators module, and I’ll update the import statements accordingly once a final location is decided.

If helpful, I can also add an nx.draw visualization to accompany the example for clarity.

[sean-chernov]

Hi! Just wanted to check in. Are there any further changes you'd like me to make (aside from the final placement), or at this point is it more a question of whether the PR fit within NetworkX? Happy to adjust if needed!

[sean-chernov]

Hello,

I'm just checking in on this PR and the related PRs #8066 and #8118.

I'm available to address any feedback, make necessary changes, or answer any questions you might have. Please let me know what the next steps are to help move this forward.

Thank you!

[sean-chernov]

Hello, we understand that review takes time, and we’re happy to respond to any questions or decisions you make. At the same time, we need to close our project within the next couple of weeks, so it would be very helpful to receive feedback on this PR, the k-lift, being the simplest one. If you’d like additional sources about k-lifts or expanders in general, we can provide them. We also have a project document that discusses these PRs and their evaluations in greater detail.

[sean-chernov]

Made the requested fixes and added k-lift to random_graphs with its test. Also updated random_graphs to be fully in sync with the main branch. Waiting for further approval before removing the separate k_lift files.

[dschult]

Searching for k-lift in the literature brought me to many discussions of a lift of a graph. But they are not generating random versions of it. So I think it makes sense to call the function random_k_lift.

Then I think the location of the random module, the test_random test module and hooks to the documentation in the random graphs makes good sense.

[sean-chernov]

Thanks for the suggestion, I’ll rename the function and PR to random_k_lift to avoid confusion with deterministic or derandomized lift constructions. This also reflects the standard naming in the literature, since the algorithm here relies on random permutations to generate the lift.

[sean-chernov]

Hi, just an update. I renamed the function to random_k_lift and added it to doc/reference/generators.rst under the random graph generators section. Would appreciate any feedback on whether this looks ready for merge or if there are additional changes needed.

Thanks!

[sean-chernov]

Hi, just checking back on my earlier response regarding the connectivity handling. In short, I outlined two possible directions:

1. updating to the more user friendly connectivity logic (with tries, clearer error handling, and docstring notes), or
2. Remove it and keep the function fully general.

I’d be happy to implement whichever approach best aligns with NetworkX’s expectations, just let me know which you’d prefer.

[dschult]

Thanks for the nudge -- I'm not sure I know which way of handling it is better. From a naive generalist perspective, it seems just fine to return disconnected results and it saves checking if the result is disconnected. From the perspective of a user/developer can you imagine the code you prepped for multiple tries to be easily provided by the user? Say the user is like you and wants to use this for expander graphs. Does putting the connected check inside this function save you considerably over having it just return the disconnected result (and I guess you would have to check that it is connected and retry if desired)?

[sean-chernov]

After some thought and based on your feedback, I will remove the connectivity raise and let the function return disconnected results. My main reasoning is that the cases that require the most effort for connectivity handling (particularly edge cases that can go either way) already correspond to base graphs that yield poor expanders at best, and thus aren’t worth complicating the function over.

To make this clear for users, I’ll add a short explanation in the docstring Notes about the connection to expanders, and mention that users who require connected results can retry externally.

This keeps the function simple, general, and consistent with NetworkX style, while still documenting its relevance to expander constructions.

[sean-chernov]

Hi, thanks again for the helpful feedback and review. With the recent changes applied, is the implementation now in good shape for merging, or would you like me to make any further adjustments?

[sean-chernov]

Thanks for the reviews and helpful suggestions on this PR! I’ve committed the formatting fixes. I’m glad the docs and structure are in good shape, and I’m happy to revisit the placement in a follow-up PR if that’s the direction you’d like to go.

[Peiffap]

Thanks for going over these again; there are still some places where the same suggestions apply. Could you go over those too? I suggested an edit adding single backticks around sigma, those should be double backticks.

[sean-chernov]

I’ve gone over the docstring again and applied the suggestions to the remaining cases I had missed earlier, including the sigma formatting. This also resolved the GitHub documentation errors I was seeing before. Thanks again for catching those details!

[sean-chernov]

I’ve fixed the nits, thanks again for the review!

[sean-chernov]

Hi, just checking in regarding this PR. It’s been about three weeks since the generalization updates (allowing all graph types and adding the relevant references), so I wanted to ask whether there’s been any further discussion or a conclusion regarding the new data and changes. Please let me know if there’s anything else I can clarify or adjust to help move it forward.

[sean-chernov]

Hello, I just wanted to follow up and mention that we’re hoping to finalize our project (including an answer regarding this PR) by the end of this month.

[sean-chernov]

Hi, just reminding you of the previous message

[sean-chernov]

Hi, just checking in to see whether there have been any updates or further thoughts on the review of this PR.

[sean-chernov]

Great, thank you! I’d like to mention that this PR, together with PR #8066 and PR #8118, is part of a project I worked on with Shai Reuven at the NSSL Laboratory, Technion. Thank you for the opportunity to contribute to NetworkX.

Once this PR is wrapped up, we’d be happy to discuss the remaining PRs as well.

[sean-chernov]

Thanks for the detailed feedback!

On the degree question: For directed graphs, yes, each lifted node preserves the in- and out-degree of its associated node in G. For undirected graphs, the degree is also preserved (not doubled), since each original edge induces a matching between copies. Considering the example in the directed test, the in/out degrees are 1 for G and also for H. For undirected graph based on the same list of edges we will get G with degree of 2 which will be preserved in H.

I’ll also make the suggested cleanups locally: – Construct test graphs explicitly using nx.(edge_list). – Move comments to their own lines. – Introduce a variable k and use it consistently in assertions (e.g. len(G) * k). – Ensure docstrings respect the 88-character line limit.