Abstract
Percolation-based graph matching algorithms rely on the availability of seed vertex pairs as side information to efficiently match users across networks. Although such algorithms work well in practice, there are other types of side information available which are potentially useful to an attacker. In this paper, we consider the problem of matching two correlated graphs when an attacker has access to side information, either in the form of community labels or an imperfect initial matching. In the former case, we propose a naive graph matching algorithm by introducing the community degree vectors which harness the information from community labels in an efficient manner. Furthermore, we analyze a variant of the basic percolation algorithm proposed in literature for graphs with community structure. In the latter case, we propose a novel percolation algorithm with two thresholds which uses an imperfect matching as input to match correlated graphs. We evaluate the proposed algorithms on synthetic as well as real-world datasets using various experiments. The experimental results demonstrate the importance of communities as side information especially when the number of seeds is small and the networks are weakly correlated.
Introduction
Graph matching, the task of finding a mapping between the vertices of two different networks, is a cornerstone of data integration and social network analysis. However, it also presents a significant privacy risk known as network de-anonymization. Most state-of-the-art matching techniques, particularly percolation-based algorithms, depend on a set of "seeds"—pre-identified pairs of nodes known to correspond to the same entity. A major challenge arises when the number of available seeds is small or the networks are weakly correlated.
This research explores how "side information"—additional data such as community memberships or noisy initial matchings—can drastically enhance matching performance. By leveraging these extra clues, an attacker can de-anonymize networks more effectively than with seeds alone.
Problem Formulation
The core problem involves matching two correlated graphs, $G_1$ and $G_2$, which are typically modeled as being sampled from a common parent graph $G$.
The goal is to identify the latent correspondence between the nodes of $G_1$ and $G_2$. The difficulty of this task increases as the correlation between the graphs decreases. Side information, such as community labels (e.g., group memberships or interests), serves to reduce the search space and provide unique "fingerprints" for nodes.
Proposed Algorithms
The authors propose three distinct algorithmic approaches to utilize side information:
- The Naive Algorithm (Community Degree Vectors): This algorithm utilizes community labels to create a "community degree vector" for each node. Instead of a single degree count, a node is characterized by its number of connections to each specific community. This high-dimensional fingerprint can allow for perfect matching even without initial seeds, provided the number of communities is sufficiently large.
- Percolation with Community Labels: This approach adapts bootstrap percolation by restricting the search for matches to nodes within the same community. Theoretical analysis shows that this constraint allows the matching threshold—the number of mutual neighbors required to confirm a match—to be lowered from $r=4$ to $r=2$ while maintaining accuracy.
- Two-Threshold Percolation: Designed to handle "imperfect matchings" (noisy data containing errors), this algorithm employs two thresholds. A lower threshold ($r_c$) is applied to pairs suggested by the imperfect matching to initiate the process, while a higher threshold ($r_m$) is used for other pairs to prevent the propagation of errors.
Experimental Evaluation
The algorithms were tested on both synthetic and real-world datasets:
- Synthetic Data: Graphs were generated using the Stochastic Block Model (SBM), which facilitates the creation of random graphs with predefined community structures.
- Real-World Data: The researchers used co-authorship networks from arXiv (Astro Physics and Condensed Matter Physics). Communities were identified using the Louvain algorithm.
Key Results
- Seed Efficiency: On synthetic SBM datasets, the proposed percolation algorithm achieved near-zero error rates with as little as a single seed, significantly outperforming traditional methods.
- Robustness in Weak Correlation: Community information proved to be the deciding factor for successful matching in scenarios where networks were only weakly correlated.
- Performance on Real Data: In the Astro Physics dataset, the two-threshold algorithm surpassed the state-of-the-art "ExpandWhenStuck" algorithm, demonstrating superior resilience to poor-quality initial seeds.
Conclusion
This work highlights the critical role of side information in graph matching. Community labels fundamentally transform the problem by reducing the search space from $N$ to $N/K$ candidates per node. While the current study utilizes the Stochastic Block Model and assumes non-overlapping communities, future work will address more complex real-world scenarios, such as overlapping social circles and different graph topologies. Understanding these vulnerabilities is essential for developing more robust privacy-preserving techniques in social networks.
Summary updated