Been a long time (~10 years) since I've looked at any graph database, and I've never used Neo4j (I remember fighting with Giraph though, had a hell of a time getting that to compile).

I like this paper's assessment of graph databases: https://db.cs.cmu.edu/papers/2024/whatgoesaround-sigmodrec2024.pdf

TLDR is graph databases do have some performance optimizations over RDBMS due to the storage layout and optimized algorithms for common queries (shortest, ancestors, etc), but ultimately you can also represent a graph as a collection of tables. Recently some RDBMS systems have been adding graph-like query languages and have been optimizing joins for graph queries and they have been claiming better performance.

If you're not doing large OLAP queries or using it for other purposes, Neo4j seems like a pretty good fit for a Nostr relay.