Graph Tokenisation | How Nodes, Edges and Subgraphs Become Model Units

A graph represents a world through entities and relationships. Tokenising a graph means deciding which nodes, edges, paths or subgraphs should become the units a model can address directly.

This differs from ordinary text tokenisation because graph structure is not primarily linear. A node can connect to many neighbours, cycles can exist, several paths can reach the same place, and relationship type can matter as much as entity identity.

This article continues the eduKateSingapore Representation and Tokenisation series.

The Graph Representation Route

WORLD ENTITIES
→ CANONICAL NODES
→ RELATIONSHIPS / EDGES
→ ATTRIBUTES
→ LOCAL NEIGHBOURHOODS
→ PATHS / SUBGRAPHS
→ NODE / EDGE / GRAPH REPRESENTATIONS
→ MODEL
→ INFERENCE / RETRIEVAL / PREDICTION
→ WORLD RETURN

1. A Graph Is a Relational Representation

A graph contains nodes representing entities or states and edges representing relationships. It preserves who or what is connected to what.

The graph is already a compression of the world into selected objects and selected relations.

2. Nodes Are Entity-Level Tokens

A node can represent a person, company, city, molecule atom, webpage, product or concept.

Its stable ID is a machine address for that entity inside the graph.

3. Node Identity Needs Canonicalisation

The same person can appear under several names. If each name becomes a separate node, relationships fragment.

Graph quality therefore depends on entity resolution, as developed in Entity Tokenisation.

4. Edges Are Relationship Tokens

An edge can represent works_for, located_in, purchased, cites, follows, connected_to or another relation.

Relationship type is part of the graph vocabulary.

5. Edge Direction Matters

Person → works_for → Company is not the same as Company → works_for → Person.

Directed graphs preserve asymmetry.

6. Undirected Edges Represent Symmetric Relations

Road connectivity or friendship may be represented symmetrically in some systems.

The graph schema decides which relationships have direction.

7. Edge Attributes Add Context

A connection can have weight, timestamp, confidence, role or provenance.

Two entities can be connected in several qualitatively different ways.

8. Multigraphs Preserve Multiple Relations

A person can be colleague, co-author and friend with the same other person.

Collapsing all three into one generic edge destroys useful structure.

9. Graphs Are Not Naturally Sequences

Text has an obvious left-to-right order. Graphs generally do not.

To use sequence models, a graph may need a traversal, ordering or serialization.

10. Serialization Creates One Linear View

A knowledge triple such as Paris | capital_of | France converts one edge into a linear sequence.

Many triples can then be serialized for language-model processing.

11. Serialization Order Is Artificial

Changing the order of independent triples should not change the graph itself.

A sequence model must learn that some ordering differences are representational rather than semantic.

12. Traversal Creates Context

Breadth-first and depth-first traversals expose different local structures first.

The traversal rule therefore becomes part of the graph-to-sequence representation.

13. Random Walks Create Sampled Graph Sequences

Methods such as DeepWalk and node2vec sample random walks through a graph and treat the resulting node sequences somewhat like sentences.

Nodes occurring in similar graph neighbourhoods can then develop similar learned representations.

14. Random Walks Preserve Some Structure and Lose Some Structure

A walk reveals local co-occurrence but does not expose the entire graph at once.

Sampling creates a partial representation.

15. Node Embeddings Compress Neighbourhood Structure

A node embedding maps one graph node to a numerical vector influenced by its connections or attributes.

The vector can support similarity and prediction while remaining distinct from the canonical node ID.

16. Identity and Similarity Are Different Relations

Two companies can have similar embeddings because their graph neighbourhoods resemble each other, while remaining completely different entities.

Stable identity should not be replaced by vector similarity.

17. Message Passing Builds Context From Neighbours

Graph neural networks update a node representation using information from neighbouring nodes and edges.

Context arrives through graph topology rather than token adjacency.

18. One Hop Defines Local Context

A one-layer message-passing model can aggregate immediate neighbours. Additional layers expand the receptive field to more distant nodes.

Graph depth functions like contextual radius.

19. Too Many Hops Can Blur Identity

Repeated aggregation can make node representations increasingly similar, a phenomenon often discussed as over-smoothing.

More graph context is not automatically better.

20. High-Degree Nodes Create Context Explosion

A popular webpage or major city can have thousands or millions of neighbours.

Neighbour sampling becomes a graph-context budgeting strategy.

21. Edge Sampling Can Bias the Representation

If sampling repeatedly favours frequent relation types, rare but important edges can disappear from model context.

Sampling policy should reflect the receiver’s task.

22. Subgraphs Are Higher-Level Tokens

A motif, community, molecule ring or organisational unit can be represented as one subgraph object.

This compresses many nodes and edges into a coarser structural unit.

23. Motifs Capture Repeated Relational Patterns

Triangles, stars, chains and cycles recur across networks.

A motif vocabulary can tokenise graph structure above individual edges.

24. Communities Create Mesoscale Representation

Social, citation and transaction graphs often contain dense clusters.

Community detection compresses many node-level relationships into group membership.

25. Community Boundaries Are Hypotheses

One graph can support several valid community structures depending on algorithm and resolution.

A detected cluster should not automatically be treated as a natural social category.

26. Graph Position Needs Structural Encoding

Unlike text, graphs do not have one absolute sequence position. Models can use degree, shortest-path distance, Laplacian features or other structural signals.

Position becomes topology.

27. Relative Position Can Be More Meaningful Than Absolute Position

“Two hops away” can matter more than an arbitrary node index.

Graph models often need relation-aware distance rather than one sequence counter.

28. Knowledge Graph Triples Are Compact Semantic Tokens

A triple such as person → born_in → city represents a structured claim with subject, predicate and object.

The triple compresses a sentence-like relation into a formal unit.

29. Knowledge Graph Claims Need Provenance

Two sources can disagree about one relationship.

An edge should preserve source, date and confidence when factual trust matters.

30. Temporal Graphs Add Event Time

Relationships can appear, disappear or change strength over time.

A static edge can be misleading if the relationship was only true during one period.

31. Dynamic Graphs Combine Event and Graph Tokenisation

An edge-created or edge-deleted event changes the graph state.

Temporal graph models therefore coordinate relation tokens with event sequences.

32. Molecules Are Natural Graphs

Atoms can be nodes and chemical bonds edges. Molecular graphs preserve connectivity more directly than a plain text name.

Graph tokenisation therefore aligns naturally with chemistry.

33. Rings and Functional Groups Are Higher-Level Molecular Tokens

Chemical behaviour often depends on recurring substructures rather than isolated atoms.

Subgraph tokens can capture those motifs.

34. Recommendation Systems Use Interaction Graphs

Users, products and interactions can form a bipartite or heterogeneous graph.

Recommendations emerge from patterns of relational proximity, not only text similarity.

35. Fraud Detection Uses Relational Context

One transaction can look normal in isolation and suspicious when connected to a network of shared devices, accounts or addresses.

Graph representation reveals structure hidden from row-by-row analysis.

36. Graph Search Is Different From Text Search

A graph query can ask for entities matching relationship patterns rather than strings.

Structured retrieval can therefore find evidence no keyword query can express naturally.

37. Graphs and Language Models Can Cross-Walk

Natural-language questions can be mapped to graph entities and relations, graph results can be retrieved, and the result can be rendered back into prose.

The system moves between sequential and relational representations.

38. Graph Serialization Can Lose Provenance

Flattening a subgraph into text may omit edge confidence, timestamps or source IDs.

Serialization should preserve the relational metadata the receiver needs.

39. Graph Token Counts Depend on the Chosen Unit

The same network can contain 10,000 nodes, 100,000 edges or a few hundred communities.

Granularity changes computational cost just as it does in text.

40. Hierarchical Graphs Preserve Several Scales

A city transport network can represent stops, routes, lines and regions simultaneously.

Different queries need different graph token scales.

41. Education Can Be Represented as a Knowledge Graph

Concepts can be nodes and prerequisite, example, misconception or application relations can be edges.

A student’s learning route becomes a traversal through conceptual structure rather than a flat list of articles.

42. Graph Tokenisation Audit

What does one node represent?
How are node identities canonicalised?
What edge types exist?
Are edges directed, weighted or temporal?
What provenance belongs to each relation?
How are node attributes represented?
What neighbourhood radius enters model context?
How are high-degree nodes sampled?
Are paths, motifs or subgraphs represented directly?
What positional or structural encoding is used?
Can graph state change over time?
How are communities defined?
Can serialized graph data return to exact source edges?
Are stable IDs separated from learned embeddings?
Does the chosen granularity match the receiver’s query?

43. What Students Should Remember

Graphs represent entities and relationships.
Nodes and edges can act as token-like units.
Graphs do not have one natural sequence order.
Traversal and serialization create partial linear views.
Subgraphs and communities are higher-level tokens.
Graph position is relational rather than simply sequential.
Knowledge graph claims need provenance.
Graph structure can reveal patterns invisible in flat tables.

44. The Deep Principle

Graph tokenisation begins where ordinary token sequences become insufficient. When meaning lies in relationships, the model needs units that preserve not only what exists but how those things connect.

A node tells the system what one thing is. An edge tells it what that thing means in relation to another. Graph intelligence begins when both identities survive the representation together.

Graph Tokenisation | How Nodes, Edges and Subgraphs Become Model-Ready Units