Comparative Architectural Analysis of

Graph Entities and Property Models:

Boost Graph Library, NebulaGraph, and
Neo4j
1. Introduction
The representation of complex relational data has evolved significantly from the rigid tables of
relational database management systems (RDBMS) to the flexible, interconnected structures
of graph technologies. At the core of this paradigm shift is the Property Graph Model (and
its variations), which posits that data is best represented as nodes (entities) and edges
(relationships), both capable of possessing internal state in the form of properties. However,
the implementation of this theoretical model varies drastically across different computational
environments.

This report provides an exhaustive technical analysis of three distinct implementations of

graph theory: The Boost Graph Library (BGL), representing the high-performance, generic
programming approach for in-memory C++ computation; NebulaGraph, representing the
distributed, strongly-typed schema approach designed for massive scale; and Neo4j,
representing the native, schema-optional Labeled Property Graph optimized for transactional
agility.

The primary objective of this research is to dissect the generalized structures of these
systems, specifically focusing on how "entities" (vertices/nodes) and "connections"
(edges/relationships) are defined, identified, and stored. Furthermore, we will investigate the
"variables"—the properties, attributes, and configuration options—that developers can
manipulate ("play with") to model complex domains. This analysis extends beyond
surface-level terminology to explore the architectural consequences of these design choices,
including storage mechanics, type safety, and operational flexibility.

2. Theoretical Framework: The Generalized Graph

Structure
Before examining the specific implementations, it is essential to establish the theoretical
baseline against which these systems are evaluated. In discrete mathematics, a graph $G$ is
typically defined as an ordered pair $G = (V, E)$, where $V$ is a set of vertices and $E$ is a
set of edges connecting pairs of vertices.

In the context of software engineering and database management, this definition is

insufficient. Application data requires state. Therefore, the industry has converged on the
Directed Property Graph model. In this generalized structure:
1.​ Entities (Vertices/Nodes): These are the fundamental units of data. They possess an
identity distinct from their properties.
2.​ Connections (Edges/Relationships): These are directed links between two entities.
They also possess an identity and can hold properties.
3.​ Variables (Properties): These are key-value pairs $P$ attached to both $V$ and $E$.
$P$ represents the domain data (e.g., weights, names, timestamps).

While BGL, NebulaGraph, and Neo4j all adhere to this high-level abstraction, their internal
treatment of "Identity," "Schema," and "Storage" creates three divergent worlds for the
developer.

2.1 Comparative Terminology Matrix

The following table synthesizes the nomenclature differences, serving as a reference point for
the detailed analysis that follows.

Concept Boost Graph NebulaGraph Neo4j

Library (BGL)

Fundamental Vertex Vertex Node

Entity

Connection Edge Edge Relationship

Entity Type (C++ Tag (Schema Label (Runtime

Classification Struct/Class) Definition) Tag)

Connection Edge Property (C++ Edge Type Relationship Type

Classification Struct)

Unique Identifier Descriptor VID (Int64 / Fixed ElementId (String) /

(Integer/Pointer) String) Identity

Data Attachment Property Map Property Property

(Interior/Exterior) (Columnar) (Key-Value)
 Schema Compile-Time Strong Schema Schema-Optional
Enforcement (Static) (DDL) (Dynamic)

Variable Storage Template Partitioned KV Doubly Linked Lists

Arguments Store

3. The Boost Graph Library (BGL): The Generic

Programming Paradigm
The Boost Graph Library (BGL) is not a database; it is a header-only C++ library based on the
generic programming paradigm. Its primary design goal is flexibility and performance,
achieved through C++ templates. In BGL, the "variables to play with" are not just data values
but the very structural components of the graph itself, defined at compile-time.

3.1 Generalized Structure: The adjacency_list

The central entity in BGL is the graph class, most commonly instantiated as an adjacency_list.
Unlike a database where the storage engine is fixed, BGL allows the developer to define the
underlying data structures for vertices and edges as template arguments. This choice
fundamentally alters the behavior of the graph's entities.

The generalized declaration is:

C++

typedef boost::adjacency_list<OutEdgeList, VertexList, Directed,​

VertexProperties, EdgeProperties, GraphProperties> Graph;​

3.1.1 Structural Variables: OutEdgeList and VertexList

The first two "variables" a developer plays with are the container selectors:
●​ VertexList: This determines how vertices are stored in memory.
○​ vecS (std::vector): Vertices are stored in a contiguous vector. The "Vertex
Descriptor" (ID) is an integer index $[0, N-1]$. This is memory efficient but has a
significant side effect: removing a vertex invalidates the descriptors of all subsequent
vertices (shifting indices).
○​ listS (std::list): Vertices are stored in a linked list. The descriptor is a pointer to the
list node. Removing a vertex does not invalidate other descriptors. This stability is a
 critical "variable" for long-running algorithms where the graph topology changes.1
●​ OutEdgeList: This determines how edges incident to a vertex are stored.
○​ vecS: Fast traversal, lower memory overhead.
○​ setS (std::set): Enforces uniqueness of edges (no parallel edges) at the cost of
insertion speed ($O(\log E)$). This structurally prevents multi-edges, a constraint the
developer can toggle via this variable.

3.2 Property Maps: The Interface for Data Variables

In BGL, data attached to vertices and edges are managed through Property Maps. This is a
significant deviation from the database "record" model. Property Maps decouple the access
mechanism from the storage mechanism.

3.2.1 Interior Properties

Interior properties are stored "inside" the graph object. Their lifetime is bound to the graph.
When using adjacency_list, these are defined via the VertexProperties and EdgeProperties
template arguments.3
●​ Predefined Tags: BGL provides a suite of property tags (e.g., vertex_distance_t,
edge_weight_t, vertex_color_t) that act as keys. Algorithms like Dijkstra's shortest path
are hard-coded to look for these specific tags.
●​ Bundled Properties: A more modern and flexible approach allows users to define a
standard C++ struct or class and pass it as the property argument.​
C++​
struct Highway { string name; double miles; int lanes; };​
typedef boost::adjacency_list<..., Highway> Map;​
​
Here, the "variables to play with" are the member variables of the Highway struct. They
are accessed directly via the graph descriptor: map[edge_descriptor].miles.4 This allows
for arbitrary complexity—vectors, maps, or even other graph objects can be nested inside
a vertex property.

3.2.2 Exterior Properties

Exterior properties are stored "outside" the graph, independent of the graph's lifetime. This is
a powerful feature for temporary variables needed only during specific algorithmic
executions.
●​ Use Case: In a Breadth-First Search (BFS), the algorithm needs to track which vertices
have been visited (colors). Instead of permanently adding a "color" field to the vertex
struct (which wastes memory after the BFS completes), the developer creates an Exterior
Property Map.3
●​ Implementation: This is typically a std::vector or an array, wrapped in an
iterator_property_map. The "variable" here is the external container. The graph provides
 the key (Vertex ID), and the external vector provides the value.
●​ Flexibility: This means the "schema" of a BGL graph is effectively extensible at runtime
for the duration of a function call. You can associate infinite new variables with vertices
without recompiling the graph structure, provided you have a way to map Vertex
Descriptors to storage locations.3

3.3 Deep Insight: The Descriptor as a Variable

In BGL, the Vertex Descriptor and Edge Descriptor are opaque types.
●​ If VertexList is vecS, the descriptor is an integer.
●​ If VertexList is listS, the descriptor is void* (pointer).​
This distinction is crucial. With integer descriptors, BGL allows "Implicit Graphs"—graphs
that don't exist in memory but are calculated on the fly (e.g., a chess game state tree).
The "entity" here is virtual, and its "variables" are computed rather than retrieved. This
level of abstraction is absent in NebulaGraph and Neo4j, which assume materialized,
persistent entities.

4. NebulaGraph: The Distributed, Strongly-Typed

Schema Paradigm
NebulaGraph represents the "Big Data" approach to graphs. It is designed for scenarios with
billions of vertices and trillions of edges. Consequently, its structure is rigid, optimized for
storage efficiency and distributed consistency (via the Raft consensus algorithm). The
"variables to play with" are strictly defined by a schema, similar to SQL tables.

4.1 Architecture: Separation of Logic and Storage

NebulaGraph splits its architecture into the Graph Service (query parsing, execution plan)
and the Storage Service (persistent KV store). This separation dictates how entities are
treated.
●​ Vertices and Edges are ultimately serialized into Key-Value pairs in RocksDB partitions.
●​ The Key: Contains the Partition ID, Vertex ID (VID), Tag ID, etc.
●​ The Value: Contains the serialized properties (the variables).6

4.2 The Immutable Variable: Vertex Identifier (VID)

In NebulaGraph, the most critical variable is the VID. Unlike Neo4j's system-generated IDs, the
VID in Nebula is user-defined and carries structural weight.
●​ Type Selection: When creating a Graph Space, the developer must choose the VID
type: INT64 or FIXED_STRING(N).
○​ INT64: Extremely efficient (8 bytes). Recommended if entities have numerical IDs.
 ○​ FIXED_STRING(N): Allows string IDs (e.g., "User_A"). However, the length N is fixed. If
N=10, "User_LongName" is truncated or rejected.
●​ Implication: This variable determines the partitioning. Nebula uses Hash(VID) %
Number_Of_Partitions to locate data. Once defined, the VID type and length cannot be
changed without migrating data to a new Space.7

4.3 Schema Variables: Tags and Edge Types

NebulaGraph does not allow arbitrary properties on nodes. It uses a strong schema model.
●​ Tags (Vertex Types): A vertex is a container for Tags. A single vertex (identified by one
VID) can possess multiple Tags. For example, VID 100 can have a Person tag (with
variables name, birthdate) and a Player tag (with variables team, position).7 This allows
for a form of vertical partitioning or "Mix-in" modeling.
●​ Edge Types: Similar to Tags, but for edges. An edge is identified by <SrcVID, DstVID,
EdgeType, Rank>.

4.3.1 Rank: A Unique Structural Variable

NebulaGraph introduces a special variable for edges called Rank (default 0). This is a signed
64-bit integer designed to solve the "Multi-Edge" problem.
●​ The Problem: In a standard key-value store, the key must be unique. If the key is
Src-Type-Dst, you can only have one edge of type Transfer between AccountA and
AccountB.
●​ The Solution: The key includes Rank. By manipulating the Rank variable (e.g., setting it to
a timestamp), developers can store millions of distinct Transfer edges between the same
two accounts. This variable is explicitly available for the developer to "play with" to model
history or versioning.8

4.4 Property Variables and Limitations

The properties (variables) attached to Tags and Edge Types are defined via Data Definition
Language (DDL).
●​ Supported Types: int, double, string, bool, timestamp, date.
●​ Schema Evolution: Adding a variable requires an ALTER TAG statement. This is a
heavyweight operation compared to Neo4j's dynamic schema.
●​ Composite Types Constraint: As of recent versions (v3.x), NebulaGraph does not
support storing List, Map, or Set as persistent properties in the schema.9
○​ Workaround: Developers must serialize lists/maps into a JSON string or split them
into separate vertices/edges. This is a significant restriction on the "variables to play
with" compared to BGL's arbitrary structs.
○​ Implication: You cannot run a query like "Find all users where 'admin' is IN roles_list"
efficiently if roles_list is a string blob. You must model roles as separate vertices
 connected by edges.

5. Neo4j: The Native, Labeled Property Graph

Paradigm
Neo4j is a native graph database, meaning it stores data on disk as linked structures rather
than indices or tables. Its model, the Labeled Property Graph, offers the highest degree of
runtime flexibility. The "variables to play with" are dynamic, schema-optional, and directly
accessible via the Cypher query language.

5.1 Generalized Structure: The Doubly Linked List

Neo4j's storage engine treats the graph topology as a set of fixed-size records linked by
pointers (offsets in a file).
●​ Node Record: Contains pointers to the first relationship, the first property, and the label
store.
●​ Relationship Record: Contains pointers to the start node, end node, next relationship for
the start node, next relationship for the end node, and the first property.
●​ Property Record: Stored in a separate linked list. Each record holds a few properties
(key-value pairs). If a node has many properties, the list grows.10

This structure means that "traversal" is effectively pointer chasing, which is $O(1)$ per hop
(Index-Free Adjacency).

5.2 Dynamic Variables: Labels and Properties

Unlike NebulaGraph's rigid Tags, Neo4j's Labels are lightweight markers.
●​ Labels: A node can have zero, one, or many labels (e.g., :Person:Actor:Director). Labels
are used primarily for grouping and indexing. They do not enforce a strict schema. A
node labeled :Person might have a name property, while another :Person node has name
and age.
●​ Properties: These are the primary variables to play with.
○​ Ad-Hoc Creation: A property can be added to any node at any time: MATCH (n) SET
n.new_variable = 123.
○​ Heterogeneity: It is technically possible (though often discouraged) for the property
weight to be an Integer on one relationship and a Float on another.

5.3 System Variables: Identity Evolution

The concept of identity in Neo4j has evolved, changing the variables developers interact with.
●​ Legacy id(): Historically, Neo4j exposed the internal storage offset (an integer) as the ID.
 This was risky because if a node was deleted and the store compacted, the ID could be
reused.
●​ Modern elementId(): Neo4j 5.x introduced elementId, a string-based identifier (e.g.,
4:39213123-....). This provides a globally unique reference within the database context.12
●​ Constraint: While visible, these system variables are generally immutable. Developers
are encouraged to define their own "Business Keys" (e.g., uuid) and enforce uniqueness
constraints, effectively creating their own stable identity variable.

5.4 Data Types and Limitations

Neo4j offers a rich set of scalar types but has specific limitations on complex structures.
●​ Supported: Integer, Float, String, Boolean.
●​ Temporal & Spatial: Neo4j has first-class support for Date, Duration, and Point (2D/3D
WGS-84). These are powerful variables for geospatial and scheduling graphs.14
●​ The List/Map Limitation:
○​ Homogeneous Lists: Neo4j can store lists of simple types (e.g., `` or ['a', 'b']).
○​ No Mixed Lists: It cannot store [1, 'a', 2.0].16
○​ No Maps: It cannot store nested Maps (JSON objects) as properties. A property
value cannot be a tree. Like Nebula, users must serialize JSON to strings or flatten
the structure (e.g., address_city, address_zip).14 This is a critical distinction from
document stores like MongoDB.

6. Comparative Analysis of "Variables to Play With"

This section synthesizes the analysis into a direct comparison of how developers can
manipulate entities and edges across the three platforms.

6.1 Nodes (Vertices)

●​ BGL: The node is a container for a C++ object. The "variables" are the struct members.
○​ Flexibility: Absolute. Can hold pointers, threads, file handles.
○​ Constraint: Static. All nodes in VertexList must be the same type.
●​ NebulaGraph: The node is a VID associated with rows in Tag tables.
○​ Flexibility: High volume, structured. Can mix-and-match Tags.
○​ Constraint: Schema-bound. No composite types. VID is immutable.
●​ Neo4j: The node is a dynamic record.
○​ Flexibility: Agile. Schema-free.
○​ Constraint: Data types limited to database scalars. Property chain length impacts
performance.

6.2 Edges (Relationships)

 ●​ BGL: Edges are fully-fledged objects defined by EdgeProperties.
○​ Unique capability: Can be purely topological (no properties) for maximum speed, or
heavy objects.
●​ NebulaGraph: Edges are strictly typed rows.
○​ Unique capability: The Rank variable allows sophisticated versioning of relationships
without creating surrogate nodes.
●​ Neo4j: Relationships are first-class entities.
○​ Unique capability: "Lightweight" relationships. Because pointers are part of the
storage structure, traversing edges is faster than scanning indices. However, deep
chains of properties on edges can slow down traversal because the engine must load
the property chain to filter.

6.3 Variable Data Types Comparison

The following table details the specific data types available for properties in each system.

Data Type Boost Graph NebulaGraph Neo4j

Category Library (BGL)

Integers int, long, size_t, etc. int8, int16, int32, Integer (64-bit)
int64

Floating Point float, double, long float, double Float (64-bit)

double

Strings std::string, char* string, fixed_string String

Booleans bool bool Boolean

Temporal Custom / date, time, Date, Time,

std::chrono datetime, DateTime, Duration
timestamp

Spatial Custom Structs Geography (Point, Point

LineString, (Cartesian/WGS-84
Polygon) )

Collections std::vector, Not Supported (as Homogeneous

std::map, std::set properties) Lists only
 Nested Objects Supported Not Supported Not Supported
(Structs/Classes) (Must
flatten/serialize)

References Pointers / Iterators N/A N/A

6.4 The "Algorithm State" Variable

A unique category of "variable" exists in BGL: Visitor State.
●​ In Neo4j or Nebula, algorithm state (e.g., "visited nodes") is internal to the engine. The
user cannot play with it easily.
●​ In BGL, the user defines "Visitor" classes that are invoked at event points (e.g.,
examine_edge, discover_vertex). The user can attach arbitrary variables to these visitors
to accumulate state during traversal. This offers a dimension of "variables to play with"
that is procedural rather than structural, unavailable in declaratively queried databases.3

7. Operational Implications and Use Case Alignment

The choice of structural variables directly impacts the operational viability of the system for
specific use cases.

7.1 Scenario: Rapid Prototyping and Exploration

●​ Winner: Neo4j.
●​ Reasoning: The ability to add any variable to any node without DDL statements allows
developers to iterate instantly. The lack of a schema means data can be messy and
cleaned up later. The "variable" here is the schema itself, which is mutable.

7.2 Scenario: Financial Transaction Graph (Scale & Consistency)

●​ Winner: NebulaGraph.
●​ Reasoning: The Rank variable on edges is crucial for modeling millions of transactions
between two accounts. The INT64 VID allows for compact storage. The strong schema
ensures that every transaction has a timestamp and amount, preventing data quality
issues at the ingest layer. Partitioning variables ensure the graph scales horizontally.

7.3 Scenario: Custom Routing Engine (Performance)

●​ Winner: Boost Graph Library.
●​ Reasoning: Routing requires complex heuristics (A* search) and custom distance
calculations. BGL allows the developer to store Lat/Lon as doubles directly in the vertex
struct and use an Exterior Property Map to store the f_score and g_score of the search
 algorithm. This avoids the overhead of database serialization/deserialization. The
"variables" are raw memory, offering maximum speed.

8. Conclusion
The generalized structure of graph entities in Boost Graph Library, NebulaGraph, and Neo4j
reveals three fundamentally different approaches to the same mathematical concept.

BGL views the graph as a Data Structure. Its entities are compile-time artifacts, and its
variables are C++ types. It offers the ultimate "playability" regarding data complexity and
algorithmic integration but requires strict compile-time definition and manages no
persistence.

NebulaGraph views the graph as a Distributed Schema. Its entities are keys in a partitioned
store, and its variables are columns in strict tables. It limits the flexibility of data types (no
maps/lists) to gain massive scalability and distributed consistency. The Rank and VID
variables are central to its structural design.

Neo4j views the graph as a Network of Objects. Its entities are linked records, and its
variables are dynamic properties. It strikes a balance, offering the rich type support of a
database with the flexibility of a document store, albeit with constraints on composite data
types and storage limits imposed by the linked-list architecture.

For the architect or developer, the decision of "what variables to play with" is effectively a
decision on the lifecycle of the data. If the variables are transient and algorithmic, BGL is the
canvas. If the variables are massive, uniform, and historical, NebulaGraph is the vault. If the
variables are evolving, interconnected, and diverse, Neo4j is the playground.

Citations
.1

Works cited

1.​ Using the Boost Graph Library, accessed December 31, 2025,
[Link]
2.​ Quick Tour of Boost Graph Library - Brown Computer Science, accessed
December 31, 2025,
[Link]
3.​ Boost Graph Library: Using Property Maps, accessed December 31, 2025,
[Link]
4.​ Bundled Properties - Boost, accessed December 31, 2025,
[Link]
5.​ [Boost-users] [BGL] Bundled properties and property maps - Google Groups,
 accessed December 31, 2025,
[Link]
6.​ Storage Service - NebulaGraph Database Manual, accessed December 31, 2025,
[Link]
torage-service/
7.​ Data model - NebulaGraph Database Manual, accessed December 31, 2025,
[Link]
8.​ nebula graph - Does nGQL allow you to reference the VID of two tags in a query ?
(rather the VID of one and the property of the other?, accessed December 31,
2025,
[Link]
e-the-vid-of-two-tags-in-a-query-rather-the-vi
9.​ Map - NebulaGraph Database Manual, accessed December 31, 2025,
[Link]
10.​Graph database concepts - Getting Started - Neo4j, accessed December 31,
2025, [Link]
11.​ What is graph data modeling? - Getting Started - Neo4j, accessed December 31,
2025, [Link]
12.​The role of elementIds and key properties - Change Data Capture - Neo4j,
accessed December 31, 2025,
[Link]
13.​Functions - Cypher Manual - Neo4j, accessed December 31, 2025,
[Link]
14.​Property, structural, and constructed values - Cypher Manual - Neo4j, accessed
December 31, 2025,
[Link]
ural-constructed/
15.​Data types and mapping to Cypher types - Neo4j JavaScript Driver Manual,
accessed December 31, 2025,
[Link]
16.​Lists - Cypher Manual - Neo4j, accessed December 31, 2025,
[Link]
17.​How to store a map or json object as a property in neo4j? - Stack Overflow,
accessed December 31, 2025,
[Link]
ect-as-a-property-in-neo4j
18.​Operate Edge types - NebulaGraph Database Manual, accessed December 31,
2025,
[Link]
ge-type/
19.​Values and types - Cypher Manual - Neo4j, accessed December 31, 2025,
[Link]