Contextual Graph Matching with Correlated Gaussian Features

• URL: http://arxiv.org/abs/2603.23305v1
• Date: Tue, 24 Mar 2026 15:11:04 GMT
• Title: Contextual Graph Matching with Correlated Gaussian Features
• Abstract summary: 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.
• Score: 2.497926557563177
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We investigate contextual graph matching in the Gaussian setting, where both edge weights and node features are correlated across two networks. We derive precise information-theoretic thresholds for exact recovery, and identify conditions under which almost exact recovery is possible or impossible, in terms of graph and feature correlation strengths, the number of nodes, and feature dimension. Interestingly, whereas an all-or-nothing phase transition is observed in the standard graph-matching scenario, the additional contextual information introduces a richer structure: thresholds for exact and almost exact recovery no longer coincide. 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.

Related papers

• Attributed Network Alignment: Statistical Limits and Efficient Algorithm [11.625288483661883]
  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.
  arXiv  Detail & Related papers  (2026-04-06T02:27:50Z)
• A Unified Framework for Interactive Visual Graph Matching via Attribute-Structure Synchronization [4.4315876561900165]
  We propose a novel framework for interactive visual graph matching.<n>In the proposed framework, an attribute-structure synchronization method is developed for representing structural and attribute features.<n>With the designed interfaces, the users can also specify a new target graph with desired structural and semantic features.
  arXiv  Detail & Related papers  (2025-07-26T02:47:09Z)
• Improving embedding of graphs with missing data by soft manifolds [51.425411400683565]
  The reliability of graph embeddings depends on how much the geometry of the continuous space matches the graph structure. We introduce a new class of manifold, named soft manifold, that can solve this situation. Using soft manifold for graph embedding, we can provide continuous spaces to pursue any task in data analysis over complex datasets.
  arXiv  Detail & Related papers  (2023-11-29T12:48:33Z)
• Structure-free Graph Condensation: From Large-scale Graphs to Condensed Graph-free Data [91.27527985415007]
  Existing graph condensation methods rely on the joint optimization of nodes and structures in the condensed graph. We advocate a new Structure-Free Graph Condensation paradigm, named SFGC, to distill a large-scale graph into a small-scale graph node set.
  arXiv  Detail & Related papers  (2023-06-05T07:53:52Z)
• Semantic Random Walk for Graph Representation Learning in Attributed Graphs [2.318473106845779]
  We propose a novel semantic graph representation (SGR) method to formulate the joint optimization of the two heterogeneous sources into a common high-order proximity based framework. Conventional embedding methods that consider high-order topology proximities can then be easily applied to the newly constructed graph to learn the representations of both node and attribute. The learned attribute embeddings can also effectively support some semantic-oriented inference tasks, helping to reveal the graph's deep semantic.
  arXiv  Detail & Related papers  (2023-05-11T02:35:16Z)
• 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)
• Collaborative likelihood-ratio estimation over graphs [55.98760097296213]
  Graph-based Relative Unconstrained Least-squares Importance Fitting (GRULSIF) We develop this idea in a concrete non-parametric method that we call Graph-based Relative Unconstrained Least-squares Importance Fitting (GRULSIF) We derive convergence rates for our collaborative approach that highlights the role played by variables such as the number of available observations per node, the size of the graph, and how accurately the graph structure encodes the similarity between tasks.
  arXiv  Detail & Related papers  (2022-05-28T15:37:03Z)
• SIGMA: A Structural Inconsistency Reducing Graph Matching Algorithm [21.1095092767297]
  We propose a novel criterion to measure the graph matching accuracy, structural inconsistency (SI) Specifically, SI incorporates the heat diffusion wavelet to accommodate the multi-hop structure of the graphs. We show that SIGMA can be derived by using a mirror descent method to solve the Gromov-Wasserstein distance with a novel K-hop-structure-based matching costs.
  arXiv  Detail & Related papers  (2022-02-06T15:18:37Z)
• Joint Graph Learning and Matching for Semantic Feature Correspondence [69.71998282148762]
  We propose a joint emphgraph learning and matching network, named GLAM, to explore reliable graph structures for boosting graph matching. The proposed method is evaluated on three popular visual matching benchmarks (Pascal VOC, Willow Object and SPair-71k) It outperforms previous state-of-the-art graph matching methods by significant margins on all benchmarks.
  arXiv  Detail & Related papers  (2021-09-01T08:24:02Z)
• Fea2Fea: Exploring Structural Feature Correlations via Graph Neural Networks [7.766921168069533]
  We introduce graph feature to feature (Fea2Fea) prediction pipelines in a low dimensional space to explore some preliminary results on structural feature correlation. The results show that there exists high correlation between some of the structural features. A redundant feature combination with initial node features, which is filtered by graph neural network has improved its classification accuracy in some graph datasets.
  arXiv  Detail & Related papers  (2021-06-24T14:36:50Z)
• Structure-Augmented Text Representation Learning for Efficient Knowledge Graph Completion [53.31911669146451]
  Human-curated knowledge graphs provide critical supportive information to various natural language processing tasks. These graphs are usually incomplete, urging auto-completion of them. graph embedding approaches, e.g., TransE, learn structured knowledge via representing graph elements into dense embeddings. textual encoding approaches, e.g., KG-BERT, resort to graph triple's text and triple-level contextualized representations.
  arXiv  Detail & Related papers  (2020-04-30T13:50:34Z)

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.