I currently have a representation of an object as a graph, and I have some similarity measure on that graph. I currently determine the class of a query object by trying to match its graph representation against every instance in the training set, and I assign the query's class as the class of the best graph matching.
Some classes have many similar features that would be good matching nodes, but certain nodes distinguish them from specific classes. For example, nodes 1 and 3 might match well in both classes class A and class B, but a match of node 2 distinguishes the object as belonging to class A. In that case, I would want node 2 to have a higher weight, as it is more important to discriminating between the two classes. At the same time, nodes 1 and 2 might match well for classes A and C, but a matching of node 3 distinguishes the object as class A, so node 3 would be more important and should be weighted as such.
This kind of discrimination between classes seems difficult to achieve. What is the best machine learning approach to perform this kind of weighted discrimination?
edit Adding details. Although two nodes in a graph may match, they are almost never identical. Imagine the graph being different parts of an image, and you have some similarity measure to define how similar two image parts are. Since two images are almost never identical, they will pretty well never be exact matches.
