Graph Databases

What it is

A graph database stores data as nodes (entities) and edges (relationships between entities), both of which can have properties (key-value attributes). This is the Labeled Property Graph (LPG) model used by Neo4j and Amazon Neptune (TinkerPop). Alternatively, the RDF (Resource Description Framework) model represents data as subject-predicate-object triples, used by Neptune in SPARQL mode and AllegroGraph.

The defining characteristic of graph databases is index-free adjacency: each node stores direct pointers to its adjacent edges, so traversing a relationship is a constant-time operation (following a pointer) rather than a join operation (scanning an index). This means a "friends of friends" query that traverses 4 hops through a 1-billion-node social graph returns in milliseconds — the same query in a relational database requires 4 recursive self-joins that grow exponentially in cost.

The Cypher query language (used by Neo4j and supported by other LPG databases) expresses graph patterns using ASCII art notation: MATCH (a:User)-[:FOLLOWS]->(b:User)-[:FOLLOWS]->(c:User) WHERE a.name = "Alice" RETURN c.name — "find all users that Alice's followees follow".

Why it exists

Relational databases implement relationships as foreign keys joined at query time. Each join requires an index lookup; 4-hop traversals require 4 joins, each scanning intermediate result sets that grow multiplicatively. For highly connected data (social graphs, fraud rings, supply chains, knowledge graphs), the relational model's query cost scales with the number of hops, while graph databases' index-free adjacency keeps traversal cost constant per hop. The performance advantage is not marginal — benchmarks consistently show 10–1000x improvement for multi-hop graph queries, a difference that determines whether a feature is viable or not.

When to use

• Recommendation engines: "Products bought by people who bought X" — collaborative filtering traverses purchase relationships between users and products.
• Fraud detection: Identifying fraud rings by finding shared entities (phone numbers, addresses, devices) across account networks — rings are multi-hop cycles in the graph.
• Social networks: Followers, friends, connections, content graphs — the core data structure is inherently a graph.
• Knowledge graphs: Entities and their semantic relationships (company → subsidiary, person → employer, product → category → taxonomy) — queried for inference and search.
• Access control / permissions: Role hierarchy and permission inheritance — "does this user have permission X?" traverses a role-assignment and role-inheritance graph.

When not to use

• Don't use a graph database for tabular, aggregation-heavy analytics — graph databases are not OLAP systems; aggregating total revenue across millions of nodes is not their strength.
• Don't use it if your data has few relationships or most queries don't traverse them — a product catalog where products aren't queried by relationship is better served by a document store.
• Don't use a graph database as a replacement for a relational OLTP database — most graph databases have weaker transactional guarantees and are not designed for high-throughput record-level CRUD.
• Don't assume graph database = better for all graph-like data — PostgreSQL with recursive CTEs handles tree traversals (organizational hierarchies, bill-of-materials) adequately for bounded depth without additional infrastructure.

Typical architecture

  Neo4j LPG Model:
  (:User {id: "alice", name: "Alice"})
       -[:FOLLOWS {since: "2023-01-01"}]->
  (:User {id: "bob", name: "Bob"})
       -[:PURCHASED {at: "2024-01-15"}]->
  (:Product {id: "p1", name: "Widget", category: "tools"})
       -[:IN_CATEGORY]->
  (:Category {name: "tools"})

  Cypher: Recommend products Alice might like:
  MATCH (alice:User {name: "Alice"})
        -[:FOLLOWS]->(:User)
        -[:PURCHASED]->(p:Product)
  WHERE NOT (alice)-[:PURCHASED]->(p)
  RETURN p.name, COUNT(*) AS popularity
  ORDER BY popularity DESC LIMIT 10

  Fraud ring detection:
  MATCH (a1:Account)-[:SHARES_DEVICE]->(d:Device)
        <-[:SHARES_DEVICE]-(a2:Account)
  WHERE a1 <> a2
  AND (a1)-[:FLAGGED_SUSPICIOUS]->()
  RETURN a2.id AS suspicious_account

  Architecture:
  Application ──▶ Neo4j (graph write + read)
                      │
                      ├──▶ Read replica (scaling read traffic)
                      └──▶ Downstream sync: domain events → Kafka
                                            → Search (Elasticsearch)
                                            → Warehouse (Redshift)
          

Pros and cons

Implementation notes

In Neo4j, always create indexes on node properties used in MATCH WHERE clauses to find the starting node of a traversal: CREATE INDEX FOR (u:User) ON (u.id). Without this index, every traversal that starts with MATCH (u:User {id: $id}) performs a full node scan. Once the starting node is found via index, subsequent traversal hops use index-free adjacency and are fast. Use EXPLAIN and PROFILE to inspect query execution plans and confirm index usage. Avoid MATCH (n) RETURN n LIMIT 10 — this scans all nodes; always start traversals from indexed properties.

For Amazon Neptune (managed graph database), choose between the TinkerPop/Gremlin interface (for LPG workloads, compatible with Neo4j data models) and SPARQL/RDF (for knowledge graphs with semantic web standards). Neptune Serverless scales automatically and is appropriate for variable or unpredictable graph query workloads. For read-heavy recommendation workloads, use Neptune read replicas and route read queries via the reader endpoint. Cache the output of expensive traversal queries (recommendations, permissions) in Redis or DynamoDB with a short TTL rather than re-traversing the graph on every request.

Common failure modes

• Supernodes: A few nodes have millions of edges (a celebrity user in a social graph with 10M followers); traversals that touch the supernode create hot spots and slow down dramatically due to the large adjacency list that must be loaded.
• Missing start-node index: A Cypher query lacks an index on the entry-point property; Neo4j performs a full scan of all nodes of that label — a query that should take 10ms takes 30 seconds on a large graph.
• Using graph DB for aggregations: A developer queries Neo4j for MATCH (o:Order) RETURN SUM(o.amount); the graph DB scans all Order nodes; this is 10–100x slower than the same query in a relational or columnar database.
• Unbounded traversal: A query pattern like MATCH (a)-[*]->(b) (variable-length traversal without bound) on a dense graph exponentially explores all reachable nodes; the query never returns or exhausts memory.
• No relationship index: Filtering traversals by relationship properties (e.g., [:FOLLOWS {since: "2024"}]) without an index on the relationship property causes full relationship scans.

Decision checklist

• Are the primary query patterns multi-hop relationship traversals where relational joins are known to be slow (measured, not assumed)?
• Is the domain inherently graph-shaped — entities defined primarily by their relationships, not their attributes?
• Are indexes created on all node properties used as starting-point filters in traversal queries?
• Is there a strategy for supernodes (high-degree nodes) — either modeling them differently or caching their adjacency lists?
• Is there a separate analytical store for aggregation queries that shouldn't run against the graph database?
• Are all traversal queries bounded with relationship-hop depth limits to prevent unintended exponential exploration?

Example use cases

• LinkedIn "People You May Know": Traverse the connection graph 2 hops from the current user, rank candidate nodes by number of shared connections, return top-N. The same query over a relational connections table requires 3 self-joins and is too slow for real-time at scale.
• Financial fraud ring detection: Accounts sharing phone numbers, addresses, or devices form connected components in the graph. A fraud analyst queries for accounts connected to a flagged account within 3 hops via shared identity attributes. The ring topology is a multi-hop cycle undetectable by simple relational queries.
• Access control / RBAC: Permissions are inherited through role hierarchies and group memberships. "Does user X have permission Y?" traverses a role-assignment graph with up to 10 hops. Graph traversal returns in <5ms; equivalent recursive SQL CTE is 200ms+ on large permission trees.

Related patterns

• Polyglot Persistence — Graph databases are a component in polyglot architectures, used alongside relational and document stores.
• Vector Databases — Both are specialized databases for specific data types; graph for relationships, vectors for semantic similarity.
• Data Modeling Patterns — Adjacency list and nested set patterns in relational databases as alternatives for tree data before adopting a graph DB.

Further reading

• Neo4j Cypher Query Language Manual
• Amazon Neptune User Guide
• Graph Databases (Robinson, Webber & Eifrem) — O'Reilly