On the Feasible Region of Efficient Algorithms for Attributed Graph Alignment

Ziao Wang, Ning Zhang, Weina Wang, Lele Wang

TL;DR

This paper introduces two efficient, polynomial-time algorithms—ATTRRICH and ATTRSPARSE—that can exactly match users across two different social networks by leveraging both connection data and shared attributes. The authors prove that even a small amount of attribute information significantly expands the "feasible region" where exact alignment is possible, narrowing the long-standing gap between theoretical limits and practical, efficient computation.

What Problem Does This Paper Address?

Graph alignment is the task of finding the correspondence between vertices in two correlated graphs. A classic application is social network de-anonymization: an attacker might try to identify users in an anonymous dataset by matching its structure to a public one.

While structure alone is powerful, real-world data often includes attributes (e.g., a user's movie-watching history or interests). "Attributed graph alignment" uses this side information to assist the matching process. Previous research in this area was split: some focused on what is mathematically possible with infinite computing power (information-theoretic limits), while others developed fast algorithms without proving they would always work. This paper bridges that gap by providing polynomial-time algorithms with rigorous theoretical performance guarantees.

Methods

The authors analyze the problem using the Attributed Erdős–Rényi pair model, where two graphs are generated by subsampling a common base graph containing both "user" vertices and "attribute" vertices.

They propose a two-step alignment strategy:

  1. Anchor Alignment: Use shared attribute neighbors to identify a set of "anchor" users who are matched with high confidence.
  2. Structural Alignment: Use the graph's edge structure (connections to the anchors) to match the remaining users.

Depending on the richness of the attribute data, they offer two specific algorithms:

  • ATTRRICH: Designed for regimes with abundant attribute information. It uses a simple one-hop neighborhood check to finish the alignment.
  • ATTRSPARSE: Designed for regimes where attributes are scarce. It employs a more sophisticated multi-hop neighborhood matching technique to overcome the lack of initial "seeds."
An illustration of the attributed Erdős–Rényi pair model and the anonymization process.

Datasets

The paper is theoretical and does not use real-world datasets for evaluation. Instead, it relies on the Attributed Erdős–Rényi pair model $\mathcal{G}(n, p, s_u; m, q, s_a)$ to mathematically define the boundaries of success for their algorithms.

Key Insights and Ideas

  • Attributes as "Noisy Seeds": Attributes effectively act as a starting point for alignment. The paper shows that even if attribute information is sparse, it can provide enough "anchors" to make the structural alignment phase computationally "easy."
  • Lowering the Complexity Threshold: In traditional graph alignment (without attributes), there is a known computational barrier related to "Otter’s constant" ($\sqrt{\alpha} \approx 0.58$). The authors demonstrate that adding even a tiny amount of attribute information can lower this threshold to an arbitrarily small constant, making previously "impossible" problems solvable in polynomial time.
  • Unified Framework: By treating attributes as a specific type of node, the authors provide a framework that integrates traditional graph alignment, seeded alignment, and bipartite alignment into a single theoretical model.

Key Results

  • Near-Optimal Feasibility: The algorithms achieve exact alignment in regions very close to the information-theoretic limits. As shown in Figure 1, the feasible regions for ATTRRICH (Area 2) and ATTRSPARSE (Area 3) cover a significant portion of the theoretically possible space (Areas 1+2+3).
  • Expanding the "Easy" Zone: The paper proves that attributes make alignment significantly easier for efficient algorithms. Figure 2 illustrates how increasing attribute information ($mqs_a^2$) turns a "?" (unknown feasibility) region into an "easy" (polynomial-time achievable) region.
  • Outperforming Existing Seeded Algorithms: When specialized to the "seeded graph alignment" problem (where some matches are known perfectly), these new algorithms outperform existing state-of-the-art polynomial-time methods in several parameter regimes, particularly when the number of seeds is relatively small.
Fig. 1: Comparison between the feasible regions of the proposed algorithms and the information-theoretic limits: the shaded area ( 1 + 2 + 3 ) represents the information-theoretically feasible region given in [1]; area 2 is the feasible region for Algorithm ATTRRICH and area 3 is the feasible region for Algorithm ATTRSPARSE; area 4 is the information-theoretically infeasible region given in [1].

Limitations and Future Work

  • The Information-Computation Gap: While the proposed algorithms are near-optimal, a gap still exists between what is achievable in polynomial time and the absolute information-theoretic limit (the white space in Figure 1). It remains an open question whether any efficient algorithm can close this gap.
  • Model Realism: The results are derived for Erdős–Rényi graphs, which assume edges are independent. Real-world social networks often exhibit clustering and power-law degree distributions. Extending these theoretical guarantees to more realistic graph models is a promising direction for future research.

Summary updated

Abstract

Graph alignment aims at finding the vertex correspondence between two correlated graphs, a task that frequently occurs in graph mining applications such as social network analysis. Attributed graph alignment is a variant of graph alignment, in which publicly available side information or attributes are exploited to assist graph alignment. Existing studies on attributed graph alignment focus on either theoretical performance without computational constraints or empirical performance of efficient algorithms. This motivates us to investigate efficient algorithms with theoretical performance guarantee. In this paper, we propose two polynomial-time algorithms that exactly recover the vertex correspondence with high probability. The feasible region of the proposed algorithms is near optimal compared to the information-theoretic limits. When specialized to the seeded graph alignment problem under the seeded Erdős--Rényi graph pair model, the proposed algorithms extends the best known feasible region for exact alignment by polynomial-time algorithms.
BibTeX
@article{wang2022feasible,
  author = {Ziao Wang and Ning Zhang and Weina Wang and Lele Wang},
  title = {{On the Feasible Region of Efficient Algorithms for Attributed Graph Alignment}},
  journal = {IEEE Trans. Information Theory},
  year = {2022},
  url = {https://openreview.net/forum?id=8ah4I43Psy},
}
Figure