{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,11]],"date-time":"2026-01-11T04:35:58Z","timestamp":1768106158877,"version":"3.49.0"},"reference-count":82,"publisher":"Association for Computing Machinery (ACM)","issue":"ICFP","license":[{"start":{"date-parts":[[2021,8,19]],"date-time":"2021-08-19T00:00:00Z","timestamp":1629331200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["1942711,1718997"],"award-info":[{"award-number":["1942711,1718997"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2021,8,22]]},"abstract":"<jats:p>Graph analytics elicits insights from large graphs to inform critical decisions for business, safety and security. Several large-scale graph processing frameworks feature efficient runtime systems; however, they often provide programming models that are low-level and subtly different from each other. Therefore, end users can find implementation and specially optimization of graph analytics error-prone and time-consuming. This paper regards the abstract interface of the graph processing frameworks as the instruction set for graph analytics, and presents Grafs, a high-level declarative specification language for graph analytics and a synthesizer that automatically generates efficient code for five high-performance graph processing frameworks. It features novel semantics-preserving fusion transformations that optimize the specifications and reduce them to three primitives: reduction over paths, mapping over vertices and reduction over vertices. Reductions over paths are commonly calculated based on push or pull models that iteratively apply kernel functions at the vertices. This paper presents conditions, parametric in terms of the kernel functions, for the correctness and termination of the iterative models, and uses these conditions as specifications to automatically synthesize the kernel functions. Experimental results show that the generated code matches or outperforms handwritten code, and that fusion accelerates execution.<\/jats:p>","DOI":"10.1145\/3473588","type":"journal-article","created":{"date-parts":[[2021,8,19]],"date-time":"2021-08-19T10:44:29Z","timestamp":1629369869000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Grafs: declarative graph analytics"],"prefix":"10.1145","volume":"5","author":[{"given":"Farzin","family":"Houshmand","sequence":"first","affiliation":[{"name":"University of California at Riverside, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mohsen","family":"Lesani","sequence":"additional","affiliation":[{"name":"University of California at Riverside, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Keval","family":"Vora","sequence":"additional","affiliation":[{"name":"Simon Fraser University, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,8,19]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3129246"},{"key":"e_1_2_2_2_1","volume-title":"Mukund Raghothaman, Sanjit A Seshia, Rishabh Singh, Armando Solar-Lezama, Emina Torlak, and Abhishek Udupa.","author":"Alur Rajeev","year":"2013"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1168918.1168906"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2814228.2814235"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/2682923.2682937"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1375581.1375595"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10703-016-0256-5"},{"key":"e_1_2_2_8_1","volume-title":"Efficient Synthesis for Concurrency by Semantics-Preserving Transformations","author":"Cerny Pavol"},{"key":"e_1_2_2_9_1","volume-title":"Regression-Free Synthesis for Concurrency","author":"Cerny Pavol"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/CLUSTER.2017.72"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1379022.1375619"},{"key":"e_1_2_2_12_1","doi-asserted-by":"crossref","unstructured":"Wei-Ngan Chin. 1992. Safe fusion of functional expressions. In ACM SIGPLAN Lisp Pointers. 11\u201320.  Wei-Ngan Chin. 1992. Safe fusion of functional expressions. In ACM SIGPLAN Lisp Pointers. 11\u201320.","DOI":"10.1145\/141478.141494"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2975991.2976000"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2851141.2851153"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068414000167"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-78791-4_19"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/PACT.1999.807510"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3192366.3192404"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3022670.2951938"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3093333.3009851"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/165180.165214"},{"key":"e_1_2_2_22_1","volume-title":"Abelian: A Compiler for Graph Analytics on Distributed, Heterogeneous Platforms. In Euro-Par 2018: Parallel Processing","author":"Gill Gurbinder","year":"2018"},{"key":"e_1_2_2_24_1","volume-title":"Powergraph: Distributed graph-parallel computation on natural graphs. In Presented as part of the 10th $USENIX$ Symposium on Operating Systems Design and Implementation ($OSDI$ 12). 17\u201330.","author":"Gonzalez Joseph E","year":"2012"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3200691.3178506"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1925844.1926423"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2240236.2240260"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/PACT.2007.4336225"},{"key":"e_1_2_2_29_1","first-page":"51","article-title":"A Declarative Approach to Automated Configuration","volume":"12","author":"Hewson John A","year":"2012","journal-title":"LISA."},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293883.3295729"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2248487.2151013"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3290387"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1932682.1869463"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806799.1806833"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1018956702672"},{"key":"e_1_2_2_36_1","doi-asserted-by":"crossref","unstructured":"Rajeev Joshi Greg Nelson and Keith Randall. 2002. Denali: a goal-directed superoptimizer. 37 ACM.  Rajeev Joshi Greg Nelson and Keith Randall. 2002. Denali: a goal-directed superoptimizer. 37 ACM.","DOI":"10.1145\/512529.512566"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1186632.1186633"},{"key":"e_1_2_2_38_1","volume-title":"International Workshop on Languages and Compilers for Parallel Computing. 301\u2013320","author":"Kennedy Ken","year":"1993"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24723-4_20"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.14778\/2212351.2212354"},{"key":"e_1_2_2_41_1","volume-title":"Graphlab: A new framework for parallel machine learning. arXiv preprint arXiv:1408.2041.","author":"Low Yucheng","year":"2014"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_2_2_43_1","volume-title":"Proceedings of the European Conference on Computer Systems (EuroSys \u201921)","author":"Mariappan Mugilan","year":"2021"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3302424.3303974"},{"key":"e_1_2_2_45_1","doi-asserted-by":"crossref","volume-title":"Superoptimizer \u2013 a Look at the Smallest Program","author":"Massalin Harry","DOI":"10.1145\/36206.36194"},{"key":"e_1_2_2_46_1","doi-asserted-by":"crossref","volume-title":"Optimizing Declarative Parallel Distributed Graph Processing by Using Constraint Solvers","author":"Morihata Akimasa","DOI":"10.1007\/978-3-319-90686-7_11"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522739"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2813885.2738007"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2908080.2908093"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2398857.2384644"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2813885.2737953"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/1183401.1183437"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.5555\/3014904.3014958"},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/2892208.2892228"},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-18378-2"},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/2815072.2815073"},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522740"},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/3140587.3062362"},{"key":"e_1_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/3133900"},{"key":"e_1_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/3314221.3314626"},{"key":"e_1_2_2_61_1","volume-title":"Souper: A synthesizing superoptimizer. arXiv preprint arXiv:1711.04422.","author":"Sasnauskas Raimondas","year":"2017"},{"key":"e_1_2_2_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/2499368.2451150"},{"key":"e_1_2_2_63_1","doi-asserted-by":"publisher","DOI":"10.14778\/3007263.3007265"},{"key":"e_1_2_2_64_1","volume-title":"International Workshop on Languages and Compilers for Parallel Computing. 235\u2013249","author":"Shashidhar G","year":"2016"},{"key":"e_1_2_2_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/3290386"},{"key":"e_1_2_2_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/2442516.2442530"},{"key":"e_1_2_2_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/2980983.2908102"},{"key":"e_1_2_2_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/1064978.1065045"},{"key":"e_1_2_2_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/1168918.1168907"},{"key":"e_1_2_2_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/1707801.1706337"},{"key":"e_1_2_2_71_1","doi-asserted-by":"publisher","DOI":"10.1145\/2499370.2462174"},{"key":"e_1_2_2_72_1","doi-asserted-by":"publisher","DOI":"10.1145\/2960414.2960421"},{"key":"e_1_2_2_73_1","doi-asserted-by":"publisher","DOI":"10.1145\/1379022.1375598"},{"key":"e_1_2_2_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/1707801.1706338"},{"key":"e_1_2_2_75_1","volume-title":"Lumos: Dependency-Driven Disk-based Graph Processing. In USENIX Annual Technical Conference (USENIX ATC \u201919)","author":"Vora Keval","year":"2019"},{"key":"e_1_2_2_76_1","doi-asserted-by":"publisher","DOI":"10.1145\/3037697.3037748"},{"key":"e_1_2_2_77_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-19027-9_23"},{"key":"e_1_2_2_78_1","doi-asserted-by":"publisher","DOI":"10.1145\/3140587.3062365"},{"key":"e_1_2_2_79_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2014.31"},{"key":"e_1_2_2_80_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-71237-6_15"},{"key":"e_1_2_2_81_1","doi-asserted-by":"publisher","DOI":"10.1145\/3276491"},{"key":"e_1_2_2_82_1","volume-title":"Gemini: A computation-centric distributed graph processing system. In 12th $USENIX$ Symposium on Operating Systems Design and Implementation ($OSDI$ 16). 301\u2013316.","author":"Zhu Xiaowei","year":"2016"},{"key":"e_1_2_2_83_1","volume-title":"Gridgraph: Large-scale graph processing on a single machine using 2-level hierarchical partitioning. In 2015 $USENIX$ Annual Technical Conference ($USENIX$$ATC$ 15). 375\u2013386.","author":"Zhu Xiaowei","year":"2015"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3473588","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3473588","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3473588","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:28:16Z","timestamp":1750195696000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3473588"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,19]]},"references-count":82,"journal-issue":{"issue":"ICFP","published-print":{"date-parts":[[2021,8,22]]}},"alternative-id":["10.1145\/3473588"],"URL":"https:\/\/doi.org\/10.1145\/3473588","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,8,19]]},"assertion":[{"value":"2021-08-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}