{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,7]],"date-time":"2026-07-07T15:55:24Z","timestamp":1783439724149,"version":"3.54.6"},"publisher-location":"California","reference-count":0,"publisher":"International Joint Conferences on Artificial Intelligence Organization","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023,8]]},"abstract":"<jats:p>In recent years, graph Transformers (GTs) have been demonstrated as a robust architecture for a wide range of graph learning tasks. However, the quadratic complexity of GTs limits their scalability on large-scale data, in comparison to Graph Neural Networks (GNNs). In this work, we propose the Kernel Decomposition Linear Graph Transformer (KDLGT), an accelerating framework for building scalable and powerful GTs. KDLGT employs the kernel decomposition approach to rearrange the order of matrix multiplication, thereby reducing complexity to linear. Additionally, it categorizes GTs into three distinct types and provides tailored accelerating methods for each category to encompass all types of GTs. Furthermore, we provide a theoretical analysis of the performance gap between KDLGT and self-attention to ensure its effectiveness. Under this framework, we select two representative GTs to design our models. Experiments on both real-world and synthetic datasets indicate that KDLGT not only achieves state-of-the-art performance on various datasets but also reaches an acceleration ratio of approximately 10 on graphs of certain sizes.<\/jats:p>","DOI":"10.24963\/ijcai.2023\/263","type":"proceedings-article","created":{"date-parts":[[2023,8,11]],"date-time":"2023-08-11T08:31:30Z","timestamp":1691742690000},"page":"2370-2378","source":"Crossref","is-referenced-by-count":3,"title":["KDLGT: A Linear Graph Transformer Framework via Kernel Decomposition Approach"],"prefix":"10.24963","author":[{"given":"Yi","family":"Wu","sequence":"first","affiliation":[{"name":"Academy for Advanced Interdisciplinary Studies, Peking University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yanyang","family":"Xu","sequence":"additional","affiliation":[{"name":"School of Software and Microelectronics, Peking University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wenhao","family":"Zhu","sequence":"additional","affiliation":[{"name":"National Key Lab of General AI, School of Intelligence Science and Technology, Peking University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Guojie","family":"Song","sequence":"additional","affiliation":[{"name":"National Key Lab of General AI, School of Intelligence Science and Technology, Peking University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zhouchen","family":"Lin","sequence":"additional","affiliation":[{"name":"National Key Lab of General AI, School of Intelligence Science and Technology, Peking University"},{"name":"Institute for Artificial Intelligence, Peking University"},{"name":"Peng Cheng Laboratory"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Liang","family":"Wang","sequence":"additional","affiliation":[{"name":"Alibaba Group, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shaoguo","family":"Liu","sequence":"additional","affiliation":[{"name":"Alibaba Group, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"10584","event":{"name":"Thirty-Second International Joint Conference on Artificial Intelligence {IJCAI-23}","theme":"Artificial Intelligence","location":"Macau, SAR China","acronym":"IJCAI-2023","number":"32","sponsor":["International Joint Conferences on Artificial Intelligence Organization (IJCAI)"],"start":{"date-parts":[[2023,8,19]]},"end":{"date-parts":[[2023,8,25]]}},"container-title":["Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence"],"original-title":[],"deposited":{"date-parts":[[2023,8,11]],"date-time":"2023-08-11T08:43:22Z","timestamp":1691743402000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ijcai.org\/proceedings\/2023\/263"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2023,8]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/ijcai.2023\/263","relation":{},"subject":[],"published":{"date-parts":[[2023,8]]}}}