Pattern Morphing for Efficient Graph Mining
Why this work is in the frame
A frame that forgets how it found something cannot be audited. These are the routes that admitted this work.
Bibliographic record
Abstract
Graph mining applications analyze the structural properties of large graphs, and they do so by finding subgraph isomorphisms, which makes them computationally intensive. Existing graph mining techniques including both custom graph mining applications and general-purpose graph mining systems, develop efficient execution plans to speed up the exploration of the given query patterns that represent subgraph structures of interest. In this paper, we step beyond the traditional philosophy of optimizing the execution plans for a given set of patterns, and exploit the sub-structural similarities across different query patterns. We propose Pattern Morphing, a technique that enables structure-aware algebra over patterns to accurately infer the results for a given set of patterns using the results of a completely different set of patterns that are less expensive to compute. Pattern morphing "morphs" (or converts) a given set of query patterns into alternative patterns, while retaining full equivalency. It is a general technique that supports various operations over matches of a pattern beyond just counting (e.g., support calculation, enumeration, etc.), making it widely applicable to various graph mining applications like Motif Counting and Frequent Subgraph Mining. Since pattern morphing mainly transforms query patterns before their exploration starts, it can be easily incorporated in existing general-purpose graph mining systems. We evaluate the effectiveness of pattern morphing by incorporating it in Peregrine, a recent state-of-the-art graph mining system, and show that pattern morphing significantly improves the performance of different graph mining applications.
Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.
Full frame distilled prediction
Teacher imitationNot calibrated prevalence, not ground truth. Human validation pending. Learned from the 10,348 direct Codex labels and 10,348 direct Gemma labels. Candidate is the union of thresholded teacher heads; consensus is their intersection. These outputs are machine_predicted_unvalidated and are not human labels or direct frontier model labels.
Codex and Gemma teacher scores by category
| Category | Codex | Gemma |
|---|---|---|
| Metaresearch | 0.000 | 0.000 |
| Meta-epidemiology (narrow) | 0.000 | 0.000 |
| Meta-epidemiology (broad) | 0.000 | 0.000 |
| Bibliometrics | 0.000 | 0.001 |
| Science and technology studies | 0.000 | 0.000 |
| Scholarly communication | 0.000 | 0.000 |
| Open science | 0.002 | 0.002 |
| Research integrity | 0.000 | 0.000 |
| Insufficient payload (model declined to judge) | 0.000 | 0.000 |
Machine scores (provisional)
The two teacher heads of the student model, read on this work. A score orders the frame for review; it never asserts a category, and the validation status ships verbatim with every row.
Baseline scores from an immature model (maturity gate not passed, 7 training rounds). Scores rank; they never assert a category.
score_only:v0-immature-baseline · verbatim from the scoring run: score_only means the number may rank works, and no category label ships from it