{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,24]],"date-time":"2025-09-24T09:37:54Z","timestamp":1758706674218,"version":"3.37.3"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2019,11,22]],"date-time":"2019-11-22T00:00:00Z","timestamp":1574380800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,11,22]],"date-time":"2019-11-22T00:00:00Z","timestamp":1574380800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Data Min Knowl Disc"],"published-print":{"date-parts":[[2020,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Data clustering, local pattern mining, and community detection in graphs are three mature areas of data mining and machine learning. In recent years, attributed subgraph mining has emerged as a new powerful data mining task in the intersection of these areas. Given a graph and a set of attributes for each vertex, attributed subgraph mining aims to find cohesive subgraphs for which (some of) the attribute values have exceptional values. The principled integration of graph and attribute data poses two challenges: (1) the <jats:italic>definition of a pattern syntax<\/jats:italic> (the abstract form of patterns) that is intuitive and lends itself to efficient search, and (2) the <jats:italic>formalization of the interestingness<\/jats:italic> of such patterns. We propose an integrated solution to both of these challenges. The proposed pattern syntax improves upon prior work in being both highly flexible and intuitive. Plus, we define an effective and principled algorithm to enumerate patterns of this syntax. The proposed approach for quantifying interestingness of these patterns is rooted in information theory, and is able to account for background knowledge on the data. While prior work quantified the interestingness for the cohesion of the subgraph and for the exceptionality of its attributes separately, then combining these in a parameterized trade-off, we instead handle this trade-off implicitly in a principled, parameter-free manner. Empirical results confirm we can efficiently find highly interesting subgraphs.<\/jats:p>","DOI":"10.1007\/s10618-019-00664-w","type":"journal-article","created":{"date-parts":[[2019,11,22]],"date-time":"2019-11-22T10:02:38Z","timestamp":1574416958000},"page":"355-393","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["SIAS-miner: mining subjectively interesting attributed subgraphs"],"prefix":"10.1007","volume":"34","author":[{"given":"Anes","family":"Bendimerad","sequence":"first","affiliation":[]},{"given":"Ahmad","family":"Mel","sequence":"additional","affiliation":[]},{"given":"Jefrey","family":"Lijffijt","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4636-5753","authenticated-orcid":false,"given":"Marc","family":"Plantevit","sequence":"additional","affiliation":[]},{"given":"C\u00e9line","family":"Robardet","sequence":"additional","affiliation":[]},{"given":"Tijl","family":"De Bie","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,11,22]]},"reference":[{"key":"664_CR1","doi-asserted-by":"publisher","first-page":"965","DOI":"10.1016\/j.ins.2015.05.008","volume":"329","author":"M Atzmueller","year":"2016","unstructured":"Atzmueller M, Doerfel S, Mitzlaff F (2016) Description-oriented community detection using exhaustive subgroup discovery. Inform Sci 329:965\u2013984","journal-title":"Inform Sci"},{"issue":"1","key":"664_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10115-017-1109-2","volume":"56","author":"AA Bendimerad","year":"2018","unstructured":"Bendimerad AA, Plantevit M, Robardet C (2018) Mining exceptional closed patterns in attributed graphs. Knowl Inf Syst 56(1):1\u201325","journal-title":"Knowl Inf Syst"},{"key":"664_CR3","doi-asserted-by":"crossref","unstructured":"Bistarelli S, Bonchi F (2005) Interestingness is not a dichotomy: introducing softness in constrained pattern mining. In: Knowledge discovery in databases: PKDD 2005, 9th European conference on principles and practice of knowledge discovery in databases, Porto, Portugal, October 3\u20137, 2005, Proceedings, pp 22\u201333","DOI":"10.1007\/11564126_8"},{"issue":"3","key":"664_CR4","doi-asserted-by":"publisher","first-page":"691","DOI":"10.1016\/j.tcs.2009.10.024","volume":"411","author":"M Boley","year":"2010","unstructured":"Boley M, Horv\u00e1th T, Poign\u00e9 A, Wrobel S (2010) Listing closed sets of strongly accessible set systems with applications to data mining. Theor Comput Sci 411(3):691\u2013700","journal-title":"Theor Comput Sci"},{"key":"664_CR5","doi-asserted-by":"crossref","unstructured":"Chen F, Zhou B, Alim A, Zhao L (2017a) A generic framework for interesting subspace cluster detection in multi-attributed networks. In: 2017 IEEE international conference on data mining, ICDM 2017, New Orleans, LA, USA, November 18\u201321, 2017, pp 41\u201350","DOI":"10.1109\/ICDM.2017.13"},{"issue":"10","key":"664_CR6","doi-asserted-by":"publisher","first-page":"2725","DOI":"10.1109\/TSP.2017.2666772","volume":"65","author":"S Chen","year":"2017","unstructured":"Chen S, Yang Y, Zong S, Singh A, Kovacevic J (2017b) Detecting localized categorical attributes on graphs. IEEE Trans Signal Process 65(10):2725\u20132740","journal-title":"IEEE Trans Signal Process"},{"key":"664_CR7","unstructured":"Chen S, Singh A, Kovacevic J (2018) Multiresolution representations for piecewise-smooth signals on graphs. CoRR. arXiv:1803.02944"},{"key":"664_CR8","first-page":"1","volume":"2","author":"TM Cover","year":"1991","unstructured":"Cover TM, Thomas JA (1991) Entropy, relative entropy and mutual information. Elements Inform Theory 2:1\u201355","journal-title":"Elements Inform Theory"},{"key":"664_CR9","doi-asserted-by":"crossref","unstructured":"De\u00a0Bie T (2011a) An information theoretic framework for data mining. In: Proceedings of the 17th ACM SIGKDD international conference on knowledge discovery and data mining, pp 564\u2013572","DOI":"10.1145\/2020408.2020497"},{"issue":"3","key":"664_CR10","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1007\/s10618-010-0209-3","volume":"23","author":"T De Bie","year":"2011","unstructured":"De Bie T (2011b) Maximum entropy models and subjective interestingness. Data Min Knowl Disc 23(3):407\u2013446","journal-title":"Data Min Knowl Disc"},{"key":"664_CR11","doi-asserted-by":"crossref","unstructured":"De\u00a0Bie T (2013) Subjective interestingness in exploratory data mining. In: International symposium on intelligent data analysis (IDA), pp 19\u201331","DOI":"10.1007\/978-3-642-41398-8_3"},{"key":"664_CR12","doi-asserted-by":"crossref","unstructured":"Eppstein D, Strash D (2011) Listing all maximal cliques in large sparse real-world graphs. In: Experimental algorithms\u201410th international symposium, SEA 2011, Kolimpari, Chania, Crete, Greece, May 5\u20137, 2011. Proceedings, pp 364\u2013375","DOI":"10.1007\/978-3-642-20662-7_31"},{"issue":"12","key":"664_CR13","doi-asserted-by":"publisher","first-page":"1233","DOI":"10.14778\/2994509.2994538","volume":"9","author":"Y Fang","year":"2016","unstructured":"Fang Y, Cheng R, Luo S, Hu J (2016) Effective community search for large attributed graphs. Proc VLDB Endowment (PVLDB) 9(12):1233\u20131244","journal-title":"Proc VLDB Endowment (PVLDB)"},{"issue":"6","key":"664_CR14","doi-asserted-by":"publisher","first-page":"803","DOI":"10.1007\/s00778-017-0482-5","volume":"26","author":"Y Fang","year":"2017","unstructured":"Fang Y, Cheng R, Chen Y, Luo S, Hu J (2017a) Effective and efficient attributed community search. VLDB J 26(6):803\u2013828","journal-title":"VLDB J"},{"issue":"6","key":"664_CR15","doi-asserted-by":"publisher","first-page":"709","DOI":"10.14778\/3055330.3055337","volume":"10","author":"Y Fang","year":"2017","unstructured":"Fang Y, Cheng R, Li X, Luo S, Hu J (2017b) Effective community search over large spatial graphs. Proc VLDB Endowment (PVLDB) 10(6):709\u2013720","journal-title":"Proc VLDB Endowment (PVLDB)"},{"key":"664_CR16","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/j.physrep.2009.11.002","volume":"486","author":"S Fortunato","year":"2010","unstructured":"Fortunato S (2010) Community detection in graphs. Phys Rep 486:75\u2013174","journal-title":"Phys Rep"},{"key":"664_CR17","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1613\/jair.1089","volume":"17","author":"D Gamberger","year":"2002","unstructured":"Gamberger D, Lavrac N (2002) Expert-guided subgroup discovery: methodology and application. J Artif Intell Res 17:501\u2013527","journal-title":"J Artif Intell Res"},{"key":"664_CR18","doi-asserted-by":"crossref","unstructured":"Gionis A, Mathioudakis M, Ukkonen A (2015) Bump hunting in the dark: local discrepancy maximization on graphs. In: 31st IEEE international conference on data engineering, ICDE 2015, Seoul, South Korea, April 13\u201317, 2015, pp 1155\u20131166","DOI":"10.1109\/ICDE.2015.7113364"},{"key":"664_CR19","doi-asserted-by":"crossref","unstructured":"G\u00fcnnemann S, F\u00e4rber I, Boden B, Seidl T (2010) Subspace clustering meets dense subgraph mining. In: 2010 IEEE international conference on data mining (ICDM), pp 845\u2013850","DOI":"10.1109\/ICDM.2010.95"},{"key":"664_CR20","doi-asserted-by":"crossref","unstructured":"Gupta M, Mallya A, Roy S, Cho JHD, Han J (2014) Local learning for mining outlier subgraphs from network datasets. In: Proceedings of the 2014 SIAM international conference on data mining, Philadelphia, Pennsylvania, USA, April 24\u201326, 2014, pp 73\u201381","DOI":"10.1137\/1.9781611973440.9"},{"issue":"9","key":"664_CR21","doi-asserted-by":"publisher","first-page":"949","DOI":"10.14778\/3099622.3099626","volume":"10","author":"X Huang","year":"2017","unstructured":"Huang X, Lakshmanan L (2017) Attribute-driven community search. Proc VLDB Endowment (PVLDB) 10(9):949\u2013960","journal-title":"Proc VLDB Endowment (PVLDB)"},{"key":"664_CR22","doi-asserted-by":"crossref","unstructured":"Huang X, Lakshmanan L, Xu J (2017) Community search over big graphs: models, algorithms, and opportunities. In: 2017 IEEE 33rd international conference on data engineering (ICDE), pp 1451\u20131454","DOI":"10.1109\/ICDE.2017.211"},{"issue":"8","key":"664_CR23","doi-asserted-by":"publisher","first-page":"1171","DOI":"10.1007\/s10994-016-5598-0","volume":"106","author":"M Kaytoue","year":"2017","unstructured":"Kaytoue M, Plantevit M, Zimmermann A, Bendimerad AA, Robardet C (2017) Exceptional contextual subgraph mining. Mach Learn 106(8):1171\u20131211","journal-title":"Mach Learn"},{"key":"664_CR24","first-page":"153","volume":"5","author":"N Lavrac","year":"2004","unstructured":"Lavrac N, Kavsek B, Flach PA, Todorovski L (2004) Subgroup discovery with CN2-SD. J Mach Learn Res 5:153\u2013188","journal-title":"J Mach Learn Res"},{"key":"664_CR25","doi-asserted-by":"crossref","unstructured":"Lemmerich F, Becker M, Singer P, Helic D, Hotho A, Strohmaier M (2016) Mining subgroups with exceptional transition behavior. In: Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, pp 965\u2013974","DOI":"10.1145\/2939672.2939752"},{"issue":"1","key":"664_CR26","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1007\/s10618-012-0298-2","volume":"28","author":"J Lijffijt","year":"2014","unstructured":"Lijffijt J, Papapetrou P, Puolam\u00e4ki K (2014) A statistical significance testing approach to mining the most informative set of patterns. Data Min Knowl Disc 28(1):238\u2013263","journal-title":"Data Min Knowl Disc"},{"issue":"1","key":"664_CR27","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/s41060-016-0004-3","volume":"1","author":"J Lijffijt","year":"2016","unstructured":"Lijffijt J, Spyropoulou E, Kang B, De Bie T (2016) P-n-rminer: a generic framework for mining interesting structured relational patterns. Int J Data Sci Anal 1(1):61\u201376","journal-title":"Int J Data Sci Anal"},{"issue":"1","key":"664_CR28","first-page":"10","volume":"20","author":"BA Miller","year":"2013","unstructured":"Miller BA, Bliss NT, Wolfe PJ, Beard MS (2013) Detection theory for graphs. Lincoln Lab J 20(1):10\u201330","journal-title":"Lincoln Lab J"},{"issue":"16","key":"664_CR29","doi-asserted-by":"publisher","first-page":"4191","DOI":"10.1109\/TSP.2015.2437841","volume":"63","author":"BA Miller","year":"2015","unstructured":"Miller BA, Beard MS, Wolfe PJ, Bliss NT (2015) A spectral framework for anomalous subgraph detection. IEEE Trans Signal Process 63(16):4191\u20134206","journal-title":"IEEE Trans Signal Process"},{"key":"664_CR30","doi-asserted-by":"crossref","unstructured":"Moser F, Colak R, Rafiey A, Ester M (2009) Mining cohesive patterns from graphs with feature vectors. In: Proceedings of the 2009 SIAM international conference on data mining (SDM), pp 593\u2013604","DOI":"10.1137\/1.9781611972795.51"},{"key":"664_CR31","first-page":"377","volume":"10","author":"PK Novak","year":"2009","unstructured":"Novak PK, Lavrac N, Webb GI (2009) Supervised descriptive rule discovery: a unifying survey of contrast set, emerging pattern and subgroup mining. J Mach Learn Res 10:377\u2013403","journal-title":"J Mach Learn Res"},{"key":"664_CR32","doi-asserted-by":"crossref","unstructured":"Perozzi B, Akoglu L, S\u00e1nchez PI, M\u00fcller E (2014) Focused clustering and outlier detection in large attributed graphs. In: Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp 1346\u20131355","DOI":"10.1145\/2623330.2623682"},{"issue":"9","key":"664_CR33","doi-asserted-by":"publisher","first-page":"2090","DOI":"10.1109\/TKDE.2012.154","volume":"25","author":"A Prado","year":"2013","unstructured":"Prado A, Plantevit M, Robardet C, Boulicaut J (2013) Mining graph topological patterns: finding covariations among vertex descriptors. IEEE Trans Knowl Data Eng 25(9):2090\u20132104","journal-title":"IEEE Trans Knowl Data Eng"},{"key":"664_CR34","unstructured":"Rice JA (2007) Mathematical statistics and data analysis, 3rd edn. Duxbury"},{"issue":"7","key":"664_CR35","doi-asserted-by":"publisher","first-page":"1644","DOI":"10.1109\/TSP.2013.2238935","volume":"61","author":"A Sandryhaila","year":"2013","unstructured":"Sandryhaila A, Moura JMF (2013) Discrete signal processing on graphs. IEEE Trans Signal Process 61(7):1644\u20131656","journal-title":"IEEE Trans Signal Process"},{"key":"664_CR36","doi-asserted-by":"crossref","unstructured":"Shang J, Wang C, Wang C, Guo G, Qian J (2016) AGAR: an attribute-based graph refining method for community search. In: Proceedings of the sixth international conference on emerging databases: technologies, applications, and theory (EDBT), pp 65\u201366","DOI":"10.1145\/3007818.3007823"},{"issue":"3","key":"664_CR37","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1109\/MSP.2012.2235192","volume":"30","author":"DI Shuman","year":"2013","unstructured":"Shuman DI, Narang SK, Frossard P, Ortega A, Vandergheynst P (2013) The emerging field of signal processing on graphs: extending high-dimensional data analysis to networks and other irregular domains. IEEE Signal Process Mag 30(3):83\u201398","journal-title":"IEEE Signal Process Mag"},{"key":"664_CR38","unstructured":"Silberschatz A, Tuzhilin A (1995) On subjective measures of interestingness in knowledge discovery. In: Proceedings of the first international conference on knowledge discovery and data mining (KDD-95), pp 275\u2013281"},{"issue":"5","key":"664_CR39","doi-asserted-by":"publisher","first-page":"466","DOI":"10.14778\/2140436.2140443","volume":"5","author":"A Silva","year":"2012","unstructured":"Silva A, Meira W, Zaki M (2012) Mining attribute-structure correlated patterns in large attributed graphs. Proc VLDB Endowment (PVLDB) 5(5):466\u2013477","journal-title":"Proc VLDB Endowment (PVLDB)"},{"key":"664_CR40","doi-asserted-by":"crossref","unstructured":"Silva A, Bogdanov P, Singh AK (2015) Hierarchical in-network attribute compression via importance sampling. In: 31st IEEE international conference on data engineering, ICDE 2015, pp 951\u2013962","DOI":"10.1109\/ICDE.2015.7113347"},{"key":"664_CR41","doi-asserted-by":"crossref","unstructured":"van Leeuwen M, De\u00a0Bie T, Spyropoulou E, Mesnage C (2016) Subjective interestingness of subgraph patterns. Mach Learn 1\u201335","DOI":"10.1007\/s10994-015-5539-3"},{"issue":"10","key":"664_CR42","doi-asserted-by":"publisher","first-page":"998","DOI":"10.14778\/3115404.3115406","volume":"10","author":"F Zhang","year":"2017","unstructured":"Zhang F, Zhang Y, Qin L, Zhang W, Lin X (2017) When engagement meets similarity: efficient (k, r)-core computation on social networks. Proc VLDB Endowment (PVLDB) 10(10):998\u20131009","journal-title":"Proc VLDB Endowment (PVLDB)"}],"container-title":["Data Mining and Knowledge Discovery"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10618-019-00664-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10618-019-00664-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10618-019-00664-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,21]],"date-time":"2020-11-21T01:19:03Z","timestamp":1605921543000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10618-019-00664-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11,22]]},"references-count":42,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,3]]}},"alternative-id":["664"],"URL":"https:\/\/doi.org\/10.1007\/s10618-019-00664-w","relation":{},"ISSN":["1384-5810","1573-756X"],"issn-type":[{"type":"print","value":"1384-5810"},{"type":"electronic","value":"1573-756X"}],"subject":[],"published":{"date-parts":[[2019,11,22]]},"assertion":[{"value":"10 October 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 November 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 November 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}