Learning Graph Matching Substitution Weights based on a Linear Regression

Attributed graphs are structures that are useful to represent objects through the information of their local parts and their relations. Each characteristic in the local parts is represented by different attributes on the nodes. In this context, the comparison between structured objects is performed through a distance between attributed graphs. If we want to correctly tune the distance and the node correspondence between graphs, we have to add some weights on the node attributes to gauge the importance of each local characteristic. In this paper, we present a method to learn the weights on each node attribute. It is based on building an embedded space and imposing the weights we want to learn to be the constants of the hyperplane deduced by a linear regression applied on a cloud of points. These points represent the node-to-node mappings.