Cluster Purity

Cluster Purity is a metric that measures the homogeneity of a single cluster by calculating the proportion of its members that belong to the dominant class. For a cluster (C_i), purity is defined as:

[ \text{Purity}(C_i) = \frac{1}{|C_i|} \max_{j} (|C_i \cap L_j|) ]

Where (|C_i|) is the size of the cluster and (L_j) is the set of items with true class label (j). The dominant class is the one with the highest count within the cluster. A purity of 1.0 indicates all entities in the cluster share the same true class label.

To assess an entire clustering solution, individual cluster purities are aggregated. The Global Purity (or overall purity) is the average across all clusters, treating each cluster equally:

[ \text{Global Purity} = \frac{1}{N_c} \sum_{i=1}^{N_c} \text{Purity}(C_i) ]

Weighted Average Purity accounts for cluster size, giving larger clusters more influence, which often better reflects the overall homogeneity of the partitioned dataset:

[ \text{Weighted Purity} = \frac{1}{N} \sum_{i=1}^{N_c} |C_i| \cdot \text{Purity}(C_i) ]

Where (N) is the total number of entities and (N_c) is the number of clusters.

Cluster Purity is one of several external validation metrics used when ground truth labels are available. It is closely related to but distinct from:

• Normalized Mutual Information (NMI): Measures the mutual information between the clustering and the true classes, normalized by their entropies. More robust to imbalanced class distributions than purity.
• Adjusted Rand Index (ARI): Corrects the Rand Index for chance agreement, providing a score between -1 and 1. It considers both pair-wise agreements and disagreements.
• F1-Score (for clustering): Can be computed per class by treating the cluster with the highest overlap as the prediction for that class, then calculating precision and recall.

Purity is simpler to interpret but can be artificially inflated by creating many small, pure clusters, which is why it's often used in conjunction with these other metrics.

In Enterprise Knowledge Graphs, Cluster Purity is applied to evaluate the results of:

• Entity Typing: Assessing if clusters of entities generated by embedding similarity correspond to a single ontological class (e.g., all Person or all Organization).
• Community Detection: Measuring the semantic coherence of subgraphs identified by algorithms like Louvain or Label Propagation. A high-purity community contains entities from a single business domain.
• Canonicalization: Evaluating if candidate clusters for entity resolution contain records that truly refer to the same real-world entity.
• Taxonomy Induction: Validating that automatically discovered hierarchical groupings are semantically pure.

Low purity in these contexts signals potential issues with embedding quality, schema conformance, or the clustering algorithm's parameters.

While intuitive, Cluster Purity has key limitations that must be considered:

• Requires Ground Truth: It is an external metric and cannot be calculated without pre-existing, accurate class labels.
• Biased by Number of Clusters: Creating more clusters trivially increases purity. A degenerate case of one entity per cluster yields a purity of 1.0 but is useless.
• Symmetric Penalty: It does not penalize a cluster for missing members of the dominant class (low recall). A cluster could be pure but contain only a small fraction of its class.
• Class Imbalance Sensitivity: In datasets with a dominant class, large clusters may have high purity simply by containing many instances of that common class, masking poor separation of minority classes.

Therefore, purity should never be used in isolation but as part of a suite of metrics including NMI, ARI, and completeness measures.

Consider a knowledge graph where entity embeddings are clustered, and we have ground truth types. Assume three clusters:

• Cluster A: 8 Person entities, 2 Organization entities. Purity = 8/10 = 0.8.
• Cluster B: 10 Location entities. Purity = 10/10 = 1.0.
• Cluster C: 5 Product entities, 5 Event entities. Purity = 5/10 = 0.5.

Global Purity = (0.8 + 1.0 + 0.5) / 3 = 0.767. Weighted Purity = (100.8 + 101.0 + 10*0.5) / 30 = 23 / 30 = 0.767 (equal cluster sizes in this case).

This reveals that Cluster C is problematic, containing a mix of semantically distinct types (Product and Event), indicating the embeddings or clustering algorithm failed to separate these concepts. An investigation into the feature space or ontology alignment would be warranted.

Entity Accuracy measures the proportion of nodes in a knowledge graph that correctly correspond to their real-world referents. It is a fundamental metric for assessing factual grounding.

• Core Focus: Verifies that an entity's type, attributes, and existence are correct (e.g., ensuring 'Paris' is correctly identified as a city, not a person).
• Contrast with Cluster Purity: While Cluster Purity assesses group homogeneity, Entity Accuracy validates the correctness of individual nodes. A cluster can be pure (all nodes are cities) but still contain inaccurate entities (e.g., a fictional city).
• Measurement: Typically calculated against a Gold Standard dataset, often expressed as a percentage of correctly identified entities.

Link Validity evaluates the semantic and factual correctness of the relationships (edges) between entities in a knowledge graph. It ensures predicates accurately reflect real-world connections.

• Core Focus: Assesses if a stated relationship is true (e.g., verifying that (CompanyA, acquires, CompanyB) is a factually correct acquisition event).
• Relationship to Clustering: In graph clustering, links often define community structure. Invalid links can create impure clusters by incorrectly grouping unrelated entities. High Link Validity is a prerequisite for meaningful cluster analysis.
• Validation Methods: Often checked via Rule-Based Validation (e.g., schema constraints) or human-in-the-loop verification.

Schema Conformance is the degree to which the instances and relationships in a knowledge graph adhere to the formal constraints defined in its governing ontology or schema (e.g., OWL, RDFS).

• Core Focus: Ensures data respects class hierarchies, property domains/ranges, cardinality rules, and data types.
• Impact on Purity: A strict, well-defined schema provides the semantic classes against which Cluster Purity is measured. Low conformance (e.g., a Person instance with a manufacturingDate property) creates noise that degrades clustering homogeneity.
• Enforcement: Managed through Constraint Satisfaction engines and validation pipelines.

Logical Consistency is a formal property where no set of facts or inferred conclusions in a knowledge graph violates the logical constraints of its ontology. It is a prerequisite for reliable reasoning.

• Core Focus: Detects contradictions, such as an entity being declared a member of two disjoint classes (e.g., Male and Female).
• Distinction from Purity: Cluster Purity measures semantic grouping; Logical Consistency ensures the graph contains no logical absurdities. An inconsistent graph can still have pure clusters, but those clusters may be based on contradictory definitions.
• Foundation for Inference: Essential for Inference Soundness, guaranteeing that derived facts are logically valid.

Embedding Quality evaluates how well the vector representations (embeddings) of knowledge graph entities and relations preserve their semantic relationships and structural properties in a continuous vector space.

• Core Focus: Measures if geometric relationships in the vector space (e.g., cosine similarity, translational distance) accurately mirror semantic relationships in the graph.
• Direct Connection to Clustering: Modern graph clustering often operates on entity embeddings. Poor embedding quality—where similar entities are not close in vector space—will directly result in low Cluster Purity, as algorithms cannot form semantically coherent groups.
• Evaluation Metrics: Assessed using tasks like link prediction (e.g., Precision@K, Recall@K) and analogy solving.

Connectedness is a structural quality metric that assesses the degree of linkage within a knowledge graph, often measured by the size of the largest connected component or the average path length between entities.

• Core Focus: Quantifies how "well-linked" the graph is, identifying isolated subgraphs or data silos.
• Interaction with Clustering: Cluster Purity is typically measured within identified clusters. Connectedness assesses the graph's overall topology between clusters. A highly disconnected graph may have very pure clusters, but this can indicate poor integration of knowledge domains.
• Business Implication: Low connectedness can hinder cross-domain queries and insights, limiting the graph's utility for enterprise-wide applications.