Given a weighted, oriented, connected graph with $10^7$ vertices and $10^{10}$ edges I need to implement the algorithm for searching various patterns on this graph for less than polynomial time.
Graph node degree can vary from $1$ to $2*10^5$, nodes and edges also have categorical attributes, that can be indexed and used during the pattern search.
Patterns are subgraphs with 5-100 nodes, some examples are shown on the pictures below, multiple edges from one node and looping is possible. The algorithm can be greedy and find only part of all pattern matchings.
I'm looking for a greedy library or method that performs multiple parallel walks on the graph to find the required pattern. It looks like "hub" nodes with a high degree make DFS ineffective for this problem.