Consistent polynomial-time unseeded graph matching for Lipschitz graphons

Yuan Zhang

Abstract

We propose a consistent polynomial-time method for the unseeded node matching problem for networks with smooth underlying structures. Despite widely conjectured by the research community that the structured graph matching problem to be significantly easier than its worst case counterpart, well-known to be NP-hard, the statistical version of the problem has stood a challenge that resisted any solution both provable and polynomial-time. The closest existing work requires quasi-polynomial time. Our method is based on the latest advances in graphon estimation techniques and analysis on the concentration of empirical Wasserstein distances. Its core is a simple yet unconventional sampling-and-matching scheme that reduces the problem from unseeded to seeded. Our method allows flexible efficiencies, is convenient to analyze and potentially can be extended to more general settings. Our work enables a rich variety of subsequent estimations and inferences.

Introduction

Graph matching—the task of finding the best alignment between two networks—is a fundamental problem in data science, with applications ranging from de-anonymizing social networks to aligning biological pathways. In its "unseeded" form, where no prior node correspondences are known, the problem is equivalent to the Graph Isomorphism problem in its exact form and is generally considered computationally daunting.

While the research community has long suspected that structured graph matching (where graphs are generated from underlying probability models) should be easier than the worst-case NP-hard combinatorial version, finding a solution that is both statistically consistent and computationally efficient has remained elusive. Previous provable solutions required quasi-polynomial time, which becomes prohibitively slow as the number of nodes ($n$) grows. This paper introduces the first algorithm that achieves both polynomial-time complexity and statistical consistency for networks with smooth underlying structures, specifically those modeled by Lipschitz graphons.

The Lipschitz Graphon Model

The algorithm relies on the assumption that the graphs are generated from a "Lipschitz graphon." In this framework, nodes are associated with latent positions, and the probability of an edge between two nodes is a smooth (Lipschitz) function of their positions. This implies that if two nodes are "similar" in the latent space, their connection patterns to the rest of the graph will also be similar. This smoothness is the key to overcoming the combinatorial explosion of the matching problem.

The Unseeded Graph Matching Algorithm

The proposed method follows a five-step pipeline to reduce the unseeded matching problem into a manageable computation:

  1. Denoising (Neighborhood Smoothing): The raw, noisy 0/1 adjacency matrices are smoothed to estimate the underlying edge probabilities. This step converts the discrete graph into a continuous-like structure.
  2. Artificial Seeding: This is the core innovation. Rather than searching for true seeds, the algorithm randomly selects a small number ($d$) of columns from the matrices to serve as "artificial seeds."
  3. Initial Alignment: Using the Hungarian algorithm, the method finds a preliminary mapping between all nodes and these artificial seeds based on their estimated connection patterns.
  4. Reduced Optimization: The algorithm solves a much smaller matching problem of size $d \times d$ via exhaustive enumeration. By choosing $d \approx \log n / \log \log n$, this search remains within polynomial time limits while providing enough information to align the global structure.
  5. Final Assembly: The results are combined to produce the final estimated permutation matrix that aligns the two graphs.

Key Insights: From "Soft" to "Hard" Seeds

A major theoretical hurdle in unseeded matching is the difficulty of finding even a single correct correspondence. This paper argues that in smooth networks, "soft" seeds—nodes that are close in latent space—are easy to find through random sampling. As the network size increases, these soft seeds behave increasingly like "hard" seeds (exact matches). By leveraging Wasserstein distances, the author proves that a small set of random samples will eventually cover the necessary connection patterns to represent the entire network structure.

Theoretical Results and Complexity

The paper provides two primary theoretical guarantees:

  • Polynomial Time Complexity: The algorithm's complexity is $O(n^C)$, where $C$ is a constant. This is a significant improvement over the previous quasi-polynomial bounds ($n^{O(\log n)}$).
  • Statistical Consistency: The author provides a mathematical proof that the discrepancy between the matched probability matrices (the "loss") converges to zero as the number of nodes $n$ approaches infinity.

Furthermore, the method is shown to be adaptable beyond simple symmetric graphs, with potential extensions to bipartite and directed networks.

Limitations and Future Directions

While this work represents a theoretical breakthrough, several challenges remain for practical implementation:

  • The Exponent Constant: The polynomial exponent $C$ depends on the smoothness constants of the graphon. If $C$ is large, the algorithm may still be computationally expensive for mid-sized real-world graphs.
  • Error Rate Optimality: While consistent, the method may not yet achieve the "minimax" optimal error rate. Future work involving "network histograms" might be required to reach peak theoretical accuracy.
  • Sparsity: The current theory focuses on relatively dense graphs. Adapting these proofs to the very sparse, scale-free networks common in real-world applications remains an open area of research.

Summary updated

Abstract

We propose a consistent polynomial-time method for the unseeded node matching problem for networks with smooth underlying structures. Despite widely conjectured by the research community that the structured graph matching problem to be significantly easier than its worst case counterpart, well-known to be NP-hard, the statistical version of the problem has stood a challenge that resisted any solution both provable and polynomial-time. The closest existing work requires quasi-polynomial time. Our method is based on the latest advances in graphon estimation techniques and analysis on the concentration of empirical Wasserstein distances. Its core is a simple yet unconventional sampling-and-matching scheme that reduces the problem from unseeded to seeded. Our method allows flexible efficiencies, is convenient to analyze and potentially can be extended to more general settings. Our work enables a rich variety of subsequent estimations and inferences.
BibTeX
@misc{zhang2018consistent,
  author = {Yuan Zhang},
  title = {{Consistent polynomial-time unseeded graph matching for Lipschitz graphons}},
  year = {2018},
  eprint = {1807.11027},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1807.11027},
}
Figure