DiNoiSe: Scaling Seedless Graph Matching to Millions of Nodes
Graph matching on social networks without any side information
The paper introduces DiNoiSe, a distributed percolation graph matching algorithm designed for large-scale social networks without side information. It combines a novel automated seed generation technique (SeGen) with a Spark-based distributed architecture to achieve high-accuracy matching on graphs with millions of nodes.
TL;DR
DiNoiSe (Distributed Noisy Seeds) is a robust, distributed framework for matching two graphs based solely on their structure—no labels or pre-defined seeds required. By combining a structural seed generator (SeGen) with a Spark-based percolation engine, it can match millions of nodes (e.g., LiveJournal) with over 95% precision, even when the initial seeds contain errors.
Background: The Challenge of the "Seedless" Social Graph
Graph matching is the art of finding correspondences between two networks. In social network analysis, this is often used for de-anonymization: if you have an anonymous graph and a labeled one (like LinkedIn), can you map the users?
Most current SOTA methods face a "Cold Start" problem: they need a set of "ground truth" seeds to start the matching process. Furthermore, as graphs grow to millions of edges, sequential algorithms hit a computational wall.
Motivation: Why Current Methods Fail
- Dependency on Seeds: Manual seed selection is impossible for large graphs.
- Noise Sensitivity: One wrong seed in a standard percolation algorithm can "infect" the entire process, leading to a cascade of false positives.
- Scalability: Existing Map-Reduce implementations often trade off accuracy for speed, failing to handle the "bucketing" of scores needed for reliability.
Methodology: The DiNoiSe Framework
1. SeGen: Automatic Structural Seed Generation
To solve the cold-start problem, the authors introduce SeGen. It uses the Weisfeiler-Lehman (WL) heuristic to create structural fingerprints for high-degree nodes.
- Each node's label includes its own degree and a sorted list of its neighbors' degrees.
- High-degree nodes from both graphs are compared using these labels.
- The Hungarian Algorithm solves a minimum weight perfect matching to pick the "best" initial pairs.
2. Distributed Percolation with Bucketing
Once seeds are found, DiNoiSe "infects" the network. If two nodes have at least r already-matched neighbors, they are considered a candidate match.
The "Bucketing" mechanism is key: it stores cumulative matching scores across Spark iterations. This ensures that even if a match isn't obvious immediately, it can be confirmed as more neighbors are matched, lending the system its "Noisy Seed" resilience.
Experimental Results: Precision at Scale
The authors tested DiNoiSe on massive datasets, including R-MAT synthetic graphs and real SNAP networks (Enron, DBLP, Amazon, LiveJournal).
Key Findings:
- Scalability: On R-MAT 22 (4.1M nodes), only the distributed DiNoiSe could finish in a reasonable time.
- Noise Tolerance: Even with only 60% seed precision from SeGen, the percolation stage corrected the errors, resulting in final F1-scores above 0.95.
- Real World Performance: On the LiveJournal network (nearly 4M nodes and 34M edges), the algorithm achieved a 0.9595 Precision, matching over 2 million individuals correctly without any names or profile data.
Critical Insight & Future Outlook
The success of DiNoiSe proves that Topology is Identity. Even without usernames, birthdays, or locations, the "shape" of your social circle is a unique identifier.
Limitations: The algorithm struggled with the com-Amazon dataset. This suggests that percolation works best on "scale-free" social networks (human interactions) but may fail on co-purchasing or product-based networks where the degree distribution leads to structural ambiguity.
Takeaway: For privacy researchers, DiNoiSe is a wake-up call. "Anonymizing" a graph by removing labels is insufficient when structural fingerprints are this robust and scalable.