## 3 Proposed Graph Compression Scheme
### Graph Manager and Reference Pattern Generator  
Figure 2 shows the structure and operation of the graph manager and reference pattern generator. The graph manager consists of two main modules. The first is the graph constructor. The graph constructor takes raw graph stream data as input and builds them into a graph. Raw graph stream data consist of edge data, for example \(\{(\
u 1,\
u 2),(\
u 2,\
u 3),\ldots\}\), which represents an edge stream. The graph constructed by the graph constructor is then passed to the reference pattern generator to find frequent patterns. The second component, the graph pattern manager, receives reference pattern candidates from the reference pattern generator, and stores and manages them in the pattern dictionary. Pattern management includes deciding reference patterns based on pattern frequency and size, and deleting less important patterns. This is explained in detail in Section 3.3. The reference pattern generator creates reference pattern candidates through a three-step process. First, in the frequent pattern initialization stage, the graph's frequent patterns are initialized. Second, in the incremental frequent pattern mining stage, frequent patterns are progressively searched for and identified. Lastly, in the reference pattern candidate generation stage, reference pattern candidates are created based on the results of incremental frequent pattern mining. The graph manager uses these reference pattern candidates to check for isomorphism between previously explored graphs and the current graph, thus repeating the process of expanding pattern graphs. During the initial exploration of the graph, as there are no reference patterns stored in the pattern dictionary, single-edge patterns are created as the initial state of all graphs, and these edges are then expanded to generate various pattern graphs. This process identifies and creates efficient compression patterns considering the dynamic and continuous characteristics of graph stream data. Algorithm 1 shows the process followed by the reference pattern generator. In a graph stream, when vertices enter in sequence as in \(G(v)\), the patterns, \(P(v)\), stored in the pattern dictionary are indexed in the order they arrive (line 3). For instance, if graph \(G(v)=[132,\ 12,\ 51,\ 43,\ 21,\ 19,\ 12,\ 3,\ldots]\) is input, the input graph can be represented as  
Figure 2: Process flow between graph manager and reference pattern generator. the pattern graph \(P(v)=[0,\ 1,\ 2,\ 3,\ 4,\ 5,\ 1,\ 6,\ldots]\). At this time, vertices already assigned an index use their existing index. Thus, if vertex 12 is input again, it is mapped as vertex 1. The next step is to check if two vertices are adjacent and proceed with the expansion (lines 4-5). Pattern expansion initializes new edges if the starting vertex of edge \(e\in g\) does not exist in the edge or if the arriving vertex does not exist, after which (lines 6-10) the expanded pattern is added (line 12). In this process, first, a new pattern is initialized; it checks if the edge's source vertex already exists in the pattern; if not, it adds that vertex to the new pattern and updates vertex_map. Last, the edges not processed in batch \(B\) are added to the dictionary, \(P\), as single-edge patterns (line 15). ```
Input: graph G, batch B, dictionary P Output: Updated Pattern Dictionary P
1 for each pattern p in P:
2 for each matched m of pattern p embedded in batch B:
3 vertex_dict = [g(v): p(v) for p(v), g(v) in m]
4 new_edges = edges in batch B incident on m but not in pattern p
5 for each edge e in new_edges:
6 g_src(v) = e.src
7 g_tgt(v) = e.tgt
8 p_src(v) = vertex_map[g_src(v)]
9 p_tgt(v) = vertex_map[g_tgt(v)]
10 extended_pattern = extend pattern p with edge e using p_src(v) and p_tgt(v)
11 if extended_pattern not in P:
12 add extended_pattern to P
13 for each untagged edge e in B:
14 if e not in P:
15 add e as a single-edge pattern to P
16 return P
```  
**Algorithm 1**Incremental frequent pattern mining. After executing Algorithm 1, each pattern is assigned a score.