GSQL Graph Algorithm Library
Updated Sep 27, 2020
Graph algorithms are functions for measuring characteristics of graphs, vertices, or relationships. Graph algorithms can provide insights into the role or relevance of individual entities in a graph. For example: How centrally located is this vertex? How much influence does this vertex exert over the others?
Some graph algorithms measure or identify global characteristics: What are the natural community groupings in the graph? What is the density of connections?
Sept 27, 2020 Updates:
Description of repository branches for different product versions
Overview of Schema-Free Algorithms
New section on Standard Parameters
Description of unification of the three output options into one algorithm instead of three algorithms.
New algorithms:
maximal independent set
minimum spanning forest
pageRank_wt
estimated_diameter
Updated parameter lists for many algorithms
Using the GSQL Graph Algorithm Library
The GSQL Graph Algorithm Library is a collection of expertly written GSQL queries, each of which implements a standard graph algorithm. Each algorithm is ready to be installed and used, either as a stand-alone query or as a building block of a larger analytics application.
GSQL running on the TigerGraph platform is particularly well-suited for graph algorithms for the several reasons:
Turing-complete with full support for imperative and procedural programming, ideal for algorithmic computation.
Parallel and Distributed Processing, enabling computations on larger graphs.
User-Extensible. Because the algorithms are written in standard GSQL and compiled by the user, they are easy to modify and customize.
Open-Source. Users can study the GSQL implementations to learn by example, and they can develop and submit additions to the library.
Library Structure
You can download the library from Github: https://github.com/tigergraph/gsql-graph-algorithm
The library contains two main sections: algorithms and tests. Within the algorithms folder are four subfolders:
schema-free: This contains algorithms that are ready to use (e.g. INSTALL QUERY) as-is.
templates: This contains algorithms that need to be prepared with the install.sh script to target them for a specific graph schema.
generated: This contains the algorithms converted from template to graph-specific format by the install.sh script.
examples: This contains examples of generated algorithms
The tests folder contains small sample graphs that you can use to experiment with the algorithms. In this document, we use the test graphs to show you the expected result for each algorithm. The graphs are small enough that you can manually calculate and sometimes intuitively see what the answers should be.
Release Branches
Starting with TigerGraph product version 2.6, the GSQL Graph Algorithm Library has release branches:
Product version branches (2.6, 3.0, etc.) are snapshots created shortly after a product version is released. They contain the best version of the graph algorithm library at the time of that product version's initial release. They will not be updated, except to fix bugs.
Master branch: the newest released version. This should be at least as new as the newest. It may contain new or improved algorithms.
Other branches are development branches.
Note that is is possible that you can run newer algorithms on an older product version, as long as the algorithm does not rely on features available only in newer product versions.
Schema-Free Algorithms
Most GSQL graph algorithms are schema-free, which means they are ready to use with any graph, regardless of the graph's data model or schema. Schema-free algorithms have run-time input parameters for the vertex type(s), edge type(s), and attributes which the user wishes to use.
Installing Template Algorithms
Remember that GSQL graph algorithms are simply GSQL queries. A few algorithms make use of GSQL features which do not yet accept run-time parameters. Instead, these algorithms are in template format. (Historically, this was the original release format for GSQL graph algorithms.) You need to run a script to personalize your algorithm and then to install it.
Make sure that the install.sh is owned by the tigergraph user.
Within the Algorithms folder is a script install.sh. When you run the script, it will first ask you which graph schema you wish to work on. (The TigerGraph platform supports multiple concurrent graphs.)
It then asks you to choose from a menu of available algorithms.
After knowing your graph schema and your algorithm, the installer will ask you some questions for that particular algorithm:
the installer will guide you in selecting appropriate vertex types and edges types. Note this does not have to be all the vertex or edge types in your graph. For example, you may have a social graph with three categories of persons and five types of relationships. You might decide to compute PageRank using Member and Guest vertices and Recommended edges.
Some algorithms use edge weights as input information (such as Shortest Path where each edge has a weight meaning the "length" of that edge. The installer will ask for the name of that edge attribute.
Single Node Mode or Distributed Mode? Queries which will analyze the entire graph (such PageRank and Community Detection) will run better in Distributed Mode, if you have a cluster of machines.
It will then ask you what type of output you would like. It will proceed to create up to three versions of your algorithm, based on the three ways of receiving the algorithm's output:
Stream the output in JSON format, the default behavior for most GSQL queries.
Save the output value(s) in CSV format to a file. For some algorithms, this option will add an input parameter to the query, to let the user specify how many total values to output.
Store the results as vertex or edge attribute values. The attributes must already exist in the graph schema, and the installer will ask you which attributes to use.
After creating queries for one algorithm, the installer will loop back to let you choose another algorithm (returning to step 2 above).
If you choose to exit, the installer makes a last request: Do you want to install your queries? Installation is when the code is compiled and bound into the query engine. It takes a few minutes, so it is best to create all your personalized queries at once and then install them as a group.
Example:
After the algorithms are installed, you will see them listed among the rest of your GSQL queries.
Running an Algorithm
Running an algorithm is the same as running a GSQL query. For example, if you selected the JSON option for pageRank, you could run it from GSQL as below:
Installing a query also creates a REST endpoint. The same query could be run thus:
GSQL lets you run queries from within other queries. This means you can use a library algorithm as a building block for more complex analytics.
Library Overview
The following algorithms are currently available. The algorithms are grouped into five classes:
Path
Centrality
Community
Similarity
Classification
Some algorithms are only appropriate for certain types of graphs. For example, Strong Connected Components (SCC) is designed for graphs with directed edges.
Coming soon means that TigerGraph plans to release this variant of the algorithm soon.
n/a means that this variant of the algorithm is typically not used
Computational Complexity
Computational Complexity is a formal mathematical term, referring to how an algorithm's requirements scale according to the size of the data or other key parameters. Computational complexity is useful for comparing one algorithm to another, but it does not describe speed in absolute terms.
For graphs, there are two key data parameters:
V (or sometimes n), the number of vertices
E (or sometimes m), the number of edges
The notation O(V^2) (read "big O V squared") means that when V is large, the computational time is proportional to V^2.
Time complexity describes how the execution time is expected to vary with the data size and other key parameters. Normally, time complexity is based on a simplified and idealized computer architecture: memory accesses and arithmetic operations always take one unit of time.
Memory complexity describes how the run-time memory usage scales with the data size and other key parameters.
Standard Parameters
To make it easier to understand and use the algorithms, the library aims to have consistent parameter names and order. Input parameters come first, parameter for the body of the algorithm come next, and output configuration parameters come last.
In GSQL, to accept a default parameter value, use _
E.g.,
closeness_cent(["Person", "Organization"], ["Likes"], _, _, _, _, _, _, _)
Parameters for the Graph Schema
Schema-free algorithms need to know the name of the vertex types, edge types, and the edge weight attribute for weighted edge algorithms.
Set notation for GSQL parameters
Use square brackets to enclose a set-type parameter, even if there is just a single item in the set, e.g.
closeness_cent(["Person", "Organization"], ["Likes"], _, _, _, _, _, _, _)
Parameters for Output Options
There are usually three options for output:
Send JSON output to standard output.
Write results to an output file in CSV format.
Store the output values in a user-specified attribute of a vertex or edge type.
Beginning with v3.0, each of the options is selected independently by setting appropriate parameters. More than one option may be selected:
Path Algorithms
These algorithms help find the shortest path or evaluate the availability and quality of routes.
Single-Source Shortest Path, Unweighted
This algorithm finds an unweighted shortest path from one source vertex to each possible destination vertex in the graph. That is, it finds n paths.
If your graph has weighted edges, see the next algorithm. With weighted edges, it is necessary to search the whole graph, whether you want the path for just one destination or for all destinations.
Description and Uses
If a graph has unweighted edges, then finding the shortest path from one vertex to another is the same as finding the path with the fewest hops. Think of Six Degrees of Separation and Friend of a Friend. Unweighted Shortest Path answers the question "How are you two related?" The two entities do not have to be persons. Shortest Path is useful in a host of applications, from estimating influences or knowledge transfer, to criminal investigation.
When the graph is unweighted, we can use a "greedy" approach to find the shortest path. In computer science, a greedy algorithm makes intermediate choices based on the data being considered at the moment, and then does not revisit those choices later on. In this case, once the algorithm finds any path to a vertex T, it is certain that that is a shortest path.
Specifications
Example
In the below graph, we do not consider the weight on edge. Using vertex A as the source vertex, the algorithm discovers that the shortest path from A to B is A-B, and the shortest path from A to C is A-D-C, etc.
Single-Source Shortest Path, Weighted
Description and Uses
Finding shortest paths in a graph with weighted edges is algorithmically harder than in an unweighted graph because even after you find a path to a vertex T, you cannot be certain that it is a shortest path. If edge weights are always positive, then you must keep trying until you have considered every in-edge to T. If edge weights can be negative, then it's even harder. You must consider all possible paths.
A classic application for weighted shortest path is finding the shortest travel route to get from A to B. (Think of route planning "GPS" apps.) In general, any application where you are looking for the cheapest route is a possible fit.
Specifications
The shortest path algorithm can be optimized if we know all the weights are nonnegative. If there can be negative weights, then sometimes a longer path will have a lower cumulative weight. Therefore, we have two versions of this algorithm
The shortest_path_any_wt query is an implementation of the Bellman-Ford algorithm. If there is more than one path with the same total weight, the algorithm returns one of them.
Currently, shortest_path_pos_wt also uses Bellman-Ford. The well-known Dijsktra's algorithm is designed for serial computation and cannot work with GSQL's parallel processing.
Example
The graph below has only positive edge weights. Using vertex A as the source vertex, the algorithm discovers that the shortest weighted path from A to B is A-D-B, with distance 8. The shortest weighted path from A to C is A-D-B-C with distance 9.
The graph below has both positive and negative edge weights. Using vertex A as the source vertex, the algorithm discovers that the shortest weighted path from A to E is A-D-C-B-E, with a cumulative score of 7 - 3 - 2 - 4 = -2.
Single-Pair Shortest Path
The Single-Pair Shortest Path task seeks the shortest path between a source vertex S and a target vertex T. If the edges are unweighted, then use the query in our tutorial document GSQL Demo Examples.
If the edges are weighted, then use the Single-Source Shortest Path algorithm. In the worst case, it takes the same computational effort to find the shortest path for one pair as to find the shortest paths for all pairs from the same source S. The reason is that you cannot know whether you have found the shortest (least weight) path until you have explored the full graph. If the weights are always positive, however, then a more efficient algorithm is possible. You can stop searching when you have found paths that use each of the in-edges to T.
All-Pairs Shortest Path
The All-Pairs Shortest Path algorithm is costly for large graphs, because the computation time is O(V^3) and the output size is O(V^2). Be cautious about running this on very large graphs.
The All-Pairs Shortest Path (APSP) task seeks to find shortest paths between every pair of vertices in the entire graph. In principle, this task can be handled by running the Single-Source Shortest Path (SSSP) algorithm for each input vertex, e.g.,
This example highlights one of the strengths of GSQL: treating queries as stored procedures which can be called from within other queries. We only show the result_attr and file_path options, because subqueries cannot send their JSON output.
For large graphs (with millions of vertices or more), however, this is an enormous task. While the massively parallel processing of the TigerGraph platform can speed up the computation by 10x or 100x, consider what it takes just to store or report the results. If there are 1 million vertices, then there are nearly 1 trillion output values.
There are more efficient methods than calling the single-source shortest path algorithm n times, such as the Floyd-Warshall algorithm, which computes APSP in O(V^3) time.
Our recommendation:
If you have a smaller graph (perhaps thousands or tens of thousands of vertices), the APSP task may be tractable.
If you have a large graph, avoid using APSP.
Minimum Spanning Tree (MST)
Description and Uses
Given an undirected and connected graph, a minimum spanning tree is a set of edges which can connect all the vertices in the graph with the minimal sum of edge weights. The library implements a parallel version of the PRIM algorithm:
Start with a set A = { a single vertex seed }
For all vertices in A, select a vertex y such that
y is not A, and
There is an edge from y to a vertex x in A, and
The weight of the edge e(x,y) is the smallest among all eligble pairs (x,y).
Add y to A, and add the edge (x,y) to MST.
Repeat steps 2 and 3 until A has all vertices in the graph.
If the user specifies a source vertex, this will be used as the seed. Otherwise, the algorithm will select a random seed vertex.
If the graph contains multiple components (i.e., some vertices are disconnected from the rest of the graph, then the algorithm will span only the component of the seed vertex.
If you do not have a preferred vertex, and the graph might have more than one component, then you should used the Minimum Spanning Forest (MDF) algorithm instead.
Specifications
Example
In social10 graph, we consider only the undirected Coworker edges.
This graph has 3 components. Minimum Spanning Tree finds a tree for one component, so which component it will work on depends on what vertex we give as the starting point. If we select Fiona, George, Howard, or Ivy as the start vertex, then it work on the 4-vertex component on the left. You can start from any vertex in the component and get the same or an equivalent MST result.
The figure below shows the result of mst(("Ivy", "Person")). Note that the value for the one vertex is ("Ivy","Person"). In GSQL, this 2-tuple format which explicitly gives the vertex type is used when the query is written to accept a vertex of any type.
File output:
The attribute version requires a boolean attribute on the edge, and it will assign the attribute to "true" if that edge is selected in the MST:
Minimum Spanning Forest (MSF)
Description and Uses
Given an undirected graph with one or more connected components, a minimum spanning forest is a set of minimum spanning trees, one for each component. The library implements the algorithm in section 6.2 of Qin et al. 2014: http://www-std1.se.cuhk.edu.hk/~hcheng/paper/SIGMOD2014qin.pdf.
Specifications
Example
Refer to the example for the MST algorithm. This graph has 3 components. MSF will find an MST for each of the three components.
Maximal Independent Set
Description and Uses
An independent set of vertices does not contain any pair of vertices which are neighbors, i.e., ones which have an edge between them. A maximal independent set is the largest independent set which contains those vertices; you cannot improve upon it, unless you start over with a different independent set. However, the search for the largest possible independent set (the maximum independent set, as opposed to the maximal independent set) is an NP-hard problem: there is no known algorithm which can find that answer in polynomial time. So we settle for maximal independent set.
This algorithm finds use in applications wanting to find the most efficient configuration which "covers" all the necessary cases. For example, it has been used to optimize delivery or transit routes, where each vertex is one transit segment, and each edge connections two segments which can NOT be covered by the same vehicle.
Specifications
Example
Consider our social10 graph, with three components.
It is clear that for each of the two triangles -- (Alex, Bob, Justin) and (Chase, Damon, Eddie) -- we can select one vertex from each triangle to be part of the MIS. For the 4-vertex component (Fiona, George, Howard, Ivy), it is less clear what will happen. If the algorithm selects either George or Ivy, then no other independent vertices remain in the component. However, the algorithm could select both Fiona and Howard; they are independent of one another.
This demonstrates the uncertainty of the Maximal Independent Set algorithm and how it differs from Maximum Independent Set. A maximum independent set algorithm would always select Fiona and Howard, plus 2 others, for a total of 4 vertices. The maximal independent set algorithm relies on chance. It could return either 3 or 4 vertices.
Cycle Detection
Description and Uses
The Cycle Detection problem seeks to find all the cycles (loops) in a graph. We apply the usual restriction that the cycles must be "simple cycles", that is, they are paths that start and end at the same vertex but otherwise never visit any vertex twice.
There are two versions of the task: for directed graphs and undirected graphs. The GSQL algorithm library currently supports only directed cycle detection. The Rocha–Thatte algorithm is an efficient distributed algorithm, which detects all the cycles in a directed graph. The algorithm will self-terminate, but it is also possible to stop at k iterations, which finds all the cycles having lengths up to k edges.
The basic idea of the algorithm is to (potentially) traverse every edge in parallel, again and again, forming all possible paths. At each step, if a path forms a cycle, it records it and stops extending it. More specifically: Initialization: For each vertex, record one path consisting of its own id. Mark the vertex as Active.
Iteration steps: Fo each Active vertex v:
Send its list of paths to each of its out-neighbors.
Inspect each path P in the list of the paths received:
If the first id in P is also id(v), a cycle has been found:
Remove P from its list.
If id(v) is the least id of any id in P , then add P to the Cycle List. (The purpose is to count each cycle only once.)
Else, if id(v) is somewhere else in the path, then remove P from the path list (because this cycle must have been counted already).
Else, append id(v) to the end of each of the remaining paths in its list.
Specifications
Example
In the social10 graph, there are 5 cycles, all with the Fiona-George-Howard-Ivy cluster.
Estimated Diameter
Description and Uses
The diameter of a graph is the worst-case length of a shortest path between any pair of vertices in a graph. It is the farthest distance to travel, to get from one vertex to another, if you always take the shortest path. Finding the diameter requires calculating (the lengths of) all shortest paths, which can be quite slow.
This algorithm uses a simple heuristic to estimate the diameter. rather than calculating the distance from each vertex to every other vertex, it select K vertices randomly, where K is a user-provided parameter. It calculates the distances from each of these K vertices to all other vertices. So, instead of calculating V*(V-1) distances, this algorithm only calculates K*(V-1) distances. The higher the value of K, the greater the likelihood of hitting the actual longest shortest path.
The current versions only computes unweighted distances.
This algorithm query employs a subquery called max_BFS_depth. Both queries are needed to run the algorithm.
Specifications
Centrality Algorithms
Centrality algorithms determine the importance of each vertex within a network. Typical applications:
PageRank is designed for directed edges. The classic interpretation is to find the most "important" web pages, based on hyperlink referrals, but it can be used for another network where entities make positive referrals of one another.
Closeness Centrality and Betweenness Centrality both deal with the idea of "centrally located."
PageRank
Description and Uses
The PageRank algorithm measures the influence of each vertex on every other vertex. PageRank influence is defined recursively: a vertex's influence is based on the influence of the vertices which refer to it. A vertex's influence tends to increase if (1) it has more referring vertices or if (2) its referring vertices have higher influence. The analogy to social influence is clear.
A common way of interpreting PageRank value is through the Random Network Surfer model. A vertex's pageRank score is proportional to the probability that a random network surfer will be at that vertex at any given time. A vertex with a high pageRank score is a vertex that is frequently visited, assuming that vertices are visited according to the following Random Surfer scheme:
Assume a person travels or surfs across a network's structure, moving from vertex to vertex in a long series of rounds.
The surfer can start anywhere. This start-anywhere property is part of the magic of PageRank, meaning the score is a truly fundamental property of the graph structure itself.
Each round, the surfer randomly picks one of the outward connections from the surfer's current location. The surfer repeats this random walk for a long time.
But wait. The surfer doesn't always follow the network's connection structure. There is a probability (1-damping, to be precise), that the surfer will ignore the structure and will magically teleport to a random vertex.
Specifications
Example
We ran pageRank on our test10 graph (using Friend edges) with the following parameter values: damping=0.85, max_change=0.001, and max_iter=25. We see that Ivy (center bottom) has the highest pageRank score (1.12). This makes sense, since there are 3 neighboring persons who point to Ivy, more than for any other person. Eddie and Justin have scores have exactly 1, because they do not have any out-edges. This is an artifact of our particular version pageRank. Likewise, Alex has a score of 0.15, which is (1-damping), because Alex has no in-edges.
Weighted PageRank
Description and Uses
The only different between weighted pageRank and standard pageRank is that edges have weights, and the influence that a vertex receives from an in-neighbor is multiplied by the weight of the in-edge.
Specifications
Personalized PageRank
Description and Uses
In the original PageRank, the damping factor is the probability of the surfer continues browsing at each step. The surfer may also stop browsing and start again from a random vertex. In personalized PageRank, the surfer can only start browsing from a given set of source vertices both at the beginning and after stopping.
Specifications
Example
We ran Personalized PageRank on our test10 graph using Friend edges with the following parameter values: damping=0.85, max_change=0.001, max_iter=25, and source="Fiona". In this case, the random walker can only start or restart walking from Fiona. In the figure below, we see that Fiona has the highest pageRank score in the result. Ivy and George have the next highest scores, because they are direct out-neighbors of Ivy and there are looping paths that lead back to them again. Half of the vertices have a score of 0, since they can not be reached from Fiona.
Closeness Centrality
We all have an intuitive understanding when we say a home, an office, or a store is "centrally located." Closeness Centrality provides a precise measure of how "centrally located" is a vertex. The steps below show the steps for one vertex v.
These steps are repeated for every vertex in the graph.
This algorithm query employs a subquery called cc_subquery. Both queries are needed to run the algorithm.
Specifications
Parameters
Example
Closeness centrality can be measured for either directed edges (from v to others) or for undirected edges. Directed graphs may seem less intuitive, however. because if the distance from Alex to Bob is 1, it does not mean the distance from Bob to Alex is also 1.
For our example, we wanted to use the topology of the Likes graph, but to have undirected edges. We emulated an undirected graph by using both Friend and Also_Friend (reverse direction) edges.
Betweenness Centrality
The Betweenness Centrality of a vertex is defined as the number of shortest paths which pass through this vertex, divided by the total number of shortest paths. That is
The TigerGraph implementation is based on A Faster Algorithm for Betweenness Centrality by Ulrik Brandes, Journal of Mathematical Sociology 25(2):163-177, (2001). For every vertex s in the graph, the pair dependency starting from vertex s to all other vertices t via all other vertices v is computed first,
Then betweenness centrality is computed as
According to Brandes, the accumulated pair dependency can be calculated as
For each single vertex, the algorithm works in two phases. The first phase calculates the number of shortest paths passing through each vertex. Then starting from the vertex on the most outside layer in a non-incremental order with pair dependency initial value of 0, traverse back to the starting vertex
This algorithm query employs a subquery called bc_subquery. Both queries are needed to run the algorithm.
Specifications
Parameters
Example
In the example below, Claire is in the very center of the social graph, and has the highest betweenness centrality. Six shortest paths pass through Sam (i.e. paths from Victor to all other 6 people except for Sam and Victor), so the score of Sam is 6. David also has a score of 6, since Brian has 6 paths to other people that pass through David.
In the following example, both Charles and David have 9 shortest paths passing through them. Ellen is in a similar position as Charles, but her centrality is weakened due to the path between Frank and Jack.
Community Algorithms
These algorithms evaluate how a group is clustered or partitioned, as well as its tendency to strengthen or break apart.
Connected Components
Description and Uses
A component is the maximal set of vertices, plus their connecting edges, which are interconnected. That is, you can reach each vertex from each other vertex. In the example figure below, there are three components.
This particular algorithm deals with undirected edges. If the same definition (each vertex can reach each other vertex) is applied to directed edges, then the components are called Strongly Connected Components. If you have directed edges but ignore the direction (permitting traversal in either direction), then the algorithm finds Weakly Connected Components.
Specifications
Example
It is easy to see in this small graph that the algorithm correctly groups the vertices:
Alex, Bob and Justin all have Community ID = 2097152
Chase, Damon, and Eddie all have Community ID = 5242880
Fiona, George, Howard, and Ivy all have Community ID = 0
Our algorithm uses the TigerGraph engine's internal vertex ID numbers; they cannot be predicted.
Strongly Connected Components
Description and Uses
A strongly connected component (SCC) is a subgraph such that there is a path from any vertex to every other vertex. A graph can contain more than one separate SCC. An SCC algorithm finds the maximal SCCs within a graph. Our implementation is based on the Divide-and-Conquer Strong Components (DCSC) algorithm[1]. In each iteration, pick a pivot vertex v randomly, and find its descendant and predecessor sets, where descendant set D_v is the vertex reachable from v, and predecessor set P_v is the vertices which can reach v (stated another way, reachable from v through reverse edges). The intersection of these two sets is a strongly connected component SCC_v. The graph can be partitioned to 4 sets: SCC_v, descendants D_v excluding SCC_v, predecessors P_v excluding SCC, and the remainders R_v. It is proved that any SCC is a subset of one of the 4 sets [1]. Thus, we can divide the graph into different subsets and detect the SCCs independently and iteratively.
The problem of this algorithm is unbalanced load and slow convergence when there are a lot of small SCCs, which is often the case in real world use cases [3]. We added two trimming stages to improve the performance: size-1 SCC trimming[2] and weakly connected components[3].
The implementation of this algorithm requires reverse edges for all directed edges considered in the graph.
[1] Fleischer, Lisa K., Bruce Hendrickson, and Ali Pınar. "On identifying strongly connected components in parallel." International Parallel and Distributed Processing Symposium. Springer, Berlin, Heidelberg, 2000.
[2] Mclendon Iii, William, et al. "Finding strongly connected components in distributed graphs." Journal of Parallel and Distributed Computing 65.8 (2005): 901-910.
[3] Hong, Sungpack, Nicole C. Rodia, and Kunle Olukotun. "On fast parallel detection of strongly connected components (SCC) in small-world graphs." Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis. ACM, 2013.
Specifications
Example
We ran scc on the social26 graph. A portion of the JSON result is shown below.
The first element "i"=1 means the whole graph is processed in just one iteration. The 5 "trim_set.size()" elements mean there were 5 rounds of size-1 SCC trimming. The final "@@.cluster_dist_heap" object" reports on the size distribution of SCCs.There is one SCC with 9 vertices, and 17 SCCs with only 1 vertex in the graph.
Label Propagation
Description and Uses
Label Propagation is a heuristic method for determining communities. The idea is simple: If the plurality of your neighbors all bear the label X, then you should label yourself as also a member of X. The algorithm begins with each vertex having its own unique label. Then we iteratively update labels based on the neighbor influence described above. It is important that they the order for updating the vertices be random. The algorithm is favored for its efficiency and simplicity, but it is not guaranteed to produce the same results every time.
In a variant version, some vertices could initially be known to belong to the same community,. If they are well-connected to one another, they are likely to preserve their common membership and influence their neighbors,
Specifications
Example
This is the same graph that was used in the Connected Component example. The results are different, though. The quartet of Fiona, George, Howard, and Ivy have been split into 2 groups. See can see the symmetry:
(George & Ivy) each connect to (Fiona & Howard) and to one another.
(Fiona & Howard) each connect to (George & Ivy) but not to one another.
Label Propagation tries to find natural clusters and separations within connected components. That is, it looks at the quality and pattern of connections. The Component Component algorithm simply asks the Yes or No question: Are these two vertices connected?
We set max_iter to 10, but the algorithm reached steady state after 3 iterations.
Louvain Method with Parallelism and Refinement
Description and Uses
The Louvain Method for community detection [1] partitions the vertices in a graph by approximately maximizing the graph's modularity score. The modularity score for a partitioned graph assesses the difference in density of links within a partition vs. the density of links crossing from one partition to another. The assumption is that if a partitioning is good (that is, dividing up the graph into communities or clusters), then the within-density should be high and the inter-density should be low.
The most efficient and empirically effective method for calculating modularity was published by a team of researchers at the University of Louvain. The Louvain method uses agglomeration and hierarchical optimization:
Optimize modularity for small local communities.
Treat each optimized local group as one unit, and repeat the modularity operation for groups of these condensed units.
The original Louvain Method contains two phases. The first phase incrementally calculates the modularity change of moving a vertex into every other community, and moves the vertex to the community with highest modularity change. The second phase coarsens the graph by aggregating the vertices which are assigned in the same community into one vertex. The first phase and second phase make up a pass. The Louvain Method performs the passes iteratively. In other words, the algorithm assigns an initial community label to every vertex, then performs the first phase, during which the community labels are changed, until there is no modularity gain. Then it aggregates the vertices with same labels into one vertex, and calculates the aggregated edge weights between new vertices. For the coarsened graph, the algorithm conducts first phase again to move the vertices into new communities. The algorithm continues until the modularity is not increasing, or runs to the preset iteration limits.
However, phase one is sequential, and thus slow for large graphs. An improved Parallel Louvain Method Louvain Method (PLM) calculates the best community to move to for each vertex in parallel [2]. In Parallel Louvain Method(PLM), the positive modularity gain is not guaranteed, and it may also swap two vertices to each other’s community. After finishing the passes, there is an additional refinement phase, which is running the first phase again on each vertex to do some small adjustments for the resulting communities. [3].
[1] Blondel, Vincent D., et al. "Fast unfolding of communities in large networks." Journal of statistical mechanics: theory and experiment 2008.10 (2008): P10008.
[2] Staudt, Christian L., and Henning Meyerhenke. "Engineering parallel algorithms for community detection in massive networks." IEEE Transactions on Parallel and Distributed Systems 27.1 (2016): 171-184.
[3] Lu, Hao, Mahantesh Halappanavar, and Ananth Kalyanaraman. "Parallel heuristics for scalable community detection." Parallel Computing 47 (2015): 19-37.
Specifications
Example
If we use louvain_parallel for social10 graph, it will give the same result as the result of as the connected components algorithm. The social26 graph is a connected graph which is quite dense. The connected components algorithm groups all the vertices into the same community, and label propagation does not consider the edge weight. On the contrary, louvain_parallel detects 7 communities in total, and the cluster distribution is shown below (csize is cluster size):
Triangle Counting
Description and Uses
Why triangles? Think of it in terms of a social network:
If A knows B, and A also knows C, then we complete the triangle if B knows C. If this situation is common, it indicates a community with a lot of interaction.
The triangle is in fact the smallest multi-edge "complete subgraph," where every vertex connects to every other vertex.
Triangle count (or density) is a measure of community and connectedness. In particular, it addresses the question of transitive relationships: If A--> B and B-->C, then what is the likelihood of A--> C?
Note that it is computing a single number: How many triangles are in this graph? It is not finding communities within a graph.
It is not common to count triangles in directed graphs, though it is certainly possible. If you choose to do so, you need to be very specific about the direction of interest: In a directed graph, If A--> B and B--> C, then
if A-->C, we have a "shortcut".
if C-->A, then we have a feedback loop.
Specifications
The tri_count algorithm is in template format. It is not yet in schema-free format.
We present two different algorithms for counting triangles. The first, tri_count(), is the classic edge-iterator algorithm. For each edge and its two endpoint vertices S and T, count the overlap between S's neighbors and T's neighbors.
One side effect of the simple edge-iterator algorithm is that it ends up considering each of the three sides of a triangle. The count needs to be divided by 3, meaning we did 3 times more work than a smaller algorithm would have.
tri_count_fast() is a smarter algorithm which does two passes over the edges. In the first pass we mark which of the two endpoint vertices has fewer neighbors. In the second pass, we count the overlap only between marked vertices. The result is that we eliminate 1/3 of the neighborhood matching, the slowest 1/3, but at the cost of some additional memory.
Example
In the social10 graph with Coworker edges, there are clearly 4 triangles.
Similarity Algorithms
There are many ways to measure the similarity between two vertices in a graph, but all of them compare either (1) the features of the vertices themselves, (2) the relationships of each of the two vertices, or (3) both. We use a graph called movie to demonstrate our similarity algorithms.
Cosine Similarity of Neighborhoods, Single Source
Description and Uses
To compare two vertices by cosine similarity, first selected properties of each vertex are represented as a vector. For example, a property vector for a Person vertex could have the elements (age, height, weight). Then the cosine function is applied to the two vectors.
The cosine similarity of two vectors A and B is defined as follows:
If A and B are identical, then cos(A, B) = 1. As expected for a cosine function, the value can also be negative or zero. In fact, cosine similarity is closely related to the Pearson correlation coefficient.
For this library function, the feature vector is the set of edge weights between the the two vertices and their neighbors.
In the movie graph shown in the figure below, there are Person vertices and Movie vertices. Every person may give rating to some of the movies. The rating score is stored on the Likes edge using the weight attribute. For example, in the graph below, Alex give a rating of 10 to the movie "Free Solo".
Specifications
The output size is always K (if K <= N), so the algorithm may arbitrarily chose to output one vertex over another, if there are tied similarity scores.
Example
Given one person's name, this algorithm calculates the cosine similarity between this person and each other person where there is at one movie they have both rated..
In the previous example, if the input is Alex, and topK is set to 5, then we calculate the cosine similarity between him and two other persons, Jing and Kevin. The JSON output shows the top k similar vertices and their similarity score in descending order. The output limit is 5 persons, but we have only 2 qualified persons:
The FILE version output is not necessarily in descending order. It looks like the following:
The ATTR version inserts an edge into the graph with the similarity score as an edge attribute whenever the score is larger than zero. The result looks like this:
Cosine Similarity of Neighborhoods, All Pairs
Description and Uses
This algorithm computes the same similarity scores as the cosine similarity of neighborhoods, single source algorithm (cosine_nbor_ss), except that it considers ALL pairs of vertices in the graph (for the vertex and edge types selected by the user). Naturally, this algorithm will take longer to run. For very large and very dense graphs, this may not be a practical choice.
Specifications
Example
Using the movie graph, calculate the cosine similarity between all pairs and show the top 5 pairs: cosine_nbor_ap(5). This is the JSON result:
The FILE output is similar to the output of cosine_nbor_file.
The ATTR version will create k edges:
Jaccard Similarity of Neighborhoods, Single Source
Description and Uses
The Jaccard index measures the relative overlap between two sets. To compare two vertices by Jaccard similarity, first select a set of values for each vertex. For example, a set of values for a Person could be the cities the Person has lived in. Then the Jaccard index is computed for the two vectors.
The Jaccard index of two sets A and B is defined as follows:
The value ranges from 0 to 1. If A and B are identical, then Jaccard(A, B) = 1. If both A and B are empty, we define the value to be 0.
Specifications
In the current
The algorithm will not output more than K vertices, so the algorithm may arbitrarily chose to output one vertex over another, if there are tied similarity scores.
Example
Using the movie graph, we run jaccard_nbor_ss("Neil", 5):
If the source vertex (person) doesn't have any common neighbors (movies) with any other vertex (person), such as Elena in our example, the result will be an empty list:
Jaccard Similarity of Neighborhoods, All Pairs
Description and Uses
This algorithm computes the same similarity scores as the Jaccard similarity of neighborhoods, single source algorithm (jaccard_nbor_ss), except that it considers ALL pairs of vertices in the graph (for the vertex and edge types selected by the user). Naturally, this algorithm will take longer to run. For very large and very dense graphs, this algorithm may not be a practical choice
Specifications
The algorithm will not output more than K vertex pairs, so the algorithm may arbitrarily chose to output one vertex pair over another, if there are tied similarity scores.
Example
For the movie graph, calculate the Jaccard similarity between all pairs and show the 5 most similar pairs: jaccard_nbor_ap(5). This is the JSON output :
Classification Algorithms
Classification algorithms, or classifiers, are one of the simplest forms of machine learning. They seek to prediction the classification of a given entity, based on the evidence of previously classified entities. Classification is closely related to similarity and clustering; all of them deal with finding and using the commonalities among entities.
k-Nearest Neighbors, Cosine Neighbor Similarity, single vertex
Description and Uses
The k-Nearest Neighbors (kNN) algorithm is one of the simplest classification algorithms. It assumes that some or all the vertices in the graph have already been classified. The classification is stored as an attribute called the label. The goal is to predict the label of a given vertex, by seeing what are the labels of the nearest vertices.
Given a source vertex in the dataset and a positive integer k, the algorithm calculates the distance between this vertex and all other vertices, and selects the k vertices which are nearest. The prediction of the label of this node is the majority label among its k-nearest neighbors.
The distance can be physical distance as well as the reciprocal of similarity score, in which case "nearest" means "most similar". In our algorithm, the distance is the reciprocal of cosine neighbor similarity. The similarity calculation used here is the same as the calculation in Cosine Similarity of Neighborhoods, Single Source. Note that in this algorithm, vertices with zero similarity to the source node are not considered in prediction. For example, if there are 5 vertices with non-zero similarity to the source vertex, and 5 vertices with zero similarity, when we pick the top 7 neighbors, only the label of the 5 vertices with non-zero similarity score will be used in prediction.
Specifications
The algorithm will not output more than K vertex pairs, so the algorithm may arbitrarily chose to output one vertex pair over another, if there are tied similarity scores.
Example
For the movie graph, we add the following labels to the Person vertices.
When we install the algorithm, answer the questions like:
We then run kNN, using Neil as the source person and k=3. This is the JSON output :
If we run cosine_nbor_ss, using Neil as the source person and k=3, we can see the persons with the top 3 similarity score:
Kat has a label "b", Kevin has a label "a", and Jing does not have a label. Since "a" and "b" is tied, the prediction for Neil is just one of the labels.
If Jing had label "b", then there would be 2 "b"s, so "b" would be the prediction.
If Jing had label "a", then there would be 2 "a"s, so "a" would be the prediction.
k-Nearest Neighbors, Cosine Neighbor Similarity, All Vertices Batch
Description and Uses
This algorithm is a batch version of the k-Nearest Neighbors, Cosine Neighbor Similarity, single vertex. It make a prediction for every vertex whose label is not known (i.e., the attribute for the known label is empty), based on its k nearest neighbors' labels.
Specifications
Example
For the movie graph shown in the single vertex version, run knn_cosine_all, using topK=3. Then you get the following result:
k-Nearest Neighbors, Cosine Neighbor Similarity, cross validation
Description and Uses
kNN is often used for machine learning. You can choose the value for topK based on your experience, or using cross validation to optimize the hyperparameters. In our library, Leave-one-out cross validation for selecting optimal k is provided. Given a k value, we run the algorithm repeatedly using every vertex with known label as the source vertex and predict its label. We assess the accuracy of the predictions for each value of k, and then repeat for different values of k in the given range. The goal is to find the value of k with highest predicting accuracy in the given range, for that dataset.
Specifications
Example
Run knn_cosine_cv with min_k=2, max_k = 5. The JOSN result:
Last updated
