Scaling GraphLLM with Bilevel-Optimized Sparse Querying
This addresses the practical limitation of computational expense for researchers and practitioners applying GraphLLM methods, though it is incremental as it optimizes an existing approach.
The paper tackles the high computational cost of using LLMs for node-level tasks on text-attributed graphs by proposing BOSQ, a framework that selectively queries LLMs, achieving orders of magnitude speedups while maintaining or improving performance.
LLMs have recently shown strong potential in enhancing node-level tasks on text-attributed graphs (TAGs) by providing explanation features. However, their practical use is severely limited by the high computational and monetary cost of repeated LLM queries. To illustrate, naively generating explanations for all nodes on a medium-sized benchmark like Photo (48k nodes) using a representative method (e.g., TAPE) would consume days of processing time. In this paper, we propose Bilevel-Optimized Sparse Querying (BOSQ), a general framework that selectively leverages LLM-derived explanation features to enhance performance on node-level tasks on TAGs. We design an adaptive sparse querying strategy that selectively decides when to invoke LLMs, avoiding redundant or low-gain queries and significantly reducing computation overhead. Extensive experiments on six real-world TAG datasets involving two types of node-level tasks demonstrate that BOSQ achieves orders of magnitude speedups over existing GraphLLM methods while consistently delivering on-par or superior performance.