{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,11]],"date-time":"2026-02-11T02:59:45Z","timestamp":1770778785670,"version":"3.50.0"},"reference-count":85,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2018,1,10]],"date-time":"2018-01-10T00:00:00Z","timestamp":1515542400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Northrop Grumman Aerospace Systems"},{"name":"NSF CAREER","award":["1452425"],"award-info":[{"award-number":["1452425"]}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["IIS-1017181"],"award-info":[{"award-number":["IIS-1017181"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"ARO Young Investigator Program","award":["W911NF-14-1-0029"],"award-info":[{"award-number":["W911NF-14-1-0029"]}]},{"name":"DARPA Transparent Computing Program","award":["FA8650-15-C-7561"],"award-info":[{"award-number":["FA8650-15-C-7561"]}]},{"name":"Facebook"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2018,4,30]]},"abstract":"<jats:p>\n            Given a network with node attributes, how can we identify communities and spot anomalies? How can we characterize, describe, or summarize the network in a succinct way? Community extraction requires a measure of quality for connected subgraphs (e.g., social circles). Existing subgraph measures, however, either consider only the connectedness of nodes inside the community and ignore the cross-edges at the boundary (e.g., density) or only quantify the structure of the community and ignore the node attributes (e.g., conductance). In this work, we focus on node-attributed networks and introduce: (1) a\n            <jats:italic>new measure of subgraph quality<\/jats:italic>\n            for attributed communities called normality, (2) a\n            <jats:italic>community extraction<\/jats:italic>\n            algorithm that uses normality\u00a0to extract communities and a few characterizing attributes per community, and (3) a\n            <jats:italic>summarization and interactive visualization<\/jats:italic>\n            approach for attributed graph exploration. More specifically, (1) we first introduce a new measure to quantify the normality of an attributed subgraph. Our normality\u00a0measure carefully utilizes structure and attributes together to quantify both the internal consistency and external separability. We then formulate an objective function to automatically infer a few attributes (called the \u201cfocus\u201d) and respective attribute weights, so as to maximize the normality\u00a0 score of a given subgraph. Most notably, unlike many other approaches, our measure allows for many cross-edges as long as they can be \u201cexonerated;\u201d i.e., either (i) are expected under a null graph model, and\/or (ii) their boundary nodes do not exhibit the focus attributes. Next, (2) we propose AMEN (for Attributed Mining of Entity Networks), an algorithm that simultaneously discovers the communities and their respective focus in a given graph, with a goal to maximize the total normality. Communities for which a focus that yields high normality\u00a0 cannot be found are considered low quality or anomalous. Last, (3) we formulate a summarization task with a multi-criteria objective, which selects a subset of the communities that (i) cover the entire graph well, are (ii) high quality and (iii) diverse in their focus attributes. We further design an interactive visualization interface that presents the communities to a user in an interpretable, user-friendly fashion. The user can explore all the communities, analyze various algorithm-generated summaries, as well as devise their own summaries interactively to characterize the network in a succinct way. As the experiments on real-world attributed graphs show, our proposed approaches effectively find anomalous communities and outperform several existing measures and methods, such as conductance, density, OddBall, and SODA. We also conduct extensive user studies to measure the capability and efficiency that our approach provides to the users toward network summarization, exploration, and sensemaking.\n          <\/jats:p>","DOI":"10.1145\/3139241","type":"journal-article","created":{"date-parts":[[2018,1,10]],"date-time":"2018-01-10T16:51:38Z","timestamp":1515603098000},"page":"1-40","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":32,"title":["Discovering Communities and Anomalies in Attributed Graphs"],"prefix":"10.1145","volume":"12","author":[{"given":"Bryan","family":"Perozzi","sequence":"first","affiliation":[{"name":"Stony Brook University, Google Research, New York, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Leman","family":"Akoglu","sequence":"additional","affiliation":[{"name":"Stony Brook University, Carnegie Mellon University, Pittsburgh, PA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,1,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213941"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13672-6_40"},{"key":"e_1_2_1_3_1","unstructured":"Leman Akoglu Hanghang Tong and Danai Koutra. 2014. Graph-based anomaly detection and description: A survey. DAMI 28 4 (2014).  Leman Akoglu Hanghang Tong and Danai Koutra. 2014. Graph-based anomaly detection and description: A survey. DAMI 28 4 (2014)."},{"key":"e_1_2_1_4_1","volume-title":"PICS: Parameter-free identification of cohesive subgroups in large attributed graphs. In SDM. 439--450.","author":"Akoglu Leman","year":"2012"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.44"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1135777.1135814"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/SocialCom-PASSAT.2012.41"},{"key":"e_1_2_1_8_1","volume-title":"Data Clustering: Algorithms and Applications","author":"Bailey James"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1162\/089976603321780317"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/2008\/10\/P10008"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783296"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Moses Charikar. 2000. Greedy approximation algorithms for finding dense components in a graph. In APPROX.   Moses Charikar. 2000. Greedy approximation algorithms for finding dense components in a graph. In APPROX.","DOI":"10.1007\/3-540-44436-X_10"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDMW.2008.99"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020524"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.72.026132"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.70.066111"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/1618595.1618605"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339630"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2470654.2466444"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/316188.316229"},{"key":"e_1_2_1_21_1","unstructured":"Gary William Flake Steve Lawrence and C. Lee Giles. 2000. Efficient identification of web communities. In KDD.  Gary William Flake Steve Lawrence and C. Lee Giles. 2000. Efficient identification of web communities. In KDD."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-014-0373-y"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835907"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339628"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939754"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2010.95"},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"Stephan G\u00fcnnemann Ines Farber Sebastian Raubach and Thomas Seidl. 2013. Spectral subspace clustering for graphs with feature vectors. In ICDM. IEEE 231--240.  Stephan G\u00fcnnemann Ines Farber Sebastian Raubach and Thomas Seidl. 2013. Spectral subspace clustering for graphs with feature vectors. In ICDM. IEEE 231--240.","DOI":"10.1109\/ICDM.2013.110"},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"Manish Gupta Arun Mallya Subhro Roy Jason H. D. Cho and Jiawei Han. 2014. Local learning for mining outlier subgraphs from network datasets. In SIAM SDM. 73--81.  Manish Gupta Arun Mallya Subhro Roy Jason H. D. Cho and Jiawei Han. 2014. Local learning for mining outlier subgraphs from network datasets. In SIAM SDM. 73--81.","DOI":"10.1137\/1.9781611973440.9"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339723"},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","unstructured":"Xiao Huang Jundong Li and Xia Hu. 2017. Accelerated attributed network embedding. In SDM. 633--641.  Xiao Huang Jundong Li and Xia Hu. 2017. Accelerated attributed network embedding. In SDM. 633--641.","DOI":"10.1137\/1.9781611974973.71"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827595287997"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827595287997"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824102"},{"key":"e_1_2_1_35_1","volume-title":"VOG: Summarizing and understanding large graphs. In SDM. 91--99.","author":"Koutra Danai","year":"2014"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129183111016816"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1081870.1081893"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1081870.1081893"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367497.1367591"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544894"},{"key":"e_1_2_1_41_1","doi-asserted-by":"crossref","unstructured":"Nan Li Huan Sun Kyle Chipman Jemin George and Xifeng Yan. 2014. A probabilistic approach to uncovering attributed graph anomalies. In SIAM SDM. 82--90.  Nan Li Huan Sun Kyle Chipman Jemin George and Xifeng Yan. 2014. A probabilistic approach to uncovering attributed graph anomalies. In SIAM SDM. 82--90.","DOI":"10.1137\/1.9781611973440.10"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2566486.2568045"},{"key":"e_1_2_1_43_1","unstructured":"Yike Liu Abhilash Dighe Tara Safavi and Danai Koutra. 2016. A graph summarization: A survey. CoRR abs\/1612.04883 (2016).  Yike Liu Abhilash Dighe Tara Safavi and Danai Koutra. 2016. A graph summarization: A survey. CoRR abs\/1612.04883 (2016)."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1143844.1143918"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1093\/sf\/67.2.281"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2556612"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1401890.1401955"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1146\/annurev.soc.27.1.415"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1086\/338954"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.3.3.177"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-44943-0_5"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.89.208701"},{"key":"e_1_2_1_53_1","doi-asserted-by":"crossref","unstructured":"M. E. J. Newman. 2003. Mixing patterns in networks. Physical Review E 67 (2003).  M. E. J. Newman. 2003. Mixing patterns in networks. Physical Review E 67 (2003).","DOI":"10.1103\/PhysRevE.67.026126"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0601602103"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780199206650.001.0001"},{"key":"e_1_2_1_56_1","unstructured":"Andrew Y. Ng Michael I. Jordan and Yair Weiss. 2001. On spectral clustering: Analysis and an algorithm. In NIPS.   Andrew Y. Ng Michael I. Jordan and Yair Weiss. 2001. On spectral clustering: Analysis and an algorithm. In NIPS."},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2013.180"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956831"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2012.07.019"},{"key":"e_1_2_1_60_1","doi-asserted-by":"crossref","unstructured":"Bryan Perozzi and Leman Akoglu. 2016. Scalable anomaly ranking of attributed neighborhoods. In SIAM SDM.  Bryan Perozzi and Leman Akoglu. 2016. Scalable anomaly ranking of attributed neighborhoods. In SIAM SDM.","DOI":"10.1137\/1.9781611974348.24"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623682"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623732"},{"key":"e_1_2_1_63_1","volume-title":"BigComp","author":"Pienta Robert"},{"key":"e_1_2_1_64_1","volume-title":"FACETS: Adaptive local exploration of large graphs. In SDM.","author":"Pienta Robert","year":"2017"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557099"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/2484702.2484706"},{"key":"e_1_2_1_67_1","doi-asserted-by":"crossref","unstructured":"Hiroaki Shiokawa Yasuhiro Fujiwara and Makoto Onizuka. 2013. Fast algorithm for modularity-based graph clustering. In AAAI.   Hiroaki Shiokawa Yasuhiro Fujiwara and Makoto Onizuka. 2013. Fast algorithm for modularity-based graph clustering. In AAAI.","DOI":"10.1609\/aaai.v27i1.8455"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.14778\/2140436.2140443"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007372"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741093"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376675"},{"key":"e_1_2_1_72_1","doi-asserted-by":"crossref","unstructured":"Amanda L. Traud Peter J. Mucha and Mason A. Porter. 2012. Social structure of Facebook networks. Physica A: Statistical Mechanics and its Applications 391 16 (2012) 4165--4180.  Amanda L. Traud Peter J. Mucha and Mason A. Porter. 2012. Social structure of Facebook networks. Physica A: Statistical Mechanics and its Applications 391 16 (2012) 4165--4180.","DOI":"10.1016\/j.physa.2011.12.021"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487645"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557111"},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2011.01898.x"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1145\/2505515.2505535"},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1145\/2501654.2501657"},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2012.139"},{"key":"e_1_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2012.138"},{"key":"e_1_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1145\/2433396.2433471"},{"key":"e_1_2_1_81_1","doi-asserted-by":"crossref","unstructured":"Jaewon Yang Julian J. McAuley and Jure Leskovec. 2013. Community detection in networks with node attributes. In ICDM. 1151--1156.  Jaewon Yang Julian J. McAuley and Jure Leskovec. 2013. Community detection in networks with node attributes. In ICDM. 1151--1156.","DOI":"10.1109\/ICDM.2013.167"},{"key":"e_1_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2594516"},{"key":"e_1_2_1_83_1","doi-asserted-by":"crossref","unstructured":"Ning Zhang Yuanyuan Tian and Jignesh M. Patel. 2010. Discovery-driven graph summarization. In ICDE. 880--891.  Ning Zhang Yuanyuan Tian and Jignesh M. Patel. 2010. Discovery-driven graph summarization. In ICDE. 880--891.","DOI":"10.1109\/ICDE.2010.5447830"},{"key":"e_1_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.35"},{"key":"e_1_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.1145\/1526709.1526781"},{"key":"e_1_2_1_86_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687709"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3139241","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3139241","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3139241","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:11:16Z","timestamp":1750212676000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3139241"}},"subtitle":["Interactive Visual Exploration and Summarization"],"short-title":[],"issued":{"date-parts":[[2018,1,10]]},"references-count":85,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,4,30]]}},"alternative-id":["10.1145\/3139241"],"URL":"https:\/\/doi.org\/10.1145\/3139241","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1,10]]},"assertion":[{"value":"2016-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-01-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}