Label Hierarchy Inference in Property Graph Databases

Table of Contents

1 Introduction

2 Background

2.1 The Property Graph Model

2.2 Cluster Analysis

2.2.1 Approaches

2.2.2 Clustering as a Search

2.3 Taxonomy

2.4 Probability Theory

3 Algorithms

3.1 Hierarchical Clustering Algorithms

3.1.1 Hierarchical Agglomerative Clustering

3.1.2 Robust Single Linkage

3.2 Partition-based Clustering

3.2.1 K-Means

3.2.2 TTSAS

3.3 Density-based Clustering

3.3.1 DBSCAN

3.3.2 OPTICS

3.3.3 HDBSCAN

3.4 Model-based Clustering – Conceptual Clustering

3.4.1 Cobweb

3.4.2 Extensions of Cobweb

3.5 Feature Extraction

3.5.1 Characteristic Sets

3.5.2 Recursive Feature Extraction

4 Label Inference

4.1 Problem Statement

4.2 Proposed Solution

4.2.1 Pre-Processing

4.2.1.1 Encoding Sets of Tags as Vectors

4.2.1.2 Feature Vector Extension

4.2.2 Clustering

4.2.3 Post-Processing: Taxonomy Extraction

5 Evaluation

5.1 Tag-based clustering

5.1.1 Setup

5.1.1.1 Data

5.1.1.2 Implementation

5.1.2 Results

5.1.3 Discussion

5.2 Graph-aware clustering of Nodes

5.2.1 Setup

5.2.1.1 Data

5.2.1.2 Pre-Processing

5.2.1.3 Implementation

5.2.2 Results

5.2.3 Discussion

6 Conclusion

6.1 Summary

6.2 Future Work

Research Objectives and Focus

The thesis aims to automate the extraction of hierarchical type taxonomies from property graph databases, addressing the lack of implicit hierarchy support in common graph data models. By deriving these structures, the study facilitates improved query optimization, data exploration, and the generation of more concise queries.

• Automated hierarchy derivation in property graphs
• Evaluation of clustering algorithms for graph structures
• Development of a graph-aware processing pipeline
• Implementation of conceptual clustering algorithms (e.g., Cobweb)
• Adaptive feature vector construction for diverse data sets

Extract from the Book

Summary of Chapters

1 Introduction: Discusses the ubiquity of hierarchical structures in data and identifies the lack of native support for these hierarchies in current property graph models.

2 Background: Provides foundational knowledge on property graph models, cluster analysis definitions, taxonomies, and probability theory.

3 Algorithms: Describes and analyzes various clustering algorithms, including hierarchical, partition-based, density-based, and conceptual clustering methods.

4 Label Inference: Outlines the problem of extracting explicit hierarchies from implicit data and presents a solution pipeline involving pre-processing, clustering, and taxonomy extraction.

5 Evaluation: Details the experimental setup and results for both tag-based and graph-aware clustering, discussing the performance and applicability of different feature vectors.

6 Conclusion: Summarizes the thesis findings and suggests potential future research directions in conceptual clustering and adaptive feature extraction.

Keywords

Property Graph Model, Hierarchical Clustering, Conceptual Clustering, Cobweb, Taxonomy Extraction, Label Inference, Graph Databases, Neo4j, Data Mining, Feature Extraction, Cardinality Estimation, Cluster Analysis, Incremental Learning, Synthetic Data, Knowledge Discovery

Frequently Asked Questions

What is the core problem addressed in this research?

The research addresses the fact that property graph databases lack internal support for hierarchical structures (type taxonomies), which are essential for tasks like query optimization and effective data exploration.

What are the central thematic areas of this work?

The thesis focuses on clustering algorithms, property graph data models, taxonomy extraction, and the development of pipelines to derive structural hierarchies automatically.

What is the primary objective of this thesis?

The primary objective is to develop and evaluate a pipeline that can automatically extract meaningful, representative type hierarchies from data within property graph databases.

Which scientific methods are utilized in this research?

The study employs a mix of survey-based research of existing clustering literature and experimental implementation of algorithms, including hierarchical agglomerative, density-based, and conceptual clustering (Cobweb) within a Neo4j environment.

What is covered in the main part of the thesis?

The main part covers the theoretical background of clustering, a detailed algorithmic overview, the design of a graph-aware taxonomy extraction pipeline, and an extensive evaluation of different feature vectors using synthetic and real-world datasets.

Which keywords characterize this research?

Key terms include Property Graph Model, Hierarchical Clustering, Conceptual Clustering, Taxonomy Extraction, and Label Inference.

Why is the Cobweb algorithm specifically highlighted in this work?

Cobweb is highlighted because it is parameter-free, incremental, provides probabilistic concept descriptions, and produces hierarchies by design, making it highly suitable for graph-aware clustering.

How is the "well-formed" nature of the hierarchy ensured?

The pipeline uses a post-processing step to flatten dendrograms into usable taxonomies by aggregating consecutive merges with identical distances.

Does a single feature vector work for all data types?

No, the research demonstrates that no single feature vector is universally optimal; instead, feature vectors must be constructed adaptively based on the specific properties and structures available in the data.