A common subgraph approach to knowledge network comparison

In my PhD - thesis, I develop a computer-based psychometric test: the Association Structure Test (AST). For every subject, the AST elicits a graph representing the subjects' knowledge structure for a specified knowledge domain. The AST is based on concepts by Schvaneveldt, Jonasstn, Yacci and Beissner, Eckert and Bonato. The aim of the AST is to predict individual performance in intellectual tasks with graph-theoretic concepts derived from the subjects' knowledge graphs. A typical knowledge AST-elicited graph looks something like this.

(This participant was a cleaner that completed the AST with the stimulus “carpet cleaning”)

The problem is that the graph-theoretic measures I employ (density, size, degree, relative maximum path length and clusters) do not correlate with outside criteria under all circumstances - sometimes they do, sometimes they don't. I am thus looking for a better measure and the idea is to develop a kind of smilarity measure for comparing subject's knowledge graphs to an expert's reference graph for performance prediction. This has been done before in Pathfinder-based approaches, but in these studies, all networks had the same number and type of nodes because nodes represent knowledge concepts that had been selected by experts prior to knowledge elicitation and the subjects only had to do pairwise comparisons between expert-selected concepts. AST-elicited networks employ subjects' free term associations as nodes and thus all graphs differ in size, degree and node label. The idea is to apply similarity algorithms that determine structural similarity between two graphs regardless of node types as employed in chemistry for proteine comparison, e.g. a common subgraph approach as suggested by Le, Ho and Phan. The idea came up in a discussion with Gunnar yesterday (thanks to Hans for introducing us) and Gunnar was so kind to offer to do the calculations for which I am very very greateful.