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