Semantic Networks

Introduction

Semantic network: graph-based knowledge representation organizing knowledge as nodes (concepts) connected by labeled edges (relations). Intuitive: matches how humans organize knowledge. Early AI representation (1960s), foundational for modern knowledge graphs.

Core idea: concepts (entities, attributes, actions) represented as nodes. Relations between concepts represented as directed edges labeled with relation type. Network captures domain knowledge. Example: "Birds have wings" represented as Bird node connected to Wings node via "has" edge.

Advantages: intuitive structure, visual representation, natural inheritance mechanism, efficient associative retrieval. Challenges: ambiguity (unclear what nodes/edges mean), incomplete semantics (lacks formal definition), reasoning limitations (unclear inference rules).

"Semantic networks provide intuitive, visual way to organize knowledge as interconnected concepts. Bridging human conceptual organization and computational representation, enabled early AI knowledge systems." -- Cognitive science and AI representation

Historical Context and Psychology

Cognitive Origins

Semantic networks inspired by cognitive psychology. Quillian's work (1966): model human semantic memory as network. Concepts interconnected: meaning understood through connections. Spreading activation explains how people retrieve related concepts.

Memory Models

Semantic network mimics long-term memory structure. Nodes represent concepts stored in memory. Links represent associations learned. Retrieval: activate concept, spreading activation retrieves related concepts.

Cognitive Processing

Humans don't store all knowledge explicitly. Use associative networks: knowledge organized by meaningful connections. Analogical reasoning: similar concepts near each other. Conceptual domains separated: cars, animals, professions clustered.

Category Theory

Semantic networks embody prototype and exemplar models of categorization. Category (bird) prototype central. Members vary from prototype (robin typical, penguin atypical). Network captures typicality differences.

Spreading Activation Model

Understanding word: activate concept node. Activation spreads to related concepts. Related concepts become primed, easier to retrieve. Explains priming effects: hearing "doctor" primes "nurse" (associated).

Basic Structure: Nodes and Links

Network Components

Semantic network graph: nodes (vertices) represent concepts. Edges (links) represent relations. Labeled edges: label specifies relation type. Directed: direction indicates subject and object of relation.

Graph Representation

Example Semantic Network:
 has
 BIRD -----> WINGS
 | |
 | is-a | enable
 | |
 ROBIN FLYING
 |
 | is-a
 |
 TWEETY
 |
 | color
 |
 RED

Node Identity

Nodes identifiable by label. Same label same node (unless system distinguishes via IDs). Ambiguity: "bank" could refer to financial institution or river bank. Disambiguate via context or explicit typing.

Link Semantics

Link label specifies relation. is-a: subsumption (subset relation). has: possession or property. attribute-of: descriptive property. Located-in: spatial relation. causes, requires, etc.

Explicit vs. Implicit Knowledge

Explicit: facts directly encoded in network. (Bird, has, wings) explicitly states birds have wings. Implicit: inferred from explicit facts. Robin inherits "has wings" from Bird via is-a link.

Flexibility

Networks flexible: add nodes/links without schema constraints (contrast database). Accommodate diverse information. Risk: no structure enforced, can become disorganized.

Node Types and Concepts

Concept Nodes

Represent concepts: objects (bird, car), properties (red, tall), actions (flying, walking), abstract ideas (justice, love). Can be concrete (tangible) or abstract. Types organized hierarchically: superclasses, instances.

Instance Nodes

Individual instances: Tweety (specific bird), John (specific person). Connected to class via is-instance-of link. Inherit properties from class.

Value Nodes

Represent attribute values: specific colors (red, blue), quantities (5, 100), descriptions. Connected via attribute links. Example: (bird, color, red).

Event Nodes

Represent events, actions, processes. (flying, agent, bird) specifies flying agent. (eating, object, apple) specifies eaten object. Enable reasoning about actions.

Modifier Nodes

Represent modifiers: temporal (yesterday, during winter), modal (can, must), intensity (very, slightly). Modify other concepts. Example: (bird, can, fly, very).

Node Attributes

Nodes may have attributes beyond label: type (concept, instance, value), definition, supporting evidence, confidence score. Richer information about nodes.

Link Types and Relations

Taxonomic Relations

is-a: class membership. instance-of: individual belongs to class. subclass-of: class subset relation. Hierarchy fundamental. Enable inheritance.

Property Relations

has: property possession or part. attribute: descriptive attribute. Connects entities to their properties. Example: (dog, has, four-legs), (apple, color, red).

Semantic Relations

agent: actor in event. object: patient/recipient. destination: location/target. source: origin. instrument: tool. Capture semantic roles in events.

Example:
(Mary, agent, give)
(give, object, book)
(give, destination, John)
(give, source, library)

Thematic Roles

agent (actor), patient (affected), beneficiary (receiver), instrument (tool), location, time. Roles describe participant in event. Important for understanding language.

Comparative Relations

similar-to: likeness. contrasts-with: opposition. analogy-of: structural similarity. Enable similarity-based reasoning, analogical inference.

Associative Relations

Free associations: conceptually connected but no specific semantic role. part-of: part-whole relations. causes, requires, implies: logical relations.

Inheritance in Semantic Networks

Inheritance Mechanism

Properties inherited through is-a/instance-of links. Instance inherits class properties. Subclass inherits superclass properties. Example: Tweety (robin instance) inherits "has wings" from Robin, which inherits from Bird.

Inheritance Chains

Follow chains to infer properties. Tweety → Robin → Bird → Animal. Tweety inherits properties transitively through chain. Efficient: store property once, apply to all instances/subclasses.

Property Blocking

Override inherited property. Penguin subclass Bird, but overrides "can fly" to false. Instance-specific overrides propagate. Expressed as explicit negative link.

Multiple Inheritance

Node inherits from multiple parents. Amphibian inherits from Vertebrate and AquaticCreature. Combines properties from both. Can cause conflicts: both parents specify conflicting properties.

Inheritance Exceptions

Handle exceptions: "birds fly" but penguins don't. Store default (most informative). Create explicit exceptions. Reason with defaults: assume unless blocked.

Efficiency Gains

Inheritance avoids redundancy: thousands of bird individuals, but store "has wings" once at Bird. Updating: change one property, affects all instances/subclasses. Massively efficient.

Spreading Activation

Activation Concept

Activate node: set activation value (typically 0-1). Activation spreads to neighbors: connected nodes receive activation. Strength decays: neighbors of neighbors receive less. Models human associative memory.

Spreading Algorithm

1. Initialize: set query node activation = 1.0
2. For each iteration:
 - Each active node sends activation to neighbors
 - Activation amount = node_activation * decay_factor
 - Accumulate incoming activation
3. Repeat until convergence (activation stabilizes)
4. Return nodes with high activation (most relevant)

Activation Decay

Activation strength decreases with distance. Direct neighbors strong activation. Nodes far away weak activation. Decay models attenuation: not all associations equally relevant.

Priming Effects

Spreading activation explains priming: hearing "doctor" activates "doctor" node, spreads to "nurse", "hospital", etc. These activated nodes easier to process. Why seeing "doctor" followed by "nurse" faster than "doctor" followed by "bread".

Retrieval Applications

Search: activate query concepts, spreading activation retrieves related concepts. Association: activate word, find associated ideas. Inference: activate premises, spreading activation to conclusions.

Implementation Issues

Decay factor selection: too high, only direct neighbors matter. Too low, irrelevant nodes activate. Iteration number: when to stop? Activation models: sum, max, average of incoming activations?

Reasoning with Semantic Networks

Inheritance Reasoning

Forward chaining: instances inherit properties from classes. Backward chaining: given property, find classes that have it. Transitive closures: compute all reachable nodes via is-a links.

Path Finding

Find path between concepts: are concepts related? Shortest path: least intermediate steps. Path explains relationship. Example: find path from Penguin to Flying via is-a (blocked) vs. negative links.

Property Inference

Infer property by traversing network. Question: does robin have wings? Traverse: Robin is-a Bird, Bird has wings. Answer: yes (inherited).

Analogy Reasoning

Find analogies: similar structures in different domains. Analogous reasoning: if domain A property holds in domain B. Transfer knowledge across domains.

Similarity Computation

Similarity: shared properties, closeness in network. Connected concepts similar. Share attributes similar. Used for categorization, retrieval.

Limitations of Semantic Networks

Lacks formal semantics: unclear what network means. Reasoning often informal: ambiguous inference rules. Not complete: can't prove all valid inferences. Expressiveness limited for complex knowledge.

Limitations and Criticisms

Semantic Ambiguity

Links ambiguous: "has" could mean part-of, property-of, ownership. Nodes ambiguous: "bank" financial or river? No explicit semantics. Leads to misinterpretation.

Inability to Represent Context

No natural way represent knowledge relative to contexts. "Birds fly" true in context of typical flying birds, false for ostriches. Network doesn't specify context sensitivity.

Incomplete Inference Capabilities

Can't handle quantification: "all birds fly except ostriches". No way express "all" and "some" systematically. Contrast first-order logic.

Difficulty with Negation

Negation awkward: penguin doesn't fly. Store explicit negative link? Implicit: no positive link means false? Ambiguous interpretation.

Indexing and Search Issues

Large networks hard to search efficiently. Many paths possible: which to follow? No principled guidance. Contrasts logical reasoning with clear derivation rules.

Lack of Explicit Semantics

No formal interpretation: what does network mean? Can't verify correctness, completeness. Relies on human interpretation. Not machine-verifiable.

Brittleness

Small changes network behavior drastically. Add link: new inferences. Remove link: reasoning breaks. Hard to maintain, evolve networks.

Comparison with Other Representations

Semantic Networks vs. First-Order Logic

Semantic Networks vs. Frames

Frames more structured: bundle related attributes. Semantic networks flat: only nodes and links. Frames support defaults, procedures. Semantic networks simpler but less powerful.

Evolution to Modern Representations

Semantic networks foundation for modern knowledge graphs. Added formality: RDF triples. Added reasoning: description logic. Combined with other representations: rules, constraints. Evolution increases formality, power.

Modern Applications and Evolution

Knowledge Graphs

Modern knowledge graphs evolved from semantic networks. Large-scale graphs: billions of nodes. Added: formal semantics (RDF/OWL), reasoning mechanisms, scalability. Core idea (graph representation) persists.

Cognitive Models

Psychologists still use semantic networks model human memory. Neuroscience: brain networks exhibit small-world properties of semantic networks. Spreading activation models attention, priming.

Natural Language Processing

Word embeddings (word2vec, GloVe): implicit semantic networks. Words nearby in vector space connected. Conceptual networks guide NLP models. Semantic role labeling uses thematic roles from semantic networks.

Ontologies and Description Logics

Ontologies formalized semantic networks. Added formal logic, reasoning. Maintained intuitive structure. OWL, RDF represent semantic networks formally.

Social Networks

Social networks semantic networks: people as nodes, relationships as edges. Friendship, collaboration, influence represented. Analysis: community detection, influence propagation mirror spreading activation.

Neural Networks

Graph neural networks extend semantic networks with learning. Nodes have embeddings. Messages pass through edges. Learn representations from data. Bridging symbolic knowledge networks and neural learning.

Hybrid Systems

Combine semantic networks with logic, learning, procedures. Knowledge graphs + machine learning: embedding-based reasoning. Hybrid enables both symbolic reasoning and approximate inference.

References

• Quillian, M. R. "Semantic Memory." Carnegie Institute of Technology Ph.D. dissertation, 1966.
• Collins, A. M., and Quillian, M. R. "Retrieval Time from Semantic Memory." Journal of Verbal Learning and Verbal Behavior, vol. 8, 1969, pp. 240-247.
• Collins, A. M., and Loftus, E. F. "A Spreading-Activation Theory of Semantic Processing." Psychological Review, vol. 82, 1975, pp. 407-428.
• Brachman, R. J., and Levesque, H. J. "Knowledge Representation and Reasoning." Morgan Kaufmann, 2004.
• Sowa, J. F. "Knowledge Representation: Logical, Philosophical, and Computational Foundations." Brooks Cole Publishing Co., 2000.