graph

package
v0.3.2 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Sep 2, 2026 License: MIT Imports: 9 Imported by: 0

README

graph

Knowledge graphs: entities, typed/weighted relations, and the traversal and inference operations on them.

Core

g := graph.NewKnowledgeGraph()
g.AddEntity(graph.NewEntity("alice", "Alice", graph.EntityPerson))
g.AddRelation(graph.NewRelation("alice", "google", "works_at", 0.9))

g.Neighbors("alice")             // adjacent entities
g.FindPath("alice", "stanford")  // BFS shortest path (*Path)
g.TransitiveClosure("alice")     // all reachable entities
g.CommonNeighbors("alice", "bob")

Entity carries typed properties (EntityPerson, EntityOrganization, ...); Relation carries type + weight + properties.

Extraction

  • NERExtractor interface — bring your own NER model.
  • HeuristicNER (NewHeuristicNER()) — dependency-free heuristic entity recognition.
  • PatternRelationExtractor + DefaultPatterns() — regex relation patterns (works_at, located_in, founded_by, part_of, ...); NewRelationPattern(name, regex, fromIndex, toIndex) for custom ones.

Learning & analytics

  • TransE — TransE-style embedding training over triples (NewTransE(store), TrainOptions); LinkPrediction ranks missing edges; NearestNeighbors finds similar entities via a GraphEmbedder.
  • EvaluateMetrics — training/link-prediction evaluation metrics.
  • Entity similarity utilities (cosine over entity embeddings) in similarity.go.

store wraps these as GraphStore (memory + SQLite persistence).

Documentation

Overview

Package graph provides a knowledge graph for storing and querying structured relationships between entities extracted from text.

Package graph provides a knowledge graph for storing and querying structured relationships between entities extracted from text.

Package graph provides a knowledge graph for storing and querying structured relationships between entities extracted from text.

Package graph provides a knowledge graph for storing and querying structured relationships between entities extracted from text.

Index

Constants

This section is empty.

Variables

View Source 
var DefaultStopwords = map[string]bool{
	"a": true, "an": true, "the": true, "and": true, "or": true,
	"but": true, "in": true, "on": true, "at": true, "to": true,
	"for": true, "of": true, "with": true, "by": true, "from": true,
	"is": true, "are": true, "was": true, "were": true, "be": true,
	"been": true, "being": true, "have": true, "has": true, "had": true,
	"do": true, "does": true, "did": true, "will": true, "would": true,
	"could": true, "should": true, "may": true, "might": true, "shall": true,
	"can": true, "it": true, "its": true, "this": true, "that": true,
	"these": true, "those": true, "i": true, "we": true, "they": true,
	"he": true, "she": true, "you": true, "me": true, "my": true,
	"your": true, "his": true, "her": true, "our": true, "their": true,
	"what": true, "which": true, "who": true, "whom": true, "where": true,
	"when": true, "how": true, "not": true, "no": true, "nor": true,
}

DefaultStopwords is a list of common English stopwords that are unlikely to be meaningful entity names on their own.

Functions

func ClusterEntities 

func ClusterEntities(embedder GraphEmbedder, numClusters int) (map[string]int, error)

ClusterEntities clusters entities based on their embeddings using a simple centroid-based clustering algorithm.

func ComputeHitsAtK 

func ComputeHitsAtK(ranks []int, k int) float64

ComputeHitsAtK computes the Hits@K for a list of ranks.

func ComputeMRR 

func ComputeMRR(ranks []int) float64

ComputeMRR computes the Mean Reciprocal Rank for a list of ranks.

func ComputeMeanRank 

func ComputeMeanRank(ranks []int) float64

ComputeMeanRank computes the Mean Rank for a list of ranks.

func EmbeddingDiversity 

func EmbeddingDiversity(embeddings [][]float32) float64

EmbeddingDiversity computes the diversity of embeddings in the space.

func EmbeddingQuality 

func EmbeddingQuality(embedder GraphEmbedder) map[string]float64

EmbeddingQuality computes quality metrics for the embedding space.

func EntityPairSimilarity 

func EntityPairSimilarity(embedder GraphEmbedder, entityID1, entityID2 string) (float64, error)

EntityPairSimilarity computes the similarity between two entities.

func NormalizeEmbedding 

func NormalizeEmbedding(emb []float32) []float32

NormalizeEmbedding normalizes an embedding vector to unit length.

func RelationPairSimilarity 

func RelationPairSimilarity(embedder GraphEmbedder, relType1, relType2 string) (float64, error)

RelationPairSimilarity computes the similarity between two relations.

func ScoreTriple 

func ScoreTriple(headEmb, relEmb, tailEmb []float32) float64

ScoreTriple computes the score for a triple using TransE scoring function. Score = -||head + relation - tail||

Types

type EmbeddingStore 

type EmbeddingStore struct {

	// EntityEmbeddings maps entity IDs to their embedding vectors.
	EntityEmbeddings map[string][]float32

	// RelationEmbeddings maps relation types to their embedding vectors.
	RelationEmbeddings map[string][]float32

	// Dimension is the embedding dimension.
	Dimension int

	// EntityIndex maps entity IDs to indices for fast lookup.
	EntityIndex map[string]int

	// RelationIndex maps relation types to indices for fast lookup.
	RelationIndex map[string]int

	// EntityList is the list of entity IDs in index order.
	EntityList []string

	// RelationList is the list of relation types in index order.
	RelationList []string
	// contains filtered or unexported fields
}

EmbeddingStore stores entity and relation embeddings in memory.

func NewEmbeddingStore 

func NewEmbeddingStore(dimension int) *EmbeddingStore

NewEmbeddingStore creates a new empty EmbeddingStore.

func (*EmbeddingStore) AddEntity 

func (s *EmbeddingStore) AddEntity(id string)

AddEntity adds an entity to the store with a random embedding.

func (*EmbeddingStore) AddRelation 

func (s *EmbeddingStore) AddRelation(relType string)

AddRelation adds a relation to the store with a random embedding.

func (*EmbeddingStore) EntityCount 

func (s *EmbeddingStore) EntityCount() int

EntityCount returns the number of entities.

func (*EmbeddingStore) GetEntityEmbedding 

func (s *EmbeddingStore) GetEntityEmbedding(entityID string) ([]float32, bool)

GetEntityEmbedding returns the embedding for an entity.

func (*EmbeddingStore) GetRelationEmbedding 

func (s *EmbeddingStore) GetRelationEmbedding(relType string) ([]float32, bool)

GetRelationEmbedding returns the embedding for a relation.

func (*EmbeddingStore) RelationCount 

func (s *EmbeddingStore) RelationCount() int

RelationCount returns the number of relations.

type Entities 

type Entities []*Entity

Entities is a sortable slice of *Entity.

func (Entities) Len 

func (e Entities) Len() int

func (Entities) Less 

func (e Entities) Less(i, j int) bool

func (Entities) Swap 

func (e Entities) Swap(i, j int)

type Entity 

type Entity struct {
	// ID is a unique identifier.
	ID string

	// Label is a human-readable name.
	Label string

	// Type classifies the entity.
	Type EntityType

	// Properties are arbitrary key-value metadata.
	Properties map[string]string

	// SourceChunks tracks which chunks this entity was extracted from.
	SourceChunks []string
}

Entity represents a node in the knowledge graph.

func ExtractEntitiesWithPatterns 

func ExtractEntitiesWithPatterns(text string, patterns []*RelationPattern) []*Entity

ExtractEntitiesWithPatterns extracts entities from text using relation patterns. Entities are those that appear in any pattern match.

func NewEntity 

func NewEntity(id, label string, typ EntityType) *Entity

NewEntity creates a new entity with the given ID, label, and type.

func (*Entity) AddSourceChunk 

func (e *Entity) AddSourceChunk(chunkID string)

AddSourceChunk adds a chunk ID to the entity's source list.

func (*Entity) GetProperty 

func (e *Entity) GetProperty(key string) string

GetProperty returns a property value, or empty string if not present.

func (*Entity) SetProperty 

func (e *Entity) SetProperty(key, value string)

SetProperty sets a property on the entity.

func (*Entity) String 

func (e *Entity) String() string

String returns a human-readable representation.

type EntitySimilarity 

type EntitySimilarity struct {
	// contains filtered or unexported fields
}

EntitySimilarity provides entity similarity search capabilities.

func NewEntitySimilarity 

func NewEntitySimilarity(embedder GraphEmbedder) *EntitySimilarity

NewEntitySimilarity creates a new EntitySimilarity instance.

func (*EntitySimilarity) FindSimilarEntities 

func (es *EntitySimilarity) FindSimilarEntities(entityID string, topK int) ([]SimilarityResult, error)

FindSimilarEntities finds entities similar to the given entity.

func (*EntitySimilarity) FindSimilarRelations 

func (es *EntitySimilarity) FindSimilarRelations(relationType string, topK int) ([]SimilarityResult, error)

FindSimilarRelations finds relations similar to the given relation.

type EntityType 

type EntityType string

EntityType classifies an entity. 

const (
	EntityPerson    EntityType = "person"
	EntityConcept   EntityType = "concept"
	EntityDocument  EntityType = "document"
	EntityLocation  EntityType = "location"
	EntityOrganizer EntityType = "organization"
	EntityOther     EntityType = "other"
)

type EvaluateMetrics 

type EvaluateMetrics struct {
	// MeanReciprocalRank is the mean reciprocal rank of correct answers.
	MeanReciprocalRank float64

	// HitsAtK is the fraction of correct answers in the top-K predictions.
	HitsAtK map[int]float64

	// MeanRank is the mean rank of correct answers.
	MeanRank float64

	// TotalTests is the total number of test triples.
	TotalTests int
}

EvaluateMetrics computes evaluation metrics for link prediction.

func NewEvaluateMetrics 

func NewEvaluateMetrics() *EvaluateMetrics

NewEvaluateMetrics creates a new EvaluateMetrics instance.

func (*EvaluateMetrics) AddResult 

func (m *EvaluateMetrics) AddResult(rank int, topKs []int)

AddResult adds a result to the metrics.

func (*EvaluateMetrics) Finalize 

func (m *EvaluateMetrics) Finalize()

Finalize computes the final metrics.

func (*EvaluateMetrics) String 

func (m *EvaluateMetrics) String() string

String returns a human-readable summary of the metrics.

type GraphEmbedder 

type GraphEmbedder interface {
	// EmbedEntity returns the embedding vector for an entity.
	EmbedEntity(entityID string) ([]float32, error)

	// EmbedRelation returns the embedding vector for a relation type.
	EmbedRelation(relationType string) ([]float32, error)

	// Dimension returns the embedding dimension.
	Dimension() int

	// Train trains the embeddings on the given triples.
	Train(triples []*Triple, opts TrainOptions) error

	// Save saves the embeddings to a file.
	Save(path string) error

	// Load loads embeddings from a file.
	Load(path string) error
}

GraphEmbedder defines the interface for learning and querying graph embeddings.

type HeuristicNER 

type HeuristicNER struct {
	Stopwords      map[string]bool
	MinLength      int
	MinGroupLength int // minimum total length for multi-word grouping (default 8)
}

HeuristicNER extracts entities using capitalized word detection with stopword filtering and multi-word grouping.

func NewHeuristicNER 

func NewHeuristicNER() *HeuristicNER

NewHeuristicNER creates a HeuristicNER with default settings.

func (*HeuristicNER) Extract 

func (h *HeuristicNER) Extract(text string) ([]*Entity, error)

Extract identifies capitalized words and groups consecutive capitalized words into multi-word entities, filtering stopwords and short tokens.

type KnowledgeGraph 

type KnowledgeGraph struct {
	// contains filtered or unexported fields
}

KnowledgeGraph stores entities and their relationships, supporting traversal, querying, and inference operations.

func NewKnowledgeGraph 

func NewKnowledgeGraph() *KnowledgeGraph

NewKnowledgeGraph creates a new empty knowledge graph.

func (*KnowledgeGraph) AddEntity 

func (g *KnowledgeGraph) AddEntity(e *Entity) bool

AddEntity adds an entity to the graph. Returns true if added, false if already exists.

func (*KnowledgeGraph) AddRelation 

func (g *KnowledgeGraph) AddRelation(r *Relation) bool

AddRelation adds a relation to the graph. Returns true if added.

func (*KnowledgeGraph) CommonNeighbors 

func (g *KnowledgeGraph) CommonNeighbors(id1, id2 string) []*Entity

CommonNeighbors finds entities that are neighbors of both given entities.

func (*KnowledgeGraph) Count 

func (g *KnowledgeGraph) Count() int

Count returns the number of entities.

func (*KnowledgeGraph) Entities 

func (g *KnowledgeGraph) Entities() Entities

Entities returns all entities sorted by label.

func (*KnowledgeGraph) FindEntitiesByLabel 

func (g *KnowledgeGraph) FindEntitiesByLabel(query string) Entities

FindEntitiesByLabel returns all entities whose label contains the query (case-insensitive).

func (*KnowledgeGraph) FindEntitiesByType 

func (g *KnowledgeGraph) FindEntitiesByType(typ EntityType) Entities

FindEntitiesByType returns all entities of a given type.

func (*KnowledgeGraph) FindPath 

func (g *KnowledgeGraph) FindPath(from, to string) *Path

FindPath finds a path between two entities using BFS. Returns nil if no path exists.

func (*KnowledgeGraph) GetEntity 

func (g *KnowledgeGraph) GetEntity(id string) (*Entity, bool)

GetEntity returns an entity by ID.

func (*KnowledgeGraph) GetRelation 

func (g *KnowledgeGraph) GetRelation(from, to, relType string) (*Relation, bool)

GetRelation returns a relation matching from/to/type.

func (*KnowledgeGraph) IncomingRelations 

func (g *KnowledgeGraph) IncomingRelations(entityID string) []*Relation

IncomingRelations returns all relations to an entity.

func (*KnowledgeGraph) Neighbors 

func (g *KnowledgeGraph) Neighbors(entityID string) []*Entity

Neighbors returns all entities directly connected to the given entity.

func (*KnowledgeGraph) OutgoingRelations 

func (g *KnowledgeGraph) OutgoingRelations(entityID string) []*Relation

OutgoingRelations returns all relations from an entity.

func (*KnowledgeGraph) RelationCount 

func (g *KnowledgeGraph) RelationCount() int

RelationCount returns the number of relations.

func (*KnowledgeGraph) Relations 

func (g *KnowledgeGraph) Relations() Relations

Relations returns all relations.

func (*KnowledgeGraph) RemoveEntity 

func (g *KnowledgeGraph) RemoveEntity(id string) bool

RemoveEntity removes an entity and all its relations.

func (*KnowledgeGraph) ShortestPathLength 

func (g *KnowledgeGraph) ShortestPathLength(from, to string) int

ShortestPathLength returns the number of edges in the shortest path between two entities. Returns -1 if no path exists.

func (*KnowledgeGraph) String 

func (g *KnowledgeGraph) String() string

String returns a summary of the graph.

func (*KnowledgeGraph) TransitiveClosure 

func (g *KnowledgeGraph) TransitiveClosure(entityID string) []*Entity

TransitiveClosure computes all entities reachable from a given entity.

type LinkPrediction 

type LinkPrediction struct {
	// contains filtered or unexported fields
}

LinkPrediction predicts missing links in the knowledge graph.

func NewLinkPrediction 

func NewLinkPrediction(embedder GraphEmbedder) *LinkPrediction

NewLinkPrediction creates a new LinkPrediction instance.

func (*LinkPrediction) PredictHead 

func (lp *LinkPrediction) PredictHead(relation string, tail string, topK int) ([]LinkPredictionResult, error)

PredictHead predicts the most likely head entities for a given (relation, tail) pair.

func (*LinkPrediction) PredictTail 

func (lp *LinkPrediction) PredictTail(head string, relation string, topK int) ([]LinkPredictionResult, error)

PredictTail predicts the most likely tail entities for a given (head, relation) pair.

type LinkPredictionResult 

type LinkPredictionResult struct {
	Head     string
	Relation string
	Tail     string
	Score    float64
}

LinkPredictionResult represents the result of a link prediction query.

type NERExtractor 

type NERExtractor interface {
	// Extract identifies entities in the given text and returns them.
	Extract(text string) ([]*Entity, error)
}

NERExtractor defines the interface for named entity recognition. Users can implement this to plug in custom NER models (e.g., OpenAI, spaCy, etc.).

type Path 

type Path struct {
	Entities  []*Entity
	Relations []*Relation
}

Path represents a sequence of entities connected by relations.

func (*Path) Length 

func (p *Path) Length() int

Length returns the number of entities in the path.

func (*Path) String 

func (p *Path) String() string

String returns a human-readable representation of the path.

type PatternRelationExtractor 

type PatternRelationExtractor struct {
	// Patterns are regex patterns that capture relation types and entity positions.
	// Each pattern should have named capture groups: "rel" for relation type,
	// and "from"/"to" for source/target entities.
	Patterns []*RelationPattern
}

PatternRelationExtractor extracts relations based on configurable text patterns.

func (*PatternRelationExtractor) ExtractRelations 

func (e *PatternRelationExtractor) ExtractRelations(text string) []*Relation

ExtractRelations extracts relations from text using the configured patterns.

type Relation 

type Relation struct {
	// From is the source entity ID.
	From string

	// To is the target entity ID.
	To string

	// Type classifies the relationship (e.g., "works_at", "part_of", "related_to").
	Type string

	// Weight is the confidence or strength of the relationship (0-1).
	Weight float64

	// Properties are arbitrary key-value metadata.
	Properties map[string]string

	// SourceChunks tracks which chunks this relation was extracted from.
	SourceChunks []string
}

Relation represents a directed edge between two entities in the knowledge graph.

func NewRelation 

func NewRelation(from, to, relType string, weight float64) *Relation

NewRelation creates a new relation with the given parameters.

func (*Relation) AddSourceChunk 

func (r *Relation) AddSourceChunk(chunkID string)

AddSourceChunk adds a chunk ID to the relation's source list.

func (*Relation) GetProperty 

func (r *Relation) GetProperty(key string) string

GetProperty returns a property value, or empty string if not present.

func (*Relation) SetProperty 

func (r *Relation) SetProperty(key, value string)

SetProperty sets a property on the relation.

func (*Relation) String 

func (r *Relation) String() string

String returns a human-readable representation.

type RelationPattern 

type RelationPattern struct {
	// Name is the relation type (e.g., "works_at", "located_in").
	Name string

	// Regex is the compiled regex pattern.
	Regex *regexp.Regexp

	// FromIndex is the 1-based capture group index for the source entity.
	FromIndex int

	// ToIndex is the 1-based capture group index for the target entity.
	ToIndex int
}

RelationPattern defines a regex pattern for extracting a specific relation type.

func DefaultPatterns 

func DefaultPatterns() []*RelationPattern

DefaultPatterns returns common relation extraction patterns.

func NewRelationPattern 

func NewRelationPattern(name, regexStr string, fromIndex, toIndex int) *RelationPattern

NewRelationPattern creates a new relation pattern from a regex string.

type Relations 

type Relations []*Relation

Relations is a sortable slice of *Relation.

func (Relations) Len 

func (r Relations) Len() int

func (Relations) Less 

func (r Relations) Less(i, j int) bool

func (Relations) Swap 

func (r Relations) Swap(i, j int)

type SimilarityResult 

type SimilarityResult struct {
	ID    string
	Score float64
	Label string
	Type  EntityType
}

SimilarityResult represents the result of a similarity query.

func NearestNeighbors 

func NearestNeighbors(embedder GraphEmbedder, entityID string, k int) ([]SimilarityResult, error)

NearestNeighbors finds the K nearest neighbors of an entity in the embedding space.

func (SimilarityResult) String 

func (sr SimilarityResult) String() string

String returns a human-readable representation of a SimilarityResult.

type TrainOptions 

type TrainOptions struct {
	// Dimension is the embedding dimension for entities and relations.
	Dimension int

	// LearningRate is the step size for gradient descent.
	LearningRate float64

	// Margin is the margin for the loss function (TransE uses this for ranking).
	Margin float64

	// Regularization is the L2 regularization strength.
	Regularization float64

	// NegativeSamples is the number of negative samples per positive triple.
	NegativeSamples int

	// Epochs is the number of training epochs.
	Epochs int

	// BatchSize is the number of triples per gradient update.
	BatchSize int
}

TrainOptions configures the training process for graph embeddings.

func DefaultTrainOptions 

func DefaultTrainOptions() TrainOptions

DefaultTrainOptions returns TrainOptions with sensible defaults.

type TransE 

type TransE struct {
	// contains filtered or unexported fields
}

TransE implements the TransE algorithm for learning graph embeddings. TransE represents entities and relations as vectors in a low-dimensional space, where the relation vector is approximately the translation from head to tail: 

head + relation ≈ tail

The loss function is margin-based: 

L = sum over positive triples of max(0, margin - score(pos) + score(neg))

func NewTransE 

func NewTransE(store *EmbeddingStore) *TransE

NewTransE creates a new TransE model with the given embedding store.

func (*TransE) Dimension 

func (t *TransE) Dimension() int

Dimension returns the embedding dimension.

func (*TransE) EmbedEntity 

func (t *TransE) EmbedEntity(entityID string) ([]float32, error)

EmbedEntity returns the embedding for an entity.

func (*TransE) EmbedRelation 

func (t *TransE) EmbedRelation(relationType string) ([]float32, error)

EmbedRelation returns the embedding for a relation.

func (*TransE) Load 

func (t *TransE) Load(path string) error

Load replaces the current embeddings with those stored at the given path (a file previously written by Save). The file must have the same embedding dimension as the underlying store; every listed entity/relation must have a well-formed vector.

func (*TransE) Save 

func (t *TransE) Save(path string) error

Save persists the current entity and relation embeddings to the given path as a JSON document (transEFile). Vectors are copied so the file is a stable snapshot of the model at the time of the call.

func (*TransE) Train 

func (t *TransE) Train(triples []*Triple, opts TrainOptions) error

Train trains the TransE model on the given triples.

type Triple 

type Triple struct {
	Head     string
	Relation string
	Tail     string
}

Triple represents a fact in the knowledge graph: (head, relation, tail).

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.