Effiziente Graphspeicherung für Entity Resolution durch cliquenbasierte Kompression

Kurzfassung: Dichte Entitätengraphen wachsen in der Kantenzahl quadratisch, während Datensätze hinzukommen — eine naive Speicherung ist damit auf Dauer nicht tragfähig. Clique-Based Graph Compression (CBGC) löst das, indem große Mengen paarweiser Kanten durch kompakte Cliquen-Datensätze ersetzt werden. In einem Produktiv-Deployment senkte CBGC den Speicherbedarf für Kanten um 99,7 %, bei voller Nachvollziehbarkeit und besserer Löschperformance.

Aspekt	Naive Kantenliste	Mit CBGC
Formel für das Kantenwachstum	n*(n-1)/2 pro Clique	1 Cliquen-Datensatz pro vollständigem Teilgraphen
Kanten bei n=1.000	Bis zu 499.500	1 Cliquen-Datensatz (+ dünn besetzter Rest)
Ersparnis in der Praxis	Ausgangswert	99,7 % weniger gespeicherte Kanten (ein Kunde)
Nachvollziehbarkeit	Vollständig (Regel-ID je Kante)	Vollständig (Regel-ID je Clique)
Löschperformance	Jede Kante durchlaufen	Clique als vorverbundenen Teilgraphen behandeln
Aufwand der Erkennung	Entfällt	NP-schwer (Maximum Clique); in der Praxis Greedy-Heuristiken
Verlustfrei?	Ja	Ja (sofern keine Eigenschaften je Kante nötig sind)

Auf dieser Seite

• Das Entitätengraph-Modell
• Das Skalierungsproblem: Quadratisches Wachstum
• Lösung: Clique-Based Graph Compression (CBGC)
• Performance-Vorteile jenseits des Speicherplatzes
• Abwägungen: Die Komplexität der Cliquenerkennung
• Über Cliquen hinaus
• Abschließende Gedanken
• FAQ: Häufig gestellte Fragen

In der Welt der Entity Resolution (ER) gehört das Verwalten und Pflegen der komplexen Beziehungen zwischen Datensätzen zu den zentralen Herausforderungen. Im Kern modelliert Tilores Entitäten als Graphen: Jeder Knoten steht für einen Datensatz, jede Kante für eine regelbasierte Übereinstimmung zwischen diesen Datensätzen. Dieser Ansatz gibt uns Flexibilität, Nachvollziehbarkeit und ein hohes Maß an Genauigkeit, bringt aber auch erhebliche Herausforderungen bei Speicherung und Rechenaufwand mit sich, besonders im großen Maßstab. Dieser Artikel erläutert im Detail, wie sich stark vernetzte Graphen mit cliquenbasierter Graphkompression effizient speichern lassen.

Das Entitätengraph-Modell

In Tilores ist eine gültige Entität ein Graph, in dem jeder Datensatz über eine Matching-Regel mit mindestens einem anderen verbunden ist. Stimmt zum Beispiel Datensatz a gemäß Regel R1 mit Datensatz b überein, speichern wir das als Kante "a:b:R1". Verbindet eine weitere Regel, etwa R2, a und b ebenfalls, speichern wir eine zusätzliche Kante "a:b:R2". Diese Kanten werden als einfache Liste gehalten, könnten alternativ aber auch über eine Adjazenzlisten-Struktur modelliert werden, um sie effizienter zu speichern.

Warum alle Kanten aufbewahren?

Die meisten Entity-Resolution- oder Master-Data-Management-Systeme bewahren die Beziehungen zwischen Datensätzen gar nicht auf, sondern speichern nur eine Repräsentation der zugrunde liegenden Daten und typischerweise einen generischen Match-Score. Der Nutzer bleibt damit im Unklaren darüber, wie die Entität zustande kam. Schlimmer noch: Er hat keine Möglichkeit, Fehler des automatischen Matchings zu korrigieren.

Alle Kanten eines Entitätengraphen aufzubewahren, erfüllt daher mehrere Zwecke:

• Nachvollziehbarkeit: Der Nutzer kann verstehen, warum zwei Datensätze derselben Entität zugeordnet wurden.
• Analytik: Aus den Metadaten der Kanten lassen sich Erkenntnisse gewinnen, etwa zur Wirksamkeit von Regeln und zur Ähnlichkeit von Daten.
• Löschen und Neuberechnen von Daten: Wird ein Datensatz gelöscht oder eine Regel geändert, muss der Graph neu berechnet werden. Die Kanteninformationen sind dafür unerlässlich, um zu verstehen, wie eine Entität entstanden ist und wie sie aktualisiert werden sollte.

Das Skalierungsproblem: Quadratisches Wachstum

Wenn von möglichen Skalierungsproblemen in der Entity Resolution die Rede ist, geht es meist um die Aufgabe, jeden Datensatz mit allen anderen abzugleichen. Das ist für sich genommen bereits eine Herausforderung — doch alle Kanten einer Entität aufzubewahren, führt auf der Speicherseite zu ganz ähnlichen Problemen. Entitäten, in denen viele Datensätze miteinander verbunden sind, erzeugen eine Vielzahl von Kanten. Im schlimmsten Fall ist jeder neue Datensatz mit allen bestehenden verbunden. Dieses quadratische Wachstum lässt sich mit folgender Formel ausdrücken:

n * (n - 1) / 2

Bei kleinen Entitäten ist das kein Problem. Eine Entität mit 3 Datensätzen kann zum Beispiel höchstens 3 Kanten haben. Für n = 100 steigt das auf 4.950 Kanten, und für n = 1.000 ergeben sich bis zu 499.500 Kanten.

Das erzeugt einen immensen Speicher- und Rechenaufwand — zumal Graphen in der Entity Resolution häufig genau diese dichte Vernetzung aufweisen.

Die Skalierungsproblematik zu verstehen, ist die Grundlage dafür, was Entity Resolution im Enterprise-Maßstab tatsächlich bedeutet: Die Matching-Logik und das Problem der Graphspeicherung sind eng miteinander verwoben.

Warum naive Kantenspeicherung im großen Maßstab nicht tragfähig ist

Bei kleinen Entitäten sind lineare Kantenlisten handhabbar. Für n=100 Datensätze erhalten Sie 4.950 Kanten, für n=1.000 bis zu 499.500. Jedes Speichersystem, das jede Kante als eigenständige Zeile behandelt, zahlt diesen Preis in voller Höhe — ohne von der strukturellen Redundanz zu profitieren, die dichte Cliquen darstellen. Die Ursache: Naive Speicherung ignoriert die Struktur vollständiger Teilgraphen, die in den Daten bereits vorhanden ist.

Lösung: Clique-Based Graph Compression (CBGC)

Eine Clique in einem Graphen ist eine Gruppe von Knoten, in der jeder Knoten mit jedem anderen Knoten dieser Gruppe verbunden ist. Eine Clique wird auch vollständiger Teilgraph genannt. Die kleinstmögliche Clique besteht aus einem einzelnen Knoten ohne Kanten. Auch ein Knotenpaar, das über eine Kante verbunden ist, bildet eine Clique. Und drei Knoten wie im Bild unten bilden eine dreieckige Clique.

Eine maximale Clique ist eine Clique, die sich durch Hinzunahme eines benachbarten Knotens nicht erweitern lässt; eine Maximum-Clique ist die Clique mit der größten Knotenzahl im gesamten Graphen. Für diesen Artikel verwenden wir den Begriff Clique nur für Cliquen mit mindestens drei Knoten.

Das eben gezeigte Dreieck ließe sich in Tilores durch die folgenden Kanten darstellen:

[
  "a:b:R1",
  "a:c:R1",
  "b:c:R1"
]

Da ein Dreieck eine Clique ist, könnten wir den Graphen auch darstellen, indem wir nur die Knoten dieser Clique und die zugehörige Regel-ID speichern:

{
  "R1": [
    ["a", "b", "c"]
  ]
}

Betrachten wir den folgenden, etwas komplizierteren Graphen:

Schon am Bild ist leicht zu erkennen, dass alle Knoten miteinander verbunden sind. Statt alle 15 Kanten aufzulisten [erinnern Sie sich an n*(n-1)/2], können wir diese Clique einfach in folgender Form speichern:

{
  "R1":[
    ["a", "b", "c", "d", "e", "f"]
  ]
}

In einem realistischen Graphen sind allerdings nicht alle Datensätze miteinander verbunden. Betrachten Sie den folgenden Graphen:

Drei größere Cliquen sind hervorgehoben: gelb, rot und blau (türkis, wenn Sie es genau nehmen). Dazu kommt ein einzelner verbleibender Knoten. Das sind zwar vermutlich die größten Cliquen, aber Sie entdecken womöglich Dutzende weitere. Sehen Sie zum Beispiel die Clique aus vier Knoten zwischen den beiden roten und den beiden gelben Knoten?

Bleiben wir bei den farbigen Cliquen, könnten wir sie folgendermaßen speichern (mit y, r und b für gelb, rot und blau):

{
  "R1": [
    ["y1", "y2", "y3"],
    ["r1", "r2", "r3", "r4", "r5"],
    ["b1", "b2", "b3", "b4", "b5", "b6"]
  ]
}

Zusätzlich können wir die verbleibenden 10 Kanten speichern (p für purpur):

[
  "y1:r1:R1",
  "y1:r2:R1",
  "y2:r1:R1",
  "y2:r2:R1",
  "r4:p1:R1",
  "r5:p1:R1",
  "r5:b1:R1",
  "b2:p1:R1",
  "y3:b5:R1",
  "y3:b6:R1"
]

Damit lässt sich der gesamte Graph nun mit nur drei Cliquen und zehn Kanten darstellen statt mit den ursprünglichen 38 Kanten.

Diese cliquenbasierte Graphkompression (CBGC) ist verlustfrei (sofern Sie keine Kanteneigenschaften benötigen). In einem realistischen Datenbestand haben wir massive Speicherersparnisse festgestellt. Bei einem Kunden senkte CBGC den Speicherbedarf für Kanten um 99,7 % und ersetzte Hunderttausende Kanten durch nur wenige Hundert Cliquen und einzelne Kanten.

Derselbe graphbasierte Ansatz liegt auch dem zugrunde, wie sich Entity Resolution mit Stammdatenmanagement verbindet, wo nachvollziehbare und korrigierbare Entitätengraphen eine Kernanforderung sind.

Performance-Vorteile jenseits des Speicherplatzes

Bei CBGC geht es nicht nur um Kompression. Es ermöglicht auch schnellere Operationen, insbesondere beim Löschen von Datensätzen und Kanten.

Jede vernünftige Entity-Resolution-Engine sollte eine Entität in mehrere aufteilen, wenn die einzige Verbindung zwischen zwei Teilgraphen gelöscht wurde, etwa aus regulatorischen oder Compliance-Gründen. Getrennte, unverbundene Teilgraphen zu identifizieren, geschieht typischerweise mit einem Algorithmus für Zusammenhangskomponenten. Kurz gesagt gruppiert er alle über Kanten verbundenen Knoten zu getrennten Teilgraphen. Dadurch muss jede Kante mindestens einmal geprüft werden.

Ist ein Graph jedoch komprimiert gespeichert, müssen nicht alle Kanten einer Clique durchlaufen werden. Es genügt, für jede Clique eine begrenzte Zahl von Kanten hinzuzufügen, beispielsweise einen transitiven Pfad zwischen den Knoten einer Clique — die Clique wird damit als vorverbundener Teilgraph behandelt.

Abwägungen: Die Komplexität der Cliquenerkennung

Es gibt eine Abwägung: Cliquenerkennung ist rechenintensiv, besonders wenn man die Maximum-Cliquen finden will — ein bekanntes NP-schweres Problem.

In der Praxis reicht es oft, diesen Aufwand zu vereinfachen. Näherungsverfahren zur Cliquenerkennung (z. B. Greedy-Heuristiken) schneiden für die meisten Einsatzzwecke gut genug ab. Zudem wird CBGC selektiv neu berechnet, in der Regel dann, wenn die Kantenzahl einer Entität einen Schwellenwert überschreitet. Dieser hybride Ansatz bringt Kompressionseffizienz und vertretbaren Rechenaufwand in Balance.

Forschung dazu, wie sich alle maximalen Cliquen in dünn besetzten Graphen in nahezu optimaler Zeit auflisten lassen (Eppstein, Loffler und Strash, 2010), bestätigt, dass eine vollständige Aufzählung maximaler Cliquen für dünn besetzte Graphen handhabbar ist, während dichte Graphen genau jenen selektiven, schwellenwertgesteuerten Ansatz erfordern, den CBGC verfolgt.

Über Cliquen hinaus

Das wohl häufigste Muster in der Entity Resolution ist der vollständige Teilgraph. Weitere Optimierungen ließen sich jedoch erzielen, indem man andere wiederkehrende Muster identifiziert, etwa

• Sterne: als Liste von Knoten speichern, deren erster Eintrag den Zentralknoten darstellt
• Pfade: als geordnete Liste von Knoten speichern
• Communities: wie eine Clique speichern und die fehlenden Kanten markieren

Abschließende Gedanken

Entity-Resolution-Systeme stehen häufig vor der Herausforderung, dichte, stark vernetzte Graphen zu verwalten. Alle Kanten naiv zu speichern, wird schnell untragbar. CBGC bietet einen effizienten Weg, Entitäten zu modellieren, indem es strukturelle Eigenschaften der Daten ausnutzt.

Es senkt nicht nur den Speicherbedarf, sondern verbessert auch die Systemperformance, besonders beim Löschen und Neuberechnen von Daten. Cliquenerkennung hat zwar ihren Rechenpreis, doch sorgfältige technische Entscheidungen erlauben es, die Vorteile zu nutzen, ohne die Skalierbarkeit zu opfern.

Für Teams, die abwägen, wie sie ein Entity-Resolution-System bauen oder integrieren, stehen die Kompromisse rund um Precision und Recall in der Entity Resolution gleichrangig neben der Speicherarchitektur als zwei der wesentlichen technischen Entscheidungen.

Wann sollten Sie CBGC auf Ihren Entitätengraphen anwenden?

CBGC ist am wertvollsten, wenn Entitäten mit hoher Datensatzzahl in Ihrem Datenbestand häufig vorkommen. Ist Ihr Graph dünn besetzt und übersteigen Entitäten selten ein Dutzend Datensätze, rechtfertigt der Aufwand der Cliquenerkennung die Speicherersparnis womöglich nicht. Tilores wendet CBGC selektiv an und stößt die Neuberechnung erst an, wenn die Kantenzahl einer Entität einen Schwellenwert überschreitet — die Technik greift also genau dort, wo sie den größten Nutzen bringt.

Sehen Sie, was aufgelöste Entitätsdaten für Ihr Unternehmen leisten — und für Ihre KI.

Sehen Sie es an Ihren eigenen Daten: Buchen Sie eine Demo für einen Durchgang mit Ihren Datensätzen, oder holen Sie sich den Evaluation Build, um aufgelöste Entitätsdaten lokal auszuprobieren.

FAQ

Was ist Clique-Based Graph Compression (CBGC) in der Entity Resolution?

CBGC ist eine Speichertechnik, die dichte Listen paarweiser Kanten in Entitätengraphen durch kompakte Cliquen-Darstellungen ersetzt. Eine Clique ist eine Gruppe von Knoten, in der jeder Knoten mit jedem anderen verbunden ist. Statt n*(n-1)/2 Kanten für einen vollständig verbundenen Teilgraphen zu speichern, werden nur die Menge der Knoten-IDs und die Regel-ID gespeichert. Das ist verlustfrei, sofern keine Eigenschaften auf Kantenebene benötigt werden.

Warum wächst der Speicherbedarf für Kanten in der Entity Resolution quadratisch?

In einem Entitätengraphen erzeugt jede Matching-Regel zwischen zwei Datensätzen eine Kante. Wenn viele Datensätze einer Entität alle miteinander verbunden sind, wächst die Zahl der Kanten mit n*(n-1)/2 (wobei n die Zahl der Datensätze ist). Für n=100 sind das 4.950 Kanten, für n=1.000 bis zu 499.500 Kanten. Dieses quadratische Wachstum erzeugt im großen Maßstab einen immensen Speicher- und Rechenaufwand.

Wie viel Speicherplatz spart CBGC in der Praxis?

In einem echten Kunden-Deployment senkte CBGC den Speicherbedarf für Kanten um 99,7 % und ersetzte Hunderttausende Kanten durch nur wenige Hundert Cliquen und einzelne Kanten.

Bringt CBGC über die Speicherersparnis hinaus Performance-Vorteile?

Ja. CBGC beschleunigt auch Operationen wie das Löschen von Datensätzen und Kanten. Wenn nach einer Löschung ein Algorithmus für Zusammenhangskomponenten unverbundene Teilgraphen erkennen soll, muss ein komprimierter Graph nicht jede Kante innerhalb einer Clique durchlaufen. Stattdessen genügt ein begrenzter transitiver Pfad je Clique, wobei jede Clique als vorverbundener Teilgraph behandelt wird.

Wie hoch ist der Rechenaufwand der Cliquenerkennung?

Maximum-Cliquen zu finden, ist ein NP-schweres Problem. In der Praxis schneiden Näherungsverfahren wie Greedy-Heuristiken für die meisten Entity-Resolution-Workloads gut genug ab. Zudem wird CBGC selektiv neu berechnet, typischerweise erst dann, wenn die Kantenzahl einer Entität einen Schwellenwert überschreitet — das hält den Rechenaufwand vertretbar.