Unseeded low-rank graph matching by transform-based unsupervised point registration

Abstract

The problem of learning a correspondence relationship between nodes of two networks has drawn much attention of the computer science community and recently that of statisticians. The unseeded version of this problem, in which we do not know any part of the true correspondence, is a long-standing challenge. For low-rank networks, the problem can be translated into an unsupervised point registration problem, in which two point sets generated from the same distribution are matchable by an unknown orthonormal transformation. Conventional methods generally lack consistency guarantee and are usually computationally costly. In this paper, we propose a novel approach to this problem. Instead of simultaneously estimating the unknown correspondence and orthonormal transformation to match up the two point sets, we match their distributions via minimizing our designed loss function capturing the discrepancy between their Laplace transforms, thus avoiding the optimization over all possible correspondences. This dramatically reduces the dimension of the optimization problem from $\Omega (n^2)$ parameters to $O(d^2)$ parameters, where $d$ is the fixed rank, and enables convenient theoretical analysis. In this paper, we provide arguably the first consistency guarantee and explicit error rate for general low-rank models. Our method provides control over the computational complexity ranging from $\omega (n)$ (any growth rate faster than $n$) to $O(n^2)$ while pertaining consistency. We demonstrate the effectiveness of our method through several numerical examples.

arXiv comment16 pages

References in corpus (11)

• Graph Isomorphism in Quasipolynomial Time
• Rate-optimal graphon estimation
• Nonparametric graphon estimation
• Statistical inference on random dot product graphs: a survey
• Convergence and Concentration of Empirical Measures under Wasserstein Distance in Unbounded Functional Spaces
• Seeded graph matching for correlated Erdős-Rényi graphs
• Detecting Overlapping Communities in Networks Using Spectral Methods
• Seeded Graph Matching Via Joint Optimization of Fidelity and Commensurability
• Network Representation Using Graph Root Distributions
• Why are Big Data Matrices Approximately Low Rank?
• Efficient Realization of Givens Rotation through Algorithm-Architecture Co-design for Acceleration of QR Factorization

Cited by in corpus (3)

• Nonparametric two-sample hypothesis testing for low-rank random graphs of differing sizes
• The Importance of Being Correlated: Implications of Dependence in Joint Spectral Inference across Multiple Networks
• Consistent polynomial-time unseeded graph matching for Lipschitz graphons