{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,13]],"date-time":"2026-10-13T18:38:17Z","timestamp":1791916697597,"version":"4.3.4"},"reference-count":29,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","funder":[{"DOI":"10.13039\/100006227","name":"Lawrence Livermore National Laboratory","doi-asserted-by":"publisher","award":["DE-AC52-07NA27344"],"award-info":[{"award-number":["DE-AC52-07NA27344"]}],"id":[{"id":"10.13039\/100006227","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006227","name":"Lawrence Livermore National Laboratory","doi-asserted-by":"publisher","award":["B600360"],"award-info":[{"award-number":["B600360"]}],"id":[{"id":"10.13039\/100006227","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000015","name":"U.S. Department of Energy","doi-asserted-by":"publisher","award":["DE-FC02-03ER25574"],"award-info":[{"award-number":["DE-FC02-03ER25574"]}],"id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000015","name":"U.S. Department of Energy","doi-asserted-by":"publisher","award":["DE-NA0002376"],"award-info":[{"award-number":["DE-NA0002376"]}],"id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Sci. Comput."],"published-print":{"date-parts":[[2017,1]]},"abstract":"<jats:p>Recently a new dimension of graphs has manifested in the network science community that goes beyond the traditional notion of connections and disconnections to include both favorable and adverse relationships. There are many applications, such as ranking and clustering, where data scientists are interested in solving linear systems associated with unsigned graphs. We show that there exists a direct relationship between a signed graph and an unsigned variant. Methods that have been applied for unsigned graphs could be applied to signed graphs in a meaningful way. Fairly robust solvers for unsigned, undirected graph Laplacians have been developed, but these solvers are not directly applicable to general, signed graphs. Gremban's expansion [K. Gremban, Combinatorial Preconditioners for Sparse, Symmetric, Diagonally Dominant Linear Systems, Ph.D. thesis and Tech. report CMU-CS-96-123, School of Computer Science, Carnegie Mellon University, Pittsburgh, 1996] is used to transform the signed, undirected graph Laplacian into an unsigned, undirected graph Laplacian with twice the number of unknowns. The solution to the linear system of the expanded matrix yields the solution of the original linear system. Thus, using Gremban's expansion, we can extend the current Laplacian solvers' robustness to signed graph Laplacians. We hope to further motivate data analysts to use signed graph models by providing optimal solvers and showing how they are related to existing unsigned graph mining techniques applied to the graph associated with the Gremban's expansion matrix. Due to the relationship between a signed graph and its unsigned graph via the Gremban expansion matrix, we conduct a preliminary investigation into the application of traditional ranking to the Gremban's expansion matrix. The rankings using Gremban's expansion for a user-movie rating graph change considerably if a signed graph Laplacian is used, indicating that applications such as recommendation systems would attain different and possibly better recommendations if a signed graph was used instead. This paper delves into the numerical stability and applicability of Gremban's expansion and proves that the error of the solution of the original linear system can be tightly bounded by the error of the expanded system. Gremban's expansion was originally created only for symmetric matrices. This paper demonstrates that the expansion is applicable not only to symmetric diagonally dominant matrices but also to nonsymmetric matrices associated with signed, directed graphs. This paper presents numerical tests on signed, undirected graphs. Both manufactured and real-world signed, undirected graph Laplacians are tested with various solvers to show that the expansion is numerically stable.<\/jats:p>","DOI":"10.1137\/16m1082433","type":"journal-article","created":{"date-parts":[[2017,10,26]],"date-time":"2017-10-26T16:24:40Z","timestamp":1509035080000},"page":"S945-S968","source":"Crossref","is-referenced-by-count":5,"title":["Numerical Methods for Gremban's Expansion of Signed Graphs"],"prefix":"10.1137","volume":"39","author":[{"given":"Alyson","family":"Fox","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thomas","family":"Manteuffel","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Geoffrey","family":"Sanders","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2017,10,26]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1145\/312129.312230"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2002.1181947"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2012.10.022"},{"key":"atypb4","first-page":"239","volume-title":"Proceedings of the 2006 Markov Anniversary Meeting","author":"Benzi M.","year":"2006"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1137\/141000671"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993674"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.46"},{"key":"atypb8","unstructured":"K. Gremban,\n                      Combinatorial Preconditioners for Sparse, Symmetric, Diagonally Dominant Linear Systems\n                      , Ph.D. thesis and Tech. report CMU-CS-96-123, School of Computer Science, Carnegie Mellon University, Pittsburgh, 1996."},{"key":"atypb9","first-page":"30","volume-title":"AAAI Spring Symposium: Social Information Processing, Association for the Advancement of Artificial Intelligence","author":"Hogg T.","year":"2008"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827500366124"},{"key":"atypb11","volume-title":"A Parallel Solver for Graph Laplacians, preprint, https:\/\/arxiv.org\/abs\/1705.06266","author":"Konolige T.","year":"2017"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1016\/j.cviu.2011.05.013"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1145\/1526709.1526809"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972801.49"},{"key":"atypb15","volume-title":"SNAP: A General Purpose Network Analysis and Graph Mining Library in C\\textup++","author":"Leskovec J.","year":"2014"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1137\/110843563"},{"key":"atypb17","first-page":"201","volume":"45","author":"Napov A.","year":"2016","journal-title":"Electron. Trans. Numer. Anal."},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1137\/16M1071420"},{"key":"atypb19","unstructured":"L. Page, S. Brin, R. Motwani, and T. Winograd,\n                      The PageRank Citation Ranking: Bringing Order to the Web\n                      , Tech. Report 1999-66 (previous number: SIDL-WP-1999-0120), Stanford InfoLab, Stanford, CA, 1999."},{"key":"atypb20","volume-title":"An Investigation into LAMG","author":"Sanders G.","year":"2015"},{"key":"atypb21","first-page":"602690","volume":"2015","author":"Shahriary S. R.","year":"2015","journal-title":"Sci. Program."},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1137\/080719157"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1137\/070685142"},{"key":"atypb24","first-page":"225","volume":"30","author":"de Sterck H.","year":"2011","journal-title":"Comput. Inform."},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150448"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1007\/s11222-007-9033-z"},{"key":"atypb27","first-page":"274","volume-title":"Proceedings of the 2005 SIAM International Conference on Data Mining, SIAM","author":"White S."},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-20847-8_1"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.1061"}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/16M1082433","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T16:11:46Z","timestamp":1787328706000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/16M1082433"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,1]]},"references-count":29,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2017,1]]}},"alternative-id":["10.1137\/16M1082433"],"URL":"https:\/\/doi.org\/10.1137\/16m1082433","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,1]]}}}