# US 12,222,987 B1 · Performing a search using a hypergraph > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,222,987 B1 - Document ID: US12222987B1 - Status: Granted - Kind: B1 - Application number: 18/467,151 - Filed: 2023-09-14 - Granted: 2025-02-11 - Earliest claimed: 2023-09-14 - Assignees: International Business Machines Corporation - Applicants: International Business Machines Corporation - Inventors: Lokesh Mishra; Gerhard Ingmar Meijer; Peter Willem Jan Staar; Michele Dolfi - Web page: https://patentgrep.com/patent/US12222987B1 ## CPC - G06F 16/9024: {Graphs; Linked lists (G06F16/9027 takes precedence)} - G06F 16/316: {Indexing structures} - G06F 16/33: Querying - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract Provided are techniques for performing a search using a hypergraph. Entities are identified. A knowledge graph using the entities is generated, wherein nodes of the knowledge graph represent the entities and edges between the nodes represent pair-wise relationships, and wherein each of the edges carries an edge score that quantifies a degree of coherence between a pair of the entities. A hypergraph using the knowledge graph is generated, wherein nodes of the hypergraph represent the entities and hyperedges represent relationships between multiple entities, and wherein each of the hyperedges carries a hyperedge score that quantifies a degree of coherence between the multiple entities. A search request is received. A search result is generated using the hypergraph, wherein the search result comprises a set of coherently related entities. The search result is returned. ## Claims ### Claim 1 A computer-implemented method, comprising operations for: identifying entities; generating a knowledge graph using the entities, wherein nodes of the knowledge graph represent the entities, wherein edges between the nodes represent pair-wise relationships, and wherein each of the edges carries an edge score that quantifies a degree of coherence between a pair of the entities; generating a hypergraph by traversing the knowledge graph, wherein nodes of the hypergraph represent the entities, wherein hyperedges represent relationships between multiple entities, wherein each of the hyperedges carries a hyperedge score that quantifies a degree of coherence between the multiple entities, and wherein each of the hyperedges comprises a set of edges of the knowledge graph; receiving a search request; generating a search result using the hypergraph, wherein the search result comprises coherently related entities comprising the entities from at least one hyperedge of the hyperedges; and returning the search result. ### Claim 2 (depends on 1) The computer-implemented method of claim 1, wherein identifying the entities further comprises operations for: performing named entity recognition to identify one or more of the entities in an information source. ### Claim 3 (depends on 1) The computer-implemented method of claim 1, wherein the entities comprise one or more user-defined entities. ### Claim 4 (depends on 1) The computer-implemented method of claim 1, wherein the edge score of a particular edge of the edges comprises a probabilistic edge score that is a function of proximity between locations of the entities in an information source, a length of the information source, and an entity type. ### Claim 5 (depends on 1) The computer-implemented method of claim 1, wherein the hyperedge score of a particular hyperedge of the hyperedges comprises a probabilistic hyperedge score that is based on the edge score of each edge that is part of the particular hyperedge. ### Claim 6 (depends on 1) The computer-implemented method of claim 1, wherein the coherently related entities comprise entities of an information source that are located in different portions of the information source. ### Claim 7 (depends on 1) The computer-implemented method of claim 1, further comprising operations for: identifying the hypergraph from a plurality of hypergraphs based on the search request. ### Claim 8 A computer program product, the computer program product comprising a computer readable storage medium having program instructions embodied therewith, the program instructions executable by a processor to cause the processor to perform operations for: identifying entities; generating a knowledge graph using the entities, wherein nodes of the knowledge graph represent the entities, wherein edges between the nodes represent pair-wise relationships, and wherein each of the edges carries an edge score that quantifies a degree of coherence between a pair of the entities; generating a hypergraph by traversing the knowledge graph, wherein nodes of the hypergraph represent the entities, wherein hyperedges represent relationships between multiple entities, wherein each of the hyperedges carries a hyperedge score that quantifies a degree of coherence between the multiple entities, and wherein each of the hyperedges comprises a set of edges of the knowledge graph; receiving a search request; generating a search result using the hypergraph, wherein the search result comprises coherently related entities comprising the entities from at least one hyperedge of the hyperedges; and returning the search result. ### Claim 9 (depends on 8) The computer program product of claim 8, wherein, for identifying the entities, the program instructions are executable by the processor to cause the processor to further perform: performing named entity recognition to identify one or more of the entities in an information source. ### Claim 10 (depends on 8) The computer program product of claim 8, wherein the entities comprise one or more user-defined entities. ### Claim 11 (depends on 8) The computer program product of claim 8, wherein the edge score of a particular edge of the edges comprises a probabilistic edge score that is a function of proximity between locations of the entities in an information source, a length of the information source, and an entity type. ### Claim 12 (depends on 8) The computer program product of claim 8, wherein the hyperedge score of a particular hyperedge of the hyperedges comprises a probabilistic hyperedge score that is based on the edge score of each edge that is part of the particular hyperedge. ### Claim 13 (depends on 8) The computer program product of claim 8, wherein the coherently related entities comprise entities of an information source that are located in different portions of the information source. ### Claim 14 (depends on 8) The computer program product of claim 8, wherein the program instructions are executable by the processor to cause the processor to further perform: identifying the hypergraph from a plurality of hypergraphs based on the search request. ### Claim 15 A computer system, comprising: one or more processors, one or more computer-readable memories and one or more computer-readable, tangible storage devices; and program instructions, stored on at least one of the one or more computer-readable, tangible storage devices for execution by at least one of the one or more processors via at least one of the one or more computer-readable memories, to perform operations comprising: identifying entities; generating a knowledge graph using the entities, wherein nodes of the knowledge graph represent the entities, wherein edges between the nodes represent pair-wise relationships, and wherein each of the edges carries an edge score that quantifies a degree of coherence between a pair of the entities; generating a hypergraph by traversing the knowledge graph, wherein nodes of the hypergraph represent the entities, wherein hyperedges represent relationships between multiple entities, wherein each of the hyperedges carries a hyperedge score that quantifies a degree of coherence between the multiple entities, and wherein each of the hyperedges comprises a set of edges of the knowledge graph; receiving a search request; generating a search result using the hypergraph, wherein the search result comprises coherently related entities comprising the entities from at least one hyperedge of the hyperedges; and returning the search result. ### Claim 16 (depends on 15) The computer system of claim 15, wherein, for identifying the entities, the program instructions further perform operations comprising: performing named entity recognition to identify one or more of the entities in an information source. ### Claim 17 (depends on 15) The computer system of claim 15, wherein the entities comprise one or more user-defined entities. ### Claim 18 (depends on 15) The computer system of claim 15, wherein the edge score of a particular edge of the edges comprises a probabilistic edge score that is a function of proximity between locations of the entities in an information source, a length of the information source, and an entity type. ### Claim 19 (depends on 15) The computer system of claim 15, wherein the hyperedge score of a particular hyperedge of the hyperedges comprises a probabilistic hyperedge score that is based on the edge score of each edge that is part of the particular hyperedge. ### Claim 20 (depends on 15) The computer system of claim 15, wherein the coherently related entities comprise entities of an information source that are located in different portions of the information source.