Expander hypergraph lifting (graph to hypergraph)

pyt-team / challenge-icml-2024

Official repository for the Topological Deep Learning Challenge 2024, organized by TAG-DS & PyT-Team and hosted by GRaM Workshop @ ICML 2024.

https://pyt-team.github.io/packs/challenge.html

MIT License

38 stars 49 forks source link

Expander hypergraph lifting (graph to hypergraph) #23

Open sukjulian opened 4 months ago

sukjulian commented 4 months ago

This lifting generates an expander (hyper-)graph, more precisely a random Ramanujan graph. It is inspired by recent works on expander graph propagation and expander graph transformers. Expander graphs have favourable, mathematical guarantees w.r.t. node connectivity. E.g., they enable message propagation from any node to any other node in few iterations.

Tags and categories:

existing lifting from the literature (however GNN literature) | connectivity-based lifting | non-deterministic lifting

The code would be considerably cleaner if we had access to networkx >= 3.3. As a workaround, we copy & pasted the required functions here. However, this can be removed and cleaned up once networkx is upgraded.

Submission by team MIA-UT: Patryk Rygiel (@PatRyg99), Julian Suk (@sukjulian)

review-notebook-app[bot] commented 4 months ago

Check out this pull request on

See visual diffs & provide feedback on Jupyter Notebooks.

Powered by ReviewNB

sukjulian commented 4 months ago

We have been discussing about expander graph lifting and came to the conclusion that the lifting target might not actually qualify as hypergraph: the incidence matrix's rows always sum to two. The lifting could be considered point cloud to graph, but it would be independent of point positions. It's probably best to discuss at some point what aligns best with the concept behind the repository.

gbg141 commented 4 months ago

Hello @sukjulian! Thank you for your submission. As we near the end of the challenge, I am collecting participant info for the purpose of selecting and announcing winners. Please email me (or have one member of your team email me) at guillermo_bernardez@ucsb.edu so I can share access to the voting form. In your email, please include:

your first and last name (as well as any other team members)
the title of the method you implemented
the input domain of the method you implemented
the output domain of the method you implemented
your pull request number (#23)

Before July 12, make sure that your submission respects all Submission Requirements laid out on the challenge page. Any submission that fails to meet this criteria will be automatically disqualified.