Learning hierarchical relationships among partially ordered objects with heterogeneous attributes and links

Objects linking with many other objects in an information network may imply various semantic relationships. Uncovering such knowledge is essential for role discovery, data cleaning, and better organization of information networks, especially when the semantically meaningful relationships are hidden or mingled with noisy links and attributes. In this paper we study a generic form of relationship along which objects can form a treelike structure, a pervasive structure in various domains. We formalize the problem of uncovering hierarchical relationships in a supervised setting. In general, local features of object attributes, their interaction patterns, as well as rules and constraints for knowledge propagation can be used to infer such relationships. Existing approaches, designed for specific applications, either cannot handle dependency rules together with local features, or cannot leverage labeled data to differentiate their importance. In this study, we propose a discriminative undirected graphical model. It integrates a wide range of features and rules by defining potential functions with simple forms. These functions are also summarized and categorized. Our experiments on three quite different domains demonstrate how to apply the method to encode domain knowledge. The efficacy is measured with both traditional and our newly designed metrics in the evaluation of discovered tree structures.