Graph Traversal

How Graph Traversal Works

Incoming Click/Event Stream
           │
           ▼
+-----------------------+
│ Data Point Extraction │
│ (IP, User, Device ID) │
+-----------------------+
           │
           ▼
+-----------------------+      +------------------+
│   Graph Construction  │──────│  Historical Data │
│ (Nodes & Edges)       │      │  (Known Frauds)  │
+-----------------------+      +------------------+
           │
           ▼
+-----------------------+
│  Traversal & Analysis │
│ (Path & Link Finding) │
+-----------------------+
           │
           ▼
+-----------------------+
│   Pattern Recognition │
│   (e.g., Fraud Rings) │
+-----------------------+
           │
           └─┬─> Legitimate Traffic (Allow)
             │
             └─> Suspicious Traffic (Flag/Block)

Graph traversal provides a powerful method for uncovering complex fraud schemes by focusing on the relationships between seemingly unrelated activities. Instead of analyzing events in isolation, it builds a connected map of interactions to see the bigger picture. This approach is highly effective at detecting coordinated attacks that traditional, rule-based systems might miss. The process moves from raw data collection to actionable fraud intelligence.

Data Aggregation and Node Creation

The process begins when a user action, such as a click on an ad, generates an event. Key data points are extracted from this event, including the user’s IP address, device ID, user agent, and session information. Each unique data point becomes a “node” in a graph. For example, IP address 192.168.1.1 is one node, and Device ID XYZ-123 is another. These nodes are the fundamental building blocks of the network model.

Edge Construction and Relationship Mapping

Once nodes are created, “edges” are drawn to connect them based on their interactions. If a click from IP address 192.168.1.1 is associated with Device ID XYZ-123, an edge is created between these two nodes. This process is repeated for all incoming traffic, building a vast, interconnected web. This “graph” visually represents how different users, devices, and IPs are related, mapping the digital fingerprints of all activity on the network.

Traversal and Pattern Analysis

With the graph constructed, traversal algorithms systematically explore the connections. These algorithms can start at a suspicious node (e.g., an IP with an unusually high click rate) and “traverse” the edges to find all connected nodes. The goal is to identify patterns indicative of fraud, such as a single device connected to hundreds of different user accounts or multiple IPs showing identical, robotic browsing behavior. This analysis reveals hidden networks of fraudulent activity.

Diagram Element Breakdown

Incoming Click/Event Stream

This represents the raw flow of data from user activities, such as ad clicks, sign-ups, or transactions. It is the starting point of the detection pipeline, containing all the initial signals that need to be analyzed.

Graph Construction (Nodes & Edges)

Here, individual data points (IPs, users) are turned into nodes, and the relationships between them (e.g., an IP used by a user) become edges. This step transforms siloed data into a connected network model, which is essential for relational analysis.

Traversal & Analysis

This is the core logic where algorithms navigate the graph to find connections and pathways between nodes. By traversing the graph, the system can determine how closely related different entities are, even if they are not directly linked.

Pattern Recognition

After traversing the graph, the system looks for predefined fraud topologies, such as “fraud rings” (clusters of tightly connected fraudulent accounts) or “fan-out” patterns (one device linked to many user accounts), to score and classify traffic.

🧠 Core Detection Logic

Example 1: Multi-Account Correlation by Device

This logic identifies a single device that is associated with an abnormally high number of user accounts. It’s a strong indicator of a bot or a fraud farm using one piece of hardware to generate fake traffic across numerous personas. This check happens after enough data is collected to build a device-to-user graph.

FUNCTION check_device_to_user_link(device_id):
  // Get all user accounts linked to this device
  linked_users = get_users_for_device(device_id)
  
  // Define a threshold for suspicious activity
  USER_THRESHOLD = 10
  
  IF count(linked_users) > USER_THRESHOLD:
    // Flag all associated users and the device
    FLAG device_id AS "Suspicious: High User Count"
    FOR each user in linked_users:
      FLAG user.id AS "Suspicious: Part of High-Volume Device Ring"
    RETURN "FRAUD_DETECTED"
  
  RETURN "OK"

Example 2: Geographic Inconsistency Check

This logic detects fraud by identifying when a user session exhibits rapid, impossible geographic relocation. For instance, if clicks associated with the same user ID originate from different continents within minutes, it suggests the use of proxies or a distributed botnet. This is a real-time check during graph traversal.

FUNCTION check_geo_mismatch(session_id, new_click_location):
  // Get the last known location for this session
  last_location = get_last_location(session_id)
  
  // If a previous location exists, calculate the distance and time
  IF last_location IS NOT NULL:
    time_diff = current_time() - last_location.timestamp
    distance = calculate_geo_distance(last_location.coords, new_click_location.coords)
    
    // Check for impossible travel speed (e.g., > 800 km/h)
    IMPOSSIBLE_SPEED_KMH = 800
    
    IF (distance / time_diff.hours) > IMPOSSIBLE_SPEED_KMH:
      FLAG session_id AS "Fraudulent: Impossible Geo-Travel"
      RETURN "FRAUD_DETECTED"
      
  // Update the session with the new location data
  update_location(session_id, new_click_location)
  RETURN "OK"

Example 3: Behavioral Anomaly Detection

This logic identifies non-human behavior by analyzing the timing and frequency of clicks within a session. Bots often perform actions at a perfectly regular, machine-like pace, unlike humans whose interactions are more random. This analysis is done by traversing the click events connected to a single session node.

FUNCTION analyze_session_timing(session_id):
  // Get all click timestamps for the session
  click_times = get_click_timestamps(session_id)
  
  // Calculate the time deltas between consecutive clicks
  deltas = []
  FOR i from 1 to count(click_times) - 1:
    delta = click_times[i] - click_times[i-1]
    add delta to deltas
    
  // Check if the variance of time deltas is unnaturally low
  LOW_VARIANCE_THRESHOLD = 0.05
  
  IF variance(deltas) < LOW_VARIANCE_THRESHOLD AND count(deltas) > 5:
    FLAG session_id AS "Suspicious: Robotic Click Cadence"
    RETURN "FRAUD_DETECTED"
    
  RETURN "OK"

📈 Practical Use Cases for Businesses

• Campaign Shielding – Protects PPC budgets by identifying and blocking traffic from botnets before they can generate fraudulent clicks, ensuring that ad spend reaches real potential customers.
• Analytics Purification – Ensures marketing analytics are based on genuine human interactions by filtering out bot-generated events, leading to more accurate insights on user behavior and campaign performance.

–

• Return on Ad Spend (ROAS) Improvement – Increases ROAS by preventing budget waste on fraudulent clicks and ensuring that advertisements are primarily shown to legitimate users who are more likely to convert.
• Lead Generation Integrity – Safeguards lead generation forms from being flooded with fake submissions by bots, ensuring the sales team receives genuine and actionable leads.

Example 1: Geofencing Rule

This pseudocode defines a geofencing rule to block clicks from locations outside a campaign’s target market. It’s used to prevent budget waste from bots that use IP addresses in regions where the business does not operate.

FUNCTION apply_geofencing(click_data):
  // Define the list of allowed countries for a campaign
  ALLOWED_COUNTRIES = ["USA", "CAN", "GBR"]
  
  // Get the country from the click's IP address
  click_country = get_country_from_ip(click_data.ip)
  
  // Check if the click's country is in the allowed list
  IF click_country NOT IN ALLOWED_COUNTRIES:
    // Block the click and log the event
    block_click(click_data.id)
    log_event("Blocked click due to geofencing violation.", click_data)
    RETURN "BLOCKED"
    
  RETURN "ALLOWED"

Example 2: Session Scoring Logic

This pseudocode demonstrates a session scoring system. It traverses various related nodes (like device, IP, user agent) and aggregates risk factors. A high score indicates the session is likely fraudulent and can be blocked in real-time.

FUNCTION calculate_session_risk(session_id):
  // Start with a base score of 0
  risk_score = 0
  
  // Get related nodes for the session
  session_data = get_session_graph(session_id)
  
  // Add points for known risk factors
  IF is_proxy(session_data.ip):
    risk_score += 40
  
  IF is_known_bot_user_agent(session_data.user_agent):
    risk_score += 50
    
  IF device_is_virtual_machine(session_data.device_id):
    risk_score += 30
  
  // If the total score exceeds a threshold, flag as fraud
  RISK_THRESHOLD = 80
  IF risk_score >= RISK_THRESHOLD:
    RETURN "HIGH_RISK"
  
  RETURN "LOW_RISK"

🐍 Python Code Examples

This code simulates detecting fraudulent clicks by identifying IP addresses that generate an unusually high number of clicks in a short time frame, a common sign of a bot or click farm attack.

# Example 1: Detect high-frequency clicks from a single IP
def detect_click_flooding(click_stream, time_window_seconds=60, click_threshold=100):
    ip_clicks = {}
    fraudulent_ips = set()

    for click in click_stream:
        ip = click['ip_address']
        timestamp = click['timestamp']

        if ip not in ip_clicks:
            ip_clicks[ip] = []
        
        # Add current click and filter out old ones
        ip_clicks[ip].append(timestamp)
        ip_clicks[ip] = [t for t in ip_clicks[ip] if timestamp - t <= time_window_seconds]

        # Check if click count exceeds threshold
        if len(ip_clicks[ip]) > click_threshold:
            fraudulent_ips.add(ip)

    return list(fraudulent_ips)

This function analyzes traffic to find multiple user accounts that share the same device ID. This helps uncover fraud rings where one person or bot network operates numerous fake accounts from a single piece of hardware.

# Example 2: Identify multiple accounts on a single device
def find_multi_account_devices(user_sessions, device_threshold=5):
    device_to_users = {}
    suspicious_devices = {}

    for session in user_sessions:
        device_id = session['device_id']
        user_id = session['user_id']

        if device_id not in device_to_users:
            device_to_users[device_id] = set()
        
        device_to_users[device_id].add(user_id)

    # Find devices exceeding the user account threshold
    for device, users in device_to_users.items():
        if len(users) > device_threshold:
            suspicious_devices[device] = list(users)
            
    return suspicious_devices

Types of Graph Traversal

• Breadth-First Search (BFS) – This method explores all neighboring nodes at the present depth before moving on to nodes at the next depth level. In fraud detection, it is useful for quickly finding the shortest path between two suspicious entities, like a known fraudulent user and a new transaction.
• Depth-First Search (DFS) – This algorithm explores as far as possible along each branch before backtracking. It is effective for identifying long chains of fraudulent activity or nested fraud rings, where one fraudulent entity leads to another in a sequential pattern.
• Connected Components Analysis – This technique identifies clusters of interconnected nodes that are isolated from the rest of the graph. It is highly effective for discovering large-scale fraud networks, such as botnets or groups of colluding users, that operate within their own closed ecosystem.
• PageRank-style Algorithms – Originally for ranking web pages, this method can be adapted to assign an “influence” or “suspicion” score to each node in the graph. Nodes that are heavily connected to other known fraudulent nodes will receive a higher score, helping to prioritize investigations.

🛡️ Common Detection Techniques

• IP Fingerprinting – This technique analyzes attributes of an IP address beyond its location, such as its owner (residential vs. data center) and history. It helps detect bots hosted in data centers or IPs known for generating spam.
• Behavioral Analysis – This method tracks user actions like click speed, mouse movements, and time on page. It identifies non-human, robotic behavior that deviates from typical user interaction patterns, effectively spotting sophisticated bots that mimic human actions.
• Device Fingerprinting – This technique collects a unique set of identifiers from a user’s device, like OS, browser version, and screen resolution. It can identify when multiple “users” are actually originating from a single device, exposing attempts to create fake accounts at scale.
• Session Heuristics – This involves analyzing the entire user session for anomalies. It looks for impossible travel (logging in from different continents in minutes) or an unusually high number of transactions, which indicates automated activity rather than genuine user engagement.
• Community Detection – This technique uses graph algorithms to identify densely connected clusters of users, devices, or IPs. These “communities” often represent organized fraud rings or botnets that work together to carry out coordinated attacks against ad campaigns.

🧰 Popular Tools & Services

Tool	Description	Pros	Cons
Graph Database Engine	A database optimized for storing and querying interconnected data. It allows for efficient traversal of complex relationships to uncover fraud rings and hidden connections in real-time.	Highly scalable; excellent for complex relational queries; fast real-time traversal.	Requires specialized knowledge (e.g., Cypher query language); can be resource-intensive.
Real-Time Analytics Platform	A service that ingests streaming data (e.g., clicks, events) and applies graph-based analysis on the fly to score traffic for fraud potential.	Immediate detection; highly scalable for large data streams; integrates well with alerting systems.	Can be costly; analysis might be less deep than batch processing; potential for latency.
Data Visualization Suite	Software used by analysts to visually explore the graph network. It helps humans spot anomalies and understand the structure of a detected fraud scheme.	Intuitive for exploring connections; aids in manual investigation; great for reporting.	Not an automated detection tool; performance can degrade with very large graphs.
ML Fraud Detection Service	A managed cloud service that uses graph-based features to train machine learning models. It automatically identifies new and evolving fraud patterns.	Adapts to new fraud tactics; reduces manual effort; highly accurate.	Can be a “black box”; requires large amounts of clean training data; potential for false positives.

📊 KPI & Metrics

To effectively measure the success of a graph traversal-based fraud detection system, it’s crucial to track metrics that reflect both its technical accuracy and its impact on business objectives. Monitoring these KPIs helps justify investment and refine detection models for better performance and higher ROI.

Metric Name	Description	Business Relevance
Fraud Detection Rate	The percentage of total fraudulent activities correctly identified by the system.	Measures the direct effectiveness of the system in catching fraud and protecting revenue.
False Positive Percentage	The percentage of legitimate activities incorrectly flagged as fraudulent.	Indicates the risk of blocking real users and harming the user experience or losing sales.
Blocked Fraudulent Spend	The total advertising budget saved by blocking fraudulent clicks or impressions.	Directly quantifies the financial ROI of the fraud prevention system.
Clean Traffic Ratio	The proportion of traffic deemed legitimate after filtering out fraudulent activity.	Reflects the overall quality of traffic reaching the site, impacting analytics and conversion rates.
Model Retraining Frequency	How often the graph models or detection rules need to be updated to adapt to new threats.	Shows the system’s adaptability and the operational overhead required to maintain its accuracy.

These metrics are typically monitored through real-time dashboards that pull data from system logs and analytics platforms. Alerts are often configured for sudden spikes in fraudulent activity or false positives. This continuous feedback loop is essential for optimizing fraud filters, adjusting detection thresholds, and ensuring the system evolves to counter new attack vectors effectively.

🆚 Comparison with Other Detection Methods

Accuracy and Sophistication

Compared to simple signature-based filters (e.g., IP blacklists), graph traversal offers far superior accuracy. Signature-based methods can only block known threats and are easily bypassed with new IPs or devices. Graph traversal, however, detects the underlying coordinated relationships between entities, allowing it to uncover novel and sophisticated fraud rings that blacklists would miss entirely.

Real-Time vs. Batch Processing

Graph traversal can be more computationally intensive than basic rule-based systems. Simple rules (e.g., “block IP if from X country”) are extremely fast and suitable for instant, real-time blocking. While some graph analysis can happen in real-time, deep, complex traversal is often better suited for near real-time or batch processing. This makes it a powerful tool for deep analysis but potentially slower for initial, low-latency filtering compared to stateless methods.

Effectiveness Against Coordinated Fraud

This is where graph traversal truly excels over other methods like standalone behavioral analytics. While behavioral analysis can spot a single bot based on its clicking patterns, it may fail to see the bigger picture. Graph traversal connects that single bot to the hundreds of other bots being controlled by the same network, allowing a security system to identify and neutralize the entire botnet at once, rather than fighting a losing battle one bot at a time.

⚠️ Limitations & Drawbacks

While powerful, graph traversal is not a silver bullet for all fraud detection scenarios. Its effectiveness can be limited by data quality, computational cost, and the specific nature of the fraudulent activity, making it less suitable in certain contexts or as a standalone solution.

• High Resource Consumption – Building and traversing large-scale graphs can demand significant memory and processing power, making it costly for services with massive traffic volumes.
• Detection Latency – Complex graph analysis may introduce delays, making it less effective for scenarios requiring instantaneous, sub-millisecond fraud decisions at the moment of a click.
• Data Sparsity Issues – If there isn’t enough data to form meaningful connections (edges) between nodes, the graph will be too sparse to reveal coordinated fraud patterns effectively.
• Difficulty with Encrypted or Obfuscated Data – The model’s effectiveness depends on clear data signals. If fraudsters successfully hide their device or IP information, building an accurate graph becomes difficult.
• Risk of Over-linking – Broad connection points, like a public WiFi IP address, can incorrectly link unrelated legitimate users, potentially leading to a higher rate of false positives if not handled carefully.

In cases of high-frequency, low-sophistication attacks, simpler and faster methods like signature-based filtering may be more appropriate as a first line of defense.

❓ Frequently Asked Questions

How is graph traversal different from a simple IP blacklist?

An IP blacklist is a static list of known bad actors. Graph traversal is a dynamic analysis technique that doesn’t rely on prior knowledge. It actively seeks out relationships between IPs, devices, and user accounts to uncover new, coordinated fraud networks that a simple blacklist would miss.

Can graph traversal operate in real-time?

Yes, but with trade-offs. Simple graph lookups, like checking if a new click is connected to a known fraud ring, can be done in real-time. However, deep, resource-intensive analysis to discover entirely new fraud networks is often performed in near real-time or in batches to avoid impacting performance.

Does this method generate many false positives?

It can if not configured properly. For example, linking all users from a large university’s public IP address could flag legitimate students. Effective systems use weighted connections and consider multiple factors (device, behavior, etc.) to minimize false positives and accurately distinguish between coincidental and collusive relationships.

Is graph traversal effective against sophisticated bots that mimic human behavior?

Yes. While a single sophisticated bot might evade behavioral detection, it cannot easily hide its connections to the network that controls it. Graph traversal excels at uncovering the command-and-control infrastructure by linking bots through shared, hidden attributes, regardless of how well each individual bot mimics a human.

What data is needed to build an effective graph for fraud detection?

A variety of data points are useful. Key signals include IP addresses, device IDs, user-agent strings, session cookies, and user account information. The more diverse and high-quality the data, the more robust and accurate the graph will be at identifying the subtle connections that link fraudulent activities together.

🧾 Summary

Graph traversal is a powerful technique in digital advertising security that models traffic as a network of interconnected nodes (e.g., IPs, devices). By analyzing the relationships and paths between these nodes, it uncovers coordinated fraudulent behavior, like botnets or click farms, that isolated analysis would miss. This method is crucial for identifying sophisticated, large-scale attacks and improving ad campaign integrity.

🔗 Related Articles

• Fraud through the eyes of a machine | Towards Data Science – https://towardsdatascience.com/fraud-through-the-eyes-of-a-machine-bd505d933822
• Real-time fraud detection with graph neural network on DGL – Amazon Science – https://www.amazon.science/publications/real-time-fraud-detection-with-graph-neural-network-on-dgl
• Financial Fraud Detection with Graph Data Science – Neo4j – https://neo4j.com/whitepapers/financial-fraud-detection-graph-data-science/
• Guide to link analysis & graph networks against fraud | Ravelin – https://www.ravelin.com/insights/guide-to-link-analysis-and-graph-networks-against-fraud
• TwiBot-22: Towards Graph-Based Twitter Bot Detection – https://arxiv.org/abs/2206.04564