2021/10/19 by Richard Mar, Mar, Richard, Oliver Schulte +2
Computer Science · #Data Mining Algorithms and Applications #Bayesian Modeling and Causal Inference #Data Management and Algorithms
paper · pdf · doi:10.48550/arxiv.2110.09767
Statistical-Relational Model Discovery aims to find statistically relevant\npatterns in relational data. For example, a relational dependency pattern may\nstipulate that a user's gender is associated with the gender of their friends.\nAs with propositional (non-relational) graphical models, the major scalability\nbottleneck for model discovery is computing instantiation counts: the number of\ntimes a relational pattern is instantiated in a database. Previous work on\npropositional learning utilized pre-counting or post-counting to solve this\ntask. This paper takes a detailed look at the memory and speed trade-offs\nbetween pre-counting and post-counting strategies for relational learning. A\npre-counting approach computes and caches instantiation counts for a large set\nof relational patterns before model search. A post-counting approach computes\nan instantiation count dynamically on-demand for each candidate pattern\ngenerated during the model search. We describe a novel hybrid approach,\ntailored to relational data, that achieves a sweet spot with pre-counting for\npatterns involving positive relationships (e.g. pairs of users who are friends)\nand post-counting for patterns involving negative relationships (e.g. pairs of\nusers who are not friends). Our hybrid approach scales model discovery to\nmillions of data facts.\n