{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,30]],"date-time":"2025-04-30T05:26:23Z","timestamp":1745990783685},"reference-count":60,"publisher":"MIT Press","issue":"8","content-domain":{"domain":["direct.mit.edu"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,7,26]]},"abstract":"<jats:p>Summarizing large-scale directed graphs into small-scale representations is a useful but less-studied problem setting. Conventional clustering approaches, based on Min-Cut-style criteria, compress both the vertices and edges of the graph into the communities, which lead to a loss of directed edge information. On the other hand, compressing the vertices while preserving the directed-edge information provides a way to learn the small-scale representation of a directed graph. The reconstruction error, which measures the edge information preserved by the summarized graph, can be used to learn such representation. Compared to the original graphs, the summarized graphs are easier to analyze and are capable of extracting group-level features, useful for efficient interventions of population behavior. In this letter, we present a model, based on minimizing reconstruction error with nonnegative constraints, which relates to a Max-Cut criterion that simultaneously identifies the compressed nodes and the directed compressed relations between these nodes. A multiplicative update algorithm with column-wise normalization is proposed. We further provide theoretical results on the identifiability of the model and the convergence of the proposed algorithms. Experiments are conducted to demonstrate the accuracy and robustness of the proposed method.<\/jats:p>","DOI":"10.1162\/neco_a_01402","type":"journal-article","created":{"date-parts":[[2021,6,7]],"date-time":"2021-06-07T21:40:43Z","timestamp":1623102043000},"page":"2128-2162","update-policy":"http:\/\/dx.doi.org\/10.1162\/mitpressjournals.corrections.policy","source":"Crossref","is-referenced-by-count":2,"title":["Direction Matters: On Influence-Preserving Graph Summarization and Max-Cut Principle for Directed Graphs"],"prefix":"10.1162","volume":"33","author":[{"given":"Wenkai","family":"Xu","sequence":"first","affiliation":[{"name":"Gatsby Unit of Computational Neuroscience, London W1T 4JG, U.K. xwk4813@gmail.com"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gang","family":"Niu","sequence":"additional","affiliation":[{"name":"RIKEN Center for Advanced Intelligence Report, Tokyo 103-0027, Japan gang.niu@riken.jp"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aapo","family":"Hyv\u00e4rinen","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Paris-Saclay, Inria, CEA, Paris 91120, France, and University of Helsinki, FIN00560 Helsinki, Finland aapo.hyvarinen@helsinki.fi"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Masashi","family":"Sugiyama","sequence":"additional","affiliation":[{"name":"RIKEN, Center for Advanced Intelligence Report, Tokyo 103-0027, Japan, and University of Tokyo, Tokyo 113-0033, Japan sugi@k.u-tokyo.ac.jp"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"281","published-online":{"date-parts":[[2021,7,26]]},"reference":[{"issue":"3","key":"2021072618251417000_B1","doi-asserted-by":"crossref","first-page":"626","DOI":"10.1007\/s10618-014-0365-y","article-title":"Graph based anomaly detection and description: A survey","volume":"29","author":"Akoglu","year":"2015","journal-title":"Data Mining and Knowledge Discovery"},{"key":"2021072618251417000_B2","first-page":"415","article-title":"Fast and reliable anomaly detection in categorical data.","author":"Akoglu","year":"2012","journal-title":"Proceedings of the 21st ACM International Conference on Information and Knowledge Management"},{"issue":"4","key":"2021072618251417000_B3","doi-asserted-by":"crossref","first-page":"1350","DOI":"10.1016\/j.patcog.2007.09.010","article-title":"SVD based initialization: A head start for nonnegative matrix factorization","volume":"41","author":"Boutsidis","year":"2008","journal-title":"Pattern Recognition"},{"issue":"2","key":"2021072618251417000_B4","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/S0169-7439(97)00032-4","article-title":"PARAFAC. Tutorial and applications","volume":"38","author":"Bro","year":"1997","journal-title":"Chemometrics and Intelligent Laboratory Systems"},{"issue":"5","key":"2021072618251417000_B5","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1002\/cem.801","article-title":"A new efficient method for determining the number of components in PARAFAC models","volume":"17","author":"Bro","year":"2003","journal-title":"Journal of Chemometrics"},{"issue":"5","key":"2021072618251417000_B6","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1108\/EUM0000000005647","article-title":"Opinion leaders as a segment for marketing communications","volume":"19","author":"Chaney","year":"2001","journal-title":"Marketing Intelligence and Planning"},{"key":"2021072618251417000_B7","doi-asserted-by":"crossref","DOI":"10.1002\/9780470747278","author":"Cichocki","year":"2009","journal-title":"Nonnegative matrix and tensor factorizations: Applications to exploratory multi-way data analysis and blind source separation"},{"issue":"3","key":"2021072618251417000_B8","doi-asserted-by":"crossref","DOI":"10.1038\/nn.3635","article-title":"Resolving human object recognition in space and time","volume":"17","author":"Cichy","year":"2014","journal-title":"Nature Neuroscience"},{"issue":"4","key":"2021072618251417000_B9","doi-asserted-by":"crossref","first-page":"1523","DOI":"10.1109\/TIT.2005.844059","article-title":"Clustering by compression","volume":"51","author":"Cilibrasi","year":"2005","journal-title":"IEEE Transactions on Information theory"},{"issue":"7\u20138","key":"2021072618251417000_B10","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1002\/cem.1236","article-title":"Tensor decompositions, alternating least squares and other tales","volume":"23","author":"Comon","year":"2009","journal-title":"Journal of Chemometrics"},{"issue":"4","key":"2021072618251417000_B11","doi-asserted-by":"crossref","first-page":"1253","DOI":"10.1137\/S0895479896305696","article-title":"A multilinear singular value decomposition","volume":"21","author":"De Lathauwer","year":"2000","journal-title":"SIAM Journal on Matrix Analysis and Applications"},{"issue":"1","key":"2021072618251417000_B12","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1111\/brv.12433","article-title":"Analysing ecological networks of species interactions","volume":"94","author":"Delmas","year":"2019","journal-title":"Biological Reviews"},{"issue":"9","key":"2021072618251417000_B13","doi-asserted-by":"crossref","DOI":"10.14569\/IJACSA.2013.040902","article-title":"Partition based graph compression.","volume":"4","author":"Dhabu","year":"2013","journal-title":"International Journal of Advanced Computer Science and Applications"},{"journal-title":"Compressing graphs and indexes with recursive graph bisection.","year":"2016","author":"Dhulipala","key":"2021072618251417000_B14"},{"issue":"1","key":"2021072618251417000_B15","doi-asserted-by":"crossref","DOI":"10.1109\/TPAMI.2008.277","article-title":"Convex and semi-nonnegative matrix factorizations.","volume":"32","author":"Ding","year":"2010","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"2021072618251417000_B16","doi-asserted-by":"crossref","first-page":"126","DOI":"10.1145\/1150402.1150420","article-title":"Orthogonal nonnegative matrix t-factorizations for clustering.","author":"Ding","year":"2006","journal-title":"Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining"},{"key":"2021072618251417000_B17","doi-asserted-by":"crossref","first-page":"517","DOI":"10.4153\/CJM-1958-052-0","article-title":"Coverings of bipartite graphs","volume":"10","author":"Dulmage","year":"1958","journal-title":"Canadian Journal of Mathematics"},{"issue":"2","key":"2021072618251417000_B18","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1137\/S0895479895290954","article-title":"The geometry of algorithms with orthogonality constraints","volume":"20","author":"Edelman","year":"1998","journal-title":"SIAM Journal on Matrix Analysis and Applications"},{"key":"2021072618251417000_B19","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1145\/2213836.2213855","article-title":"Query preserving graph compression.","author":"Fan","year":"2012","journal-title":"Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data"},{"issue":"3\u20135","key":"2021072618251417000_B20","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/j.physrep.2009.11.002","article-title":"Community detection in graphs","volume":"486","author":"Fortunato","year":"2010","journal-title":"Physics Reports"},{"issue":"12","key":"2021072618251417000_B21","doi-asserted-by":"crossref","DOI":"10.1371\/journal.pone.0168180","article-title":"Characterizing variability of modular brain connectivity with constrained principal component analysis","volume":"11","author":"Hirayama","year":"2016","journal-title":"PLOS One"},{"issue":"3","key":"2021072618251417000_B22","doi-asserted-by":"crossref","first-page":"445","DOI":"10.1162\/NECO_a_00810","article-title":"Orthogonal connectivity factorization: Interpretable decomposition of variability in correlation matrices","volume":"28","author":"Hyv\u00e4rinen","year":"2016","journal-title":"Neural Computation"},{"key":"2021072618251417000_B23","first-page":"111","article-title":"Pairwise likelihood ratios for estimation of non-gaussian structural equation models","volume":"14","author":"Hyv\u00e4rinen","year":"2013","journal-title":"Journal of Machine Learning Research"},{"key":"2021072618251417000_B24","first-page":"511","volume-title":"Handbook of social economics","author":"Jackson","year":"2011"},{"issue":"3","key":"2021072618251417000_B25","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1137\/07070111X","article-title":"Tensor decompositions and applications","volume":"51","author":"Kolda","year":"2009","journal-title":"SIAM Review"},{"key":"2021072618251417000_B26","doi-asserted-by":"crossref","first-page":"481","DOI":"10.1525\/9780520411586-036","article-title":"Nonlinear programming.","author":"Kuhn","year":"1951","journal-title":"Proceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability"},{"key":"2021072618251417000_B27","first-page":"556","volume-title":"Advances in neural information processing systems","author":"Lee","year":"2001"},{"key":"2021072618251417000_B28","doi-asserted-by":"crossref","first-page":"631","DOI":"10.1145\/1150402.1150479","article-title":"Sampling from large graphs.","author":"Leskovec","year":"2006","journal-title":"Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery And Data Mining"},{"issue":"1","key":"2021072618251417000_B29","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1016\/j.eng.2018.02.004","article-title":"Social influence analysis: Models, methods, and evaluation.","volume":"4","author":"Li","year":"2018","journal-title":"Engineering"},{"issue":"10","key":"2021072618251417000_B30","doi-asserted-by":"crossref","first-page":"1852","DOI":"10.1109\/TKDE.2018.2807843","article-title":"Influence maximization on so cial graphs: A survey","volume":"30","author":"Li","year":"2018","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"issue":"3","key":"2021072618251417000_B31","doi-asserted-by":"crossref","DOI":"10.1145\/3186727","article-title":"Graph summarization methods and applications: A survey","volume":"51","author":"Liu","year":"2018","journal-title":"ACM Computing Surveys"},{"journal-title":"An empirical comparison of the summarization power of graph clustering methods","year":"2015","author":"Liu","key":"2021072618251417000_B32"},{"key":"2021072618251417000_B33","doi-asserted-by":"crossref","first-page":"1755","DOI":"10.1145\/2939672.2939856","article-title":"Scalable pattern matching over compressed graphs via dedensification.","author":"Maccioni","year":"2016","journal-title":"Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining"},{"issue":"4","key":"2021072618251417000_B34","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/j.physrep.2013.08.002","article-title":"Clustering and community detection in directed networks: A survey","volume":"533","author":"Malliaros","year":"2013","journal-title":"Physics Reports"},{"journal-title":"A survey on methods and systems for graph compression.","year":"2015","author":"Maneth","key":"2021072618251417000_B35"},{"key":"2021072618251417000_B36","first-page":"48","article-title":"CSI: Community-level social influence analysis.","author":"Mehmood","year":"2013","journal-title":"Proceedings of the Joint European Conference on Machine Learning and Knowledge Discovery in Databases"},{"key":"2021072618251417000_B37","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1137\/1.9781611972771.13","article-title":"Clustering by weighted cuts in directed graphs.","author":"Meil\u0103","year":"2007","journal-title":"Proceedings of the 2007 SIAM International Conference on Data Mining"},{"key":"2021072618251417000_B38","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1145\/1376616.1376661","article-title":"Graph summarization with bounded error.","author":"Navlakha","year":"2008","journal-title":"Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data"},{"issue":"3","key":"2021072618251417000_B39","doi-asserted-by":"crossref","first-page":"328","DOI":"10.1177\/1075547008328797","article-title":"A two-step flow of influence? Opinion-leader campaigns on climate change","volume":"30","author":"Nisbet","year":"2009","journal-title":"Science Communication"},{"issue":"10","key":"2021072618251417000_B40","doi-asserted-by":"crossref","first-page":"2292","DOI":"10.1016\/j.clinph.2004.04.029","article-title":"Identifying true brain interaction from EEG data using the imaginary part of coherency","volume":"115","author":"Nolte","year":"2004","journal-title":"Clinical Neurophysiology"},{"journal-title":"Subsampling large graphs and invariance in networks","year":"2017","author":"Orbanz","key":"2021072618251417000_B41"},{"issue":"1","key":"2021072618251417000_B42","doi-asserted-by":"crossref","DOI":"10.1186\/1756-0381-4-10","article-title":"Using graph theory to analyze biological networks","volume":"4","author":"Pavlopoulos","year":"2011","journal-title":"BioData Mining"},{"key":"2021072618251417000_B43","doi-asserted-by":"crossref","first-page":"1296","DOI":"10.1145\/2623330.2623701","article-title":"Fast influence-based coarsening for large networks.","author":"Purohit","year":"2014","journal-title":"Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining"},{"issue":"1","key":"2021072618251417000_B44","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/j.cosrev.2007.05.001","article-title":"Graph clustering","volume":"1","author":"Schaeffer","year":"2007","journal-title":"Computer Science Review"},{"key":"2021072618251417000_B45","doi-asserted-by":"crossref","first-page":"1097","DOI":"10.1145\/2487575.2487690","article-title":"Information cartography: Creating zoomable, large-scale maps of information.","author":"Shahaf","year":"2013","journal-title":"Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining"},{"key":"2021072618251417000_B46","doi-asserted-by":"crossref","first-page":"792","DOI":"10.1145\/1102351.1102451","article-title":"Non-negative tensor factorization with applications to statistics and computer vision.","author":"Shashua","year":"2005","journal-title":"Proceedings of the 22nd International Conference on Machine Learning"},{"issue":"8","key":"2021072618251417000_B47","doi-asserted-by":"crossref","first-page":"888","DOI":"10.1109\/34.868688","article-title":"Normalized cuts and image segmentation","volume":"22","author":"Shi","year":"2000","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"2021072618251417000_B48","first-page":"1074","article-title":"Topic: Toward perfect influence graph summarization.","author":"Shi","year":"2016","journal-title":"Proceedings of the 2016 IEEE 32nd International Conference on Data Engineering"},{"key":"2021072618251417000_B49","doi-asserted-by":"crossref","first-page":"983","DOI":"10.1109\/ICDM.2014.128","article-title":"Flow-based influence graph visual summarization.","author":"Shi","year":"2014","journal-title":"2014 IEEE International Conference on Data Mining"},{"issue":"12","key":"2021072618251417000_B50","doi-asserted-by":"crossref","first-page":"3417","DOI":"10.1109\/TKDE.2015.2453957","article-title":"Vegas: Visual influence graph summarization on citation networks","volume":"27","author":"Shi","year":"2015","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"issue":"1","key":"2021072618251417000_B51","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1080\/1350178042000330887","article-title":"Graphical models, causal inference, and econometric models","volume":"12","author":"Spirtes","year":"2005","journal-title":"Journal of Economic Methodology"},{"issue":"11","key":"2021072618251417000_B52","first-page":"572","article-title":"Characterizing dissolved organic matter fluorescence with parallel factor analysis: A tutorial","volume":"6","author":"Stedmon","year":"2008","journal-title":"Limnology and Oceanography: Methods"},{"key":"2021072618251417000_B53","doi-asserted-by":"crossref","first-page":"807","DOI":"10.1145\/1557019.1557108","article-title":"Social influence analysis in large-scale networks.","author":"Tang","year":"2009","journal-title":"Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining"},{"key":"2021072618251417000_B54","article-title":"Local opinion leaders to improve health professional practice and health care outcomes.","volume":"3","author":"Thomson","year":"1998","journal-title":"Cochrane Library"},{"issue":"6","key":"2021072618251417000_B55","doi-asserted-by":"crossref","first-page":"881","DOI":"10.1177\/1090198106297855","article-title":"Identifying opinion leaders to promote behavior change","volume":"34","author":"Valente","year":"2007","journal-title":"Health Education and Behavior"},{"key":"2021072618251417000_B56","first-page":"585","article-title":"Compression picks item sets that matter.","author":"Leeuwen","year":"2006","journal-title":"Proceedings of the European Conference on Principles of Data Mining and Knowledge Discovery"},{"journal-title":"Representing classroom social structure","year":"1981","author":"Vickers","key":"2021072618251417000_B57"},{"issue":"1","key":"2021072618251417000_B58","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1007\/s10618-010-0202-x","article-title":"KRIMP: Mining item sets that compress","volume":"23","author":"Vreeken","year":"2011","journal-title":"Data Mining and Knowledge Discovery"},{"key":"2021072618251417000_B59","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1007\/978-3-642-19656-0_32","article-title":"Tracking communities in dynamic social networks.","author":"Xu","year":"2011","journal-title":"Proceedings of the International Conference on Social Computing, Behavioral-Cultural Modeling, and Prediction"},{"key":"2021072618251417000_B60","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1109\/ISI.2009.5137323","article-title":"Finding leaders from opinion networks.","author":"Zhou","year":"2009","journal-title":"Proceedings of the 2009 IEEE International Conference on Intelligence and Security Informatics"}],"container-title":["Neural Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/direct.mit.edu\/neco\/article-pdf\/33\/8\/2128\/1930917\/neco_a_01402.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/direct.mit.edu\/neco\/article-pdf\/33\/8\/2128\/1930917\/neco_a_01402.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,1]],"date-time":"2024-09-01T11:04:57Z","timestamp":1725188697000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/neco\/article\/33\/8\/2128\/101868\/Direction-Matters-On-Influence-Preserving-Graph"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,26]]},"references-count":60,"journal-issue":{"issue":"8","published-online":{"date-parts":[[2021,7,26]]},"published-print":{"date-parts":[[2021,7,26]]}},"URL":"https:\/\/doi.org\/10.1162\/neco_a_01402","relation":{},"ISSN":["0899-7667","1530-888X"],"issn-type":[{"type":"print","value":"0899-7667"},{"type":"electronic","value":"1530-888X"}],"subject":[],"published-other":{"date-parts":[[2021,8]]},"published":{"date-parts":[[2021,7,26]]}}}