Given a heterogeneous information network (HIN) and a query meta-path P of length i, the densest P-partite subgraph problem finds the subgraph, spanning the i typed layers of P, that maximizes a parameter-free density: the number of meta-path instances over the geometric mean of the layer sizes. It has applications across bibliographic, e-commerce, and biomedical networks. The state-of-the-art approximation linearizes the geometric-mean objective by fixing per-layer weights, but solves one subproblem for every feasible weight set, of which there are $O((n/i)^i)$, and on each achieves only a $1/i$ approximation. We show that neither the exhaustive enumeration nor the loose guarantee is necessary. First, we replace enumeration by covering: polylogarithmically many representative weight sets, localized further by a data-dependent bound, cover all feasible ones while losing only a tunable factor $1+\eta$ in density. Second, we cast each fixed-weight subproblem as a weighted supermodular densest-subgraph instance and solve it near-optimally, lifting the overall guarantee to $(1-\delta)/(1+\eta)$. To our knowledge, this is the first near-optimal density approximation beyond the bipartite ($i=2$) case, and it yields a PTAS for every fixed i. Algorithmically, our solver is an adaptive peeling scheme that never materializes the meta-path instances, whose number can exceed the graph size by orders of magnitude. An incumbent-driven reduction further discards representative weight sets before their subproblems are solved. Experiments on five real HINs show that our algorithms achieve substantial speedups over enumeration-based baselines and can further certify the near-optimality of the returned subgraph.
Lu Chen, Chengfei Liu, Rui Zhou et al.· 0 citations
Integrating structured knowledge graphs (KGs) with Large Language Models (LLMs) is essential for trustworthy, knowledge intensive conversational systems. However, existing Retrieval Augmented Generation (RAG) methods typically rely on a retrieval-as-context paradigm that linearizes structured subgraphs into unstructured prompt tokens. This approach not only flattens rich structural dependencies but also leads to context inflation and evidence attenuation in multi-turn dialogues. To address these limitations, we propose KGA-LM, a framework that integrates external knowledge via representation-level grounding. Rather than treating retrieved evidence as transient input artifacts, KGA-LM encodes compact multi-hop subgraphs using a Graph Transformer and fuses them into the LLM decoder through a compatibility-aware latent interface. This design aligns the heterogeneous latent spaces of the graph encoder and the LLM, while a dual-gated fusion mechanism dynamically regulates the influence of non-parametric graph evidence across turns. Experiments on multiple conversational benchmarks demonstrate that KGA-LM significantly improves factual accuracy and reduces hallucination compared to prompt-linearized baselines. Crucially, by decoupling knowledge injection from prompt length, our approach mitigates retrieval signal decay under long contexts, offering a superior trade-off between grounding quality and inference efficiency.
Yunfei Li, Chengfei Liu, Rui Zhou et al.· Proceedings of the 32nd ACM...· 0 citations
By decoupling knowledge injection from prompt length, the KGA-LM approach mitigates retrieval signal decay under long contexts, offering a superior trade-off between grounding quality and inference efficiency.
Yunfei Li, Chengfei Liu, Rui Zhou et al.· Proceedings of the 32nd ACM...· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
