Skip to content
START FOR FREE
START FOR FREE
  • SUPPORT
  • COMMUNITY
Menu
  • SUPPORT
  • COMMUNITY
MENUMENU
  • Products
    • The World’s Fastest and Most Scalable Graph Platform

      LEARN MORE

      Watch a TigerGraph Demo

      TIGERGRAPH CLOUD

      • Overview
      • TigerGraph Cloud Suite
      • FAQ
      • Pricing

      USER TOOLS

      • GraphStudio
      • Insights
      • Application Workbenches
      • Connectors and Drivers
      • Starter Kits
      • openCypher Support

      TIGERGRAPH DB

      • Overview
      • GSQL Query Language
      • Compare Editions

      GRAPH DATA SCIENCE

      • Graph Data Science Library
      • Machine Learning Workbench
  • Solutions
    • The World’s Fastest and Most Scalable Graph Platform

      LEARN MORE

      Watch a TigerGraph Demo

      Solutions

      • Solutions Overview

      INCREASE REVENUE

      • Customer Journey/360
      • Product Marketing
      • Entity Resolution
      • Recommendation Engine

      MANAGE RISK

      • Fraud Detection
      • Anti-Money Laundering
      • Threat Detection
      • Risk Monitoring

      IMPROVE OPERATIONS

      • Supply Chain Analysis
      • Energy Management
      • Network Optimization

      By Industry

      • Advertising, Media & Entertainment
      • Financial Services
      • Healthcare & Life Sciences

      FOUNDATIONAL

      • AI & Machine Learning
      • Time Series Analysis
      • Geospatial Analysis
  • Customers
    • The World’s Fastest and Most Scalable Graph Platform

      LEARN MORE

      CUSTOMER SUCCESS STORIES

      • Ford
      • Intuit
      • JPMorgan Chase
      • READ MORE SUCCESS STORIES
      • Jaguar Land Rover
      • United Health Group
      • Xbox
  • Partners
    • The World’s Fastest and Most Scalable Graph Platform

      LEARN MORE

      PARTNER PROGRAM

      • Partner Benefits
      • TigerGraph Partners
      • Sign Up
      TigerGraph partners with organizations that offer complementary technology solutions and services.​
  • Resources
    • The World’s Fastest and Most Scalable Graph Platform

      LEARN MORE

      BLOG

      • TigerGraph Blog

      RESOURCES

      • Resource Library
      • Benchmarks
      • Demos
      • O'Reilly Graph + ML Book

      EVENTS & WEBINARS

      • Graph+AI Summit
      • Graph for All - Million Dollar Challenge
      • Events &Trade Shows
      • Webinars

      DEVELOPERS

      • Documentation
      • Ecosystem
      • Developers Hub
      • Community Forum

      SUPPORT

      • Contact Support
      • Production Guidelines

      EDUCATION

      • Training & Certifications
  • Company
    • Join the World’s Fastest and Most Scalable Graph Platform

      WE ARE HIRING

      COMPANY

      • Company Overview
      • Leadership
      • Legal Terms
      • Patents
      • Security and Compliance

      CAREERS

      • Join Us
      • Open Positions

      AWARDS

      • Awards and Recognition
      • Leader in Forrester Wave
      • Gartner Research

      PRESS RELEASE

      • Read All Press Releases
      TigerGraph Recognized in 2022 Gartner® Critical Capabilities for Cloud Database Management Systems for Analytical Use Cases
      January 12, 2023
      Read More »

      NEWS

      • Read All News

      A Shock to the System: ShockNet Predicts How Economic Shocks Could Affect the World Economy

      TigerGraph Recognized for the First Time in the 2022 Gartner® Magic Quadrant™ for Cloud Database Management Systems

  • START FREE
    • The World’s Fastest and Most Scalable Graph Platform

      GET STARTED

      • Request a Demo
      • CONTACT US
      • Try TigerGraph
      • START FREE
      • TRY AN ONLINE DEMO

Graph Pattern Matching in GSQL

  • Songting Chen
  • March 13, 2019
  • blog, Developers, GSQL
  • Blog >
  • Graph Pattern Matching in GSQL

In this short technical blog, I will show you how to use GSQL to search a graph for all the occurrences of a small graph pattern.  We call this pattern matching.

Consider the problem of matching a pattern of vertices and directed edges in a graph for a single type of vertex. For example, we want to match a given pattern (fig.1) in a graph (fig.2). There are different ways to do the pattern matching, but the basic idea is to pick a reference vertex or edge in the pattern that is a good traversal starting point, and then traverse the graph and try to match the rest of the pattern. I will show you how to do that with two sample solutions.

In the first solution we will start from vertex “A”, and in the second solution, we will start from the edge “B -> C” and use parallel traversal to have 2 symmetrical starting points. For each solution, we have two versions of the query: pattern counting and pattern enumeration. Pattern counting queries only print the occurrence count of the pattern, while pattern enumeration queries list of the specific vertices and edges in each match.

Fig .1 Given Pattern for Pattern Matching

Fig.2 Sample Graph of Social Network

Starting From Vertex “A”

The first solution is to start from each vertex in the graph, treat it as vertex “A” in the pattern, and see if we can successfully traverse in the same pattern as our target pattern.  In other words, we can write a subquery whose traversal flow matches our pattern, and which accepts a starting vertex as an input parameter. This vertex will be regarded as vertex “A” in the process of pattern matching. When doing the pattern matching, we can try to find the “B” and “C” vertices first, then an edge from “B” to “C”, and then check whether they have any common 1-hop neighbor (vertex “D”). We can either count the pattern matches, or also show the details of each pattern matched.

Sample Query of Count Patterns:

# sub query: return the number of matched patterns for the source vertex
CREATE QUERY pattern_count_sub(VERTEX source) FOR GRAPH social returns (INT){
    OrAccum @is_1hop;
    BagAccum<Vertex> @@d;
    A = {source};

    Hop1 = SELECT b
        FROM A:a -(Friend:e) -> Person:b
        ACCUM [email protected]_1hop = true; // flag for 1-hop neighbors
    Hop2 = SELECT c
        FROM Hop1:b -(Friend:e) -> Person:c
        // check if b and c both have @is_1hop=true -> valid b,c pair
        WHERE [email protected]_1hop == true 
        // Count how many neighbors b&c have in common -> d's
        ACCUM @@d += b.neighbors("Friend") INTERSECT
                     c.neighbors("Friend");

    RETURN @@d.size();
}

# main query: print the number of matched patterns for each vertex 
CREATE QUERY pattern_count() FOR GRAPH social {
    MapAccum<Vertex, INT> @@pattern_count;
     Start = {Person.*};
     Start = SELECT s
            FROM Start:s
            ACCUM @@pattern_count += (s -> pattern_count_sub(s));
     PRINT @@pattern_count;
}


JSON Result:

[
  {
    "@@pattern_count": {
      "0": 2,
      "1": 1,
      "2": 1,
      "3": 0,
      "4": 1,
      "5": 0,
      "6": 0
    }
  }
]

If we also want to print each match of the given pattern, we can add a local nested accumulator to store the patterns, and write the details into a file.

Sample Query for Pattern Enumeration:

# sub query: prints the matched patterns for the source vertex to file
CREATE QUERY pattern_detail_sub(VERTEX source, FILE f) FOR GRAPH social returns (INT){
        OrAccum @is_1hop;
        MapAccum<VERTEX, BagAccum<VERTEX>> @patterns;
        SumAccum<INT> @@cnt = 0;
        A = {source};

        Hop1 = SELECT b
               FROM A:a -(Friend:e) -> Person:b
               ACCUM [email protected]_1hop = true; // flag for 1-hop neighbours
        Hop2 = SELECT c
               FROM Hop1:b -(Friend:e) -> Person:c
               // check if b and c both have @is_1hop=true -> valid b,c pair
               WHERE [email protected]_1hop == true
               ACCUM [email protected] += (c -> b.neighbors("Friend") INTERSECT 
                                          c.neighbors("Friend"))
               POST-ACCUM FOREACH (typeC, typeD) IN [email protected] DO
                                  IF typeD.size() > 0 THEN
                                        f.println(source, b, typeC, typeD), 
                                        //(a, b, c, [d]) [d] is a collection of vertex d
                                        @@cnt += typeD.size()
                                  END
                          END;
        RETURN @@cnt;
}

# main query: call sub query for each vertex
CREATE QUERY pattern_detail(FILE f) FOR GRAPH social {
          SumAccum<INT> @@pattern_count;
          Start = {Person.*};

          f.println("a", "b", "c", "[d]");
          Start = SELECT s
                  FROM Start:s
                  ACCUM @@pattern_count += pattern_detail_sub(s, f);

          PRINT @@pattern_count;
}

JSON Result:

[
  {
    "@@pattern_count": 5
  }
]

File Output:

a,b,c,[d]
2,4,5,6
4,5,6,3
0,2,4,5
0,4,5,6
1,2,4,5

Starting From Edge “B->C”

Another solution is to use the B->C edge as the head of the pattern. Every edge in the graph is a candidate B->C edge, and then we find whether the source and target vertices have common neighbors (“D” and “A”) through both edges and reverse edges. This solution can only be used when the graph contains reverse edges.

Sample Query to Count Patterns:

CREATE QUERY pattern_count_edge() FOR GRAPH social {
        SumAccum<INT> @@n_pattern;
        Start = {Person.*};
        Start = SELECT b
                FROM Start:b -(Friend:e) -> Person:c
                ACCUM INT through_edge = COUNT(b.neighbors("Friend") INTERSECT 
                                               c.neighbors("Friend")),
                      INT through_rev_edge = COUNT(b.neighbors("Also_Friend") INTERSECT 
                                                   c.neighbors("Also_Friend")),
                      @@n_pattern += through_edge * through_rev_edge;
        PRINT @@n_pattern;
}

JSON Result:

[
  {
    "@@n_pattern": 5
  }
]

Sample Query for Pattern Enumeration:

CREATE QUERY pattern_detail_edge(FILE f) FOR GRAPH social {
    SumAccum<INT> @@n_pattern;
    GroupByAccum<VERTEX typeC, BagAccum<VERTEX> typeA, BagAccum<VERTEX> typeD> @patterns;
    Start = {Person.*};

    f.println("a", "b", "c", "[d]");
    Start = SELECT b
            FROM Start:b -(Friend:e) -> Person:c
            ACCUM [email protected] += (c -> b.neighbors("Also_Friend") INTERSECT 
                                       c.neighbors("Also_Friend"), 
                                       b.neighbors("Friend") INTERSECT 
                                       c.neighbors("Friend"))
            POST-ACCUM FOREACH (typeC, typeA, typeD) IN [email protected] DO
                               IF typeA.size() > 0 AND typeD.size() > 0 THEN
                                       @@n_pattern += typeA.size() * typeD.size(),
                                       FOREACH a IN typeA DO
                                               f.println(a, b, typeC, typeD)
                                       END
                               END
                       END;
    PRINT @@n_pattern;
}

JSON Result:

[
  {
    "@@n_pattern": 5
  }
]

File Output:

a,b,c,[d]
1,2,4,5
0,2,4,5
0,4,5,6
2,4,5,6
4,5,6,3

To try these queries in the sample graph, please click on the Github link below and follow the instructions: https://github.com/Suxiaocai/blog_examples/tree/master/pattern_match

You Might Also Like

TigerGraph Showcases Unrivaled Performance at Scale

TigerGraph Showcases Unrivaled Performance at Scale

January 12, 2023
How to Create a Visual Graph Analytics Application Using TigerGraph Insights in 30 mins

How to Create a Visual Graph...

November 14, 2022
Turbocharge your business intelligence with TigerGraph’s ML Workbench on TigerGraph Cloud

Turbocharge your business intelligence with TigerGraph’s...

November 14, 2022

Introducing TigerGraph 3.0

July 1, 2020

Everything to Know to Pass your TigerGraph Certification Test

June 24, 2020

Neo4j 4.0 Fabric – A Look Behind the Curtain

February 7, 2020

TigerGraph Blog

  • Categories
    • blogs
      • About TigerGraph
      • Benchmark
      • Business
      • Community
      • Compliance
      • Customer
      • Customer 360
      • Cybersecurity
      • Developers
      • Digital Twin
      • eCommerce
      • Emerging Use Cases
      • Entity Resolution
      • Finance
      • Fraud / Anti-Money Laundering
      • GQL
      • Graph Database Market
      • Graph Databases
      • GSQL
      • Healthcare
      • Machine Learning / AI
      • Podcast
      • Supply Chain
      • TigerGraph
      • TigerGraph Cloud
    • Graph AI On Demand
      • Analysts and Research
      • Customer 360 and Entity Resolution
      • Customer Spotlight
      • Development
      • Finance, Banking, Insurance
      • Keynote
      • Session
    • Video
  • Recent Posts

    • It’s Time to Harness the Power of Graph Technology [Infographic]
    • TigerGraph Showcases Unrivaled Performance at Scale
    • TigerGraph 101 An Introduction to Graph | Jan 26th @ 9am PST
    • Data Science Salon New York
    • Tech For Retail
    TigerGraph

    Product

    SOLUTIONS

    customers

    RESOURCES

    start for free

    TIGERGRAPH DB
    • Overview
    • Features
    • GSQL Query Language
    GRAPH DATA SCIENCE
    • Graph Data Science Library
    • Machine Learning Workbench
    TIGERGRAPH CLOUD
    • Overview
    • Cloud Starter Kits
    • Login
    • FAQ
    • Pricing
    • Cloud Marketplaces
    USEr TOOLS
    • GraphStudio
    • TigerGraph Insights
    • Application Workbenches
    • Connectors and Drivers
    • Starter Kits
    • openCypher Support
    SOLUTIONS
    • Why Graph?
    industry
    • Advertising, Media & Entertainment
    • Financial Services
    • Healthcare & Life Sciences
    use cases
    • Benefits
    • Product & Service Marketing
    • Entity Resolution
    • Customer 360/MDM
    • Recommendation Engine
    • Anti-Money Laundering
    • Cybersecurity Threat Detection
    • Fraud Detection
    • Risk Assessment & Monitoring
    • Energy Management
    • Network & IT Management
    • Supply Chain Analysis
    • AI & Machine Learning
    • Geospatial Analysis
    • Time Series Analysis
    success stories
    • Customer Success Stories

    Partners

    Partner program
    • Partner Benefits
    • TigerGraph Partners
    • Sign Up
    LIBRARY
    • Resources
    • Benchmark
    • Webinars
    Events
    • Trade Shows
    • Graph + AI Summit
    • Million Dollar Challenge
    EDUCATION
    • Training & Certifications
    Blog
    • TigerGraph Blog
    DEVELOPERS
    • Developers Hub
    • Community Forum
    • Documentation
    • Ecosystem

    COMPANY

    Company
    • Overview
    • Careers
    • News
    • Press Release
    • Awards
    • Legal
    • Patents
    • Security and Compliance
    • Contact
    Get Started
    • Start Free
    • Compare Editions
    • Online Demo - Test Drive
    • Request a Demo

    Product

    • Overview
    • TigerGraph 3.0
    • TIGERGRAPH DB
    • TIGERGRAPH CLOUD
    • GRAPHSTUDIO
    • TRY NOW

    customers

    • success stories

    RESOURCES

    • LIBRARY
    • Events
    • EDUCATION
    • BLOG
    • DEVELOPERS

    SOLUTIONS

    • SOLUTIONS
    • use cases
    • industry

    Partners

    • partner program

    company

    • Overview
    • news
    • Press Release
    • Awards

    start for free

    • Request Demo
    • take a test drive
    • SUPPORT
    • COMMUNITY
    • CONTACT
    • Copyright © 2023 TigerGraph
    • Privacy Policy
    • Linkedin
    • Facebook
    • Twitter

    Copyright © 2020 TigerGraph | Privacy Policy

    Copyright © 2020 TigerGraph Privacy Policy

    • SUPPORT
    • COMMUNITY
    • COMPANY
    • CONTACT
    • Linkedin
    • Facebook
    • Twitter

    Copyright © 2020 TigerGraph

    Privacy Policy

    • Products
    • Solutions
    • Customers
    • Partners
    • Resources
    • Company
    • START FREE
    START FOR FREE
    START FOR FREE
    TigerGraph
    PRODUCT
    PRODUCT
    • Overview
    • GraphStudio UI
    • Graph Data Science Library
    TIGERGRAPH DB
    • Overview
    • Features
    • GSQL Query Language
    TIGERGRAPH CLOUD
    • Overview
    • Cloud Starter Kits
    TRY TIGERGRAPH
    • Get Started for Free
    • Compare Editions
    SOLUTIONS
    SOLUTIONS
    • Why Graph?
    use cases
    • Benefits
    • Product & Service Marketing
    • Entity Resolution
    • Customer Journey/360
    • Recommendation Engine
    • Anti-Money Laundering (AML)
    • Cybersecurity Threat Detection
    • Fraud Detection
    • Risk Assessment & Monitoring
    • Energy Management
    • Network Resources Optimization
    • Supply Chain Analysis
    • AI & Machine Learning
    • Geospatial Analysis
    • Time Series Analysis
    industry
    • Advertising, Media & Entertainment
    • Financial Services
    • Healthcare & Life Sciences
    CUSTOMERS
    read all success stories

     

    PARTNERS
    Partner program
    • Partner Benefits
    • TigerGraph Partners
    • Sign Up
    RESOURCES
    LIBRARY
    • Resource Library
    • Benchmark
    • Webinars
    Events
    • Trade Shows
    • Graph + AI Summit
    • Graph for All - Million Dollar Challenge
    EDUCATION
    • TigerGraph Academy
    • Certification
    Blog
    • TigerGraph Blog
    DEVELOPERS
    • Developers Hub
    • Community Forum
    • Documentation
    • Ecosystem
    COMPANY
    COMPANY
    • Overview
    • Leadership
    • Careers  
    NEWS
    PRESS RELEASE
    AWARDS
    START FREE
    Start Free
    • Request a Demo
    • SUPPORT
    • COMMUNITY
    • CONTACT
    Dr. Jay Yu

    Dr. Jay Yu | VP of Product and Innovation

    Dr. Jay Yu is the VP of Product and Innovation at TigerGraph, responsible for driving product strategy and roadmap, as well as fostering innovation in graph database engine and graph solutions. He is a proven hands-on full-stack innovator, strategic thinker, leader, and evangelist for new technology and product, with 25+ years of industry experience ranging from highly scalable distributed database engine company (Teradata), B2B e-commerce services startup, to consumer-facing financial applications company (Intuit). He received his PhD from the University of Wisconsin - Madison, where he specialized in large scale parallel database systems

    Todd Blaschka | COO

    Todd Blaschka is a veteran in the enterprise software industry. He is passionate about creating entirely new segments in data, analytics and AI, with the distinction of establishing graph analytics as a Gartner Top 10 Data & Analytics trend two years in a row. By fervently focusing on critical industry and customer challenges, the companies under Todd's leadership have delivered significant quantifiable results to the largest brands in the world through channel and solution sales approach. Prior to TigerGraph, Todd led go to market and customer experience functions at Clustrix (acquired by MariaDB), Dataguise and IBM.