Cheat sheets

Graphs and Knowledge Graphs

Graph matrices, Laplacian and message passing, entity linking, relation extraction and hybrid graph memory.

  • Concepts and terms
  • Tasks and commands
  • Annotated code
  • Diagrams
  • Defaults and numbers
  • Troubleshooting
  • Questions and tips

Source

Graph matrices#

Adjacency
A[i][j] = 1 for an edge. It is symmetric for an undirected graph.
Degree matrix
D is diagonal with the degree of each node. A triangle gives diag(2, 2, 2).
Laplacian
L = D - A. It is positive semi-definite. All eigenvalues are \ge 0.
Zero eigenvalues
their count equals the number of connected components.
Fiedler value
the smallest non-zero eigenvalue. A small value shows a bottleneck.
Message passing
H^{(k+1)} = \sigma(A_{\text{norm}} H^{(k)} W). Each row of A_{\text{norm}} sums to 1.
GCN layer
\sigma(\hat{D}^{-1/2} \hat{A} \hat{D}^{-1/2} H W) with self-loops \hat{A} = A + I.
PageRank
(1-d)/n + d \sum \text{score}(u) / \text{out}(u) with d=0.85.

Graph tasks in code#

TaskCode
Build a graphGraph(n_nodes, directed=False)
Add an edgeadd_edge(u, v, weight=1.0)
Hop distances and visit orderbfs(graph, start) returns order, distances
Find componentsconnected_components(graph)
Split into two clustersspectral_clustering(graph, k=2)
One GNN roundmessage_passing(graph, features, weight_matrix)
Rank nodespagerank(graph, damping=0.85, max_iter=100, tol=1e-6)
Laplacian eigenvalues, ascendingnp.linalg.eigvalsh(L)

Spectral split with numpy#

D = np.diag(A.sum(axis=1))degree matrix
L = D - ALaplacian
eigenvalues, eigenvectors = np.linalg.eigh(L)ascending order
eigenvalues[1]Fiedler value
fiedler = eigenvectors[:, 1]Fiedler vector
group_a = np.where(fiedler >= 0)[0]one cluster
group_b = np.where(fiedler < 0)[0]the other cluster
G = nx.karate_club_graph()34 nodes, 78 edges
nx.number_connected_components(G)
nx.pagerank(G)node importance

Text to knowledge graph#

1NERfind the entity mentions in the text.2Corefresolve "he" to the right entity before RE.3Entity linkingmap each mention to one KB id.4Relation extractionemit (subject, relation, object) triples withspans.5Verifymatch each triple element to the source. Rejectunsupported triples.6Ontology mappingmap relations to canonical ids, for example P108employer.7Graph loadstore each triple with its doc id and char-span.

Extract, verify, build#

def verify(triples, text):
verified = []
for t in triples:
s, e = t["span"]
if text[s:e] != t["evidence"]:span must match the source
continue
verified.append(t)
return verified
triples = extract(doc)regex PATTERNS, one P id each
graph = build_graph(verify(triples, doc))subject to relation, object
for rel, obj, ev in graph.get("Tim Cook", []):ev is the source sentence
if rel == "P169":CEO of

Mem0Config and defaults#

SettingDefaultNote
w_relevance0.6Raise it for retrieval agents
w_importance0.2Raise it for compliance agents
w_recency0.2Raise it for chat agents
recency_halflife_s86400.0Recency halves each half-life
importance0.5Set on each record at add time
scopeuserOr session or agent
top_k5Vector search pulls 3 times more first
KV hit relevance0.4Fixed relevance for KV-only records

Hybrid memory: Mem0#

cosineexact hitsubgraphclientadd()text, user_id,metadatastoreVectorStoresemanticsimilaritystoreKVStoreuser_id,fact_type, entitystoreGraphStoretyped edges, validflagprocessFusion scorerelevance,importance,recencysearch()fused top_kcosineexact hitsubgraphclientadd()text,user_id,metadatastoreVectorStoresemanticsimilaritystoreKVStoreuser_id,fact_type,entitystoreGraphStoretyped edges,valid flagprocessFusionscorerelevance,importance,recencysearch()fused top_k

Failures and fixes#

SymptomCauseFix
Frequent entity always winsPopularity biasFine-tune on domain data
Right entity never scoredLow candidate recallMeasure mention recall @ 30 first
Wrong entity for a new nameMention is not in the KBPredict NIL
"He founded Apple" lostNo coreference before RERun coref first
Triples the text does not supportLLM hallucinationVerify every span against the source
Graph cannot be queriedOpen IE relation driftCollapse to canonical ids
Vector recall degradesEmbedding drift as corpus growsRe-embed the top-N-used records
50 edges per messageNoisy extractorCap graph writes per add call

Abbreviations#

BFS / DFS
breadth-first with a queue, depth-first with a stack. Both O(V + E).
GCN
graph convolutional network. Message passing with symmetric normalization.
EL
entity linking. Map a mention to a unique KB entry.
KB
knowledge base. Wikidata, Wikipedia, DBpedia or a domain KB.
NIL
the prediction that no KB entry matches.
RE
relation extraction. Text to (subject, relation, object) triples.
AEVS
Anchor-Extraction-Verification-Supplement. Span-verified extraction.
Open IE
any verbal phrase is a relation. High recall, low precision.
Mem0g
typed edges with temporal validity for relationship queries.

Questions#

Why BFS for hop distance?
The BFS level of a node is its shortest path in an unweighted graph.
How does the Fiedler vector split?
Positive entries go in one cluster. Negative entries go in the other.
What do K rounds of message passing see?
The K-hop neighborhood of each node.
Why report two EL numbers?
99% disambiguation on 80% candidate recall is an 80% pipeline.
Why mark an edge invalid?
Temporal queries traverse the valid-at-time subgraph.
Why three memory stores?
One store is wrong for two of the three query classes.

Tips#

  • Use networkx in production. Use the scratch code to learn what it does.
  • Give every triple a source char-span and a doc id.
  • Map open IE relations onto a closed ontology before you merge them.
  • Budget 60-80% of the engineering work for canonicalization.
  • Add P580 start time and P582 end time to time-bounded relations.
  • Report in-KB accuracy (P@1) and the NIL-detection rate on AIDA-CoNLL.
  • Pick one scope for each memory write: user, session or agent.