Graphs and Activation Spread Flashcards
What is a Graph?
Structure that consists of
vertices (nodes) and edges.
▪ Vertices and edges can
have labels (labelled
graph), or not (unlabeled
graph)
▪ Edges can have a
direction (directed graph),
or not (undirected graph).
Graph representation as adjacency matrix
Adjacency matrix A
▪ i = row-index
▪ j = column-index
▪ A(i,j) = number of
edges e(i,j)
▪ Uniquely represents
the graph
Semantic Networks
Labelled directed graphs (vertices, edges, labels)
▪ Semantics (meaning) associated with labels (special
labels, like „is_a“, or „is_parts_of“)
▪ Procedures that implement inferencing on semantic
networks
Different types of semantic networks; hybrids exist
▪ Definitional networks (~taxonomies, ontologies)
▪ Assertional networks
▪ Implicational networks (describing beliefs, causalities,
inferences)
Semantic Network – Example Tree of
Porphyry (300 CE)
Idea: Classify everthing
that exists in natural life
Semantic Network – Example WordNet
WordNet: Lexical
database of English
▪ Concepts are nodes
▪ Concepts can be
expressed by multiple
words, with the
relationship “synonym”
▪ Concepts are related to
by semantic
relationships, e.g.,
generalization,
aggregation
Semantic Network – Example, logic representation (based
on Russell & Norvig – AI, 3rd Edition, Ch. 12.5.1)
𝐹𝑒𝑚𝑎𝑙𝑒𝑃𝑒𝑟𝑠𝑜𝑛𝑠 𝑥 → 𝑃𝑒𝑟𝑠𝑜𝑛𝑠 𝑥
▪ 𝑀𝑎𝑙𝑒𝑃𝑒𝑟𝑠𝑜𝑛𝑠 𝑥 → 𝑃𝑒𝑟𝑠𝑜𝑛𝑠 𝑥
▪ 𝑃𝑒𝑟𝑠𝑜𝑛𝑠 𝑥 → 𝑀𝑎𝑚𝑚𝑎𝑙𝑠 𝑥
▪ 𝑃𝑒𝑟𝑠𝑜𝑛𝑠 𝑥 → ∃𝑦: ℎ𝑎𝑠𝑀𝑜𝑡ℎ𝑒𝑟(𝑥, 𝑦) ∧
𝐹𝑒𝑚𝑎𝑙𝑒𝑃𝑒𝑟𝑠𝑜𝑛𝑠(𝑦)
▪ 𝑃𝑒𝑟𝑠𝑜𝑛𝑠 𝑥 → 𝐿𝑒𝑔𝑠(𝑥, 2)
▪ FemalePersons(Mary)
▪ MalePersons(John)
▪ sisterOf(Mary,John)
▪ Legs(John,1)
Semantic Networks as Knowledge
Representation
Semantic Networks were invented as a new and
„more natural“ type of knowledge representation
▪ They could be arbitrarily formal or informal
▪ Informal (see examples on Slides 11 and 12):
Represent any kinds of relationships between
concepts in the form of a semantic network
▪ Formal (see example on Slides 13 and 14):
Represent logic statements in the form of a semantic
network
▪ Semantic networks have the same expressive power as
logic.
Reasoning over graphs
to infer further knowledge about the instances, concepts,
and their relationships which are represented by the graph
Reasoning over Semantic Networks with
Logic-Based Semantics
Semantic network could be expressed as logic -> reasoning
using logic inference mechanisms
▪ Might be possible to use simpler reasoning to answer queries
using graph transversal:
Example queries for Example on Slide 13:
▪ How many legs does John have?
▪ How many legs does Mary have
➢ Answer query by: Start from instance node, travel up the
hierarchy to the first outgoing relationship “Legs”, and take
value at the end.
Discussion:
▪ Simple, can deal with default values and deviations from default
values; gets complex in cases of complex inheritance and
subsumption hierarchies.
Data graphs
Also called assertional graphs
Structure data, represent facts (relationships between
instances)
Graphs – Example Flight Connections
Which other examples can you think of – what could
well be represented as a graph?
Graphs – Example “Ahnentafel Herzog
Ludwig”
Reasoning over graphs with graphspecific algorithms
to infer further knowledge about the instances, concepts,
and their relationships which are represented by the graph
Spreading activation
Relationship semantics:
▪ connection via social software between people
▪ For instance: is friends with
Given
▪ Graph
▪ Set of initial activated nodes, each with an activation
value. Max (typically)=1; min (typically)=0
▪ Activation threshold value, above this, a node fires
▪ Decay value D
▪ Termination criteria (differ, e.g., a fixed number of cycles,
no firing in a cycle)
When a node i fires at t1, for all connected nodes j, with
A(i,j) the weight of the edge between i and j:
ActivationValue(j, t2) =
ActivationValue(j,t1)+ActivationValue(i,t1)A(i,j)D
What questions can we answer with spreading
activation?
➢What are similar / close nodes?
➢Used in information retrieval (graphs contain
documents and metadata)
➢Modelling propagation: Where will sth. Spread out to?
(Information, virus)
Using graph measures for reasoning
Typical graph measures used to reason over
graphs as knowledge representation
(Shortest) Path: Interpretation: What is the relationship
between vertices v1 and v2?
Centrality: Interpretation: What are the most important
concepts or individuals represented in the graph?
▪ Most influential persons in a social network, key
infrastructure nodes in the Internet, super-spreaders
of disease, …