IP Library › Granted Patent US 12,748,874
Granted Patent B2
US 12,748,874 · App. 18/693,623 · Granted Sep 29, 2026

Graph-based condition identification

Inventors: Jonathan Roscoe (London, GB); Robert Hercock (London, GB)
Assignee: BRITISH TELECOMMUNICATIONS PUBLIC LIMITED COMPANY
G06F21/6218G06F16/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,748,874
App. No.
18/693,623
Granted
Sep 29, 2026
Kind
B2
Abstract

A computer implemented method for detecting the existence of a condition indicated by data represented by a set of input graph data structures can include receiving at least a pair of training graph data structures of nodes and edges wherein each node indicates one or more characteristics of an event and each edge indicates an association between events, and wherein at least a subset of nodes and edges in each training graph relate to the existence of the condition, identifying an association between at least one pair of nodes in which each node of a pair occurs in a disparate training graph and at least one of the pair of nodes relates to the existence of the condition, and generating an edge between the pair of nodes so as to generate a composite training graph including at least a pair of the training graph data structures; extracting a proper subgraph of the composite training graph including at least one of the at least one pair of nodes, such that the proper subgraph indicates the existence of the condition including nodes and edges from each of the pair of graphs for comparison with the set of input graphs to identify an indication of the existence of the condition by the input graphs.

Claims (14)

1 . A computer implemented method for detecting an existence of a condition indicated by data represented by a set of at least two input graph data structures of nodes and edges, the method comprising:

receiving at least a pair of training graph data structures of nodes and edges, wherein each node indicates one or more characteristics of an event and each edge indicates an association between events, and wherein at least a subset of the nodes and the edges in each training graph data structure relate to the existence of the condition;

identifying an association between at least one pair of nodes in which each node of a pair occurs in a disparate training graph data structure and at least one of the pair of nodes relates to the existence of the condition, and generating an edge between the pair of nodes so as to generate a composite training graph data structure including at least a pair of the training graph data structures;

extracting a proper subgraph of the composite training graph data structure including at least one of the at least one pair of nodes, such that the proper subgraph indicates the existence of the condition including the nodes and the edges from each of the pair of graphs for comparison with the set of at least two input graph data structures to identify an indication of the existence of the condition by the input graph data structures;

identifying an association between at least one pair of nodes in the input graph data structures in which each node of a pair occurs in a disparate input graph data structure, and generating an edge between the pair of nodes so as to generate a composite input graph data structure including at least a pair of the input graph data structures; and

searching the composite input graph data structure for occurrences of the proper subgraph to identify an indication of the existence of the condition by the input graph data structures so as to determine the existence of the condition.

2 . The method of claim 1 , wherein identifying an association between a pair of nodes includes one or more of: identifying a semantic association between the pair of nodes; identifying a vector similarity between the pair of nodes based on a vector embedding; identifying a geospatial similarity between the pair of nodes; identifying an association based on centrality, node-degree, eigenvector or betweenness of the pair of nodes; identifying a temporal similarity between the pair of nodes; or applying a clustering process in which the pair of nodes are clustered together.

3 . The method of claim 1 , wherein the proper subgraph is defined based on one or more predetermined criteria for identifying limits of one or more of a size, a scope, or an extent of the proper subgraph.

4 . The method of claim 1 , wherein searching the composite input graph data structure for occurrences of the proper subgraph includes searching for arrangements of the nodes and the edges between the nodes in the proper subgraph occurring in the composite input graph data structure irrespective of data stored or represented by or with the nodes of the proper subgraph and the composite input graph.

5 . The method of claim 4 , wherein data stored by at least one or more nodes or one or more edges of the proper subgraph and the composite input graph data structure is protected from disclosure.

6 . The method of claim 5 , wherein the protected data is protected by one or more of: encryption; data obfuscation; data redaction; data removal; or data replacement.

7 . The method of claim 1 , wherein the condition is a security condition.

8 . A computer system comprising a processor and memory storing computer program code for performing the method of claim 1 .

9 . A non-transitory computer-readable storage medium comprising computer program code to, when loaded into a computer system and executed thereon, cause the computer system to perform the method as claimed in claim 1 .

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Jan 23, 2026
From: ROSCOE, JONATHAN; HERCOCK, ROBERT
To: BRITISH TELECOMMUNICATIONS PUBLIC LIMITED COMPANY
Reel/Frame 073563/0249 →
Priority Claims (1)
GB 2113473 · Sep 21, 2021 · national
Continuity (1)
Related Publication 20240394393A1 · Nov 28, 2024
References Cited (79)
US 5812998A · Tsutsumi et al. · 1998 [cited by applicant]
US 7403951B2 · Setlur et al. · 2008 [cited by applicant]
US 7660441B2 · Chen et al. · 2010 [cited by applicant]
US 7933451B2 · Kloer · 2011 [cited by applicant]
US 8441958B2 · Thubert et al. · 2013 [cited by applicant]
US 8576229B2 · Dykes et al. · 2013 [cited by applicant]
US 9119055B2 · Vaccari et al. · 2015 [cited by applicant]
US 9305264B2 · Miró · 2016 [cited by applicant]
US 9911340B2 · Samarasekera et al. · 2018 [cited by applicant]
US 10496722B2 · Bobick et al. · 2019 [cited by applicant]
US 10917425B2 · Liu · 2021 [cited by examiner]
US 11481687B2 · Fang · 2022 [cited by examiner]
US 11941374B2 · Makhija · 2024 [cited by examiner]
US 11989964B2 · Agarwal · 2024 [cited by examiner]
US 12015628B1 · Lv · 2024 [cited by examiner]
US 12267337B2 · Hercock · 2025 [cited by examiner]
US 20070182818A1 · Buehler · 2007 [cited by applicant]
US 20100191532A1 · Rodriguez et al. · 2010 [cited by applicant]
US 20150070506A1 · Chattopadhyay et al. · 2015 [cited by applicant]
US 20170063910A1 · Muddu et al. · 2017 [cited by applicant]
US 20180299877A1 · Cheng et al. · 2018 [cited by applicant]
US 20180329958A1 · Choudhury et al. · 2018 [cited by applicant]
US 20190065869A1 · Savla et al. · 2019 [cited by applicant]
US 20200081445A1 · Stetson et al. · 2020 [cited by applicant]
US 20200097491A1 · Berthiaume · 2020 [cited by applicant]
US 20200151272A1 · Freitag et al. · 2020 [cited by applicant]
US 20200160101A1 · Kim et al. · 2020 [cited by applicant]
US 20210042499A1 · Hammad et al. · 2021 [cited by applicant]
US 20210152574A1 · Maida et al. · 2021 [cited by applicant]
US 20210279280A1 · M G et al. · 2021 [cited by applicant]
US 20220335806A1 · Dice et al. · 2022 [cited by applicant]
US 20230072641A1 · Parameswaran et al. · 2023 [cited by applicant]
US 20240394332A1 · Roscoe et al. · 2024 [cited by applicant]
US 20240395018A1 · Roscoe et al. · 2024 [cited by applicant]
CN 102706352B · 2014 [cited by applicant]
CN 104933175A · 2015 [cited by applicant]
CN 107527038A · 2017 [cited by applicant]
CN 106777373B · 2018 [cited by applicant]
CN 108694244A · 2018 [cited by applicant]
CN 109140168A · 2019 [cited by applicant]
EP 2123221A2 · 2009 [cited by applicant]
EP 3681124A1 · 2020 [cited by applicant]
JP H096958A · 1997 [cited by applicant]
JP H11345342A · 1999 [cited by applicant]
International Search Report and Written Opinion received for PCT Patent Application No. PCT/EP2022/073618, mailed on Dec. 6, 2022, 14 pages. [cited by applicant]
International Search Report and Written Opinion received for PCT Patent Application No. PCT/EP2022/073619, mailed on Nov. 9, 2022, 11 pages. [cited by applicant]
International Search Report and Written Opinion received for PCT Patent Application No. PCT/EP2022/073620, mailed on Nov. 30, 2022, 11 pages. [cited by applicant]
Office Action received for Great Britain Patent Application No. 2113472.1, mailed on Mar. 7, 2022, 8 pages. [cited by applicant]
Office Action received for Great Britain Patent Application No. 2113473.9, mailed on Feb. 16, 2022, 7 pages. [cited by applicant]
Office Action received for Great Britain Patent Application No. 2113474.7, mailed on Jan. 31, 2022, 7 pages. [cited by applicant]
“The IBM i2 Intelligence Analysis Portfolio Delivers Powerful New Capabilities to Significantly Enhance the User Experience and to Extend Applicability to a Wider Community”, IBM United States Software Announcement 218-… [cited by applicant]
Ahmed , et al., “On the Effect of Geometries Simplification on Geo-spatial Link Discovery”, Procedia Computer Science, vol. 137, 2018, pp. 139-150. [cited by applicant]
Bazgir , et al., “Representation of Features as Images with Neighborhood Dependencies for Compatibility with Convolutional Neural Networks”, Nature Communications, vol. 11, No. 4391, 2020, pp. 1-13. [cited by applicant]
Csillik , et al., “Object-Based Time-Constrained Dynamic Time Warping Classification of Crops Using Sentinel-2”, Remote Sensing, vol. 11, No. 1257, 2019, pp. 1-26. [cited by applicant]
Djuric , et al., “Motion Prediction of Traffic Actors for Autonomous Driving using Deep Convolutional Networks”, Available at <arXiv:1808.05819v1>, Aug. 17, 2018, 10 pages. [cited by applicant]
Esri Arcgis Blog , “How to Perform Spatial Analysis”, Available Online at <https://www.esri.com/arcgis-blog/products/analytics/analytics/how-to-perform-spatial-analysis/>, Feb. 28, 2018, 6 pages. [cited by applicant]
Janeja , et al., “Detecting Anomalous Geospatial Trajectories through Spatial Characterization and Spatio-Semantic Associations”, Proceedings of the 2004 Annual National Conference on Digital Government Research, Articl… [cited by applicant]
Jean , et al., “Tile2Vec: Unsupervised Representation Learning for Spatially Distributed Data”, Available Online at <https://arxiv.org/abs/1805.02855v2>, May 30, 2018, pp. 1-19. [cited by applicant]
Jiang , et al., “Geospatial Data to Images: A Deep-Learning Framework for Traffic Forecasting”, Tsinghua Science and Technology, vol. 24, No. 1, Feb. 2019, pp. 52-64. [cited by applicant]
Mccoy , et al., “ArcGIS 9: Using ArcGIS Spatial Analyst”, Environmental Systems Research Institute, 2001, pp. 1-238. [cited by applicant]
Rath , et al., “Word Image Matching Using Dynamic Time Warping”, IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2003, pp. 1-7. [cited by applicant]
Sharif , et al., “Context-Awareness in Similarity Measures and Pattern Discoveries of Trajectories: A Context-based Dynamic Time Warping Method”, GIScience & Remote Sensing, vol. 54, No. 3, 2017, pp. 426-452. [cited by applicant]
Sharma , et al., “DeepInsight: A Methodology to Transform a Non-Image Data to an Image for Convolution Neural Network Architecture”, Scientific Reports, vol. 9, No. 11399, 2019, pp. 1-7. [cited by applicant]
Wang , et al., “Classifying NBA Offensive Plays Using Neural Networks”, Research Papers Competition, MIT Sloan Sports Analytics Conference, 2016, pp. 1-9. [cited by applicant]
Candia et al., Uncovering individual and collective human dynamics from mobile phone records, J. Phys. A: Math. Theor. 41 (2008) 224015 (11pp), Published May 21, 2008. [cited by applicant]
Chuanga et al., Local alliances and rivalries shape near-repeat terror activity of al-Qaeda, ISIS, and insurgents, PNAS, Oct. 15, 2019, vol. 116, No. 42, 20898-20903. [cited by applicant]
Cohen, node2vec: Embeddings for Graph Data, Apr. 16, 2018 (https://towardsdatascience.com/node2vec-embeddings-for-graph-data-32a866340fef). [cited by applicant]
Faucher, Python: Detecting Twitter Bots with Graphs and Machine Learning, Aug. 7, 2020 (https://towardsdatascience.com/python-detecting-twitter-bots-with-graphs-and-machine-learning-41269205ab07). [cited by applicant]
Godec, Graph Embeddings—The Summary, Dec. 31, 2018 (https://towardsdatascience.com/graph-embeddings-the-summary-cc6075aba007). [cited by applicant]
Goyal et al., Graph Embedding Techniques, Applications, and Performance: A Survey, arXiv: 1705.02801, May 9, 2017. [cited by applicant]
Grover et al., node2vec: Scalable Feature Learning for Networks, Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, Aug. 13-17, 2016, San Francisco, CA, USA. [cited by applicant]
Liu et al., Crisisbert: A Robust Transformer for Crisis Classification and Contextual Crisis Embedding, arXiv:2005.06627, May 18, 2020. [cited by applicant]
Narayanan et al., graph2vec: Learning Distributed Representations of Graphs, arXiv:1707.05005, Jul. 17, 2017. [cited by applicant]
Perozzi et al., DeepWalk: Online Learning of Social Representations, arXiv: 1403.6652, Jun. 27, 2014. [cited by applicant]
Wang et al., Structural Deep Network Embedding, Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, Aug. 13-17, 2016, San Francisco, CA, USA. [cited by applicant]
Palash (palash1992), “GEM,” GitHub repository, https://github.com/palash1992/GEM, last accessed Apr. 14, 2026. [cited by applicant]
Elior Cohen (eliorc), “Nod2Vec-FIFA17-Example.ipynb,” GitHub repository, https://github.com/eliorc/Medium/blob/master/Nod2Vec-FIFA17-Example.ipynb (accessed Apr. 14, 2026). [cited by applicant]
Medusa Labs, “Medusa®—Social Media Intelligence and OSINT Platform,” https://www.medusa-labs.com/ (accessed Apr. 14, 2026). [cited by applicant]
Siren, “Law Enforcement and Intelligence—Search-based Investigative Intelligence Platform for data analysis and link analysis,” https://siren.io/law-enforcement-and-intelligence/ (accessed Apr. 14, 2026). [cited by applicant]