=Paper=
{{Paper
|id=Vol-1523/STIDS_2015_T07_Vanderlyn_etal
|storemode=property
|title=Similarity in Semantic Graphs: Combining Structural, Literal, and Ontology-based Measures
|pdfUrl=https://ceur-ws.org/Vol-1523/STIDS_2015_T07_Vanderlyn_etal.pdf
|volume=Vol-1523
|dblpUrl=https://dblp.org/rec/conf/stids/VanderlynAP15
}}
==Similarity in Semantic Graphs: Combining Structural, Literal, and Ontology-based Measures==
https://ceur-ws.org/Vol-1523/STIDS_2015_T07_Vanderlyn_etal.pdf
1
Similarity in Semantic Graphs: Combining
Structural, Literal, and Ontology-based
Measures
Lindsey Vanderlyn , Carl Andersen, Plamen Petrov
Raytheon BBN Technologies, Arlington, VA, USA
{lvanderl, canderse, ppetrov}@bbn.com
Abstract—Semantic graphs provide a valuable way to II. S EMANTIC G RAPHS
represent data while preserving real world meaning. As
these graphs become more popular for storing large
Resource Description Framework (RDF) graphs are
quantities of data, it is important to have methods of comprised of two types of elements: resources and
determining similarity between nodes in the graph. This literals. Resources are things which can be described,
paper extends previous structural similarity algorithms by such as objects and relationships. To remove ambiguity
taking advantage of meaning contained in a graph’s literals about which object a statement is being made, resources
and the graph’s ontology and allowing users to control
how much each type of similarity effects overall scores.
are given globally unique resource identifiers. Literals,
Preliminary tests indicate that including these sources of in comparison, are used to annotate resources with data
similarity increases scores in way that is better aligned with values such as strings and integers. There is no expecta-
human intuition. tion that literals will be unique, so with RDF statements
in the form of subject-predicate-object triples, literals are
Keywords: Semantic Graphs, Graph Similarity, Se-
never allowed to be the subject or the predicate.
mantic Similarity, Structural Similarity, Ontological Sim-
Another key feature of RDF graphs is the inclusion
ilarity, Literal Similarity, Intelligence Problem Decom-
of ontology data in the graph itself. Ontologies are
position, Random Walks
often compared to relational database schemas. Ontolo-
gies define classes, relationships, and their inheritances.
Through these definitions, all of the statements defined
I. I NTRODUCTION for a class are added to the graph (inferred) every time
a user creates a new instance of that class. For example,
One of the challenges faced with increasingly large when given an ontology, a reasoning engine will infer
data sets is analyzing the information. In particular, that instances of a class are also instances of all of the
finding similar pieces of data from within a larger data class’s ancestors.
set can prove difficult. This problem is especially present
when analyzing semantic graphs, which preserve the III. M OTIVATION FOR THIS WORK
meaning and context of data by representing objects in
This work is primarily motivated as part of an effort to
terms of their relationships. Raytheon BBN Technologies
develop a tool for creating intelligence problem decom-
(BBN) has been expanding previous research to fully
positions represented as semantic graphs. In this context,
utilize information encoded in a semantic graph.
finding similarity between nodes in a semantic graph
The present paper proposes SSDM+, an algorithm
could allow analysts to collaborate and reuse portions
which extends existing techniques for computing the
of existing problem decompositions when working on a
structural similarity between two graph nodes. Structural
new problem.
similarity techniques measure node pair similarity by ex-
amining the similarity of the pair’s respective subgraphs.
In the following sections, we will give a brief introduc- A. Semantic problem decomposition
tion to semantic graphs, detail the motivation behind this In order for analysts to determine what informa-
research, describe the prior work we build on, explain tion needs to be collected for a particular intelligence
the new algorithm we have developed, and demonstrate problem, they must first break the problem down in a
the application of our algorithm to the decomposition of logical and systematic way - a process we refer to as
a notional intelligence problem of “Illegal Fishing”. problem decomposition. To illustrate this, we will use
STIDS 2015 Proceedings Page 50
2
a fictitious intelligence problem of “Illegal Fishing in in their paper: Scaling Link-Based Similarity Search [5],
Hawaii” shown on Fig. 1. The first step is to determine and the Semantic Similarity Distance Metric (SSDM)
the states in which entities related to the problem (e.g., [7]. These algorithms share the following desirable qual-
fishing boats) can exist. For example, a fishing boat ities:
might be either “in port” or “in a legal fishing zone”. • They are domain-independent, meaning that they
Next, the analyst must specify how to tell if an entity can be applied to any data representing relationships
is in a particular state by creating indicators. Indicators between entities.
must be boolean statements such as “boat moving” or • They can be computed efficiently over very large
“outriggers deployed”. The analyst then specifies the datasets, in contrast to algorithms which scale very
observable phenomena, or stimuli, that needs to be poorly, such as ones which rely on Singular Value
collected in order to determine if an indicator is present. Decomposition [4].
Next the analyst defines sensor system specific collection • They have the ability not only to determine the
parameters, called observation needs such as resolution, similarity of any two given nodes, but also to
location, and time to collect the stimuli. Finally, an an- generate a list of entities which are most similar
alyst can specify algorithms which combine input from to one specified by a user.
one or more observation needs to determine whether an • The computations are easily understood, meaning
indicator is present. that similarity scores generated can be explained
Semantic graphs are a good way to represent problem based on the actual computation performed - some-
decompositions because they provide an intuitive way for thing which can be difficult with more abstract
analysts to capture the relationships from a mental model calculations.
of the problem into a format, which is both machine- • The algorithms look beyond a node’s immediate
readable and human-understandable. In addition, storing neighbor to create a broader knowledge of the
the decomposition as a graph preserves the semantics entity’s structural context.
of the relationships between decomposition components. We provide a more in depth explanation of each of
Finally, these graphs can also be reasoned over to the previous algorithms below followed by an overview
determine completeness, decomposition alternatives, or of the changes we have made with SSDM+.
efficiency of collection.
A. SimRank
The key insight of SimRank is that two nodes are
similar if they are connected to similar nodes [2]. This
simple idea can be translated mathematically as: the
similarity score between two entities is the average
pairwise similarity of their neighbors, scaled by a decay
factor.
A concrete example of this can be seen with movie
data. Consider the example in Fig. 2.
Fig. 1: Example of a simple semantic problem decomposition
graph for the intelligence problem “Illegal Fishing in Hawaii”.
Nodes in column 1 represent intelligence problems (not shown),
column 2 - States, column 3 - Indicators, column 4 - Algo-
rithms, column 5 - Stimuli, and nodes in column 6 represent Fig. 2: Example of a semantic graph [7] with information on
Observation Needs. Edges represent logical relationships such movies. Director 1 and Director 2 are similar because they
as “Supports” or “State Transition”. directed similar movies, although the directors themselves are
not connected
IV. P REVIOUS A LGORITHMS Movie 1 and Movie 2 appear to be similar to each
Our work on SSDM+ derives from three earlier works. other because they are in the same genre and they both
These are SimRank [2], the work of Fogaras and Racz have two of the same actors. Furthermore, although
STIDS 2015 Proceedings Page 51
3
Director 1 and Director 2 do not share any nodes, they set of shared possible next steps for the two nodes only
can also be considered similar because they directed contains one edge with the lowest index. Therefore, if
similar movies. SimRank provides a formalization of this each of the walkers chooses the edge with the lowest
type of idea. index from this set, they will choose the same edge and
Each pair’s similarity is dependent on many other meet.
pairs because of the recursive definition of SimRank. On The output of one run of Fogaras and Racz’s scalable
small datasets, the system can be solved with an iterative SimRank algorithm is a collection of fingerprint graphs
algorithm. On large datasets, it can be solved using an which store the convergence data for each of the random
efficient approximate method outlined by Fogaras and walkers. Each graph stores the node a walker began
Racz in [5]. The SSDM calculation and our extensions on, the node it merged into, and how many steps it
are based on this efficient approximate method. took for that convergence to occur. These fingerprint
graphs are precomputed and are collected to be stored
B. Fogaras and Racz’s extensions in database which can be queried at runtime. Separating
The algorithm outlined by Fogaras and Racz relies the fingerprint graph generation and querying allows real
on the mathematical notion of a random walk through time similarity queries to be quite rapid.
a graph, in which an abstract walker steps from node
to node through the graph by following random edges C. SSDM
[5]. In the original SimRank paper, Jeh and Widom SSDM [7], also developed by BBN, was closely
[2] observed that the SimRank score of two nodes related to SimRank with two principal differences. The
can be approximated from the expected meeting time first difference is that SSDM seeks to be independent
of two random walkers starting at those two nodes; a of ontological choice, meaning that the directionality of
longer expected meeting time corresponds with a lower each edge (predicate) is ignored.
SimRank score. Fogaras and Racz used this observation The second involves the semantics of RDF graphs.
to develop an efficient and scalable algorithm for calcu- Whereas SimRank is a measure over unlabeled directed
lating similarity scores. In their algorithm, one walker graphs, SSDM incorporates the semantic labels given to
is initialized per node and at every time step, each edges. This makes it well-suited to semantic graph data,
walker steps across one edge. To reduce the number of which is organized in subject-predicate-object triples.
computations required, walkers converge (are treated as a Subjects and objects are equivalent to nodes in the graph
single walker) when they meet at the same node. Fogaras and predicates are equivalent to edges. In RDF graphs,
and Racz found that this type of convergence does not these predicates, or labeled edges, describe how the
reduce the correctness of the approximate calculation. nodes they connect are related to each other. In order to
utilize the meaning contained in these edge labels, the
SSDM algorithm only considers two walkers to have met
if they arrived at the same node having traveled through
an identical list of edges to get there. This adds a stricter
definition of similarity; it is no longer good enough that
two nodes were connected to the same third one, they
now had to be connected in the same (semantic) way.
V. SSDM+: I NCORPORATING LITERAL AND
Fig. 3: Diagram of walker convergence [7]. Walkers a, b, c, ONTOLOGY- BASED SIMILARITY
and d begin as independent. As the progress through the graph
(left to right) they meet each other and converge. Our new algorithm builds off of previous work with
SSDM by allowing literals to influence similarity scores,
Additionally, Fogaras and Racz’s algorithm incen- relaxing the need for walkers to meet at the exact same
tivises walkers to converge if they are near each other. resource in order to converge, and creating a stricter
Convergence is encouraged as a result of how a walker approach to how the ontology influences similarity.
chooses its next step. In this model, all of the edges in the This is motivated by the desire to create a cohesive
graph are randomly assigned an index and walkers will model for including literal and ontological similarity in a
always choose the edge with the lowest index to step to. larger structural similarity framework. Additionally, we
This shuffling of indexes is universal. This means that if removed the weighting of similarity scores based on
walkers share multiple of the same possible next steps, the time it takes walkers to meet (decay), because the
and the walkers select a shared node as the next step, identical paths restriction already significantly decreases
they must choose the same shared node. Restated: the the probability of any walkers meeting after very few
STIDS 2015 Proceedings Page 52
4
steps and we found that further decay was not neces- long strings or vastly different types of data, alternative
sary. Otherwise we retained the same functionality and to Levenshtein distance (e.g., [6]) can be utilized.
methods as the original SSDM algorithm.
In SSDM, similarity was calculated only taking into B. Ontological Similarity
account the resources in the graph; literals in the graph
were completely ignored. Additionally because of the In an analogous way, we added ontology-based sim-
strict definition of convergence, nodes which humans ilarity by allowing walkers to converge if they stepped
might consider to be very nearly the same (such as onto resources which we considered to be ontologically
multiple instances of the same class) could not contribute similar. In this case, we define “ontologically similar”
directly to the similarity scores. This approach does as: sharing a most-distant-salient ancestor, with salience
not fully utilize the ontological information stored in a defined as:
semantic graph. String literals often serve as meaningful Salience = 1 (instances/total) (1)
labels for nearby nodes; numerical literals store quan-
tities that tend to be of similar magnitude for nearby where instances is the number of instances of a class and
nodes. Therefore ignoring literals causes some nodes to total represents the total number of nodes in the graph.
appear much more similar than a human might consider This number represents how unique each class is, or how
them and the requirement for walkers to walk the exact much of the graph is not made up of instances of that
same predicate path, prevented inferred inheritance from class.
sufficiently representing the ontological similarity of two
nodes. In particular, because of the number of inferred
classes a resource might have, it was highly probably
that two nodes, which shared an ancestor, might walk a
path to that ancestor, but each take a different number
of steps to get there. Additionally, many of the inferred
classes are very high level concepts (e.g. owl:Thing) and
the number of instances of these classes is high enough
in a graph that even if two walkers did converge at one
of these parent classes, a human would not consider that
convergence to have added any similarity. Fig. 4: Example of finding the most-distantly-salient ancestor.
With SSDM+, we combine both the literal and onto- The node “In Illegal Fishing zone” is an instance of a State
logical similarity into a larger structural approach. There (fairly unique). State is also a subclass of owl:Thing, but
because that is too common to be considered salient, “In Illegal
may be other existing works which make use of literal Fishing zone’s” most-distant-salient node is State.
and ontological similarity, but we are unaware of any
others which do so as part of a cohesive structural
To find the most-distant-salient ancestor, we precom-
similarity measurement.
puted the salience of each class and traced its ancestry
until we could find the most distantly related ancestor
A. Literal Similarity which remained more salient than a user defined cutoff
(see example in Fig. 4). Defining similarity this way
In order to incorporate literal similarity, we had to means that all instances of a class that is considered to
loosen the definitions of convergence present in the be salient (or instances of that class’s children) will have
original paper [7]. Rather than only converging when the same most distantly related ancestor, thus reducing
two walkers had reached the same resource (referred to the number of comparisons needed to find similar nodes.
here as ”physcal” convergence), walkers could converge Additionally, when we implemented the ontology-based
if they reached two literals that were sufficiently similar. matching, we removed nodes representing inferred types
In this case, we defined similarity for numeric literals from the graph, which allows the user to fully control the
as the ratio of the smaller over the larger - or percent. effect of ontology-based matches on the final similarity
The similarity for all other literals - which for simplicity score and removes the possibility for nodes to match
were converted to strings - was calculated as a Leven- based on a shared, unsalient class.
shtein distance between the two, normalized for their
sizes. Levenshtein distance is a measure of structural
similarity between two strings by measuring the number C. Five Types of Convergence
of substitutions, insertions, and deletions required to turn To make this tool as flexible as possible, we compute
one string into the other. These metrics work well with an overall similarity score composed of five different
the data sets we tested, but for graphs which contain similarity scoring methods. The user assigns weights
STIDS 2015 Proceedings Page 53
5
for each type, allowing them to emphasize the method D. Integration of new types of convergence
they believe will deliver the most accurate results in the As with the original SSDM, finding similarity is
current context. broken into two stages: a preprocessing stage where
fingerprint graphs (trees) are generated from the conver-
gences that occur during random walkers and a runtime
stage where these trees are queried. The changes we have
made affect the former. SSDM+, our new algorithm,
maintains the random walk paradigm of the original
SSDM algorithm and continues to use convergences to
generate trees. The primary difference is the way walkers
can converge. By extension, trees now also contain an
additional piece of information: the type of conver-
gence which has occurred. Tracking the convergence
type allows a user to control how much each type of
convergence affects the similarity scores they receive.
By preserving the random walks paradigm, we gain
a consistent framework for assessing all five types of
similarity. From a more practical view, however, the
requirement that walkers must travel the same predicate
path greatly reduces the number of comparisons which
must be completed to find literal and ontological simi-
Fig. 5: Visualization of different convergence types. Arrows
represent edges in the graph connecting nodes. Light (blue) larity.
dotted lines indicate literal similarity of unconnected nodes. In addition, the order which we check convergences
Dark (purple) dotted lines indicate ontological similarity of was also influenced by the need to reduce the number
two unconnected nodes. of comparisons, a need which becomes increasingly
important as datasets grow. We first check the ”physical”
convergences because they are the most common type of
Walkers are considered to have converged when:
convergence. We then check for literal convergences and
1) Physical convergence: two or more walkers meet then for ontological convergences. This order matters
at the same resource less because we separate the literals and resources so the
2) Ontology-based convergence: two or more walkers two types of convergence are independent of one another.
step onto nodes whose classes share a most-distant- In order to reduce the number of comparisons we must
salient ancestor perform, we changed the way “physical” convergence is
3) Literal based convergence: two or more walkers calculated. In the new method, we sort all walkers by the
step onto literals that are more similar than a user defined path they have traveled, then split within those groups,
cutoff by the current location of the walker. With the nodes
that did not converge, but did walk the same path, we
4) First ontology-based convergence: the nodes they
split the walkers based on whether they are located at a
start on are considered to be ontologically the same -
resource or a literal and look to see if they can converge
because the graph sizes can become quite large, this is
via ontological similarity or literal similarity. This is
only evaluated after the first step
a more efficient method (as compared to the original
5) First literal based convergence: walkers step onto SSDM), when literal and ontological similarity must
similar literals after the first step - this is considered also be determined. The main drawback to this order
significant because it is the only step where the literals of comparisons is that literal and ontological similarity
are guaranteed to be connected to the node a walker are not calculated until after the first step has been taken.
started on This greatly increases the speed of the calculation, but
The last two types of convergence are separate from does ignore ontological and literal similarity between
the others because they are the only two types of two original nodes if their walkers did not take the same
convergence that happen based on the original nodes a first step. Given the high number of random walks we
walker started on. If a user were to query the similarity perform for each graph, we consider this acceptable.
between two nodes, while they are important to finding
the overall structural similarity, those two are the only VI. T ESTING AND T UNING
types of similarity that are uniquely about the queried In the course of the development of the SSDM+
nodes. algorithm, we executed multiple test cases comparing
STIDS 2015 Proceedings Page 54
6
the results of the algorithm against human intuition on tests, we used a smaller dataset - four graphs, rather
which nodes should be considered to be similar. Based than ten - and aimed to find parameters which returned
on these empirical results, we developed a procedure for results that we, as humans, understood to be similar. In
tuning the similarity paramters, as outlined below. order to get more universal results, we made sure to test
several different types of nodes and observe the results.
A. Determining literal and ontological cutoff similarities This proved to be interesting as some of the nodes were
more influenced by literals - in both positive and negative
To determine some baseline values for similarity manners - than others. From these tests we were able
thresholds, we experimented with both the literal and to find the weights which had the greatest improvement
ontological cutoffs. Cutoffs represented the minimum over the results generated from only considering physical
similarity needed for a user to consider two literals convergence.
or two resources to be the same for the purposes of Results of this type of tuning may be dependent to the
allowing convergence. We recorded the time it took to datasets we used. We believe that, in order to use this
generate trees and the similarity scores between three for other datasets, it would be important to run a similar
sets of nodes. These experiments allowed us to optimize test to choose appropriate weights.
the shortest time needed to generate the trees for the
highest increase in similarity from the added literal and
ontological matching. For all of the tests, the weighting VII. A PPLICATION : I LLEGAL F ISHING P ROBLEM
on each type of convergence was kept equal so that only D ECOMPOSITION
the cutoffs were being varied. From our experiments, A tool for finding similarity between nodes in a
we found that literals needed to be at least 60% similar semantic graph can be useful in a variety of settings.
and classes could be considered salient if less than In this case, however, we are primarily interested in
60% of the instance data was an instance of that class. how it can aid in rapid development of intelligence
With higher cutoffs, the time needed to generate the problem decompositions via the retrieval and reuse of
trees began to increase dramatically. With lower cutoffs, existing decomposition structures. While representing
similarity scores did not match very well with human problem decompositions in a semantic way has many
predications. It should be noted that these baseline benefits, it can also be a time consuming process to
values were generated using mock intelligence problem manually input all of the relevant nodes. We envision
decompositions and may need to be adjusted for other using SSDM+ to suggest nodes from existing problem
types of datasets. decompositions which are similar to a node selected by
a user. In this way, the user would be able to look at the
graphs associated with each suggestion and, if desired,
B. Determining weights for physical, literal, and onto-
copy the suggested node and its children into the new
logical convergences
decomposition.
In order to see the effect of allowing literal and onto- This interaction reduces the amount of time it takes
logical matching, we created a series of decompositions. an analyst to perform their job, but also gives them
We then tested them to see how changing the weighting more context for generating a new decomposition. In
of each type of similarity affected which nodes were addition to saving the analyst time, a tool like this also
returned as similar when queried and how similar the provides analysts the opportunity to see how their peers
algorithm considered them. As a first test, we constructed solved similar problems. This type of knowledge sharing
ten identical graphs whose only difference was in the could allow analysts to envision new ways of completing
literal labels associated with each node. The goal of this their decomposition tasks. This latter feature has the
test was to show that when a node was selected, the most potential to be especially significant, given the limited
similar resources would be the corresponding nodes in sensor resources for collecting stimuli.
the other graphs. In this section we use the mock decomposition prob-
Once we verified that this was true, we started to test lem of illegal fishing which we described earlier in the
on graphs which were generated from the same tem- paper and demonstrate some of the preliminary results
plate, but were not identical. Templates in the Semantic we have been generating.
Problem Decomposition (SPD) tool are fragments of a
decomposition that can be reused. When they are copied
into a new graph, they retain all of their properties, A. Results
except that all of the nodes in the graph are given The results shown in this section were determined
new randomly generate Universal Resource Identifiers by comparative analysis of similarity suggestions. We
(URIs), which are globally unique. These graphs were created four decompositions from the same starting
the primary data we used to test the weighting. In these template and modified them by adding and deleting
STIDS 2015 Proceedings Page 55
7
Top Three Suggestions of Most Similar Nodes and Their Top Three Suggestions of Most Similar Nodes and Their
Similarity Scores for the Node: “In Illegal Fishing Zone 4” Similarity Scores for the Node: “Outriggers not deployed 4”
Types of
First Second Third First Second Third
suggestion suggestion suggestion Types of
convergence suggestion suggestion suggestion
(score) (score) (score) convergence
(score) (score) (score)
In Illegal In Illegal In Comms2 SAR SAR4
Physical (SSDM) Fishing Zone Fishing Zone2 transit3 Physical (SSDM)
(0.40) (0.38) (0.37)
(0.57) (0.46) (0.33)
Physical and Comms2 SAR SAR4
In Illegal In Illegal In
Physical and Literal (0.40) (0.38) (0.37)
Fishing Zone Fishing Zone2 transit3
Literal Outriggers Outriggers Transponder
(0.57) (0.46) (0.33) Physical and
In Illegal In Illegal In Illegal not deployed deployed2 On3
Physical and Ontological
Fishing Zone Fishing Zone2 Fishing Zone3 (0.69) (0.51) (0.42)
Ontological Physical, Outriggers not Outriggers Boat
(0.85) (0.75) (0.73)
Physical, In Illegal In Illegal In Illegal Literal, and deployed deployed2 Moving2
Literal, and Fishing Zone Fishing Zone2 Fishing Zone3 Ontological (0.70) (0.51) (0.42)
Ontological (0.85) (0.75) (0.73)
TABLE II: Top three results from similar decompositions
TABLE I: Top three results from similar decompositions when when querying for most similar nodes to the “Outriggers not
querying for most similar nodes to the “In Illegal Fishing deployed” node. The far left column describes the types of
Zone” node. The far left column describes the types of con- convergence which contributed to the scores and the remaining
vergence which contributed to the scores and the remaining columns represent the labels of the highest scoring nodes and
columns represent the labels of the highest scoring nodes and their similarity scores. SSDM+’s use of Literal and Ontolog-
their similarity scores. All of the suggestions are the same class ical convergence performs in a more human understandable
(States), but SSDM+’s inclusion of Literal and Ontological way here: suggesting nodes which are all of the same class
convergence produces scores which align better with human (Indicator) as the node for which the query was generated, in
understanding, and does find the “In Illegal Fishing Zone” contrast to the original SSDM algorithm which suggests only
node from each graph to be the top three most similar. Stimuli nodes.
nodes and connections. This gave us four similar, but not in Table I, the top suggestions are all for the correspond-
identical decompositions. We then generated suggestions ing nodes from other similar decomposition models.
for several nodes varying which types of convergences These top-suggestion nodes have nearly the same labels
contributed to the similarity scores. A sample of the as the queried node and, in this test, have identical
results can be seen in Table I and Table II where we connections. The similarity scores increase dramatically
show the top three suggested nodes and their similarity with ontological similarity turned on, demonstrating
scores for two of our test nodes. For simplicity, if a type the value-added of ontological matching; however, even
of convergence was included the weight was set to 1 and when considering non-ontological matching the the top
if it was not included, the weight was set to 0. three suggestions of SSDM+ are still as good or better
In the first example, both algorithms perform similarly. than that of SSDM.
The main difference is the magnitude of the scores. It While more extensive testing would provide a more
should be noted, however, that while both algorithms definitive picture, our preliminary results indicate that
produced results which were all of the same class (State) supplementing physical convergence with literal and
as the node from which the query was generated, the ontological convergence does increase the accuracy of
modified algorithm - when ontological similarity was similarity calculations and the relevance of the results
included - was able to provide a “In Illegal Fishing generated. Additionally, we believe that the incentivized
Zone” node for each of the top three results. The second Physical convergence described in Section V may un-
example, though shows a more extreme distance. The equally weight the Physical component of the score. We
results of the modified algorithm, are from the same plan to investigate and address this issue in future work.
class (Indicators) as the node from which the query was
generated, while the results from the original algorithm VIII. F UTURE W ORK
are Stimuli - a class which connects to Indicators. There are several possible directions for future work.
From our experimentation, we found that are two main The first, and most pressing, is a more rigorous compar-
improvements offered by SSDM+. The first improvement ison between SSDM+ and the original SSDM algorithm.
is that the top suggestions are more frequently closer A major difficulty in performing such a comparison is
matches for the node which has been queried. The the lack of concrete ground truth similarity values to
second improvement stems from the addition of terms for compare our algorithm results to. To that end, there is
new types of similarity which were previously ignored, a need to develop a repeatable system for quantifying
resulting in higher scores that align more closely with which nodes humans consider to be similar. However,
how a human might perceive the similarity. For example due to the subjective nature of such measurements,
STIDS 2015 Proceedings Page 56
8
constructing ground truth data based on user judgments IX. C ONCLUSION
presents many challenges. An alternative approach could Due to the wide spectrum of application of semantic
be to compare the similarity results from our SSDM+ graphs, finding similarity within and between them also
algorithm to similarity derived from entity attribute com- has significant utility. In this paper, we focused on
parison - comparisons of the presence/absence of certain extending previous structural semantic similarity algo-
attributes. If we choose to pursue this path, there are rithms with functionality aimed at aiding analysts in
several well-established algorithms [8] that we could the development of new intelligence problem decom-
use. However, since the data we have been using so positions. The resulting extended SSDM (or SSDM+)
far consists of only a handful of main classes, such algorithm will be incorporated in a tool that finds frag-
comparisons may not be as useful. ments of existing graphs, which could be relevant to the
The second area for improvement is in tree generation. problem being decomposed. This not only saves analyst
One of the goals prompting this research was to develop time by allowing them to reuse relevant pieces from
a way for intelligence analysts to reuse portions of existing decompositions, but also allows the exploration
existing decompositions when developing new mission of options for completing the decompositions in ways
packages. To aid in that process, we hoped that analysts that might not have been previously considered. The
could click on a node they had added to their graph modifications we made to the SSDM algorithm allow
and query for all similar nodes among all of the mission it to take better advantage of the data stored in semantic
packages that had already been developed. This is not graphs rather than merely using structural (physical) con-
yet possible because of the latency involved in the tree vergences. By providing users control (via weights) over
(re-)generation stage. In order to re-run the entire graph the various types of convergences - physical, literal, and
analysis, it takes more than a minute on small graphs ontological - SSDM+ becomes easily customizable to
with size of approximately three hundred nodes. Such varying datasets. The extended algorithm also produces
a long delay is unlikely to be tolerated by an analyst results that better match human intuitions on similarity.
in interactive mode. We are currently investigating ways In the future, we plan to develop a more rigorous test to
to reduce latency, including further optimization of the quantify these improvements and to speed up the off-line
algorithm and applying the algorithm incrementally as (tree) generation of similarity traces.
nodes are added to a graph.
We also plan to explore more accurate techniques of R EFERENCES
determining literal similarity. In particular, at present, we [1] T. Berners-Lee, M. Handler, & O. Lassila, “The seman-
tic web”, Scientific American, May 2008. [Online]. Avaiable:
analyze only the structure of textual literals rather than http://www.ds3web.it/miscellanea/the semantic web.pdf
looking at the meaning of that text. Finally, although [2] G. Jeh & J. Widom, “SimRank: a measure of structural-context
we have relaxed the strictness in matching nodes, we similarity”, in Proceedings of the eigth ACM SIGKDD interna-
tional conference on Knowledge discovery and data mining, ser.
still require that walkers walk an identical predicate KDD ‘02 New York, Ny: ACM, 2002, pp. 538-543. [Online].
path. It may be, that in a similar way to the additional Available: http://doi.acm.org/10.1145/77504/775126
insight gained by allowing ontological matching, we [3] A. Islam & D. Inkpen, “Semantic text similarity using corpus-
based word similarity and string similarity”, ACM Transactions on
could also gain a better measure of similarity by relaxing Knowledge Discovery from Data, vol. 2 no. 2 pp. 1-25, July 2008.
the predicate restrictions so that walkers would also be [Online]. Available: http://doi.acm.org/10.1145/1376815.1376819
allowed to travel similar rather than identical predicate [4] R. Hartley & A. Zisserman, Multiple view Geometry in Computer
Vision. Cambridge University Press, 2003. [Online]. Available:
paths. The challenge with this would be to find a http://books.google.com/books?id=si3R3Pfa98QC
computationally efficient way of relaxing the restrictions [5] D. Fogaras & B. Racz, “Scaling link-based similarity search”, in
because performing something similar to our ontological Proceedings of the 14th international conference on World Wide
Web, ser. WWW ‘05. New York, NY: ACM, 2005, pp. 641-650.
check for convergence would be too time intensive for [Online]. Available: http://doi.acm.org/10.1145/1060745.1060839
a dataset of any reasonable size. [6] W. H. Gomaa, “A Survey of Text Similarity Approaches”, INter-
national Journal of Computer Applications, vol 68, no. 13, 2013.
Additionally, the role of literals is currently under- doi:10.1.1.403.5446
mined by the fact that we encourage convergence in [7] C. Olsson, P. Petrov, J. Sherman, A. Perez-Lopez. “Finding and
the same way as the original SSDM algorithm which Explaining Similarities in Linked Data”, Semantic Technology
for Intelligence, Defense, and Security (STIDS 2011), Fairfax,
biases physical convergences to occur. In doing this, Virginia, November 2011.
literal matches occur much less frequently and thus have [8] B. Gallagher “Matching Structure and Semantics: A Survey
less of an effect on the total results. Due to the low on Graph-Based Pattern Matching”, American Association
for Artificial Intelligence, 2006, [Online]. Available:
repeatability, however, we found it was not feasible to http://www.aaai.org/Papers/Symposia/Fall/2006/FS-06-02/FS06-
stop encouraging convergence. To fully utilize similarity 02-007.pdf
from literals in the graph, an alternative to the way
convergence is encouraged would need to be developed.
STIDS 2015 Proceedings Page 57