Systems and methods for detecting anomalous data in federated learning using topological data analysis

Abstract

Systems and methods for detecting anomalous data updates in federated learning. In some aspects, the system receives a plurality of data updates. Each data update contains data in a first real-valued space. The system selects a first function to project the plurality of data updates into a second real-valued space. The system selects a second function to partition the second real-valued space into a plurality of sectors. The system generates a plurality of sector datasets associated with the plurality of sectors. The system processes the plurality of sector datasets to generate a relational data structure. The system determines outliers in the relational data structure corresponding to anomalous data updates.

What is claimed is: 
     
         1 . A system for detecting anomalous data updates in a federated learning system, comprising:
 receiving a plurality of data updates from one or more client devices in a federated learning system, wherein each data update includes data in a first real-valued space;   processing, using a lens function, the plurality of data updates to project the plurality of data updates into a second real-valued space, wherein data in the first real-valued space corresponds to a data representation in the second real-valued space;   processing, using a cover function, data representations in the second real-valued space corresponding to the plurality of data updates to partition the data representations in the second real-valued space into a plurality of sectors;   generating a plurality of sector datasets corresponding to the plurality of sectors, wherein each sector dataset includes data representations included in a corresponding sector;   processing, using a cluster function, the plurality of sector datasets to generate a relational data structure, wherein the relational data structure comprises a plurality of clusters, and wherein each cluster in the plurality of clusters includes data representations from one or more sector datasets from the plurality of sector datasets;   determining, using the relational data structure, one or more anomalous data updates corresponding to one or more outliers, wherein the one or more outliers include data representations further than a distance threshold from a cluster in the plurality of clusters in the relational data structure;   selecting a permissible set of data updates from the plurality of data updates by removing the one or more anomalous data updates; and   training the federated learning system using the permissible set of data updates.   
     
     
         2 . A method for detecting anomalous data submissions, comprising:
 receiving a plurality of data updates, wherein each data update contains data in a first real-valued space;   selecting a first function to project the plurality of data updates into a second real-valued space;   selecting a second function to partition the second real-valued space into a plurality of sectors;   generating a plurality of sector datasets associated with the plurality of sectors;   processing the plurality of sector datasets to generate a relational data structure; and   determining one or more outliers in the relational data structure corresponding to anomalous data updates.   
     
     
         3 . The method of  claim 2 , wherein the relational data structure comprises a set of clusters comprising data in the first real-valued space from the plurality of data updates. 
     
     
         4 . The method of  claim 3 , wherein using the relational data structure to detect anomalous data updates comprises:
 selecting a distance threshold based on the relational data structure;   labelling as outliers data representations further than the distance threshold from a cluster in the set of clusters in the relational data structure;   selecting a percentage to be a normalcy threshold; and   determining data updates with a proportion of outliers higher than the normalcy threshold to be anomalous.   
     
     
         5 . The method of  claim 2 , wherein the first function may generate a data profile for an update dataset, comprising:
 one or more distributions of features in the update dataset;   a frequency of null values for one or more features;   a covariance matrix between features in the update dataset; and   metadata regarding the update dataset.   
     
     
         6 . The method of  claim 5 , wherein the first function may further process the data profile, comprising:
 using a first machine learning model, processing the one or more distributions of features, the frequency of null values, the covariance matrix, and metadata to generate a representation vector, wherein the representation vector is in the second real-valued space.   
     
     
         7 . The method of  claim 2 , wherein the first function may recombine a first set of features of data in a data update into a second set of features, comprising:
 generating a covariance matrix based on the first set of features;   computing a set of eigenvectors for the covariance matrix;   selecting a measure of coverage and selecting a subset of eigenvectors from the set of eigenvectors based on the measure of coverage; and   determining the second set of features corresponding to the subset of eigenvectors.   
     
     
         8 . The method of  claim 2 , wherein partitioning the second real-valued space into the plurality of sectors comprises:
 generating a plurality of regions in the second real-valued space, wherein each region in the plurality of regions is defined by boundary parameters, and wherein each region in the plurality of regions is of uniform length and size;   for each region in the plurality of regions, determining a density of data in the region to compare against a threshold density; and   for each region in the plurality of regions, expanding the boundary parameters of the region such that density of data in the region meets the threshold density.   
     
     
         9 . The method of  claim 2 , wherein partitioning the second real-valued space into the plurality of sectors comprises:
 generating a plurality of regions in the second real-valued space, wherein each region in the plurality of regions is defined by boundary parameters, and wherein each region in the plurality of regions is of uniform length and size;   determining a plurality of overlap data among the plurality of regions, wherein overlap data belong to more than one region in the plurality of regions;   for each region in the plurality of regions, determining a proportion of data that is overlap data to compare against a threshold proportion; and   for each region in the plurality of regions, expanding the boundary parameters of the region such that proportion of data that is overlap data in the region meets the threshold proportion.   
     
     
         10 . The method of  claim 2 , wherein generating the plurality of sector datasets associated with the plurality of sectors comprises:
 for each sector in the plurality of sectors, projecting the data in the sector from the second real-valued space into the first real-valued space; and   generating the plurality of sector datasets to correspond to the plurality of sectors, wherein each sector dataset contains data in a corresponding sector projected into the first real-valued space.   
     
     
         11 . The method of  claim 10 , wherein processing the plurality of sector datasets to generate the relational data structure comprises:
 retrieving a second machine learning model, wherein the second machine learning model is trained to cluster data in a dataset in the first real-valued space into one or more clusters;   using the second machine learning model, clustering data in each sector into one or more clusters; and   generating the relational data structure, comprising one or more nodes and one or more edges, wherein each node corresponds to a cluster in the one or more clusters, and wherein each edge between two clusters represents data belonging to both clusters.   
     
     
         12 . A non-transitory computer-readable medium comprising instructions that, when executed by one or more processors, cause operations comprising:
 receiving a plurality of data updates, wherein each data update contains data in a first real-valued space;   selecting a first function to project the plurality of data updates into a second real-valued space;   selecting a second function to partition the second real-valued space into a plurality of sectors;   generating a plurality of sector datasets associated with the plurality of sectors;   using the plurality of sector datasets, determining one or more anomalous data updates corresponding to one or more outliers; and   removing the one or more anomalous data updates from the plurality of data updates.   
     
     
         13 . The non-transitory computer-readable medium of  claim 12 , further comprising a relational data structure, the relational data structure comprising: a set of clusters comprising data in the first real-valued space from the plurality of data updates. 
     
     
         14 . The non-transitory computer-readable medium of  claim 13 , wherein using the relational data structure to detect anomalous data updates comprises:
 selecting a distance threshold based on the relational data structure;   labelling as outliers data further than the distance threshold from a cluster in the set of clusters in the relational data structure;   selecting a percentage to be a normalcy threshold; and   determining data updates with a proportion of outliers higher than the normalcy threshold to be anomalous.   
     
     
         15 . The non-transitory computer-readable medium of  claim 12 , wherein the first function may generate a data profile for an update dataset, comprising:
 one or more distributions of features in the update dataset;   a frequency of null values for one or more features;   a covariance matrix between features in the update dataset; and   metadata regarding the update dataset.   
     
     
         16 . The non-transitory computer-readable medium of  claim 15 , wherein the first function may further process the data profile, comprising:
 using a first machine learning model, processing the one or more distributions of features, the frequency of null values, the covariance matrix, and metadata to generate a representation vector, wherein the representation vector is in the second real-valued space.   
     
     
         17 . The non-transitory computer-readable medium of  claim 12 , wherein the first function may recombine a first set of features of data in a data update into a second set of features, comprising:
 generating a covariance matrix based on the first set of features;   computing a set of eigenvectors for the covariance matrix;   selecting a measure of coverage and selecting a subset of eigenvectors from the set of eigenvectors based on the measure of coverage; and   determining the second set of features corresponding to the subset of eigenvectors.   
     
     
         18 . The non-transitory computer-readable medium of  claim 12 , wherein partitioning the second real-valued space into the plurality of sectors comprises:
 generating a plurality of regions in the second real-valued space, wherein each region in the plurality of regions is defined by boundary parameters, and wherein each region in the plurality of regions is of uniform length and size;   for each region in the plurality of regions, determining a density of data in the region to compare against a threshold density; and   for each region in the plurality of regions, expanding the boundary parameters of the region such that density of data in the region meets the threshold density.   
     
     
         19 . The non-transitory computer-readable medium of  claim 12 , wherein generating the plurality of sector datasets associated with the plurality of sectors comprises:
 for each sector in the plurality of sectors, projecting the data in the sector from the second real-valued space into the first real-valued space; and   generating the plurality of sector datasets to correspond to the plurality of sectors, wherein each sector dataset contains data in a corresponding sector projected into the first real-valued space.   
     
     
         20 . The non-transitory computer-readable medium of  claim 13 , further comprising processing the plurality of sector datasets to generate the relational data structure, comprising:
 retrieving a second machine learning model, wherein the second machine learning model is trained to cluster data in a dataset in the first real-valued space into one or more clusters;   using the second machine learning model, clustering data in each sector into one or more clusters; and   generating the relational data structure, comprising one or more nodes and one or more edges, wherein each node corresponds to a cluster in the one or more clusters, and wherein each edge between two clusters represents data belonging to both clusters.