  An important task for Homeland Security is the prediction of threat
vulnerabilities, such as through the detection of relationships between
seemingly disjoint entities. A structure used for this task is a "semantic
graph", also known as a "relational data graph" or an "attributed relational
graph". These graphs encode relationships as "typed" links between a pair of
"typed" nodes. Indeed, semantic graphs are very similar to semantic networks
used in AI. The node and link types are related through an ontology graph (also
known as a schema). Furthermore, each node has a set of attributes associated
with it (e.g., "age" may be an attribute of a node of type "person").
Unfortunately, the selection of types and attributes for both nodes and links
depends on human expertise and is somewhat subjective and even arbitrary. This
subjectiveness introduces biases into any algorithm that operates on semantic
graphs. Here, we raise some knowledge representation issues for semantic graphs
and provide some possible solutions using recently developed ideas in the field
of complex networks. In particular, we use the concept of transitivity to
evaluate the relevance of individual links in the semantic graph for detecting
relationships. We also propose new statistical measures for semantic graphs and
illustrate these semantic measures on graphs constructed from movies and
terrorism data.
