Attributed Network Alignment: Statistical Limits and Efficient Algorithm

• URL: http://arxiv.org/abs/2604.04365v1
• Date: Mon, 06 Apr 2026 02:27:50 GMT
• Title: Attributed Network Alignment: Statistical Limits and Efficient Algorithm
• Abstract summary: We study the problem of recovering a hidden correspondence between two correlated graphs when both edge weights and node features are observed.<n>We propose QPAlign, an algorithm based on a quadratic programming relaxation, and demonstrate its strong empirical performance on both synthetic and real datasets.
• Score: 11.625288483661883
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper studies the problem of recovering a hidden vertex correspondence between two correlated graphs when both edge weights and node features are observed. While most existing work on graph alignment relies primarily on edge information, many real-world applications provide informative node features in addition to graph topology. To capture this setting, we introduce the featured correlated Gaussian Wigner model, where two graphs are coupled through an unknown vertex permutation, and the node features are correlated under the same permutation. We characterize the optimal information-theoretic thresholds for exact recovery and partial recovery of the latent mapping. On the algorithmic side, we propose QPAlign, an algorithm based on a quadratic programming relaxation, and demonstrate its strong empirical performance on both synthetic and real datasets. Moreover, we also derive theoretical guarantees for the proposed procedure, supporting its reliability and providing convergence guarantees.

Related papers

• Unsupervised Graph Representation Learning with Complementary View Alignment [9.33832512108175]
  Unsupervised graph representation learning aims to derive meaningful node embeddings without relying on labeled data.<n>We propose textscAlignGAE, a novel extension of textitMaskGAE that preserves the full frequency spectrum through complementary view alignment.<n>Our framework introduces a dual-encoder architecture that separately processes structural and attribute information, incorporates node positional encoding, and employs dual reconstruction tasks for both edges and node attributes.
  arXiv  Detail & Related papers  (2026-07-27T12:15:25Z)
• Contextual Graph Matching with Correlated Gaussian Features [2.497926557563177]
  We investigate contextual graph matching in the Gaussian setting, where both edge weights and node features are correlated across two networks.<n>We derive precise information-theoretic thresholds for exact recovery, and identify conditions under which almost exact recovery is possible or impossible.<n>Our results provide the first rigorous characterization of how structural and contextual information interact in graph matching, and establish a benchmark for designing efficient algorithms.
  arXiv  Detail & Related papers  (2026-03-24T15:11:04Z)
• DREAM: Dual-Standard Semantic Homogeneity with Dynamic Optimization for Graph Learning with Label Noise [53.55187452152358]
  This paper proposes a novel method, Dual-Standard Semantic Homogeneity with Dynamic Optimization (DREAM) for reliable, relation-informed optimization on graphs with label noise.<n>Specifically, we design a relation-informed dynamic optimization framework that iteratively reevaluates the reliability of each labeled node in the graph.
  arXiv  Detail & Related papers  (2026-01-24T12:54:18Z)
• Covariate-assisted graph matching [1.4466802614938332]
  We propose two novel graph matching methods, where a partial alignment for a set of nodes, called seeds, is known.<n>The effectiveness of our methods is demonstrated through numerical experiments and in an application to matching the statistics academic genealogy and the collaboration networks.
  arXiv  Detail & Related papers  (2025-12-12T18:12:56Z)
• Bounds on Perfect Node Classification: A Convex Graph Clustering Perspective [50.3088702686312]
  We present an analysis of the transductive node classification problem, where the underlying graph consists of communities that agree with the node labels and node features.<n>For node classification, we propose a novel optimization problem that incorporates the node-specific information in a spectral graph clustering framework.
  arXiv  Detail & Related papers  (2025-08-27T19:22:35Z)
• Matrix Completion with Graph Information: A Provable Nonconvex Optimization Approach [5.235925587710112]
  We consider the problem of matrix completion with graphs as side information depicting the interrelations between variables.<n>We propose in this paper a graph regularized matrix completion algorithm called GSGD, based on preconditioned projected descent approach.
  arXiv  Detail & Related papers  (2025-02-12T16:21:01Z)
• Deep Manifold Graph Auto-Encoder for Attributed Graph Embedding [51.75091298017941]
  This paper proposes a novel Deep Manifold (Variational) Graph Auto-Encoder (DMVGAE/DMGAE) for attributed graph data. The proposed method surpasses state-of-the-art baseline algorithms by a significant margin on different downstream tasks across popular datasets.
  arXiv  Detail & Related papers  (2024-01-12T17:57:07Z)
• T-GAE: Transferable Graph Autoencoder for Network Alignment [79.89704126746204]
  T-GAE is a graph autoencoder framework that leverages transferability and stability of GNNs to achieve efficient network alignment without retraining. Our experiments demonstrate that T-GAE outperforms the state-of-the-art optimization method and the best GNN approach by up to 38.7% and 50.8%, respectively.
  arXiv  Detail & Related papers  (2023-10-05T02:58:29Z)
• GrannGAN: Graph annotation generative adversarial networks [72.66289932625742]
  We consider the problem of modelling high-dimensional distributions and generating new examples of data with complex relational feature structure coherent with a graph skeleton. The model we propose tackles the problem of generating the data features constrained by the specific graph structure of each data point by splitting the task into two phases. In the first it models the distribution of features associated with the nodes of the given graph, in the second it complements the edge features conditionally on the node features.
  arXiv  Detail & Related papers  (2022-12-01T11:49:07Z)
• Semi-Supervised Clustering of Sparse Graphs: Crossing the Information-Theoretic Threshold [3.6052935394000234]
  Block model is a canonical random graph model for clustering and community detection on network-structured data. No estimator based on the network topology can perform substantially better than chance on sparse graphs if the model parameter is below a certain threshold. We prove that with an arbitrary fraction of the labels feasible throughout the parameter domain.
  arXiv  Detail & Related papers  (2022-05-24T00:03:25Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  We propose a bi-level optimization approach for learning the optimal graph structure. We also explore a low-rank approximation model for further reducing the time complexity.
  arXiv  Detail & Related papers  (2022-05-06T03:37:00Z)
• Interpretable Deep Graph Generation with Node-Edge Co-Disentanglement [55.2456981313287]
  We propose a new disentanglement enhancement framework for deep generative models for attributed graphs. A novel variational objective is proposed to disentangle the above three types of latent factors, with novel architecture for node and edge deconvolutions. Within each type, individual-factor-wise disentanglement is further enhanced, which is shown to be a generalization of the existing framework for images.
  arXiv  Detail & Related papers  (2020-06-09T16:33:49Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.