3.0 Implementation in TigerGraph Using GSQL

To execute Common Neighbors algorithms, we will utilize the TigerGraph database as our graph data storage and use GSQL for algorithm implementation. Because of TigerGraph’s distributed nature we can run the algorithm distributedly and with memory efficiency.

We will evaluate performance differences between the intersect method and the optimized approach by using the above pre-established use-case: calculating common cardholders who shop at two different merchants and then assigning a weighted edge between those merchants based on that count.

The files for building Schema/Load Data and running queries in TigerGraph are in the appendix.

3.1 Intersect method GSQL implementation:

The query below shows the implementation of the Intersection method and how to insert the merchant-merchant edges in O(nK²) time.

CREATE DISTRIBUTED QUERY _02_common_cards_intersect(
  INT min_edge_weight = 1
)
FOR GRAPH optimizing_common_neighbors {
  SetAccum @merchants;
  MapAccum<VERTEX, INT> @edge_weight;
  DATETIME before;

  cards = {Card.*};
  before=(now());
  // Collect all Merchants on the Card
  merchants = SELECT m FROM cards:c- (card_merchant_past_interaction:e) - Merchant:m
              ACCUM c.@merchants+=m; //O(M) where M= number of cards
  PRINT "Time to collection of merchants on cards ",datetime_diff(now(), before);

  // INSERT edges and weights using the INTERSECT method.
  before=(now());
  temp = SELECT m FROM merchants:m -(card_merchant_past_interaction:e)- Card:c
          ACCUM
            FOREACH merc IN c.@merchants DO // O(N*K) where N =number of Merchants and K= Max degree of Card
              IF getvid(m) < getvid(merc) THEN
                tg_common_neighbors(m,merc,min_edge_weight) //O(K_a+K_b) where K_a and K_b are the degrees of the merchant pair
              END
            END; //Total complexity O(N*K*(K_a+K_b))=O(N.K^2)
  PRINT "Time to INSERT edges using intersect method",datetime_diff(now(), before);
}

The sub-query tg_common_neighbors called in the above query does the actual intersection in O(K_a + K_b) time.
Below is the sub query logic:

//Intersect subquery
CREATE QUERY tg_common_neighbors(
  VERTEX v_source,
  VERTEX v_target,
  INT min_edge_weight
)
FOR GRAPH optimizing_common_neighbors {
  avs = {v_source};
  bvs = {v_target};
  INT sz;
  na = SELECT n
       FROM avs -(card_merchant_past_interaction:e)- :n;

  nb = SELECT n
       FROM bvs -(card_merchant_past_interaction:e)- :n;

  # Get neighbors in common for source and target and compute the common neighbors
  u = na INTERSECT nb;
  sz=u.size();

  # Insert edge only if the weight is >= min_edge_weight
  IF sz >= min_edge_weight THEN
    INSERT INTO merchant_merchant (FROM ,TO ,weight) VALUES (v_source,v_target,sz) ;
  END;
}

3.2 Optimized Common Neighbors implementation

For optimization we simply replace the intersect sub query tg_common_neighbors by counting the edge weight for each merchant-merchant vertex pair and hence reduce the complexity to O(K).

CREATE DISTRIBUTED QUERY _02_common_cards_optimized(
  INT min_edge_weight = 1
) 
FOR GRAPH optimizing_common_neighbors { 
  SetAccum @merchants;
  MapAccum<VERTEX, INT> @edge_weight;
  DATETIME before;
  
  cards = {Card.*};
  before=(now());
  // Collect all Merchants on the Card
  merchants = SELECT m FROM cards:c- (card_merchant_past_interaction:e) - Merchant:m
              ACCUM c.@merchants+=m; //O(M) where M= number of cards
  PRINT "Time to collection of merchants on cards ",datetime_diff(now(), before);
  
  // Establish logical edges an summed weights 
  before=(now());
  temp = SELECT m FROM merchants:m -(card_merchant_past_interaction:e)- Card:c
          ACCUM
            FOREACH merc IN c.@merchants DO // O(N*K) where N =number of Merchants and K= Max degree of Card
              IF getvid(m) < getvid(merc) THEN m.@edge_weight += (merc -> 1) //O(1)
              END
            END; //Total complexity O(N*K*1)=O(N.K)
  PRINT "Time to establish merchant-merchant edges using optimized common neighbors ",datetime_diff(now(), before);
  
  // Insert edges
  before=(now());  
  temp = SELECT m FROM merchants:m
          POST-ACCUM
            FOREACH (merc, w) IN m.@edge_weight DO
              IF w >= min_edge_weight THEN                 // Insert edge only if the weight is >= min_edge_weight
                  INSERT INTO merchant_merchant VALUES (m, merc, w)
              END
            END;
  PRINT "Time to INSERT merchant-merchant edges  ",datetime_diff(now(), before); 
}