System, method, and recording medium for efficient cohesive subgraph identification in entity collections for inlier and outlier detection

• US 10,282,636 B2
• Filed: 10/24/2017
• Issued: 05/07/2019
• Est. Priority Date: 09/14/2015
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Cheng, Yu, Pankanti, Sharathchandra U., Ratha, Nalini K.
• Primary Examiner(s): Shin, Soo
• Application Number:
  US15/791,662
• Publication Number:
  US 20180060694A1
• Time in Patent Office: 560 Days
• Field of Search: None
• CPC Class Codes: G06F 18/22 Matching criteria, e.g. proximity measures
• CPC Class Codes: G06F 18/23 Clustering techniques
• CPC Class Codes: G06F 18/29 Graphical models, e.g. Bayesian networks
• CPC Class Codes: G06V 10/84 using probabilistic graphical models from image or video features, e.g. Markov models or Bayesian networks
• CPC Class Codes: G06V 20/30 in albums, collections or shared content, e.g. social network photos or video
• CPC Class Codes: G06V 40/161 Detection; Localisation; Normalisation

Abstract

A similarity detection system receiving a plurality of input entities, the system including a cohesive subgraph identification device configured to calculate, based on attributes of the plurality of input entities, a first parameter and a second parameter based on the first parameter, and further configured to identify a plurality of subgraphs from the second parameter and a subgraph correlation tracking and clustering device configured to determine a relationship between different subgraphs based on a similarity factor between the second parameter and the plurality of subgraphs.

Claims

1. A similarity detection system receiving a plurality of input entities, the system comprising:

a face detection and verification device configured to extract a face region from the plurality of input entities and to extract shift features from the face region as images, the face detection and verification device excludes items in the input entities that have facial features but are not a real face of a person;

a cohesive subgraph identification device configured to calculate, based on attributes of the plurality of input entities, a first parameter and a second parameter based on the first parameter, and further configured to identify a plurality of subgraphs from the second parameter; and

a subgraph correlation tracking and clustering device configured to determine a relationship between different subgraphs based on a similarity factor between the second parameter and the plurality of subgraphs,

wherein the subgraph correlation tracking and clustering device is further configured to output outliers that include the subgraphs not combined by the subgraph correlation tracking and clustering device,

wherein the subgraph correlation tracking and clustering device uses source nodes and target nodes of nodes in a post network such that on each iteration, each source node propagates edge similarities to a neighborhood of the source node along paths, and, each target node aggregates the similarities that are propagated in from their neighbors, and

wherein the subgraph correlation tracking and clustering device measures the correlations between subgraphs as an amount of average path similarities that are propagated and aggregated to detect outliers within the images and based on the correlation between the subgraphs and similarities, the subgraph correlation tracking and clustering device combines subgraphs to output inliers,

wherein the first parameter includes k-cores and the second parameter includes (k, d)-cores,

wherein the (k, d)-cores include a cohesive internal structure adjusted by at least d common neighbors as witnesses of commonality between the nodes in the post network connected by each edge,

wherein d is an integer greater than zero,

wherein given the post network as G(V,E) defined as k-cores from all the nodes represented as G(V,E), the cohesive subgraph identification device recursively removes the nodes with a degree less than k from G(V,E), until all the remaining nodes have a degree of at least k with a result being a set of k-cores that form the basis for the (k, d)-cores generation,

wherein the cohesive subgraph identification device uses k from the (k, d)-cores to adjust an edge density, and uses d from the (k, d) cores to control a strength of the similarities between the subgraphs generated and the k-cores, thereby the cohesive subgraph identification device generates a maximal (k, d)-core which is a subgraph of a maximal k-core,

wherein the cohesive subgraph identification device generates the (k, d)-core by removing n nodes with a degree less than k recursively by only verifying the degree of n nodes,

wherein given a maximal path length, the average path similarities aggregated by each of the target nodes are computed by multiplying all the edge similarities along the path, dampened by a dampening factor on each hop.

2. The similarity detection system according to claim 1, herein the plurality of input entities comprise a list of images.

3. The similarity detection system according to claim 1, wherein the subgraph correlation tracking and clustering device is further configured to output inliers that include the subgraphs combined by the subgraph correlation tracking and clustering device.

4. The similarity detection system according to claim 1, wherein the attributes comprise a mathematical representation of the entities.

5. The similarity detection system according to claim 1, wherein the second parameter includes an additional factor to control a strength of the similarity factor between entities than the first parameter.

6. The similarity detection system according to claim 1, wherein the cohesive subgraph identification device calculates the second parameter using either a Zigzag algorithm or a NodeFirst algorithm.

7. The similarity detection system according to claim 6, wherein the ZigZag algorithm:

generates a first set of the k-Cores by removing the nodes with a degree less than k recursively from G(V, E);

while the first set of the k-Cores is not empty;

generates a second set of (d+1, d)-Cores by removing the edges with a witnesses less than d recursively from the first set of the k-Cores;

exits the algorithm if the first set of the k-Cores equals the second set of the (d+1, d)-Cores;

if the first set of the k-Cores does not equal the second set of the (d+1, d)-Cores, generates a third set of the k-Cores by removing the edges with a witnesses less than d recursively from the first set of the k-Cores;

exits the algorithm if the first set of the k-Cores equals the third set of the k-Cores; and

returns the first set of the k-Cores when the first set of the k-Cores equals either the second set of the (d+1, d)-Cores or the third set of the k-Cores.

8. The similarity detection system according to claim 1, wherein the face detection and verification device identifies the face region from the plurality of input entities that is in fact the face and verifies that the region is actually the face of the person.

9. The similarity detection system according to claim 1, wherein the face detection and verification device verities that only one face exists in the images of the plurality of input entities.

10. The similarity detection system according to claim 9, wherein the face detection and verification device identifies a number of face regions detected in the images and removes images from the input entities with multiple faces in the images.

11. The similarity detection system according to claim 1, wherein the cohesive subgraph identification device only deletes nodes and checks the degree.

12. The similarity detection system according to claim 1, wherein each parameter in the k-core has a weight associated with each point and the k-core shows a strength of similarity between each image.

13. The similarity detection system according to claim 1, wherein the cohesive subgraph identification device only deletes nodes and checks the degree, and

wherein each parameter in the k-core has a weight associated with each point and the k-core shows a strength of similarity between each image.

14. The similarity detection system according to claim 1, wherein the subgraph correlation tracking and clustering device determines a relationship between different subgraphs based on a similarity factor between the (k, d)-cores and the plurality of subgraphs output by the subgraph correlation tracking and clustering device.

15. The similarity detection system according to claim 1, wherein the subgraph correlation tracking and clustering device combines the different subgraphs together based on the similarity factor between the (k, d)-cores of the plurality of subgraphs.

16. The similarity detection system according to claim 1, wherein the cohesive subgraph identification device calculates the second parameter using a Zigzag algorithm that:

generates a first set of the k-Cores by removing the nodes with a degree less than k recursively from G(V, E);

while the first set of the k-Cores is not empty;

generates a second set of (d+1, d)-Cores by removing the edges with a witnesses less than d recursively from the first set of the k-Cores;

exits the algorithm if the first set of the k-Cores equals the second set of the (d+1, d)-Cores;

if the first set of the k-Cores does not equal the second set of the (d+1, d)-Cores, generates a third set of the k-Cores by removing the edges with a witnesses less than d recursively from the first set of the k-Cores;

exits the algorithm if the first set of the k-Cores equals the third set of the k-Cores; and

returns the first set of the k-Cores when the first set of the k-Cores equals either the second set of the (d+1, d)-Cores or the third set of the k-Cores, and

wherein the dampening factor on each hop is between 0 and 1.

17. A similarity detection method, comprising:

receiving a plurality of input entities;

extracting a face region from the plurality of input entities and shift features from the face region as images;

excluding items in the input entities that have facial features but are not a real face of a person;

calculating, based on attributes of the plurality of input entities, a first parameter and a second parameter based on the first parameter;

identifying a plurality of subgraphs from the second parameter;

determining a relationship between different subgraphs based on a similarity factor between the second parameter and the plurality of subgraphs;

outputting outliers that include the subgraphs not combined by the combining;

using source nodes and target nodes of nodes in a post network such that on each iteration, each source node propagates edge similarities to a neighborhood of the source node along paths, and each target node aggregates the similarities that are propagated in from their neighbors; and

measuring the correlations between subgraphs as an amount of average path similarities that are propagated and aggregated to detect outliers within the images and based on the correlation between the subgraphs and similarities, and combining subgraphs to output inliers,

wherein the first parameter includes k-cores and the second parameter includes (k, d)-cores,

wherein the (k, d)-cores include a cohesive internal structure adjusted by at least d common neighbors as witnesses of commonality between the nodes in the post network connected by each edge,

wherein d is an integer greater than zero,

wherein given the post network as G(V,E) defined as k-cores from all the nodes represented as G(V,E), the cohesive subgraph identification device recursively removes the nodes with a degree less than k from G(V,E), until all the remaining nodes have a degree of at least k with a result being a set of k-cores that form the basis for the (k, d)-cores generation,

wherein the calculating uses k from the (k, d)-cores to adjust an edge density, and uses d from the (k, d)-cores to control a strength of the similarities between the subgraphs generated and the k-cores, thereby generating a maximal (k, d)-core which is a subgraph of a maximal k-core,

wherein the cohesive subgraph identification device generates the (k, d)-core by removing n nodes with a degree less than k recursively by only verifying the degree of n nodes,

wherein given a maximal path length, the average path similarities aggregated by each of the target nodes are computed by multiplying all the edge similarities along the path, dampened by a dampening factor on each hop.

18. The similarity detection method according to claim 17, wherein the plurality of input entities comprise a list of images.

19. A non-transitory computer-readable recording medium recording a similarity detection program, the program causing a computer to perform:

receiving a plurality of input entities;

extracting a face region from the plurality of input entities and shift features from the face region as images;

excluding items in the input entities that have facial features but are not a real face of a person;

calculating, based on attributes of the plurality of input entities, a first parameter and a second parameter based on the first parameter;

identifying a plurality of subgraphs from the second parameter;

determining a relationship between different subgraphs based on a similarity factor between the second parameter and the plurality of subgraphs;

outputting outliers that include the subgraphs not combined by the combining;

using source nodes and target nodes of nodes in a post network such that on each iteration, each source node propagates edge similarities to a neighborhood of the source node along paths, and each target node aggregates the similarities that are propagated in from their neighbors; and

measuring the correlations between subgraphs as an amount of average path similarities that are propagated and aggregated to detect outliers within the images and based on the correlation between the subgraphs and similarities, and combining subgraphs to output inliers,

wherein the first parameter includes k-cores and the second parameter includes (k, d)-cores,

wherein the (k, d) -cores include a cohesive internal structure adjusted by at least d common neighbors as witnesses of commonality between the nodes in the post network connected by each edge,

wherein d is an integer greater than zero,

wherein given the post network as G(V,E) defined as k-cores from all the nodes represented as G(V,E), the cohesive subgraph identification device recursively removes the nodes with a degree less than k from G(V,E), until all the remaining nodes have a degree of at least k with a result being a set of k-cores that form the basis for the (k, d)-cores generation,

wherein the calculating uses k from the (k, d)-cores to adjust an edge density, and uses d from the (k, d)-cores to control a strength of the similarities between the subgraphs generated and the k cores, thereby generating a maximal (k, d)-core which is a subgraph of a maximal k-core,

wherein the cohesive subgraph identification device generates the (k, d)-core by removing a nodes with a degree less than k recursively by only verifying the degree of n nodes,

wherein given a maximal path length, the average path similarities aggregated by each of the target nodes are computed by multiplying all the edge similarities along the path, dampened by a dampening, factor on each hop.

20. The non-transitory computer-readable recording medium according to claim 19, wherein the plurality of input entities comprise a list of images.