Compositional Graph Encoding

Topics: Graph structures, knowledge graphs, semantic triples, role-filler binding Time: 20 minutes Prerequisites: 00_quickstart.py, 01_basic_operations.py Related: 23_app_symbolic_reasoning.py, 24_app_working_memory.py

This example demonstrates how to encode graph structures using compositional bind/bundle operations without requiring a dedicated GraphEncoder. This is the canonical approach in hyperdimensional computing for representing structured knowledge.

Key concepts: - Node encoding: random hypervectors for entities - Edge encoding: bind(bind(source, relation), target) - Graph bundling: bundle all edges into single hypervector - Query operations: unbind to traverse relationships - Multi-hop queries: compose unbinding operations

This compositional approach is fundamental for knowledge graphs, semantic networks, and any relational data structures.

from holovec import VSA

print("=" * 70)
print("Compositional Graph Encoding")
print("=" * 70)
print()

# ============================================================================
# Demo 1: Basic Graph - Nodes and Edges
# ============================================================================
print("=" * 70)
print("Demo 1: Basic Graph Encoding")
print("=" * 70)

# Create model
model = VSA.create('FHRR', dim=10000, seed=42)

# Encode nodes (entities) as random hypervectors
print("\nEncoding nodes:")
alice = model.random(seed=1)
bob = model.random(seed=2)
charlie = model.random(seed=3)
print("  alice   → random hypervector")
print("  bob     → random hypervector")
print("  charlie → random hypervector")

# Encode relation types
print("\nEncoding relations:")
friend_of = model.random(seed=10)
knows = model.random(seed=11)
print("  friend_of → random hypervector")
print("  knows     → random hypervector")

# Create edges: bind(bind(source, relation), target)
print("\nCreating edges:")
edge1 = model.bind(model.bind(alice, friend_of), bob)      # alice --friend_of--> bob
edge2 = model.bind(model.bind(bob, friend_of), charlie)    # bob --friend_of--> charlie
edge3 = model.bind(model.bind(alice, knows), charlie)      # alice --knows--> charlie

print("  alice --friend_of--> bob")
print("  bob --friend_of--> charlie")
print("  alice --knows--> charlie")

# Bundle edges into graph
graph = model.bundle([edge1, edge2, edge3])
print("\nGraph: bundled all edges into single hypervector")

# Query: Who is Alice's friend?
print("\n" + "=" * 70)
print("Query: Who is Alice's friend?")
print("=" * 70)

query_result = model.unbind(model.unbind(graph, alice), friend_of)

# Check similarity to all nodes
print("\nSimilarity to known nodes:")
print(f"  alice:   {float(model.similarity(query_result, alice)):.3f}")
print(f"  bob:     {float(model.similarity(query_result, bob)):.3f}  ← Answer!")
print(f"  charlie: {float(model.similarity(query_result, charlie)):.3f}")

print("\nKey observation:")
print("  - Query recovers 'bob' as Alice's friend")
print("  - Single unbind operation traverses graph edge")

# ============================================================================
# Demo 2: Knowledge Graph - Semantic Triples
# ============================================================================
print("\n" + "=" * 70)
print("Demo 2: Knowledge Graph with Semantic Triples")
print("=" * 70)

# Encode entities and concepts
print("\nEncoding entities and concepts:")
paris = model.random(seed=20)
france = model.random(seed=21)
eiffel_tower = model.random(seed=22)
london = model.random(seed=23)
england = model.random(seed=24)

# Encode relation types
capital_of = model.random(seed=30)
located_in = model.random(seed=31)
landmark_of = model.random(seed=32)

print("  Entities: paris, france, eiffel_tower, london, england")
print("  Relations: capital_of, located_in, landmark_of")

# Create knowledge triples
print("\nCreating knowledge triples:")
triples = []

# Paris is capital of France
triple1 = model.bind(model.bind(paris, capital_of), france)
triples.append(triple1)
print("  (paris, capital_of, france)")

# Eiffel Tower is located in Paris
triple2 = model.bind(model.bind(eiffel_tower, located_in), paris)
triples.append(triple2)
print("  (eiffel_tower, located_in, paris)")

# Eiffel Tower is landmark of Paris
triple3 = model.bind(model.bind(eiffel_tower, landmark_of), paris)
triples.append(triple3)
print("  (eiffel_tower, landmark_of, paris)")

# London is capital of England
triple4 = model.bind(model.bind(london, capital_of), england)
triples.append(triple4)
print("  (london, capital_of, england)")

# Build knowledge graph
knowledge_graph = model.bundle(triples)
print("\nKnowledge graph: bundled all triples")

# Query 1: What is Paris the capital of?
print("\n" + "=" * 70)
print("Query 1: What is Paris the capital of?")
print("=" * 70)

result1 = model.unbind(model.unbind(knowledge_graph, paris), capital_of)

print("\nSimilarity to countries:")
print(f"  france:  {float(model.similarity(result1, france)):.3f}  ← Answer!")
print(f"  england: {float(model.similarity(result1, england)):.3f}")

# Query 2: What is located in Paris?
print("\n" + "=" * 70)
print("Query 2: What is located in Paris?")
print("=" * 70)

result2 = model.unbind(model.unbind(knowledge_graph, paris), located_in)

print("\nSimilarity to landmarks:")
print(f"  eiffel_tower: {float(model.similarity(result2, eiffel_tower)):.3f}  ← Answer!")
print(f"  london:       {float(model.similarity(result2, london)):.3f}")

# ============================================================================
# Demo 3: Multi-Hop Queries
# ============================================================================
print("\n" + "=" * 70)
print("Demo 3: Multi-Hop Graph Queries")
print("=" * 70)

# Build a social network
print("\nBuilding social network:")
print("  alice --works_with--> bob")
print("  bob --manages--> charlie")
print("  charlie --reports_to--> diana")

diana = model.random(seed=4)
works_with = model.random(seed=12)
manages = model.random(seed=13)
reports_to = model.random(seed=14)

# Create edges
edges = []
edges.append(model.bind(model.bind(alice, works_with), bob))
edges.append(model.bind(model.bind(bob, manages), charlie))
edges.append(model.bind(model.bind(charlie, reports_to), diana))

social_graph = model.bundle(edges)
print("\nSocial graph created")

# Single-hop: Who does Alice work with?
print("\n" + "=" * 70)
print("Single-hop query: Who does Alice work with?")
print("=" * 70)

hop1 = model.unbind(model.unbind(social_graph, alice), works_with)
print(f"  bob:     {float(model.similarity(hop1, bob)):.3f}  ← Alice works with Bob")
print(f"  charlie: {float(model.similarity(hop1, charlie)):.3f}")

# Two-hop: Who does Bob manage?
print("\n" + "=" * 70)
print("Two-hop query: Who does Alice's colleague manage?")
print("=" * 70)
print("  Step 1: Find who Alice works with → bob")
print("  Step 2: Find who bob manages → charlie")

hop2 = model.unbind(model.unbind(social_graph, hop1), manages)
print(f"\n  charlie: {float(model.similarity(hop2, charlie)):.3f}  ← Bob manages Charlie")
print(f"  diana:   {float(model.similarity(hop2, diana)):.3f}")

print("\nKey observation:")
print("  - Multi-hop queries compose unbinding operations")
print("  - Each hop uses result of previous query")
print("  - Enables traversal of complex graph structures")

# ============================================================================
# Demo 4: Bidirectional Edges and Graph Properties
# ============================================================================
print("\n" + "=" * 70)
print("Demo 4: Bidirectional Edges and Graph Properties")
print("=" * 70)

# Create bidirectional friendship graph
print("\nCreating bidirectional friendship graph:")
print("  alice <--> bob    (mutual friends)")
print("  bob <--> charlie  (mutual friends)")
print("  alice --> diana   (one-way follows)")

follows = model.random(seed=15)

# Bidirectional: both directions
edges_bidir = []
edges_bidir.append(model.bind(model.bind(alice, friend_of), bob))
edges_bidir.append(model.bind(model.bind(bob, friend_of), alice))  # Reverse
edges_bidir.append(model.bind(model.bind(bob, friend_of), charlie))
edges_bidir.append(model.bind(model.bind(charlie, friend_of), bob))  # Reverse
edges_bidir.append(model.bind(model.bind(alice, follows), diana))   # One-way

friendship_graph = model.bundle(edges_bidir)
print("\nFriendship graph created with bidirectional edges")

# Query: Who are Bob's friends? (people who point back to Bob)
print("\n" + "=" * 70)
print("Query: Who considers Bob a friend?")
print("=" * 70)

bob_friends = model.unbind(model.unbind(friendship_graph, bob), friend_of)

print("\nSimilarity to potential friends:")
print(f"  alice:   {float(model.similarity(bob_friends, alice)):.3f}  ← Mutual friend")
print(f"  charlie: {float(model.similarity(bob_friends, charlie)):.3f}  ← Mutual friend")
print(f"  diana:   {float(model.similarity(bob_friends, diana)):.3f}  ← Not mutual")

print("\nKey observation:")
print("  - Bidirectional edges enable reverse queries")
print("  - Can find both outgoing and incoming edges")
print("  - Models undirected graphs naturally")

# ============================================================================
# Demo 5: Role-Filler Bindings in Structures
# ============================================================================
print("\n" + "=" * 70)
print("Demo 5: Complex Structures with Role-Filler Binding")
print("=" * 70)

print("\nEncoding a sentence structure:")
print("  Sentence: 'Alice gave Bob a book'")
print("  Structure: (agent=Alice, action=gave, recipient=Bob, object=book)")

# Encode roles
agent = model.random(seed=40)
action = model.random(seed=41)
recipient = model.random(seed=42)
obj = model.random(seed=43)

# Encode fillers
gave = model.random(seed=50)
book = model.random(seed=51)

# Create role-filler bindings
print("\nCreating role-filler bindings:")
bindings = []
bindings.append(model.bind(agent, alice))
bindings.append(model.bind(action, gave))
bindings.append(model.bind(recipient, bob))
bindings.append(model.bind(obj, book))

print("  agent ⊗ alice")
print("  action ⊗ gave")
print("  recipient ⊗ bob")
print("  object ⊗ book")

# Bundle into sentence representation
sentence = model.bundle(bindings)
print("\nSentence: bundled all role-filler pairs")

# Query: Who is the agent?
print("\n" + "=" * 70)
print("Query: Who performed the action?")
print("=" * 70)

agent_result = model.unbind(sentence, agent)

print("\nSimilarity to entities:")
print(f"  alice:   {float(model.similarity(agent_result, alice)):.3f}  ← Agent")
print(f"  bob:     {float(model.similarity(agent_result, bob)):.3f}")

# Query: What was given?
print("\n" + "=" * 70)
print("Query: What was given?")
print("=" * 70)

object_result = model.unbind(sentence, obj)

print("\nSimilarity to objects:")
print(f"  book: {float(model.similarity(object_result, book)):.3f}  ← Object")
print(f"  gave: {float(model.similarity(object_result, gave)):.3f}")

print("\nKey observation:")
print("  - Role-filler binding separates structure from content")
print("  - Can query by role to retrieve filler")
print("  - Enables compositional semantic representations")

# ============================================================================
# Summary
# ============================================================================
print("\n" + "=" * 70)
print("Summary: Compositional Graph Encoding Key Takeaways")
print("=" * 70)
print()
print("✓ No special encoder needed: Use bind/bundle primitives")
print("✓ Flexible representation: Nodes, edges, properties")
print("✓ Efficient queries: Single unbind traverses edges")
print("✓ Multi-hop: Compose unbinding for path traversal")
print("✓ Bidirectional: Model undirected graphs naturally")
print("✓ Role-filler: Separate structure from content")
print()
print("Graph encoding pattern:")
print("  1. Nodes: random hypervectors for entities")
print("  2. Relations: random hypervectors for edge types")
print("  3. Edges: bind(bind(source, relation), target)")
print("  4. Graph: bundle(all edges)")
print("  5. Query: unbind(unbind(graph, source), relation) → target")
print()
print("Use cases:")
print("  - Knowledge graphs: Semantic triples, ontologies")
print("  - Social networks: Friendship, follower graphs")
print("  - Scene graphs: Object relationships in images")
print("  - Semantic parsing: Sentence structure, dependencies")
print()
print("Next steps:")
print("  → 23_app_symbolic_reasoning.py - Advanced role-filler reasoning")
print("  → 24_app_working_memory.py - Query graphs with cleanup")
print("  → 25_app_integration_patterns.py - Combine with other encoders")
print()
print("=" * 70)