arXiv:2510.22479cs.LG2025-10NeurIPS

用可学习的离散编码实现高效图检索,精度与速度更优。

Contextual Tokenization for Graph Inverted Indices

  • 基于上下文表示生成可微分的二值编码,构建类似文本索引的图索引
  • 在多个数据集上达到更高检索精度,且查询速度比基线快2倍以上
  • 适合需要大规模图搜索的应用,如生物网络、知识图谱分析

从大型图语料库中检索包含给定查询图同构子图的图,是众多实际应用的核心操作。尽管近年来多向量图表示和基于集合对齐与包含的评分方法能提供高精度的子图同构检测,但其在检索中的应用受限于需对语料库图进行穷举评分。我们提出CORGII(用于倒排索引的图上下文表示),一种从上下文稠密图表示出发,通过可微分离散化模块在学习的隐空间词汇表上生成稀疏二值码的图索引框架。这种类文本文档的表示使我们能够利用经典且高度优化的倒排索引,同时支持软(向量)集合包含评分。进一步地,我们将传统固定影响权重(如TF-IDF、BM25)替换为数据驱动的可训练影响权重。最后,我们探索了词元扩展,以支持多探查索引,实现更平滑的精度-效率权衡。据我们所知,CORGII是首个使用离散词元映射到高效倒排列表的稠密图表示索引器。大量实验表明,相比多个基线,CORGII在精度与效率之间提供了更优的平衡。

原文摘要 · Abstract (English)

Retrieving graphs from a large corpus, that contain a subgraph isomorphic to a given query graph, is a core operation in many real-world applications. While recent multi-vector graph representations and scores based on set alignment and containment can provide accurate subgraph isomorphism tests, their use in retrieval remains limited by their need to score corpus graphs exhaustively. We introduce CORGII (Contextual Representation of Graphs for Inverted Indexing), a graph indexing framework in which, starting with a contextual dense graph representation, a differentiable discretization module computes sparse binary codes over a learned latent vocabulary. This text document-like representation allows us to leverage classic, highly optimized inverted indices, while supporting soft (vector) set containment scores. Pushing this paradigm further, we replace the classical, fixed impact weight of a `token' on a graph (such as TFIDF or BM25) with a data-driven, trainable impact weight. Finally, we explore token expansion to support multi-probing the index for smoother accuracy-efficiency tradeoffs. To our knowledge, CORGII is the first indexer of dense graph representations using discrete tokens mapping to efficient inverted lists. Extensive experiments show that CORGII provides better trade-offs between accuracy and efficiency, compared to several baselines.

图检索倒排索引可学习编码子图匹配

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。