An Application to Implement Sum-Product Operations Through Message Passing

Sum-Product operations are being used to compute marginals of a (complicated) global function which factors into a set of local factor functions. Instead of computing marginals directly from the global function, sum-product operations applied on local functions enable to split the original problem into smaller ones, as well as computing marginals in an efficient and parallel way. With factor functions operating on subsets of the global function’s variable set, the relation between variables and factor functions can be represented by a factor graph, with each edge connecting a variable node to a factor function node it is part of. These factor graphs are the underlying structure of the message passing approach which basically consists of sending messages, i.e. values computed by the vertices of the factor graph along the edges of the latter. Once a variable vertex has received messages from all of its neighbours, it can compute the result marginal value from these values. In this project, message passing will be used to compute probabilities of correctness for links in the context of a Peer Data Management System (PDMS). A link in the model used is a mapping from a source ontology attribute to a target ontology attribute. The goal is automated detection of incorrect links by the application, i.e. results of low correctness probability values for incorrect links and high values for correct ones. The implemented application offers a graphical user interface for creation of and operation on modeled peers, cycle detection methods, creation and storage of factor graphs, a message passing algorithm running on those factor graphs and output of intermediary and final results.