Graphs and Activation Spread Flashcards

1
Q

What is a Graph?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Graph representation as adjacency matrix

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Semantic Networks

A

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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Semantic Network – Example Tree of
Porphyry (300 CE)

A

Idea: Classify everthing
that exists in natural life

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Semantic Network – Example WordNet

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Semantic Networks as Knowledge
Representation

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Reasoning over graphs

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Reasoning over Semantic Networks with
Logic-Based Semantics

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Data graphs

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Graphs – Example Flight Connections

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Graphs – Example “Ahnentafel Herzog
Ludwig”

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Reasoning over graphs with graphspecific algorithms

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Spreading activation

A

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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Using graph measures for reasoning

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Path and shortest path

A

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?

17
Q

Centrality

A

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