Graph vs. Relational: Navigating the Trade-offs of Social Graph Design

TL;DR

Choosing a graph database doesn't automatically guarantee superior performance for social networks. This study analyzes Neo4j using the BG benchmark to reveal that physical design choices (like how you label friendship edges) and workload characteristics (like the presence of profile images) radically shift the "winner" between Graph and Relational systems.

Context: Beyond Middle-Tier Benchmarking

Most developers choose graph databases like Neo4j because they "feel" more natural for social networks. However, in the academic coordinate system, this work moves beyond intuitive feelings. It introduces the SoAR (Social Action Rating)—a metric that measures the highest throughput a system can sustain while ensuring 95% of requests finish in under 100ms.

The Core Conflict: Why is this Hard?

The primary challenge in social graph design is the Read/Write Tension.

1. Compute vs. Stored: If you store a user's friend count as a property (Stored), your "View Profile" is instant, but your "Accept Friend" action becomes expensive because it must update counters.
2. Labeled vs. Distinct: Do you mark a friendship as "pending" or "confirmed" via a property label, or do you delete a "Pending" edge and create a "Friend" edge?

Methodology: The 2x2 Design Space

The authors categorize graph representations into four distinct quadrants to test their resilience against heavy write traffic.

Insights on Graph Actions:

• Get Shortest Distance (GSD): The authors highlight a fascinating trade-off between Speed and Accuracy. In Neo4j, limiting traversal depth makes the query 6x faster but can drop accuracy to as low as 7% depending on the member's "friendship density" ($\varphi$).
• The RDBMS Paradox: Surprisingly, for queries like "List Common Friends," an industrial RDBMS (SQL-X) decimated Neo4j. Because the RDBMS stores friendships in a compact, vertically-sliced table, it avoids the overhead of loading entire vertex objects (which might contain heavy metadata).

Experimental Analysis: Results that Surprise

The most striking finding comes from the Image Variable.

• In a "No Image" environment: SQL-X (Relational) provides a SoAR of ~20,550, while Neo4j only manages ~1,460.
• In a "With Image" environment: The tables turn. SQL-X drops to 360, while Neo4j stays stronger at 835.

Why? Relational databases traditionally struggle with BLOB (Binary Large Object) storage within the table row, causing massive IO overhead during joins. Neo4j’s architecture handles these property attachments more gracefully under high concurrency.

Critical Insight & Conclusion

The Takeaway

This paper serves as a reality check for the "Graph is always better for relationships" dogma. If your graph consists of simple IDs and high-speed traversals, an optimized SQL schema might actually be your best bet. However, if your data model is heterogeneous—mixing large profile properties with complex relationships—Neo4j provides a much more stable throughput (SoAR) under strict SLAs.

Limitations

The study focuses on a single-node Neo4j deployment via REST. In 2026, the industry has moved toward distributed graph clusters. The REST API overhead itself might be a bottleneck that obscures the true potential of the underlying storage engine compared to native drivers.

Future Work

The authors point toward investigating "Push vs. Pull" social feeds (e.g., Timeline materialization). This is where the physical design of the graph will truly be tested: should a new post be "pushed" to all friend nodes, or "pulled" at query time? The battle between storage footprint and read latency continues.