Although recent advances of significant subgraph mining enable us to find subgraphs that are statistically significantly associated with the class variable from graph databases, it is challenging to interpret the resulting subgraphs due to their massive number and their propositional representation. Here we represent graphs by probabilistic logic programming and solve the problem of summarizing significant subgraphs by structure learning of probabilistic logic programs. Learning probabilistic logical models leads to a much more interpretable, expressive and succinct representation of significant subgraphs. We empirically demonstrate that our approach can effectively summarize significant subgraphs with keeping high accuracy.
AggarwalC.C. and HanJ., editors. Frequent Pattern Mining, Springer, 2014.
2.
AgrawalR.ImielińskiT. and SwamiA., Mining association rules between sets of items in large databases, In Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, 1993, pp. 207–216.
3.
AgrawalR. and SrikantR., Fast algorithms for mining association rules, In Proceedings of the 20th International Conference on Very Large Data Bases, 1994, pp. 487–499.
4.
BellodiE. and RiguzziF., Expectation Maximization over Binary Decision Diagrams for probabilistic logic programs, Intelligent Data Analysis17(2) (2013), 343–363.
5.
BellodiE. and RiguzziF., Structure learning of probabilistic logic programs by searching the clause space, Theory and Practice of Logic Programming15(2) (2015), 169–212.
6.
BermanH.M.WestbrookJ.FengZ.GillilandG.BhatT.N.WeissigH.ShindyalovI.N. and BourneP.E., The protein data bank, Nucleic Acids Research28 (2000), 235–242.
7.
BoltonE.E.WangY.ThiessenP.A. and BryantS.H., PubChem: integrated platform of small molecules and biological activities, Annual Reports in Computational Chemistry4 (2008), 217–241.
8.
CostaV.S.PageD.QaziM. and CussensJ., CLP(BN): constraint logic programming for probabilistic knowledge, CoRR, abs/1212.2519, 2012.
9.
DavisJ. and GoadrichM., The relationship between precision-recall and ROC curves, In Proceedings of the 23rd International Conference on Machine Learning, 2006, pp.233–240.
10.
De RaedtL.KimmigA. and ToivonenH., ProbLog: A probabilistic Prolog and its application in link discovery, In Proceedings of the 20th International Joint Conference on Artificial Intelligence, volume 7, 2007, pp. 2462–2467.
11.
FinnP.MuggletonS.PageD. and SrinivasanA., Pharmacophore discovery using the inductive logic programming system progol, Machine Learning30(2) (1998), 241–270.
12.
GutmannB.ThonI. and De RaedtL., Learning the parameters of probabilistic logic programs from interpretations, In GunopulosD.HofmannT.MalerbaD. and VazirgiannisM., editors, European Conference on Machine Learning and Knowledge Discovery in Databases, volume 6911 of LNCS, Springer, 2011, pp. 581–596.
13.
HanJ.PeiJ. and YinY., Mining frequent patterns without candidate generation, In Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data, 2000, pp. 1–12.
14.
InokuchiA.WashioT. and MotodaH., An apriori-based algorithm for mining frequent substructures from graph data, In Principles of Data Mining and Knowledge Discovery, volume 1910 of LNCS, Springer, 2000, pp. 13–23.
15.
JinN.YoungC. and WangW., Graph classification based on pattern co-occurrence, In Proceedings of the 18th ACM Conference on Information and Knowledge Management, 2009, pp. 573–582.
16.
KimmigA. and De RaedtL., Local query mining in a probabilistic Prolog, In Proceedings of the 21st International Joint Conference on Artificial Intelligence, volume 2, 2009, pp. 1095–1100.
17.
Llinares-LópezF.GrimmD.G.BodenhamD.A.GierathsU.SugiyamaM.RowanB. and BorgwardtK.M., Genome-wide detection of intervals of genetic heterogeneity associated with complex traits, Bioinformatics31(12) (2015), i240–i249.
18.
Llinares-LópezF.PapaxanthosL.RoqueiroD.BodenhamD. and BorgwardtK., CASMAP: detection of statistically significant combinations of SNPs in association mapping, Bioinformatics12 (2018).
19.
Llinares-LópezF.SugiyamaM.PapaxanthosL. and BorgwardtK.M., Fast and memory-efficient significant pattern mining via permutation testing, In Proceedings of the 21st ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2015, pp. 725–734.
20.
MeertW.StruyfJ. and BlockeelH., Learning ground CP-Logic theories by leveraging Bayesian network learning techniques, Fundamenta Informaticae89(1) (2008), 131–160.
21.
MuggletonS., Inverse entailment and Progol, New Generation Computing13 (1995), 245–286.
22.
NijssenS. and KokJ.N., A quickstart in frequent structure mining can make a difference, In Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2004, pp. 647–652.
23.
PapaxanthosL.Llinares-LopezF.BodenhamD. and BorgwardtK.M., Finding significant combinations of features in the presence of categorical covariates, In Advances in Neural Information Processing Systems, volume 29, 2016, pp. 2271–2279.
24.
PeiJ.HanJ.Mortazavi-AslB.PintoH.ChenQ.DayalU. and HsuM.-C., PrefixSpan: Mining sequential patterns efficiently by prefix-projected pattern growth, In Proceedings of the 17th International Conference on Data Engineering, 2001, pp. 215–224.
25.
PooleD., The Independent Choice Logic and beyond, In De RaedtL.FrasconiP.KerstingK. and MuggletonS., editors, Probabilistic Inductive Logic Programming, volume 4911 of LNCS, Springer Berlin Heidelberg, 2008, pp. 222–243.
26.
RiguzziF., Speeding up inference for probabilistic logic programs, The Computer Journal57(3) (2014), 347–363.
27.
RiguzziF. and SwiftT., Tabling and answer subsumption for reasoning on logic programs with annotated disjunctions, In International Conference on Logic Programming, volume 7 of LIPIcs, 2010, pp. 162–171.
28.
RiguzziF. and SwiftT., The PITA system: Tabling and answer subsumption for reasoning under uncertainty,Theory and Practice of Logic Programming11(4–5) (2011), 433–449.
29.
RiguzziF. and SwiftT., Well-definedness and efficient inference for probabilistic logic programming under the distribution semantics, Theory and Practice of Logic Programming13(2) (2013), 279–302.
30.
SatoT., A statistical learning method for logic programs with distribution semantics, In Proceedings of the 12th International Conference on Logic Programming, 1995, pp. 715–729.
31.
SatoT., A glimpse of symbolic-statistical modeling by PRISM, Journal of Intelligent Information Systems31(2) (2008), 161–176.
32.
SatoT. and KameyaY., Parameter learning of logic programs for symbolic-statistical modeling, Journal of Artificial Intelligence Research15 (2001), 391–454.
33.
SugiyamaM.Llinares-LópezF.KasenburgN. and BorgwardtK.M., Significant subgraph mining with multiple testing correction, In Proceedings of the 2015 SIAM International Conference on Data Mining, 2015, pp. 37–45.
34.
TaroneR.E., A modified Bonferroni method for discrete data, Biometrics46(2) (1990), 515–522.
35.
TeradaA.Okada-HatakeyamaM.TsudaK. and SeseJ., Statistical significance of combinatorial regulations, Proc Natl Acad Sci USA110(32) (2013), 12996–13001.
36.
TeradaA.TsudaK. and SeseJ., Fast Westfall-Young permutation procedure for combinatorial regulation discovery, In 2013 IEEE International Conference on Bioinformatics and Biomedicine (BIBM), 2013, pp. 153–158.
37.
VennekensJ.VerbaetenS. and BruynoogheM., Logic Programs With Annotated Disjunctions, In International Conference on Logic Programming, volume 3131 of LNCS, Springer, 2004, pp. 195–209.
38.
VreekenJ.van LeeuwenM. and SiebesA., KRIMP: Mining itemsets that compress, Data Mining and Knowledge Discovery23(1) (2011), 169–214.
39.
WestfallP.H. and YoungS.S., Resampling-based multiple testing: Examples and methods for p-value adjustment, John Wiley & Sons, 1993.
40.
YanX. and HanJ., gSpan: Graph-based substructure pattern mining, In Proceedings of 2002 IEEE International Conference on Data Mining, 2002, pp. 721–724.
41.
YoshizoeK.TsudaK. and TeradaA., MP-LAMP: parallel detection of statistically significant multi-loci markers on cloud platforms, Bioinformatics34(17) (2018), 3047–3049.
42.
ZakiM.J. and MeiraW., Jr., Data Mining And Analysis, Cambridge, 2016.
