Abstract
This paper studies seeded graph matching for power-law graphs. Assume that two edge-correlated graphs are independently edge-sampled from a common parent graph with a power-law degree distribution. A set of correctly matched vertex-pairs is chosen at random and revealed as initial seeds. Our goal is to use the seeds to recover the remaining latent vertex correspondence between the two graphs. Departing from the existing approaches that focus on the use of high-degree seeds in $1$-hop neighborhoods, we develop an efficient algorithm that exploits the low-degree seeds in suitably-defined $D$-hop neighborhoods. Specifically, we first match a set of vertex-pairs with appropriate degrees (which we refer to as the first slice) based on the number of low-degree seeds in their $D$-hop neighborhoods. This significantly reduces the number of initial seeds needed to trigger a cascading process to match the rest of the graphs. Under the Chung-Lu random graph model with $n$ vertices, max degree $\Theta(\sqrt{n})$, and the power-law exponent $2<\beta<3$, we show that as soon as $D> \frac{4-\beta}{3-\beta}$, by optimally choosing the first slice, with high probability our algorithm can correctly match a constant fraction of the true pairs without any error, provided with only $\Omega((\log n)^{4-\beta})$ initial seeds. Our result achieves an exponential reduction in the seed size requirement, as the best previously known result requires $n^{1/2+\epsilon}$ seeds (for any small constant $\epsilon>0$). Performance evaluation with synthetic and real data further corroborates the improved performance of our algorithm.
Introduction
Graph matching—the process of identifying the hidden alignment between nodes in two correlated networks—is a cornerstone of modern data science. It has critical applications in de-anonymizing social networks, aligning biological structures, and computer vision. In many practical scenarios, this is approached as a "seeded" problem: we are given a small set of known, correctly matched vertex pairs (seeds) to help us uncover the rest of the network.
However, real-world networks—such as Twitter, the internet, or protein-interaction maps—rarely follow simple random distributions. Instead, they exhibit power-law degree distributions, where a few massive "hubs" coexist with millions of sparsely connected nodes. Traditional matching algorithms rely on 1-hop "witnesses" (shared immediate neighbors) to identify matches. In power-law graphs, this approach is remarkably inefficient, requiring a massive seed set—often $O(n^{1/2})$—to trigger a successful matching cascade. This paper introduces the Power-Law D-hop (PLD) algorithm, which leverages extended $D$-hop neighborhoods to achieve an exponential reduction in the required seed size.
The Challenge of Power-Law Graphs
In standard random graphs (like Erdős-Rényi), looking $D$ hops away provides only a linear or constant-factor improvement. In power-law graphs, the situation is more complex. While $D$-hops offer more potential witnesses, they also introduce significant noise. Because of high-degree hubs, a path of length 2 or 3 can connect almost any two nodes in the network. If an algorithm simply counts $D$-hop neighbors, "fake pairs" (incorrect matches) will share nearly as many witnesses as true pairs, leading to catastrophic errors.
The PLD Algorithm: A Controlled Approach
To harness the power of $D$-hops without succumbing to the noise of hubs, the PLD algorithm employs a strategy of "controlled" exploration through three distinct phases:
- Degree Slicing: The algorithm partitions the graph into "slices" based on vertex degrees. This allows the algorithm to treat nodes of different structural importance differently.
- Controlled D-hop Matching (The "Goldilocks" Slice): Instead of starting with the highest-degree nodes, the algorithm identifies an optimal "first slice" of middle-tier nodes. It matches these nodes using $D$-hop witnesses while strictly excluding high-degree nodes from acting as seeds or intermediate routing nodes. By filtering out the hubs during this sensitive phase, the algorithm prevents fake pairs from accumulating false witnesses.
- Cascading and Percolation: Once the first slice is confidently matched, it provides a massive influx of new, reliable seeds. The algorithm then cascades down to lower-degree slices using standard 1-hop matching and eventually employs Percolation Graph Matching (PGM) to align the sparsest nodes in the network.
Theoretical and Empirical Results
The authors provide a rigorous mathematical proof using the Chung-Lu random graph model. For a graph with $n$ vertices and a power-law exponent $\beta$ between 2 and 3, the PLD algorithm requires only $\Omega((\log n)^{4-\beta})$ seeds to correctly match a constant fraction of the network. This moves the requirement from polynomial ($n^{1/2}$) to polylogarithmic—an exponential improvement.
Synthetic and Real-World Performance
The algorithm's theoretical strength is mirrored in its empirical performance:
- Synthetic Data: On a 10,000-node synthetic graph, PLD achieved near-perfect accuracy with only ~50 seeds, while competing state-of-the-art methods required between 150 and 220 seeds.
- Facebook Network: Using a dataset of ~63,000 students and staff from the University of Oregon, PLD significantly outperformed five baseline algorithms (including DDM and User-Matching).
- Autonomous Systems (AS): In matching internet infrastructure networks that evolved over time, PLD proved robust even when the graphs were of different sizes or had degraded correlation.
Conclusion
The PLD algorithm demonstrates that hubs in power-law graphs are a double-edged sword: they facilitate connectivity but create noise that can derail matching. By actively ignoring high-degree nodes during the initial $D$-hop phase, the algorithm finds a "Goldilocks" zone that allows for highly efficient matching with minimal initial information. Future work remains to be done in estimating graph parameters (like the power-law exponent) more dynamically and exploring whether these $D$-hop techniques can eventually enable "unseeded" matching in power-law networks.
Summary updated