IP Library › Granted Patent US 12,511,325
Granted Patent B2
US 12,511,325 · App. 18/647,297 · Granted Dec 30, 2025

Reranking documents based on graph representations of the documents

Inventors: Anton Tsitsulin (Jersey City, NJ); Bryan Thomas Perozzi (Cranford, NJ); Bahare Fatemi (Montreal, CA); Jialin Dong (Los Angeles, CA)
Assignee: GOOGLE LLC
G06F16/338G06F16/35G06F16/9024
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 12,511,325
App. No.
18/647,297
Granted
Dec 30, 2025
Kind
B2
Abstract

A computer-implemented method includes: in response to receiving a query, retrieving a plurality of documents; generating a first graph representation which graphically represents the plurality of documents utilizing a plurality of nodes indicating a concept and a plurality of edges indicating a relationship between at least two nodes among the plurality of nodes; generating a second graph representation with respect to the plurality of documents, based on connection information associated with the first graph representation; ranking the plurality of documents, based on the second graph representation; and applying one or more machine-learned models to generate a response to the query based on the plurality of documents ranked based on the second graph representation.

Claims (47)

1 . A computer-implemented method, comprising:

in response to receiving a query, retrieving, by a computing system comprising one or more processors, a plurality of documents stored in one or more databases;

generating, by the computing system, a first graph representation which graphically represents the plurality of documents utilizing a plurality of nodes indicating a concept and a plurality of edges indicating a relationship between at least two nodes among the plurality of nodes;

generating, by the computing system, a second graph representation with respect to the plurality of documents, based on connection information associated with the first graph representation, the connection information representing structural information and semantic information between nodes among the plurality of nodes representing the plurality of documents;

ranking, by the computing system, the plurality of documents, based on the second graph representation; and

applying, by the computing system, one or more first machine-learned models, to generate a response to the query based on the plurality of documents ranked based on the second graph representation.

2 . The computer-implemented method of claim 1 , wherein

the first graph representation includes an abstract meaning representation (AMR) graph, and

the second graph representation includes a document graph generated based on AMR connection information.

3 . The computer-implemented method of claim 2 , wherein generating the second graph representation including the document graph comprises removing isolated nodes from the document graph.

4 . The computer-implemented method of claim 2 , wherein generating the second graph representation comprises generating document embeddings for the plurality of documents by encoding a concatenation of each document with the connection information.

5 . The computer-implemented method of claim 2 , wherein the connection information includes one or more single source shortest paths from a first node among the plurality of nodes to one or more other nodes among the plurality of nodes.

6 . The computer-implemented method of claim 5 , wherein

the first node is a question node, and

each of the one or more single source shortest paths start from the question node.

7 . The computer-implemented method of claim 2 , further comprising applying one or more second machine-learned models to update the second graph representation for each of a plurality of layers of the one or more second machine-learned models by applying a function that aggregates a representation of a first node from the document graph and one or more neighboring nodes of the first node from the document graph.

8 . The computer-implemented method of claim 7 , wherein the one or more second machine-learned models include one or more graph neural networks.

9 . The computer-implemented method of claim 8 , the one or more graph neural networks include one or more 2-layer graph convolutional networks.

10 . The computer-implemented method of claim 1 , wherein

at least some documents from among the plurality of documents correspond to a passage from a text corpus, the passage having a predetermined length.

11 . The computer-implemented method of claim 1 , wherein retrieving the plurality of documents comprises implementing a dense embedding-based passage retrieval model to extract the plurality of documents in an open-domain question answering environment.

12 . The computer-implemented method of claim 1 , wherein ranking the plurality of documents is based on the second graph representation and a pairwise loss function.

13 . A computing system, comprising:

one or more processors; and

one or more non-transitory computer-readable media that store instructions that, when executed by the one or more processors, cause the computing system to perform operations, the operations comprising:

in response to receiving a query, retrieving a plurality of documents stored in one or more databases;

generating a first graph representation which graphically represents the plurality of documents utilizing a plurality of nodes indicating a concept and a plurality of edges indicating a relationship between at least two nodes among the plurality of nodes;

generating a second graph representation with respect to the plurality of documents, based on connection information associated with the first graph representation, the connection information representing structural information and semantic information between nodes among the plurality of nodes representing the plurality of documents;

ranking the plurality of documents, based on the second graph representation; and

applying one or more machine-learned models to generate a response to the query based on the plurality of documents ranked based on the second graph representation.

14 . The computing system of claim 13 , wherein

the first graph representation includes an abstract meaning representation (AMR) graph, and

the second graph representation includes a document graph generated based on AMR connection information.

15 . The computing system of claim 14 , wherein generating the second graph representation including the document graph comprises removing isolated nodes from the document graph.

16 . The computing system of claim 14 , wherein generating the second graph representation comprises generating document embeddings for the plurality of documents by encoding a concatenation of each document with the connection information.

17 . The computing system of claim 14 , wherein the connection information includes one or more single source shortest paths from a first node among the plurality of nodes to one or more other nodes among the plurality of nodes.

18 . The computing system of claim 14 , wherein the operations further comprise:

applying one or more second machine-learned models to update the second graph representation for each of a plurality of layers of the one or more second machine-learned models by applying a function that aggregates a representation of a first node from the document graph and one or more neighboring nodes of the first node from the document graph.

19 . The computing system of claim 18 , wherein

the one or more second machine-learned models include one or more graph neural networks, and

the one or more graph neural networks include one or more 2-layer graph convolutional networks.

20 . One or more non-transitory computer-readable media that collectively store instructions that, when executed by one or more processors, cause the one or more processors to perform operations, the operations comprising:

in response to receiving a query, retrieving a plurality of documents stored in one or more databases;

generating a first graph representation which graphically represents the plurality of documents utilizing a plurality of nodes indicating a concept and a plurality of edges indicating a relationship between at least two nodes among the plurality of nodes;

generating a second graph representation with respect to the plurality of documents, based on connection information associated with the first graph representation, the connection information representing structural information and semantic information between nodes among the plurality of nodes representing the plurality of documents;

ranking the plurality of documents, based on the second graph representation; and

applying one or more machine-learned models to generate a response to the query based on the plurality of documents ranked based on the second graph representation.

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Sep 8, 2024
From: TSITSULIN, ANTON; PEROZZI, BRYAN THOMAS; FATEMI, BAHARE; DONG, JIALIN
To: GOOGLE LLC
Reel/Frame 068520/0287 →
Continuity (1)
Related Publication 20250335486A1 · Oct 30, 2025
References Cited (59)
US 9892110B2 · Sexton · 2018 [cited by examiner]
US 10810193B1 · Subramanya · 2020 [cited by examiner]
US 11615152B2 · Haldar · 2023 [cited by examiner]
US 11669556B1 · Hasan · 2023 [cited by examiner]
US 20070185910A1 · Koike · 2007 [cited by examiner]
US 20140372956A1 · Bisca · 2014 [cited by examiner]
US 20220318316A1 · Haldar · 2022 [cited by examiner]
US 20230252234A1 · Hoang · 2023 [cited by examiner]
US 20240126988A1 · Amin · 2024 [cited by examiner]
Asai et al., “Learning to Retrieve Reasoning Paths Over Wikipedia Graph for Question Answering”, arXiv:1911.10470v2, Feb. 14, 2020, 22 pages. [cited by applicant]
Bai et al., “Graph Pre-Training for AMR Parsing and Generation”, arXiv:2203.07836v4, May 4, 2022, 15 pages. [cited by applicant]
Bai et al., “Semantic Representation for Dialogue Modeling”, arXiv:2105.10188v2, Jun. 1, 2021, 16 pages. [cited by applicant]
Banarescu, “Abstract Meaning Representation for Sembanking”, Seventh Linguistic Annotation Workshop and Interoperability with Discourse, Sofia, Bulgaria, Aug. 8-9, 2013, 9 pages. [cited by applicant]
Costa et al., “Leveraging Knowledge Graph for Open-Domain Question Answering”, 2018 Institute of Electrical and Electronics Engineers /WIC/ Association for Computing Machinery International Conference on Web Intelligenc… [cited by applicant]
Devlin et al., “BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding”, arXiv:1810.04805v2, May 24, 2019, 16 pages. [cited by applicant]
Dong et al., “Don't Forget to Connect! Improving RAG with Graph-based Reranking”, arXiv:2405.18414v1, May 28, 2024, 19 pages. [cited by applicant]
Glass et al., “Re2G: Retrieve, Rerank, Generate”, arXiv:2207.06300v1, Jul. 13, 2022, 15 pages. [cited by applicant]
Gong et al., “Exploiting Edge Features for Graph Neural Networks”, arXiv: 1809.02709v2, Jan. 28, 2019, 10 pages. [cited by applicant]
Google et al., “PaLM 2 Technical Report”, arXiv:2305.10403v3, Sep. 13, 2023, 93 pages. [cited by applicant]
Hamilton, “Inductive Representation Learning on Large Graphs”, arXiv:1706.02216v4, Sep. 10, 2018, 19 pages. [cited by applicant]
Huang et al., “DSQA-LLM: Domain-Specific Intelligent Question Answering Based on Large Language Model”, International Conference on AI-generated Content, Shanghai, China, Aug. 25-26, 2023. [cited by applicant]
Izacard et al., “Leveraging Passage Retrieval with Generative Models for Open Domain Question Answering”, arXiv:2007.01282v2, Feb. 3, 2021, 6 pages. [cited by applicant]
Joshi et al., “TriviaQA: A Large Scale Distantly Supervised Challenge Dataset for Reading Comprehension”, arXiv:1705.03551v2, May 13, 2017, 11 pages. [cited by applicant]
Ju et al., “Grape: Knowledge Graph Enhanced Passage Reader for Open-Domain Question Answering”, arXiv:2210.02933v2, Oct. 10, 2022, 13 pages. [cited by applicant]
Karpukhin et al., “Dense Passage Retrieval for Open-Domain Question Answering”, arXiv:2004.04906v3, Sep. 30, 2020, 13 pages. [cited by applicant]
Kipf, “Semi-Supervised Classification with Graph Convolutional Networks”, arXiv:1609.02907v4, Feb. 22, 2017, 14 pages. [cited by applicant]
Kwiatkowski et al., “Natural Questions: A Benchmark for Question Answering Research”, Transactions of the Association for Computational Linguistics, vol. 7, Apr. 2, 2019, 14 pages. [cited by applicant]
LangChain, “Enhancing RAG-Based Application Accuracy by Constructing and Leveraging Knowledge Graphs”, Mar. 15, 2024, https://blog.langchain.dev/enhancing-rag-based-applications-accuracy-by-constructing-and-leveraging-k… [cited by applicant]
Lewis et al., “BART: Denoising Sequence-to-Sequence Pretraining for Natural Language Generation, Translation, and Comprehension”, arXiv:1910.13461v1, Oct. 29, 2019, 10 pages. [cited by applicant]
Lewis et al., “Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks”, arXiv:2005.11401v4, Apr. 12, 2021, 19 pages. [cited by applicant]
Li et al., “Improving Pairwise Ranking for Multi-Label Image Classification”, arXiv:1704.03135v3, Jun. 1, 2017, 9 pages. [cited by applicant]
Li et al., “Towards General Text Embeddings with Multi-Stage Contrastive Learning”, arXiv:2308.03281v1, Aug. 7, 2023, 18 pages. [cited by applicant]
Liu et al., “RoBERTa: A Robustly Optimized BERT Pretraining Approach”, arXiv:1907.11692v1, Jul. 26, 2019, 13 pages. [cited by applicant]
Loshchilov et al., “Decoupled Weight Decay Regularization”, arXiv:1711.05101v3, Jan. 4, 2019, 19 pages. [cited by applicant]
Ma et al., Fine-Tuning LLaMA for Multi-Stage Text Retrieval , arXiv:2310.08319v1, Oct. 12, 2023, 12 pages. [cited by applicant]
Microsoft Research Blog, “GraphRAG: Unlocking LLM Discovery on Narrative Private data”, Feb. 13, 2024, https://www.microsoft.com/en-us/research/blog/graphrag-unlocking-llm-discovery-on-narrative-private-data/, retrieved… [cited by applicant]
Naseem et al., “DocAMR: Multi-Sentence AMR Representation and Evaluation”, arXiv:2112.08513v2, May 6, 2022, 10 pages. [cited by applicant]
Nogueira et al., “Document Ranking with a Pretrained Sequence-to-Sequence Model”, arXiv:2003.06713v1, Mar. 14, 2020, 8 pages. [cited by applicant]
OpenAI, “GPT-4 is OpenAI's Most Advanced System, Producing Safer and More Useful Responses”, https://openai.com/gpt-4, retrieved on Jun. 17, 2024, 7 pages. [cited by applicant]
OpenAI, “Pioneering Research on the Path to AGI”, https://openai.com/research/, retrieved on Jun. 17, 2024. [cited by applicant]
Park et al., “RINK: Reader-Inherited Evidence Reranker for Table-and-Text Open Domain Question Answering”, Thirty-Seventh Association for the Advancement of Artificial Intelligence Conference on Artificial Intelligence,… [cited by applicant]
Pradeep et al., “Squeezing Water from a Stone: A Bag of Tricks for Further Improving Cross-Encoder Effectiveness for Reranking”, Forty-Fourth European Conference on Information Retrieval, Stavanger, Norway, Apr. 10-14, … [cited by applicant]
Siriwardhana et al., “Improving the Domain Adaptation of Retrieval Augmented Generation (RAG) Models for Open Domain Question Answering”, arXiv:2210.02627v1, Oct. 6, 2022, 15 pages. [cited by applicant]
Tan et al., “Can ChatGPT Replace Traditional KBQA Models? An In-Depth Analysis of The Question Answering Performance of The Gpt LLM Family”, arXiv:2303.07992v3, Sep. 20, 2023, 20 pages. [cited by applicant]
Touvron et al., “LLaMA: Open and Efficient Foundation Language Models”, arXiv:2302.13971v1, Feb. 27, 2023, 27 pages. [cited by applicant]
Veličković et al., “Graph Attention Networks”, arXiv:1710.10903v3, Feb. 4, 2018, 12 pages. [cited by applicant]
Voorhees et al., “The TREC-8 Question Answering Track”, Second International Conference on Language Resources and Evaluation (LREC'00), Athens, Greece, May 31-Jun. 2, 2000, 8 pages. [cited by applicant]
Wang et al., “Evaluating Open-QA Evaluation”, arXiv:2305.12421v4, Oct. 23, 2023, 28 pages. [cited by applicant]
Wang et al., “Exploiting Abstract Meaning Representation for Open-Domain Question Answering”, arXiv:2305.17050v1, May 26, 2023, 12 pages. [cited by applicant]
Wolf et al., “HuggingFace's Transformers: State-of-the-Art Natural Language Processing”, arXiv:1910.03771v5, Jul. 14, 2020, 8 pages. [cited by applicant]
Xiao et al., “C-Pack: Packaged Resources to Advance General Chinese Embedding”, arXiv:2309.07597v4, May 12, 2024, 9 pages. [cited by applicant]
Xiao et al., “RetroMAE: Pre-Training Retrieval-Oriented Transformers Via Masked Auto-Encoder”, arXiv:2205.12035v2, Oct. 17, 2022, 11 pages. [cited by applicant]
Xu et al., “How Powerful are Graph Neural Networks?” arXiv:1810.00826v3, Feb. 22, 2019, 17 pages. [cited by applicant]
Yu et al., “KG-FiD: Infusing Knowledge Graph in Fusion-In-Decoder for Open-Domain Question Answering”, arXiv:2110.04330v2, Jun. 6, 2022, 14 pages. [cited by applicant]
Zhuang et al., “RankT5: Fine-Tuning T5 for Text Ranking with Ranking Losses”, arXiv:2210.10634v1, Oct. 12, 2022, 13 pages. [cited by applicant]
Gangemi et al., “Text2AMR2FRED, a Tool for Transforming Text into RDF/OWL Knowledge Graphs via Abstract Meaning Representation” ISWC 2023 Posters and Demos: 22nd International Semantic Web Conference, Nov. 6-10, 2023, A… [cited by applicant]
International Search Report and Written Opinion for Application No. PCT/US2025/025729, mailed Jul. 18, 2025, 14 pages. [cited by applicant]
Liao et al., “Abstract Meaning Representation for Multi-Document Summarization”, Proceedings of the 27th International Conference on Computational Linguistics, Aug. 20-26, 2018, Santa Fe, New Mexico, USA, 13 pages. [cited by applicant]
Pramanik et al., “UNIQORN: Unified Question Answering over RDF Knowledge Graphs and Natural Language Text”, Journal of Web Semantics, 27 pages. [cited by applicant]