Graph-Based Risk Modeling: Start with the Relationships

September 2026 · 14 min read

Before you start: Know what a classifier’s input row and target label mean. A graph database or neural network is not required.

An application’s permissions, age, and behavior describe the application itself. Its publisher and hosting domains connect it to other applications. A graph makes those relationships explicit so we can ask: what evidence does this application’s neighborhood add?

Our synthetic application A shares a publisher with B, which has a confirmed risky label. A also shares a hosting domain with C and D. C is confirmed benign; D has not been resolved. A’s connections deserve inspection, but they do not establish A’s label. This chapter builds the graph and its first feature row; the next chapter turns that row into a model input.

Represent the evidence before aggregating it

A node represents an application or a metadata entity, such as a publisher. An edge records an observed relationship: “A was published by P1.” Its type tells us what the connection means. Keeping application nodes on one side and metadata nodes on the other gives a bipartite graph: every edge crosses between the two sides. Publisher and domain remain different metadata types.

Use a typed key such as ("publisher", "P1"), not a bare string that could also be a domain ID. Resolve identity under a recorded rule: repeated observations of one publisher are not new publishers, and a similar display name is not proof of common ownership. A null publisher should stay missing. Turning every null into a node named “unknown” would connect unrelated applications through a data-cleaning artifact.

Keep unknown separate from benign. The former describes missing knowledge; the latter is a conclusion with a source and a time. Filling unknown labels with zero can make investigation coverage look like evidence of risk.

Projecting to app neighbors changes what you can see

A projection replaces an app → metadata → app path with an app–app edge. The publisher view contributes A–B. The shared domain contributes A–C, A–D, and C–D. All three domain edges originate from one metadata entity; they are not three independent discoveries.

Projection is useful when an algorithm expects only application nodes. Preserve the supporting metadata IDs and relation types alongside each projected edge. Otherwise a later reviewer cannot tell whether A–B means a common publisher, a generic host, or several overlapping sources.

Computing a few aggregates through app–metadata joins can avoid storing that clique. It does not make the underlying hub informative, and the join can still be expensive. Group by the metadata entity first where possible, subtract the target app’s own contribution, and retain per-type counts.

A transparent weighting rule

We will give a rare shared item more weight per app pair than a common item. Let $a$ and $b$ be distinct applications, $N(a)$ their metadata neighbors, and $d_m$ the number of distinct apps connected to metadata item $m$. Let $\alpha_{\mathrm{type}(m)}$ be a nonnegative weight chosen for its relation type. Sum over metadata shared by both apps:

A shared item has at least two apps, so this denominator is positive. The degree discount follows Newman’s collaboration weighting, implemented in NetworkX; the type weights are our modeling choice. It is a measure of connection strength, not a probability of risk.

For this series, choose publisher weight 2 and domain weight 1. P1 has degree 2, so A–B receives $2/(2-1)=2$. The shared host has degree 3, so A–C and A–D each receive $1/(3-1)=0.5$. These deliberately chosen values make the arithmetic inspectable. Tune relation weights on validation data, and compare against simpler unweighted counts.

This rule reduces each pair’s share of a hub; it does not remove the hub’s total influence. For one app, adding its contributions across the other $d_m-1$ apps gives the type weight back. Several domains owned by the same provider can also repeat related evidence. Degree weighting and evidence independence are different issues.

Build the graph that existed when the decision was made

Historical evaluation needs two times: event time, when the relationship occurred or was observed, and available time, when the scoring pipeline could use that record. A relationship observed on 2 August but ingested on 8 August cannot help a prediction made on 4 August. Joining today’s complete graph onto old training rows would quietly supply that later knowledge.

A point-in-time join retrieves feature values appropriate to each example’s timestamp. For this graph, our contract also checks when records became usable, how corrections are versioned, and whether an old relationship has expired. An event-time filter alone cannot reconstruct late ingestion.

# One observation, not a complete graph implementation.
edge = {
    "app_id": "D",
    "entity_type": "domain",
    "entity_id": "shared-host.example",
    "observed_at": "2026-08-02T00:00:00Z",
    "available_at": "2026-08-08T00:00:00Z",
    "source_version": "metadata-v3",
}
# For each decision time:
# 1. Keep records observed AND available by that time.
# 2. Apply the declared expiry/correction policy as of that time.
# 3. Deduplicate typed edges; preserve the source observations.
# 4. Compute distinct-app degrees from this eligible snapshot.
# 5. Join label versions available at that time.
# 6. Aggregate neighbors, excluding the target and its label.

Produce a feature row you can explain

At the 10 August cutoff, A has one publisher neighbor, B, and two domain neighbors, C and D. Preserve the denominator of every fraction:

The domain feature says one reviewed neighbor is benign and one is unresolved. Writing “0 of 2 are risky” would hide the missing label. With no resolved neighbors, use a missing indicator or a declared prior plus a zero-evidence count. The next chapter’s smoothing example makes that choice explicit.

Start with per-type neighbor counts, resolved-label coverage, weighted neighbor scores, and evidence age. Keep A’s own permissions, age, and behavior too. Save which neighbor and source contributed to each aggregate. That record explains a feature; a separate supervised model decides how useful it is for predicting A’s outcome.

Check whether the relationship supports the prediction

Homophily means connected nodes tend to share a property. It must be checked for the label and relation you care about. Sharing a service provider may say little about risk; two applications from one publisher may still behave differently. Measure the incremental value of each relation on later decisions, including new apps with sparse evidence.

Before training, check four concrete invariants: duplicate observations do not inflate degree; missing identifiers do not create shared nodes; the target’s label cannot enter its own features; and adding a record available after a cutoff does not change that cutoff’s feature row. These catch graph-construction mistakes that a high validation score can conceal.

Continue with weighted features, smoothing, and propagation. The graph is now an auditable source of evidence, ready to be tested as a model input.

References and further reading

• NetworkX: collaboration-weighted projection — The degree-discounted projection rule and its Newman reference; our relation-type multipliers are an extension.
• Feast: point-in-time joins — Historical feature lookup. The chapter additionally distinguishes event time from availability time for late-arriving graph evidence.