Graph Thinking: Why Connections Matter

Relational Data: Limitations for Connected Systems

Relational databases store data in tables, organizing information into predefined rows and columns. This structure excels at managing independent entities and their attributes, such as customer records or product catalogs. Relationships between these entities are established through foreign keys, linking rows across different tables.

To retrieve connected data, relational models rely on join operations. A simple relationship, like finding a user’s direct friends, requires a self-join on a Friendships table. As the depth of connections increases, the number of required joins grows significantly. For example, finding “friends of friends of friends” demands multiple chained self-joins.

Consider a simplified social network schema:

CREATE TABLE Users (
    id INT PRIMARY KEY,
    name VARCHAR(255)
);

CREATE TABLE Friendships (
    user_id INT,
    friend_id INT,
    PRIMARY KEY (user_id, friend_id),
    FOREIGN KEY (user_id) REFERENCES Users(id),
    FOREIGN KEY (friend_id) REFERENCES Users(id)
);

Finding a user’s direct friends involves a single join:

SELECT U2.name
FROM Users U1
JOIN Friendships F ON U1.id = F.user_id
JOIN Users U2 ON F.friend_id = U2.id
WHERE U1.name = 'Alice';

Output:

name
----
Bob
Charlie

To find friends of friends, the query complexity increases:

SELECT DISTINCT U3.name
FROM Users U1
JOIN Friendships F1 ON U1.id = F1.user_id
JOIN Users U2 ON F1.friend_id = U2.id
JOIN Friendships F2 ON U2.id = F2.user_id
JOIN Users U3 ON F2.friend_id = U3.id
WHERE U1.name = 'Alice' AND U3.id != U1.id;

This query requires three joins and involves traversing two “hops” in the relationship chain. Each additional hop necessitates another join, escalating the query’s complexity and execution cost. Databases process joins by matching rows, an operation that becomes computationally expensive as the number of joins or the size of the tables grows. This can lead to slow query times, particularly for deeply connected data.

Beyond performance, relational schemas are rigid. Defining new types of relationships or modifying existing ones often requires schema alterations and migration scripts. This rigidity makes it difficult to adapt to changing data models where connections between entities are dynamic and varied. The relational model also treats relationships as secondary to entities, inferring them through foreign keys rather than representing them as first-class citizens with their own properties and directions.

Graph Elements: Nodes, Edges, and Properties Defined

Graphs model relationships between discrete entities. This structure consists of fundamental components: nodes and edges, each capable of holding descriptive data.

Nodes, also known as vertices, represent individual entities within the graph. In a social network, a node might represent a specific person. In an inventory system, a node could represent a product or a warehouse location. Each node is unique and forms a distinct point in the graph’s topology.

Edges, also known as relationships or links, connect two nodes. An edge signifies a relationship or interaction between the connected entities. For example, an edge could represent a “FRIENDS_WITH” relationship between two person nodes, or an “IS_STORED_AT” relationship between a product node and a warehouse node. Edges can be directed, indicating a flow from a source node to a target node (e.g., “FOLLOWS” from User A to User B), or undirected, where the relationship is mutual (e.g., “FRIENDS_WITH”).

Both nodes and edges can carry properties. Properties are key-value pairs that store metadata, providing specific details about the node or edge. A Person node might have properties such as name: "Alice", age: 30, or city: "New York". An OWNS edge between a Customer node and a Product node could store purchaseDate: "2023-10-26" and quantity: 1.

To categorize these components, nodes and edges often use labels or types. Node labels classify the entity (e.g., Person, Product, Order). Edge types define the nature of the relationship (e.g., FRIENDS_WITH, PURCHASED, DELIVERS). These labels and types enable structured navigation and querying, allowing systems to distinguish between different kinds of entities and their interactions.

Consider a simple graph segment:

(Alice:Person {name: "Alice", age: 30})--[FRIENDS_WITH {since: "2018-01-15"}]-->(Bob:Person {name: "Bob", age: 32})

This segment shows two Person nodes, “Alice” and “Bob”, each with name and age properties. An edge of type FRIENDS_WITH connects them, holding a since property indicating the start of their friendship. The arrow --> indicates a directed relationship, from Alice to Bob. This structure clearly defines the entities, their relationship, and associated metadata.

Real-World Graphs: Modeling Practical Scenarios

Real-world systems inherently organize as networks of connected entities. Social media platforms, for instance, represent users as nodes. A friendship or a follow relationship between two users forms an edge. If the connection is mutual, like a Facebook friendship, the edge is undirected. If one user follows another, as on X (formerly Twitter), the edge is directed, pointing from the follower to the followed.

Transportation networks map similarly. Cities or specific locations become nodes. Roads, train lines, or flight paths between these locations are edges. These edges often carry a weight, representing the distance, travel time, or cost associated with traversing that connection. A direct flight from New York to London might be a single edge with a weight of 7 hours.

Dependencies within software projects also form a graph structure. Each software package or module can be a node. If package A requires package B to function, a directed edge points from A to B. This structure is crucial for package managers like npm or pip to resolve installation orders and identify conflicts. For example, A -> B, A -> C, B -> D, C -> D indicates A depends on B and C, and both B and C depend on D. To install A, D must be installed first, then B and C, and finally A.

A -> B
A -> C
B -> D
C -> D

Citation networks in academia illustrate another directed graph. Research papers are nodes. A citation from paper A to paper B creates a directed edge from A to B. Analyzing these connections helps identify influential papers or track the evolution of research topics over time.

These graph models allow us to ask specific questions about the system. In a social network, we can find the shortest path between two people (degrees of separation). In a transportation network, we determine the most efficient route. For dependencies, we identify the correct build order. Each scenario uses the same underlying graph principles but applies them to different data and problems.

Graph Thinking: Initial Misconceptions to Avoid

Many engineers initially approach graph data as a new schema for relational tables. This often leads to attempts to force a row-and-column structure onto inherently connected data, missing the fundamental shift in perspective.

Consider modeling users and their follow relationships. A common relational approach uses a Users table and a Follows junction table to link follower_id to followed_id.

CREATE TABLE Users (
    user_id INT PRIMARY KEY,
    name VARCHAR(255)
);

CREATE TABLE Follows (
    follower_id INT,
    followed_id INT,
    FOREIGN KEY (follower_id) REFERENCES Users(user_id),
    FOREIGN KEY (followed_id) REFERENCES Users(user_id),
    PRIMARY KEY (follower_id, followed_id)
);

The pitfall here is viewing Follows merely as a foreign key constraint between two Users. The relationship itself is secondary, an artifact of the schema. This perspective limits the ability to query patterns through relationships or add details to the connection directly.

Another common error is to assume all connections are simple binary links without properties. A “works for” relationship between a Person and a Company, for instance, might need a startDate and endDate. In a relational model, these attributes typically reside on the Person or a separate Employment table.

When thinking in graphs, relationships (edges) can carry properties just like entities (nodes). Failing to recognize this capability means losing a powerful way to model context and detail directly on the connection itself, rather than scattering it across multiple tables or entities.

Finally, some assume graph thinking applies only to niche problems like social networks or pathfinding. This narrows the scope prematurely. Any domain with rich, interconnected entities, where the relationships themselves carry meaning, benefits from a graph perspective. Examples include supply chains, regulatory compliance, knowledge bases, and fraud detection.

Understanding these initial conceptual hurdles clears the path for adopting a true graph-centric view, where entities and their connections are equally important and richly descriptive.

Your First Graph: Sketching a Simple Network

A common task involves modeling interconnected data. Consider a simplified forum where users create posts and follow each other. The goal is to represent this system’s structure using a graph.

The system’s primary entities are users and posts. These become the graph’s nodes. Each user node requires a unique identifier, like user:101, and a display name, such as “Alice”. Each post node also needs a unique ID, for example, post:2001, along with its content and creation timestamp.

Relationships between these entities form the graph’s edges. A FOLLOWS relationship exists between two user nodes, indicating one user tracks another’s activity. This is a directed edge: (user:101)-[FOLLOWS]->(user:102) signifies Alice follows Bob, but Bob does not necessarily follow Alice back. Similarly, a CREATED_BY relationship connects a post node to the user node who authored it: (post:2001)-[CREATED_BY]->(user:101). This edge is also directed, as the post is created by the user, not vice-versa.

For instance, imagine three users: Alice (user:101), Bob (user:102), and Carol (user:103). Alice follows Bob. Bob follows Carol. Alice creates a post “Hello World” (post:2001) at 2023-10-26T10:00:00Z.

This scenario translates into the following graph sketch:

(user:101 {name: "Alice"})
(user:102 {name: "Bob"})
(user:103 {name: "Carol"})
(post:2001 {content: "Hello World", timestamp: "2023-10-26T10:00:00Z"})

(user:101)-[FOLLOWS]->(user:102)
(user:102)-[FOLLOWS]->(user:103)
(post:2001)-[CREATED_BY]->(user:101)

Node properties, often called attributes, store specific data. For user:101, name: "Alice" is a property. For post:2001, content and timestamp are properties, providing context beyond just the entity’s existence. Edges can also have properties; for example, a FOLLOWS edge might carry a since timestamp to record when the follow began. For this basic model, FOLLOWS and CREATED_BY edges do not require additional properties. This initial sketch provides a clear, connected view of the forum’s core elements.