TL;DR
Matching two correlated networks (like anonymized social graphs) usually requires a massive number of known "seed" nodes if the networks have power-law degree distributions. This paper introduces the Power-Law D-hop (PLD) algorithm, which looks at extended $D$-hop neighborhoods instead of just immediate neighbors, exponentially reducing the required number of initial seeds from $O(n^{1/2})$ to just $O(\text{polylog}(n))$.
What Problem Does This Paper Address?
Graph matching aims to find the hidden alignment between the nodes of two similar graphs. This is a fundamental problem in social network de-anonymization, computer vision, and computational biology. Often, researchers use "seeded" graph matching, where a small set of known, correctly matched vertex pairs (seeds) is provided to kickstart the alignment process.
Most real-world networks (like Twitter or the internet) are power-law graphs. They feature extreme degree variations: a few massive "hubs" connected to everything, and millions of sparsely connected nodes. Existing algorithms match nodes by looking at 1-hop "witnesses" (shared immediate neighbors). However, because of the extreme degree variations in power-law graphs, 1-hop matching requires a huge number of initial seeds—specifically $n^{1/2+\epsilon}$ seeds for a graph of $n$ nodes—to successfully trigger a matching cascade. If you don't have that many seeds, the algorithm fails to find enough shared neighbors to confidently match the rest of the graph.
Methods
To drastically reduce the seed requirement, the authors propose looking further out: using $D$-hop witnesses (nodes connected by paths of length $D$).
However, applying $D$-hops to power-law graphs is dangerous. Because of the massive hubs, if you look 2 or 3 hops away, almost every node is connected to every other node. This causes "fake pairs" (incorrect matches) to share just as many $D$-hop neighbors as true pairs.
To solve this, the authors designed the Power-Law D-hop (PLD) algorithm, which carefully controls the $D$-hop neighborhood:
- Degree Slicing: The algorithm partitions the graph into "slices" based on vertex degrees.
- Controlled $D$-hop Matching: It selects a mathematically optimal "first slice" to match using $D$-hop witnesses. Crucially, it excludes high-degree nodes from acting as seeds or intermediate routing nodes. By filtering out the hubs, the algorithm prevents fake pairs from accumulating false witnesses.
- Cascading: Once this first slice is confidently matched, it provides a massive influx of new seeds. The algorithm then cascades down to lower-degree slices using standard 1-hop matching, and finally uses a Percolation Graph Matching (PGM) algorithm to sweep up the sparsest, lowest-degree nodes.
Datasets
The authors evaluated their algorithm on both synthetic and real-world datasets:
- Synthetic: Graphs generated using the Chung-Lu random graph model, which allows researchers to explicitly control the power-law exponent and average degree.
- Real-world (Facebook): A Facebook Friendship Network of ~63,000 students and staff from the University of Oregon.
- Real-world (Autonomous Systems): A dataset of 9 Autonomous Systems (AS) peering networks inferred from Oregon route-views (~10,000 to 11,000 nodes each), representing the internet's infrastructure over time.
Key Insights and Ideas
- The exponential power of $D$-hops: In standard random graphs (Erdős-Rényi), looking $D$ hops away only provides a constant-factor improvement in matching. But in power-law graphs, $D$-hops are a game-changer, providing an exponential reduction in the number of seeds required.
- Hubs are a double-edged sword: Hubs make networks highly navigable, but for graph matching, they create "noise" by artificially inflating the similarity of mismatched pairs. Actively ignoring high-degree nodes during the initial $D$-hop phase is the secret sauce that makes this algorithm work.
- The "Goldilocks" first slice: You can't just start matching the highest-degree nodes. The algorithm identifies the perfect middle-tier degree slice to match first—nodes whose $D$-hop neighborhoods are large enough to find low-degree seeds, but small enough to avoid overlapping with fake pairs.
Key Results
- Theoretical Guarantee: The authors mathematically prove that for a Chung-Lu graph with $n$ vertices and a power-law exponent between 2 and 3, the PLD algorithm only needs $\Omega((\log n)^{4-\beta})$ seeds to correctly match a constant fraction of the network without errors. This is an exponential improvement over the previous $n^{1/2+\epsilon}$ state-of-the-art.
- Synthetic Performance: On a 10,000-node synthetic graph, PLD achieved near-perfect accuracy with only ~50 seeds. Competing state-of-the-art methods (like DDM or User-Matching) required 150 to 220+ seeds to achieve the same accuracy.
- Real-world Performance: PLD significantly outperformed 5 baseline algorithms (DDM, Y-test, User-Matching, 2-hop, PGM) on both the Facebook and AS network datasets, proving robust even when the two graphs being matched were of different sizes or degraded over time.
Limitations and Future Work
- Limitations: To set its internal thresholds (like which slices to create and what degree cutoffs to use), the PLD algorithm requires estimating several parameters of the underlying graph, such as the power-law exponent ($\beta$), the average degree, and the edge correlation probability between the two graphs. While the authors provide statistical methods to estimate these, it adds a layer of complexity to real-world deployment.
- Future Work: The authors highlight a highly promising future direction: investigating whether the power of $D$-hops can be leveraged to match power-law graphs without any initial seeds at all (unseeded graph matching).
Summary updated