Finding Fraud Rings with Link Analysis: A Union-Find Approach

Most fraud checks evaluate one order at a time: is this card valid, does the AVS match, does the device look risky? That works when the attacker is using stolen credentials. It breaks down when the credentials are real, such as when a fraudster operates through accounts that belong to cooperating or recruited people. Every individual record looks clean.

What a single operator cannot easily hide is reuse. They ship to the same drop address, check out from the same laptop, or cycle the same handful of payment instruments across "unrelated" accounts. Those connections only show up when you stop looking at rows and start looking at relationships. For the full set of order-, account-, and portfolio-level warning signs in this kind of scheme, see the overview of second-party fraud red flags. This article focuses on one of them: building the link-analysis layer that surfaces shared-infrastructure clusters.

The data model: accounts and identifiers as a graph

Model your customer base as a bipartite graph:

• Account nodes: one per customer account.
• Identifier nodes: one per distinct device fingerprint, normalized shipping address, payment instrument fingerprint, phone number, or email.
• Edges: an account is connected to every identifier it has used.

Two accounts are "linked" if a path exists between them through shared identifiers. A connected component in this graph is a candidate cluster.

You don't need a graph database to start. A table of (account_id, identifier_type, identifier_value, first_seen, last_seen) is enough, and a union-find structure can compute components over millions of edges on a single machine.

Step 1: Normalize identifiers before you link anything

Graph quality depends almost entirely on identifier normalization. Two strings that refer to the same thing must collapse to the same node, and two strings that don't must stay separate.

Using a processor fingerprint for cards keeps raw card numbers out of your fraud pipeline entirely, which also keeps that system out of a large chunk of PCI DSS scope.

Step 2: Handle supernodes before they swallow your graph

This is the failure mode that kills most first attempts. Some identifiers are legitimately shared by thousands of accounts:

• IP addresses behind carrier-grade NAT or corporate proxies
• Office mailrooms, university dorms, and package lockers
• Freight forwarders (which are both a red flag and a supernode)
• Your own warehouse address used for in-store pickup

If you union through any of these, you get one giant component containing most of your customers, and the analysis becomes useless.

Two standard defenses:

1. Degree caps per identifier type. Count how many distinct accounts touch each identifier. Skip identifiers above a type-specific threshold when building components. An address with 4 accounts is interesting; one with 4,000 is infrastructure.
2. Allow/deny lists. Explicitly exclude known infrastructure (your stores, known lockers). Track known reshippers separately: don't use them to link accounts, but do flag any account that ships to them.

IPs are usually too noisy to link on at all. Use them as cluster features, not edges.

Step 3: Compute components with union-find

Union-find (disjoint set union) is a good fit: it processes edges in a single pass, with path compression and union by rank giving near-constant amortized time per operation.

from collections import defaultdict

class DSU:
    def __init__(self):
        self.parent, self.rank = {}, {}

    def find(self, x):
        self.parent.setdefault(x, x)
        self.rank.setdefault(x, 0)
        root = x
        while self.parent[root] != root:
            root = self.parent[root]
        while self.parent[x] != root:          # path compression
            self.parent[x], x = root, self.parent[x]
        return root

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1

DEGREE_CAP = {"device": 10, "address": 8, "card": 5, "phone": 5}

def build_clusters(edges, excluded=frozenset()):
    # edges: iterable of (account_id, id_type, id_value)
    edges = list(edges)
    degree = defaultdict(set)
    for acct, t, v in edges:
        degree[(t, v)].add(acct)

    dsu = DSU()
    for acct, t, v in edges:
        dsu.find(f"acct:{acct}")              # register isolated accounts
        key = (t, v)
        if key in excluded or t not in DEGREE_CAP:
            continue
        if len(degree[key]) > DEGREE_CAP[t]:
            continue                           # supernode: skip as a link
        dsu.union(f"acct:{acct}", f"{t}:{v}")

    clusters = defaultdict(set)
    for node in list(dsu.parent):
        if node.startswith("acct:"):
            clusters[dsu.find(node)].add(node[5:])
    return [c for c in clusters.values() if len(c) > 1]

The degree caps here are placeholders. Set them from your own data by looking at the degree distribution for each identifier type and choosing a cutoff above the household-sharing range.

Worked example

Six accounts, with these edges:

Walking through it:

• A1, A2, A3 share device D1, so they merge.
• A3 and A4 share address S3, which pulls A4 into the same component, even though A4 never touched D1. This transitive link is exactly what row-level review misses.
• A5 and A6 share only the carrier NAT IP, which isn't an edge type at all. They stay separate.

Result: one cluster {A1, A2, A3, A4}. Four accounts with four different cards and four different names, connected by one laptop and one drop address.

Step 4: Score clusters, not just membership

A component is a candidate, not a verdict. Families share devices. Roommates share addresses. Compute features per cluster and score them:

The last row matters. A cluster held together by a single shared address is weak evidence. A cluster where accounts share devices and addresses and cards is much harder to explain innocently.

A dispute on any member is also a strong propagation signal. When one account in a cluster files a fraud claim, review the open orders of the others before they ship.

Step 5: Add time to the edges

Identifier reuse that's years apart means something different from reuse within the same week. Store first_seen and last_seen on each edge and either:

• build components only from edges active within a rolling window (say, 90 days), or
• weight edges by recency and compute clusters with a weighted method instead of plain union-find.

Without this, an address that changed hands two tenants ago will keep linking strangers forever.

Batch vs. real-time

Union-find supports incremental unions but not deletions. A practical split:

• Nightly batch: rebuild components from scratch with current degree caps and time windows. This handles expiring edges cleanly.
• At checkout: look up the incoming order's device, address, and card in the precomputed cluster index. If any of them belongs to a flagged cluster, add that to the order's risk score.

If you need fully real-time linking, a graph database or a streaming connected-components job is the next step, but most teams get substantial value from the batch-plus-lookup pattern first.

Common mistakes and how to catch them

• One giant component. Check the size of your largest cluster after every run. If it suddenly jumps, a new supernode slipped under the cap. Log the top identifiers by degree each run.
• Linking on IP. Almost always too noisy. Use it as a feature.
• Over-normalizing addresses. Spot-check clusters linked only by address; if they're all apartment buildings, your unit parsing is broken.
• Auto-declining cluster members. Feed cluster risk into scoring or step-up verification, not hard blocks. Many cluster members will be legitimate.
• Never measuring outcomes. Track dispute rates for flagged vs. unflagged clusters over time. If flagged clusters don't dispute at a higher rate, your features or thresholds are wrong.

Testing the pipeline

You rarely have clean labels, so seed your own. Inject synthetic rings into a copy of production data: N accounts sharing a device and a drop address, with varied names and cards. Then verify that:

1. each synthetic ring comes back as exactly one cluster,
2. it doesn't merge with real customers through a supernode, and
3. its cluster score lands above your review threshold.

Also inject benign patterns, like a family of four on one device with one shared address, and confirm they score low. Both test sets belong in CI, so a change to normalization or degree caps can't silently break detection.

Link analysis won't catch a lone actor using a single borrowed account. What it does catch is scale, which is where most of the losses are. Once reuse becomes visible as structure, it's very hard for an operator to hide.