Download as PDF, PPTX
![© 2020 TigerGraph. All Rights Reserved Cosine Similarity If each item is described by a list of numerical values (a vector), then multiply the vectors together and divide by their lengths. ● If A=B, then Cos(A,B) = 1 19 A= (6,2) B= (4,4) Cos(A,B) = (6*4 + 2*4) / [√(6*6+2*2)√(4*4 + 4*4)] = (24+8) / [√40 √32 ] = 0.8944](https://image.slidesharecdn.com/graphgurus30graphalgorithms4-similarity1-200402221701/75/Using-Graph-Algorithms-For-Advanced-Analytics-Part-4-Similarity-30-graph-algorithms-4-similarity-1-19-2048.jpg)
![© 2020 TigerGraph. All Rights Reserved Graph-Based Structural Similarity Use a vertex's neighbors as its feature set ● Cosine: Use edge weights to each neighboring vertex 21 A Order W B X Y Z 2 3 1 2 1 4 A's weighted neighbors = {2,0,4,1} B's weighted neighbors = {3,1,0,2} Cos(A,B) = 8 / [√21√14] = 0.4666 W,X,Y,Z represent feature vertices, different vertex types than A,B](https://image.slidesharecdn.com/graphgurus30graphalgorithms4-similarity1-200402221701/75/Using-Graph-Algorithms-For-Advanced-Analytics-Part-4-Similarity-30-graph-algorithms-4-similarity-1-21-2048.jpg)
![© 2020 TigerGraph. All Rights Reserved SimRank Example 1st Round: sr(A,B) = c * Avg [ sr(W,W), sr(Y,W), sr(Z,W), sr(W,X), sr(Y,X), sr(Z,X), sr(W,Z), sr(Y,Z), sr(Z,Z)] = c*(1+0+0+0+0+0+0+0+1)/9 = 2c/9 23 A Order W B X Y Z 2 3 1 2 1 4 A and B each have 3 neighbors, so there are 9 possible pairs of neighbors. 2 of the neighbors are shared (W and Z) To complete round 1, compute scores for every other pair of vertices. For round 2, repeat, using the round 1 values for computing the average SimRank of neighbors.](https://image.slidesharecdn.com/graphgurus30graphalgorithms4-similarity1-200402221701/75/Using-Graph-Algorithms-For-Advanced-Analytics-Part-4-Similarity-30-graph-algorithms-4-similarity-1-23-2048.jpg)
![© 2020 TigerGraph. All Rights Reserved RoleSim Example 1st Round: rs(A,B) = (1-b) * Max [ sr(W,W), sr(Y,W), sr(Z,W), sr(W,X), sr(Y,X), sr(Z,X), sr(W,Z), sr(Y,Z), sr(Z,Z)] / 3 + b = (1-b)*(1+1+0)/3 + b = 2(1-b)/3 + b 27 A Order W B X Y Z 2 3 1 2 1 4 A and B each have 3 neighbors, so we seek 3 pairs of neighbors. 2 of the neighbors are shared (W and Z) To complete round 1, compute scores for every other pair of vertices. For round 2, repeat, using the round 1 values for computing the max. RoleSim of neighbor-pairs.](https://image.slidesharecdn.com/graphgurus30graphalgorithms4-similarity1-200402221701/75/Using-Graph-Algorithms-For-Advanced-Analytics-Part-4-Similarity-30-graph-algorithms-4-similarity-1-27-2048.jpg)
Uploaded byTigerGraph
Using Graph Algorithms For Advanced Analytics - Part 4 Similarity 30 graph algorithms 4 similarity (1)
The document discusses the use of graph algorithms for advanced analytics, focusing on similarity algorithms and their role in identifying relationships within data. Victor Lee, the presenter, outlines various types of algorithms such as Jaccard, Cosine, SimRank, and RoleSim, which help analyze connected data and ascertain similarity between entities. It emphasizes that defining similarity is subjective and context-dependent, with implications for applications such as healthcare and fraud detection.
Using Graph Algorithms For Advanced Analytics - Part 4 Similarity 30 graph algorithms 4 similarity (1)
- 1. Graph Gurus 30 UsingGraph Algorithms for Advanced Analytics Part 4 - Similarity 1
- 2. © 2020 TigerGraph.All Rights Reserved Today's Presenter 2 Victor Lee Head of Product Strategy & Developer Relations ● BS in Electrical Engineering and Computer Science from UC Berkeley, MS in Electrical Engineering from Stanford University ● PhD in Computer Science from Kent State University focused on graph data mining ● 20+ years in tech industry
- 3. © 2020 TigerGraph.All Rights Reserved Some Housekeeping Items ● Although your phone is muted we do want to answer your questions - submit your questions at any time using the Q&A tab in the menu ● The webinar is being recorded and will uploaded to our website shortly (https://www.tigergraph.com/webinars/) and the URL will be emailed you ● If you have issues with Zoom please contact the panelists via chat 3
- 4. © 2020 TigerGraph.All Rights Reserved Move Faster with TigerGraph Cloud 4 Built for agile teams who would rather build innovative applications than procure hardware or configure and manage databases ● Start for free ● Move to production with distributed data and HA replication
- 5. © 2020 TigerGraph.All Rights Reserved Today’s Outline 5 1 3 2 Recap of Parts 1 to 3: Path, Centrality & Community Graph Algorithms Similarity Algorithms Local vs. Global structure/properties Same is Easy; Similarity is Tricky What factors are important to you? 4 Demo Running and modifying GSQL Similarity Algorithms
- 6. © 2020 TigerGraph.All Rights Reserved Review: Analytics with Graph Algorithms ● Graph algorithms answer fundamental questions about connected data ● Each algorithm in a library is tool in an analytics toolkit ● Building blocks for more complex business questions 6 Specialized functions Combine to make something better
- 7. © 2020 TigerGraph.All Rights Reserved Example Questions/Analyses for Graph Algorithms Which entity is most centrally located? ● For delivery logistics or greatest visibility ● Closeness Centrality, Betweenness Centrality algorithms 7 How much influence does this entity exert over the others? ● For market penetration & buyer influence ● PageRank algorithm Which entity has similar relationships to this entity? ● For grouping customers, products, etc. ● Cosine Similarity, SimRank, RoleSim algorithms What are the natural community groupings in the graph? ● For partitioning risk groups, workgroups, product offerings, etc. ● Community Detection, MinCut algorithms
- 8. © 2020 TigerGraph.All Rights Reserved Summary for Shortest Path Algorithms Graph Gurus 26 8 1 4 3 Graph Algorithms - tools and building blocks for analyzing graph data GSQL Algorithm Library - runs in-database, high-performance, easy to read and modify Shortest Path Algorithms - different algorithms for weighted and unweighted graphs 2 Learning To Use Algorithms - know what problem they solve, pros and cons
- 9. © 2020 TigerGraph.All Rights Reserved Summary for Centrality Algorithms Graph Gurus 27 9 1 4 3 Centrality Algorithms - abstract concepts of location and travel Customizing GSQL Library algorithms is easy and familiar, like procedural SQL PageRank - uses directed referral edges to find the most influential nodes. Personalized PageRank is localized. 2 Closeness and Betweenness use shortest paths. Betweenness is more complex.
- 10. © 2020 TigerGraph.All Rights Reserved Summary for Community Detection Algorithms Graph Gurus 29 10 1 3 2 Community Detection Algorithms Use connectedness to decide boundaries Strict vs. Lenient Community Rules Black&white rules are not always helpful. Louvain uses relative density. Communities are Clusters, not Partitions Don't have to include everyone. Can overlap? 4 Pre- or Post- step with other algorithms Many algorithms assume you start from just one connected community
- 11. © 2020 TigerGraph.All Rights Reserved Some Types of Graph Algorithms ● Search ● Path Finding & Analytics ● Centrality / Ranking ● Clustering / Community Detection ● Similarity ● Classification 11
- 12. © 2020 TigerGraph.All Rights Reserved Healthcare Best Practices: Identify Similar Individuals 12 Wellness, resources, and cost at stake ● Track events and interactions in the patient's journey ● What makes this individual and their journey significant? ● What are key points, when the right intervention is essential?
- 13. © 2020 TigerGraph.All Rights Reserved Other Use Cases ● What were the early signs that made the opportunity stand out? ● What steps did the investor take? ● How did the opportunity and market change? 13 Find Investment Opportunities Similar to Successful Ones: Possible signs: ● Sudden suspicious transactions ○ Size ○ Transaction type ○ Business type ○ Platform used ● Connections to parties already considered high risk Find Activity Similar to That of a Known Fraudster/Swindler:
- 14. © 2020 TigerGraph.All Rights Reserved Modeling Similarity as a Graph Problem Tables: 14 Customer Supplier Location 2 Product Payment PURCHASED RESIDES SHIPS TO PURCHASED SHIPS FROM A C C EPTED MAKES Location 2 N O TIFIES Entity Graph: Simple hub-and-spoke pattern Location 1 Entity itself is in one table, but the factors that make the entity distinctive require joins to other tables
- 15. © 2020 TigerGraph.All Rights Reserved "Same" is Easy; Similar is Tricky ● Conceptually easy to find exact matches ○ But exact match is rarely needed or appropriate ● Similarity is in the Eye of the Beholder ○ What Factors do you care about? ○ What are their relative importance? ● Are you outcome-driven? ○ Graph-based approach is good because it shows you all known associations, without picking in advance which ones matter. ○ Machine learning can help pick the important factors. 15
- 16. © 2020 TigerGraph.All Rights Reserved What Factors to Use 16 Q: Which is more similar to a hippopotamus: a whale or a pig? A: If you look are regular observations, it's a pig. If you look at genes, it's a whale.
- 17. © 2020 TigerGraph.All Rights Reserved Classical Feature-Based Similarity Functions ● Jaccard Similarity ● Cosine Similarity ● Graph-based variations 17
- 18. © 2020 TigerGraph.All Rights Reserved Jaccard Similarity Count how many features are in common ● When you have non-numeric, categorical, yes/no features ● Jaccard value ranges from 0 to 1 18 Example: ● Basket 1 has {milk, bread, chicken, mushrooms, bananas} ● Basket 2 has {bread, cheese, ham, bananas} ● Basket 3 has {tofu, noodles, bok choy, mushrooms,} Jacc(1,2) = |{bread,bananas}| / |{milk, bread, chicken, mushrooms, bananas, cheese, ham} = 2/7 Jacc(1,3) = |{mushrooms}| / |{milk, bread, chicken, mushrooms, bananas,tofu,noodles, bok choy} = 1/8 A B A ∩ B A ∪ B
- 19. © 2020 TigerGraph.All Rights Reserved Cosine Similarity If each item is described by a list of numerical values (a vector), then multiply the vectors together and divide by their lengths. ● If A=B, then Cos(A,B) = 1 19 A= (6,2) B= (4,4) Cos(A,B) = (6*4 + 2*4) / [√(6*6+2*2)√(4*4 + 4*4)] = (24+8) / [√40 √32 ] = 0.8944
- 20. © 2020 TigerGraph.All Rights Reserved Graph-Based Structural Similarity Use a vertex's neighbors as its feature set ● Jaccard: Count each neighboring vertex 20 A Order W B X Y Z 2 3 1 2 1 4 A's neighbors = {W,Y,Z} B's neighbors = {W,X,Z} Jacc(A,B) = |{W,Z}| / |{W,X,Y,Z}| = 2/4 W,X,Y,Z represent feature vertices, different vertex types than A,B
- 21. © 2020 TigerGraph.All Rights Reserved Graph-Based Structural Similarity Use a vertex's neighbors as its feature set ● Cosine: Use edge weights to each neighboring vertex 21 A Order W B X Y Z 2 3 1 2 1 4 A's weighted neighbors = {2,0,4,1} B's weighted neighbors = {3,1,0,2} Cos(A,B) = 8 / [√21√14] = 0.4666 W,X,Y,Z represent feature vertices, different vertex types than A,B
- 22. © 2020 TigerGraph.All Rights Reserved SimRank 1. A vertex is perfectly similar to itself: 2. Two vertices are similar if they have similar neighbors: , where Ai = each (in)neighbor of U Bj = each (in)neighbor of V c = constant, typically 0.6 to 0.8 Can be computed iteratively, like PageRank 22
- 23. © 2020 TigerGraph.All Rights Reserved SimRank Example 1st Round: sr(A,B) = c * Avg [ sr(W,W), sr(Y,W), sr(Z,W), sr(W,X), sr(Y,X), sr(Z,X), sr(W,Z), sr(Y,Z), sr(Z,Z)] = c*(1+0+0+0+0+0+0+0+1)/9 = 2c/9 23 A Order W B X Y Z 2 3 1 2 1 4 A and B each have 3 neighbors, so there are 9 possible pairs of neighbors. 2 of the neighbors are shared (W and Z) To complete round 1, compute scores for every other pair of vertices. For round 2, repeat, using the round 1 values for computing the average SimRank of neighbors.
- 24. © 2020 TigerGraph.All Rights Reserved Comments ● Cosine, Jaccard are local computations, looking only one hop deep. ● SimRank analyzes more of the graph (typically the whole graph), looks deeper to find more meaningful similarity, thus requires more computation. ● NOTE: Cosine, Jaccard, and SimRank work okay on homogenous graphs (one type of vertex, but have even more meaning with bipartite graphs, where there are Entity vertices and Feature vertices. ● Drawback: SimRank penalizes for having more neighbors in common. 24
- 25. © 2020 TigerGraph.All Rights Reserved A More Rigorous Sense of Structural Similarity ● Smith family structurally equivalent to Jones family? ● Smith family similar to Lee family? ● What about the individuals: Who is S3 similar to? The most similar? Somewhat similar? 25
- 26. © 2020 TigerGraph.All Rights Reserved RoleSim Two vertices are similar if they have similar neighborhoods, where both size and type of neighborhood matters. ● Key difference from SimRank is to find not the average neighbor pairing but the optimal neighbor pairing. w(M) is a maximal matching of the neighbors Nu and Nv of vertices u and v, respectively. ● If neighborhoods of u and v are equivalent, then RoleSim(u,v) = 1 26
- 27. © 2020 TigerGraph.All Rights Reserved RoleSim Example 1st Round: rs(A,B) = (1-b) * Max [ sr(W,W), sr(Y,W), sr(Z,W), sr(W,X), sr(Y,X), sr(Z,X), sr(W,Z), sr(Y,Z), sr(Z,Z)] / 3 + b = (1-b)*(1+1+0)/3 + b = 2(1-b)/3 + b 27 A Order W B X Y Z 2 3 1 2 1 4 A and B each have 3 neighbors, so we seek 3 pairs of neighbors. 2 of the neighbors are shared (W and Z) To complete round 1, compute scores for every other pair of vertices. For round 2, repeat, using the round 1 values for computing the max. RoleSim of neighbor-pairs.
- 28. DEMO GSQL Graph Algorithmsin TigerGraph Cloud 28
- 29. © 2020 TigerGraph.All Rights Reserved GSQL Graph Algorithm Library ● Written in GSQL - high-level, parallelized ● Open-source, user-extensible ● Well-documented 29 docs.tigergraph.com/graph-algorithm-library
- 30. © 2020 TigerGraph.All Rights Reserved TigerGraph GSQL Graph Algorithm Library ✓ Call each algorithm as a GSQL query or as a RESTful endpoint ✓ Run the algorithms in-database (don't export the data) ✓ Option to update the graph with the algorithm results ✓ Able to modify/customize the algorithms. Turing-complete language. ✓ Massively parallel processing to handle big graphs 30
- 31. © 2020 TigerGraph.All Rights Reserved Summary 31 1 3 2 Similarity is in the Eye of the Beholder What factors matter to you? How much? Jaccard and Cosine Similarity Counting matches vs. measuring numerical alignment Graph modeling helps with Similarity Hub-and-spoke view 4 Deeper Measures: SimRank and RoleSim Define similarity recursively, look multiple hops deep (globally)
- 32. Q&A Please submit yourquestions via the Q&A tab in Zoom 32
- 33. © 2020 TigerGraph.All Rights Reserved More Questions? Join our Developer Forum https://groups.google.com/a/opengsql.org/forum/#!forum/gsql-users Sign up for our Developer Office Hours (every Thursday at 11 AM PST) https://info.tigergraph.com/officehours 33
- 34. © 2020 TigerGraph.All Rights Reserved Additional Resources Start Free at TigerGraph Cloud Today! https://www.tigergraph.com/cloud/ Test Drive Online Demo https://www.tigergraph.com/demo Download the Developer Edition https://www.tigergraph.com/download/ Guru Scripts https://github.com/tigergraph/ecosys/tree/master/guru_scripts 34
- 35. © 2020 TigerGraph.All Rights Reserved Upcoming Graph Guru Events Coming to London, San Francisco, Seattle and more. View all events and request your own here: https://www.tigergraph.com/graphguruscomestoyou/ Next webinar: Using Giraffle to Manage Deployments at an Enterprise Scale Wednesday, March 11, at 11am PST https://info.tigergraph.com/webinar-giraffle 35
- 36.