Localized visual graph filters for complex graph queries

Abstract

Embodiments of the present invention provide a system for querying a graph based on applying filters to a visual representation of the graph. The system allows complicated graph query operations to be performed with ease visually. During operation, the system obtains data indicating vertices and edges of a graph. The system displays a visual representation of the graph for a user. The system receives, from the user, a command defining a local graph filter comprising a region in the visual representation. The system then filters a representation of the graph, and stores the filtered representation.

What is claimed is: 
     
         1 . A computer-implemented method for querying a graph, comprising:
 obtaining, by a computer system comprising a set of processors, a data structure representing a graph comprising vertices and edges;   displaying, for a user, a visual representation of the graph;   receiving, from the user, a command defining a local graph filter, wherein the local graph filter comprises a region in the visual representation of the graph;   filtering a representation of the graph to select a subset of vertices visually represented within the region, and edges connecting vertices in the subset; and   storing the selected vertices and edges of the filtered representation of the graph in a non-transitory storage medium.   
     
     
         2 . The method of  claim 1 , further comprising:
 receiving, from the user, an additional local graph filter comprising an additional region in the visual representation of the graph;   determining a combined region in the visual representation of the graph as a union or an intersection of the region and the additional region; and   filtering the representation of the graph to select a combined set of vertices visually represented within the combined region, and edges connecting vertices in the combined set.   
     
     
         3 . The method of  claim 1 , wherein receiving the command defining the local graph filter further comprises receiving, from the user via a pointing device, a boundary delimiting the region in the visual representation of the graph. 
     
     
         4 . The method of  claim 1 , wherein the received local graph filter further specifies a set of constraints, and wherein filtering the representation of the graph comprises further filtering the subset of vertices visually represented within the region to select vertices satisfying the constraints, and edges connecting the selected vertices. 
     
     
         5 . The method of  claim 4 , wherein receiving the command defining the local graph filter further comprises:
 displaying, for the user, a slider control associated with the local graph filter and representing a property of vertices in the graph;   receiving, from the user via a pointing device and according to a position of the slider control, a value for the property; and   setting a respective constraint based on the received value for the property.   
     
     
         6 . The method of  claim 4 , wherein a respective constraint defines a range of values for one or more of:
 a degree of a respective vertex in the graph;   a number of triangles associated with a respective vertex in the graph;   a number of cliques associated with a respective vertex in the graph;   a number of graphlets associated with a respective vertex in the graph;   a k-core number of a respective vertex in the graph;   a measure of graph distance of a respective edge in the graph; and   a measure of graph connectivity of a respective vertex in the graph.   
     
     
         7 . The method of  claim 4 , wherein a respective vertex in the graph is associated with auxiliary properties, and a respective constraint defines a range of values for an auxiliary property of the respective vertex. 
     
     
         8 . The method of  claim 7 , wherein the auxiliary property includes one or more of:
 an age of a person;   a wealth or income level of a person;   a geographic location of a person;   a purchase history of a person;   a person's friends or social network;   a time of a transaction;   an amount of a transaction;   spatial or temporal information of a commercial activity;   a derived property of the graph;   a property obtained from a matrix factorization of the graph;   an attribute based on a classification or regression method for prediction in the graph; and   an attribute representing whether a vertex or edge has been correctly classified.   
     
     
         9 . A non-transitory computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for querying a graph, the method comprising:
 obtaining, by the computer, a data structure representing a graph comprising vertices and edges;   displaying, for a user, a visual representation of the graph;   receiving, from the user, a command defining a local graph filter, wherein the local graph filter comprises a region in the visual representation of the graph;   filtering a representation of the graph to select a subset of vertices visually represented within the region, and edges connecting vertices in the subset; and   storing the selected vertices and edges of the filtered representation of the graph in a non-transitory storage medium.   
     
     
         10 . The computer-readable storage medium of  claim 9 , wherein the method further comprises:
 receiving, from the user, an additional local graph filter comprising an additional region in the visual representation of the graph;   determining a combined region in the visual representation of the graph as a union or an intersection of the region and the additional region; and   filtering the representation of the graph to select a combined set of vertices visually represented within the combined region, and edges connecting vertices in the combined set.   
     
     
         11 . The computer-readable storage medium of  claim 9 , wherein the received local graph filter further specifies a set of constraints, and wherein filtering the representation of the graph comprises further filtering the subset of vertices visually represented within the region to select vertices satisfying the constraints, and edges connecting the selected vertices. 
     
     
         12 . The computer-readable storage medium of  claim 11 , wherein receiving the command defining the local graph filter further comprises:
 displaying, for the user, a slider control associated with the local graph filter and representing a property of vertices in the graph;   receiving, from the user via a pointing device and according to a position of the slider control, a value for the property; and   setting a respective constraint based on the received value for the property.   
     
     
         13 . The computer-readable storage medium of  claim 11 , wherein a respective vertex in the graph is associated with auxiliary properties, and a respective constraint defines a range of values for an auxiliary property of the respective vertex. 
     
     
         14 . The computer-readable storage medium of  claim 13 , wherein the property includes one or more of:
 an age of a person;   a wealth or income level of a person;   a geographic location of a person;   a purchase history of a person;   a person's friends or social network;   a time of a transaction;   an amount of a transaction;   spatial or temporal information of a commercial activity;   a derived property of the graph;   a property obtained from a matrix factorization of the graph;   an attribute based on a classification or regression method for prediction in the graph; and   an attribute representing whether a vertex or edge has been correctly classified.   
     
     
         15 . A computing system for querying a graph, the system comprising:
 a set of multiple processors, and   a non-transitory computer-readable medium coupled to the set of processors having instructions stored thereon that, when executed by the set of processors, cause the set of processors to perform a method for querying a graph, the method comprising:   obtaining a data structure representing a graph comprising vertices and edges;   displaying, for a user, a visual representation of the graph;   receiving, from the user, a command defining a local graph filter, wherein the local graph filter comprises a region in the visual representation of the graph;   filtering a representation of the graph to select a subset of vertices visually represented within the region, and edges connecting vertices in the subset; and   storing the selected vertices and edges of the filtered representation of the graph in a non-transitory storage medium.   
     
     
         16 . The computing system of  claim 15 , wherein the method further comprises:
 receiving, from the user, an additional local graph filter comprising an additional region in the visual representation of the graph;   determining a combined region in the visual representation of the graph as a union or an intersection of the region and the additional region; and   filtering the representation of the graph to select a combined set of vertices visually represented within the combined region, and edges connecting vertices in the combined set.   
     
     
         17 . The computing system of  claim 15 , wherein the received local graph filter further specifies a set of constraints, and wherein filtering the representation of the graph comprises further filtering the subset of vertices visually represented within the region to select vertices satisfying the constraints, and edges connecting the selected vertices. 
     
     
         18 . The computing system of  claim 17 , wherein receiving the command defining the local graph filter further comprises:
 displaying, for the user, a slider control associated with the local graph filter and representing a property of vertices in the graph;   receiving, from the user via a pointing device and according to a position of the slider control, a value for the property; and   setting a respective constraint based on the received value for the property.   
     
     
         19 . The computing system of  claim 17 , wherein a respective vertex in the graph is associated with auxiliary properties, and a respective constraint defines a range of values for an auxiliary property of the respective vertex. 
     
     
         20 . The computing system of  claim 19 , wherein the auxiliary property includes one or more of:
 an age of a person;   a wealth or income level of a person;   a geographic location of a person;   a purchase history of a person;   a person's friends or social network;   a time of a transaction;   an amount of a transaction;   spatial or temporal information of a commercial activity;   a derived property of the graph;   a property obtained from a matrix factorization of the graph;   an attribute based on a classification or regression method for prediction in the graph; and   an attribute representing whether a vertex or edge has been correctly classified.