Graphs and Activation Spread

Question 1

What is a Graph?

Answer 1

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).

Question 2

Graph representation as adjacency matrix

Answer 2

Adjacency matrix A
▪ i = row-index
▪ j = column-index
▪ A(i,j) = number of
edges e(i,j)
▪ Uniquely represents
the graph

Question 3

Semantic Networks

Answer 3

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)

Question 4

Semantic Network – Example Tree of
Porphyry (300 CE)

Answer 4

Idea: Classify everthing
that exists in natural life

Question 5

Semantic Network – Example WordNet

Answer 5

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

Question 6

Semantic Network – Example, logic representation (based
on Russell & Norvig – AI, 3rd Edition, Ch. 12.5.1)

Answer 6

𝐹𝑒𝑚𝑎𝑙𝑒𝑃𝑒𝑟𝑠𝑜𝑛𝑠 𝑥 → 𝑃𝑒𝑟𝑠𝑜𝑛𝑠 𝑥
▪ 𝑀𝑎𝑙𝑒𝑃𝑒𝑟𝑠𝑜𝑛𝑠 𝑥 → 𝑃𝑒𝑟𝑠𝑜𝑛𝑠 𝑥
▪ 𝑃𝑒𝑟𝑠𝑜𝑛𝑠 𝑥 → 𝑀𝑎𝑚𝑚𝑎𝑙𝑠 𝑥
▪ 𝑃𝑒𝑟𝑠𝑜𝑛𝑠 𝑥 → ∃𝑦: ℎ𝑎𝑠𝑀𝑜𝑡ℎ𝑒𝑟(𝑥, 𝑦) ∧
𝐹𝑒𝑚𝑎𝑙𝑒𝑃𝑒𝑟𝑠𝑜𝑛𝑠(𝑦)
▪ 𝑃𝑒𝑟𝑠𝑜𝑛𝑠 𝑥 → 𝐿𝑒𝑔𝑠(𝑥, 2)
▪ FemalePersons(Mary)
▪ MalePersons(John)
▪ sisterOf(Mary,John)
▪ Legs(John,1)

Question 7

Semantic Networks as Knowledge
Representation

Answer 7

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.

Question 8

Reasoning over graphs

Answer 8

to infer further knowledge about the instances, concepts,
and their relationships which are represented by the graph

Question 9

Reasoning over Semantic Networks with
Logic-Based Semantics

Answer 9

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.

Question 10

Data graphs

Answer 10

Also called assertional graphs
Structure data, represent facts (relationships between
instances)

Question 11

Graphs – Example Flight Connections

Answer 11

Which other examples can you think of – what could
well be represented as a graph?

Question 12

Graphs – Example “Ahnentafel Herzog
Ludwig”

Question 13

Reasoning over graphs with graphspecific algorithms

Answer 13

to infer further knowledge about the instances, concepts,
and their relationships which are represented by the graph

Question 14

Spreading activation

Answer 14

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)

Question 15

Using graph measures for reasoning

Answer 15

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, …

Question 16

Path and shortest path

Answer 16

Path and shortest path
Path between v1 and vn
: Sequence of vertices (v1
, v2 ,
… vn
), all vi are different, such that edges (vi , vi +1)
exist in the graph.
Shortest path – minimises the weights of constituent
edges
▪ What edge weight is needed for shortest path to
correspond to the path with the fewest edges?

Question 17

Centrality

Answer 17

There isn‘t the one and only centrality measure.
Centrality measures are often application specific.
Examples
▪ Degree centrality = how many incoming connections in one
node
CD(v)=deg(v) – the centrality of vertex v is its degree
▪ Closeness centrality = the closer a node is to all other nodes,
the more central
𝐶𝐶 𝑥 =
𝑁
σ𝑦 𝑑(𝑦,𝑥)
… where d(y,x) is the length of the shortest
path between x and d; and N is the number of nodes in the graph