TL;DR
node2bits is a novel framework that generates compact, binary "fingerprints" (hashcodes) for nodes in large-scale, evolving networks to solve the user stitching problem. By combining temporal random walks with feature-based hashing, it achieves up to a 5% improvement in accuracy over state-of-the-art methods while requiring up to 339x less storage space.
Introduction: The User Stitching Problem
In the digital world, a single person often interacts with services through multiple "fragmented" identities: a laptop session at work, a mobile app at home, and an anonymous browser window on a tablet. User stitching (or identity stitching) is the task of linking these disparate sessions to the same real-world individual.
This task is incredibly difficult for three primary reasons:
- Scale: Real-world web services have millions of users and billions of interactions. Comparing every session to every other session is computationally impossible (quadratic complexity).
- Sparsity: Cookies expire and IP addresses change, leaving behind thin, disconnected trails of data.
- Representation Overhead: Modern machine learning often represents users as "embeddings" (vectors of floating-point numbers). For billions of nodes, storing these dense vectors requires massive amounts of expensive memory.
The authors aim to create a representation that is temporal (respects the order of events), attribute-aware (uses what we know about the session), and compact (binary instead of floating-point).
Methodology
The node2bits framework follows a three-step pipeline to transform raw network data into tiny, searchable bitstrings:
- Temporal Random Walk Sampling: Unlike standard random walks that move blindly across a graph,
node2bitsuses "temporally valid" walks. This means the walk can only move from an interaction at time $t_1$ to an interaction at $t_2$ if $t_2 \ge t_1$. This captures the actual chronological flow of user behavior. - Feature-based Context Construction: Most graph algorithms rely on node IDs. However, in user stitching, the same user has different IDs for different sessions. To fix this,
node2bitsreplaces IDs with features (e.g., device type, location, or topological metrics like PageRank). This makes the model "ID-independent"—it looks for people who act the same, even if their IDs are different. - Histogram Aggregation & SimHash: The framework aggregates these feature-based contexts into histograms to capture the distribution of behaviors at different "temporal distances." Finally, it uses SimHash (a Locality Sensitive Hashing technique) to compress these high-dimensional histograms into short binary codes. Because it uses LSH, similar behaviors naturally result in similar bitstrings, allowing for lightning-fast similarity searches.
Datasets and Evaluation
The authors evaluated node2bits on six diverse datasets:
- Comp-X: A large, proprietary real-world web log dataset from a major company, containing ground-truth user identities.
- Citeseer & Yahoo Messenger: Heterogeneous networks representing paper-author relations and message exchanges.
- Bitcoin, Digg, & Wiki-talk: Temporal networks used to test the framework's ability to handle time-stamped interactions.
For the public datasets without ground-truth "stitching" labels, the authors used a "user replica" strategy, where they strategically split existing nodes to simulate fragmented identities.
Key Insights and Ideas
- Structural Identity over Proximity: Traditional embeddings (like node2vec) assume that if two nodes are close together in a graph, they are similar. In user stitching, two sessions by the same user might not be directly connected at all.
node2bitsfocuses on structural equivalence—if two nodes have similar local patterns of behavior over time, they are likely the same person. - The Power of Binary: By moving from 32-bit floats to 1-bit representations, the authors drastically reduce the "memory wall" that prevents graph algorithms from scaling to billions of edges.
- Time as a Constraint, Not Just a Feature: By enforcing temporal validity in the random walks, the model filters out "impossible" paths, leading to a more realistic representation of user intent.
Key Results
- Accuracy:
node2bitsoutperformed traditional techniques and real-valued embedding baselines by up to 5.16% in F1 score for the user stitching task. - Efficiency: The binary representations are incredibly lean, using between 63x and 339x less storage than standard methods. For example, on the Wiki dataset, while other methods required over 1GB,
node2bitsrequired only 4.2MB. - Scalability: The algorithm's complexity is linear with respect to the number of edges, making it viable for massive, industrial-scale networks.
Limitations and Future Work
While highly effective, the authors note a few areas for improvement:
- Temporal Trade-off: Constraining walks to be strictly temporal can sometimes limit the "context" the model sees, especially in very sparse graphs where valid temporal paths are short.
- Hyperparameter Sensitivity: The choice of "MAX temporal distance" (how far back in time the model looks) is crucial; looking too far back can introduce noise that degrades performance.
- Future Directions: The authors suggest extending the framework to handle even more complex edge types and exploring privacy-preserving variants of these binary representations to further protect user data.
Summary updated