Graph Algorithms: The Core Of Graph Analytics
Graph Algorithms:The Core of Graph AnalyticsMelli Annamalai and Ryota Yamanaka, Product Management, OracleAugust 27, 2020
AskTOM Office Hours: Graph Database and Analytics Welcome to our AskTOM Graph Office Hours series!We’re back with new product updates, use cases, demos and technical ch?oh 3084 Sessions will be held about once a month Subscribe at the page above for updates on upcoming session topics & datesAnd submit feedback, questions, topic requests, and view past session recordings Note: Spatial now has a new Office Hours series for locationanalysis & mapping features in Oracle .search?oh 77612Copyright 2020, Oracle and/or its affiliates
Safe harbor statementThe following is intended to outline our general product direction. It is intended for informationpurposes only, and may not be incorporated into any contract. It is not a commitment to deliver anymaterial, code, or functionality, and should not be relied upon in making purchasing decisions. Thedevelopment, release, timing, and pricing of any features or functionality described for Oracle’sproducts may change and remains at the sole discretion of Oracle Corporation.3Copyright 2020, Oracle and/or its affiliates
Agenda1. Introduction to Graph Algorithms2. Graph Algorithms Use Cases3. Running Graph AlgorithmsMelliMelliRyota4. Scalability in Graph AnalyticsRyotaMelliRyotaNashua, New Hampshire, USABangkok, Thailand@AnnamalaiMelli4Copyright 2020, Oracle and/or its affiliates@ryotaymnk
Recap: Creating a Graph and Querying a Graph5Copyright 2020, Oracle and/or its affiliates
Product Overview: Graph Database and AnalyticsGraph data model: A different way to model your dataProperty Graph Feature in Oracle Database:Enterprise capabilitiesHighly scalable In-memory query and analytics and in-database query 10s of billions of edges and verticesPGQL: Powerful SQL-like graph query languageAnalytics Java API: 50 pre-built graph analysis algorithmsVisualization Light-weight web application, UI accessible from a browser6Copyright 2020, Oracle and/or its affiliatesGraph Applications: Financial Law enforcement andsecurity Manufacturing Public sector Pharmaand more
What is a Graph?A collection of points (vertices/nodes) and lines between those points (edges)datenameMelliamountcash transferJeanaddressaccount nocash transferpurchasedJohn7Copyright 2020, Oracle and/or its affiliates
Create a Graph from Database TablesACCT IDACCOUNTSPGQL DDL SYNTAX:0CREATE PROPERTY GRAPH bank graphVERTEX TABLES (ACCOUNTS LABEL Account PROPERTIES ( ACCT ID ))EDGE TABLES (TRANSACTIONSSOURCE KEY ( FROM ACCOUNT ) REFERENCES ACCOUNTSDESTINATION KEY ( TO ACCOUNT ) REFERENCES ACCOUNTSLABEL transfer PROPERTIES ( AMOUNT )12345 TRANSACTIONSFROM ACCOUNTTO 0705024934363
Cash Transfer Graph9Copyright 2020, Oracle and/or its affiliates
10Graph Queries: Finding Patterns in a GraphProperty Graph Query Language (PGQL)Copyright 2020, Oracle and/or its affiliatesIs there a pattern that connectsIs therea patternthat connects528to 326and 569?259 to 869 to 387 and TCHMATCH(v1)-[e1]- (v2),(v1)-[e1]- (v2)-[e2]- (v3)-[e3]- (v1)MATCHwhere v1.id 259(v1)-[e2]- (v3)and v2.id 869 and v3.id 387where v1.id 528 and v2.id 326 and v3.id 569
11Graph Queries: Finding Patterns in a GraphCyclesPathsSELECT v1, v2, v3, e1,e2,e3MATCH (v1)-[e1]- (v2)-[e2]- (v3)-[e3]- (v1)SELECT *AxleMATCH (n)-/:transfer{1,6}/- (m)RodWHERE ID(n) 1WheelDiscSELECT n, ARRAY AGG(ID(m)), ARRAY AGG(ID(e))Screw (-[e:transfer]- (m))* (n))MATCH TOP 2 SHORTEST ((n)WHERE ID(n) 1PatternsCopyright 2020, Oracle and/or its affiliates
Graph Algorithms12Copyright 2020, Oracle and/or its affiliates
Graph AlgorithmsAnalyze the full graphDerive information about: What is the value of a vertex in relation to other vertices? Centrality, PageRank, Betweenness Centrality, In how many ways can you reach vertex B from vertex A? Shortest path, Fattest path, Number of hops in path, How tightly (or sparsely) is the graph connected? Arethere tightly connected sub-graphs within the graph? Are there isolated vertices in the graph? Strongly connected, Weakly connected components, Evaluating structures13Copyright 2020, Oracle and/or its affiliates
Graph Analytics - 50 Built-in AlgorithmsDetecting Components and CommunitiesRanking and WalkingPageRank, Personalized PageRank,Degree Centrality, Closeness Centrality,Vertex Betweenness Centrality,Eigenvector Centrality, HITS, SALSA,Random Walk with RestartStrongly Connected Components,Weakly Connected Components,Label Propagation,Conductance Minimization,InfomapEvaluating StructuresPath-FindingAdamic-Adar Index, Conductance,Cycle Detection, Degree Distribution,Eccentricity, K-Core, LCC, Modularity,Reachability Topological Ordering,Triangle CountingLink Prediction14WTF (Who to follow)Copyright 2020, Oracle and/or its affiliatesShortest Path (Bellman-Ford, Dijkstra,Bidirectional Dijkstra), Fattest Path,Compute Distance Index,Enumerate Simple Paths,Fast Path Finding, Hop DistanceOthersMinimum Spanning-Tree,Matrix Factorization
Ranking: Importance of VerticesUse cases Financial: Find accounts throughwhich most of the money flows Retail: Influencers in a social network,for product recommendation Law enforcement: Vertices with highbetweenness centrality valuesdetermine links between groups15Copyright 2020, Oracle and/or its affiliates
Paths between VerticesUse cases Telecommunications: Networkmanagement: What-If analysis. Financial: Was there a cash transferbetween these two accounts?AxleRodWheelDiscScrew16Copyright 2020, Oracle and/or its affiliates Manufacturing: Dependency analysis in aBill of Materials graph
Detecting CommunitiesUse cases Financial: Does this suspiciousaccount belong to acommunity of fraudsters? Financial: Community of users usingthe same device Retail: Can behavior of members of thecommunity predict churn?17Copyright 2020, Oracle and/or its affiliates
Running Graph Algorithms18Copyright 2020, Oracle and/or its affiliates
Setup Your Graph ServerInstallation: .3Clone repository(Note, the branch is 20.3) git clone https://github.com/ryotayamanaka/oracle-pg.git -b 20.3Download and extract packages(Note, the packages are version 20.3) sh extract.shBuild and start the docker containers docker-compose up -d19Copyright 2020, Oracle and/or its affiliates
Run Algorithms from JShell or ZeppelinThe interpreter for ApacheZeppelin Notebook is providedand Groovy syntax is supported.(Python API is also planned)We can run algorithms:analyst.pagerank(graph2)20Copyright 2020, Oracle and/or its affiliates
Write Queries to Get the ResultsAfter running algorithms, theresults are stored into the graph,e.g. each node gets a newproperty "pagerank".pagerank: 0.180Users can access the results usingPGQL queries:SELECT a.account no, a.pagerankFROM MATCH (a)ORDER BY a.pagerank DESC21Copyright 2020, Oracle and/or its affiliatespagerank: 0.123
Visualize the ResultsLogin with the samesession ID as the onewhich ran the algorithms.The size of nodes can belinked to the pagerankscores.22Copyright 2020, Oracle and/or its affiliates
Example - Bank Customer b lab-2-customer-360-analysis23Copyright 2020, Oracle and/or its affiliates
Influential AccountsWhich is the account with the highest pagerank?Filter by "transfer" relationship, run pagerankalgorithm. The result is stored as "pagerank" newnode property, and it can be queried.graph2 graph.filter(new EdgeFilter("edge.label() 'transfer'"));analyst.pagerank(graph2);SELECT a.account no, a.pagerankFROM MATCH (a)ORDER BY a.pagerank DESC24
Community DetectionFind the communities where every accountis reachable from every other accountRun strongly connected component algorithm andreflect the results into "component" node property.result analyst.sccKosaraju(sg)SELECTa.scc kosaraju, COUNT(a.account no)FROM MATCH (a)GROUP BY a.scc kosaraju25
RecommendationWhich merchants should be recommended to theaccount "-201" based on the purchase history?Filter by "purchased" relationship, run personalizedpagerank from the node 201, and then query :SELECT ID(x), x.name, x.pagerankFROM MATCH (x)WHERE x.type 'merchant'AND NOT EXISTS (SELECT *FROM MATCH (x)-[:purchased by]- (a)WHERE ID(a) 201)ORDER BY x.pagerank DESC26
More AlgorithmsAll built-in algorithmsare listed here.https://docs.oracle.com/cd/E56133 ight 2020, Oracle and/or its affiliates
More AlgorithmsEach algorithm pageprovides the description,implementation, and thelink to Javadoc page.28Copyright 2020, Oracle and/or its affiliates
More Algorithms.29Copyright 2020, Oracle and/or its affiliatesThe method section foreach algorithm hasexamples to show howit can be used in Java.
Scalability in Graph Analytics30Copyright 2020, Oracle and/or its affiliates
Two Types of Processing in Graph AnalyticsQuery Search for surrounding nodes Traverse property paths Pattern matching Extract sub-graphs31Copyright 2020, Oracle and/or its affiliatesAlgorithm Rank importance of nodes Detect components and clusters Evaluate structure of communities Shortest paths
Two Types of Processing in Graph AnalyticsOracle Graph Server can execute both queries, algorithms, mutation (simplify, filter, .)and their combination.Which is the node in 3 stepsfrom my node, and has the highestpagerank among them?32Copyright 2020, Oracle and/or its affiliates
Graph Algorithms and Analysis FlowsPattern 1 - Finding significant nodes1. Run graph algorithms for scoring all nodes ranking (centrality, pagerank, .) community detection2. The scores ( new features) are used for: finding high score nodes as conditions in graph query as machine learning input Use Cases Financial fraud detection, Tax fraud detection,Influencer detection, Anormal behavior detectionin cyber security, Scoring importance of devices innetworks (utility and communication)33Copyright 2020, Oracle and/or its lance.share infofraud communityfraud closeness.is fraudMule account detection(AskTOM - May 28, 2020)
Graph Algorithms and Analysis FlowsPattern 2 - Enabling advanced queries1. Select specific node(s)2. Run graph algorithms against the node(s) personalized ranking (PPR, .) community detection reachability3. Query to return the results to applications: often real-time Use Cases Reachability between devices (utility andcommunication), Recommendation for a customer(retail), Find other members in the samecommunity (fraud and crime analysis)34Copyright 2020, Oracle and/or its affiliatesReal-time recommendation app(AskTOM - July 2, 2020)
Custom AlgorithmsPGX Algorithm is a Javasyntax language to writecustom graph algorithms(Using Green-Marl is notsupported)PGX Algorithm specificationis here. Also, each built-inalgorithm page shows theirimplementations in PGXAlgorithm.35Copyright 2020, Oracle and/or its affiliates
Custom AlgorithmsPartsRootUse case of custom algorithm inManufacturing BoM (bill of materials):1 Some of the calculation processes can beoptimized, implementing them as storedprograms on Graph Server. E.g. sum up the numbers of parts in a BoMtree. One-time traversal from the root node(BFS: breath first search) calculates thenumbers of all parts and the graph cankeep the results as node properties.PartsA2PartsD1PartsH36Copyright 2020, Oracle and/or its rtsGIDnumA1B1C4D2E6F8G40H2I12
Helpful Links Graphs at OracleSearch for "Oracle Graph Server and Client"to download from oracle.comhttps://www.oracle.com/goto/graph Oracle Property Graphhttp://www.oracle.com/goto/propertygraph Blog: Examples, Tips and Trickshttp://bit.ly/OracleGraphBlog AskTOM Series: ffice 3084 Social Media Twitter: @OracleBigData, @SpatialHannes, @JeanIhm, @ryotaymnk LinkedIn: Oracle Spatial and Graph Group YouTube: youtube.com/c/OracleSpatialandGraph37Copyright 2020, Oracle and/or its affiliates
AskTOM Office Hours: Graph Database and Analytics Welcome to our AskTOM Graph Office Hours series!We’re back with new product updates, use cases, demos and technical ch?oh 3084 Sessions will be held about once a month Subscribe at the page above for updates on upcoming session topics & datesAnd submit feedback, questions, topic requests, and view past session recordings Note: Spatial now has a new Office Hours series for locationanalysis & mapping features in Oracle .search?oh 776138Copyright 2020, Oracle and/or its affiliates
Our mission is to help peoplesee data in new ways, discover insights,unlock endless possibilities.
Graph Algorithms: The Core of Graph Analytics Melli Annamalai and Ryota Yamanaka, Product Management, Oracle August 27, 2020. 2 AskTOM Office Hours: Graph Database and Analytics Welcome to our AskTOM Graph Office Hours series! We’re back with
May 02, 2018 · D. Program Evaluation ͟The organization has provided a description of the framework for how each program will be evaluated. The framework should include all the elements below: ͟The evaluation methods are cost-effective for the organization ͟Quantitative and qualitative data is being collected (at Basics tier, data collection must have begun)
Silat is a combative art of self-defense and survival rooted from Matay archipelago. It was traced at thé early of Langkasuka Kingdom (2nd century CE) till thé reign of Melaka (Malaysia) Sultanate era (13th century). Silat has now evolved to become part of social culture and tradition with thé appearance of a fine physical and spiritual .
On an exceptional basis, Member States may request UNESCO to provide thé candidates with access to thé platform so they can complète thé form by themselves. Thèse requests must be addressed to esd rize unesco. or by 15 A ril 2021 UNESCO will provide thé nomineewith accessto thé platform via their émail address.
̶The leading indicator of employee engagement is based on the quality of the relationship between employee and supervisor Empower your managers! ̶Help them understand the impact on the organization ̶Share important changes, plan options, tasks, and deadlines ̶Provide key messages and talking points ̶Prepare them to answer employee questions
Dr. Sunita Bharatwal** Dr. Pawan Garga*** Abstract Customer satisfaction is derived from thè functionalities and values, a product or Service can provide. The current study aims to segregate thè dimensions of ordine Service quality and gather insights on its impact on web shopping. The trends of purchases have
Chính Văn.- Còn đức Thế tôn thì tuệ giác cực kỳ trong sạch 8: hiện hành bất nhị 9, đạt đến vô tướng 10, đứng vào chỗ đứng của các đức Thế tôn 11, thể hiện tính bình đẳng của các Ngài, đến chỗ không còn chướng ngại 12, giáo pháp không thể khuynh đảo, tâm thức không bị cản trở, cái được
The totality of these behaviors is the graph schema. Drawing a graph schema . The best way to represent a graph schema is, of course, a graph. This is how the graph schema looks for the classic Tinkerpop graph. Figure 2: Example graph schema shown as a property graph . The graph schema is pretty much a property-graph.
Oracle Database Spatial and Graph In-memory parallel graph analytics server (PGX) Load graph into memory for analysis . Command-line submission of graph queries Graph visualization tool APIs to update graph store : Graph Store In-Memory Graph Graph Analytics : Oracle Database Application : Shell, Zeppelin : Viz .
