Deep Graph Matching under Quadratic Constraint

• URL: http://arxiv.org/abs/2103.06643v2
• Date: Sun, 14 Mar 2021 06:47:22 GMT
• Title: Deep Graph Matching under Quadratic Constraint
• Authors: Quankai Gao, Fudong Wang, Nan Xue, Jin-Gang Yu, Gui-Song Xia
• Abstract summary: We propose to explicitly formulate pairwise graph structures as a textbfquadratic constraint incorporated into the deep graph matching framework. The quadratic constraint minimizes the pairwise structural discrepancy between graphs, which can reduce the ambiguities brought by only using the extracted CNN features. To give more precise and proper supervision, a well-designed false matching loss against class imbalance is proposed, which can better penalize the false negatives and false positives with less overfitting.
• Score: 30.72996618021077
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Recently, deep learning based methods have demonstrated promising results on the graph matching problem, by relying on the descriptive capability of deep features extracted on graph nodes. However, one main limitation with existing deep graph matching (DGM) methods lies in their ignorance of explicit constraint of graph structures, which may lead the model to be trapped into local minimum in training. In this paper, we propose to explicitly formulate pairwise graph structures as a \textbf{quadratic constraint} incorporated into the DGM framework. The quadratic constraint minimizes the pairwise structural discrepancy between graphs, which can reduce the ambiguities brought by only using the extracted CNN features. Moreover, we present a differentiable implementation to the quadratic constrained-optimization such that it is compatible with the unconstrained deep learning optimizer. To give more precise and proper supervision, a well-designed false matching loss against class imbalance is proposed, which can better penalize the false negatives and false positives with less overfitting. Exhaustive experiments demonstrate that our method competitive performance on real-world datasets.

Related papers

• ExMAG: Learning of Maximally Ancestral Graphs [2.740961764574832]
  We propose a score-based learning algorithm for learning maximally ancestral graphs. We show that the proposed approach turns out to produce more accurate results when applied to small and medium-sized synthetic instances up to 25 variables.
  arXiv  Detail & Related papers  (2025-03-11T10:08:39Z)
• Boosting Graph Neural Network Expressivity with Learnable Lanczos Constraints [7.605749412696919]
  Graph Neural Networks (GNNs) excel in handling graph-structured data but often underperform in link prediction tasks. We present a novel method to enhance the expressivity of GNNs by embedding induced subgraphs into the graph Laplacian matrix's eigenbasis. We demonstrate the ability to distinguish graphs that are indistinguishable by 2-WL, while maintaining efficient time complexity.
  arXiv  Detail & Related papers  (2024-08-22T12:22:00Z)
• Implicit Graph Neural Diffusion Networks: Convergence, Generalization, and Over-Smoothing [7.984586585987328]
  Implicit Graph Neural Networks (GNNs) have achieved significant success in addressing graph learning problems. We introduce a geometric framework for designing implicit graph diffusion layers based on a parameterized graph Laplacian operator. We show how implicit GNN layers can be viewed as the fixed-point equation of a Dirichlet energy minimization problem.
  arXiv  Detail & Related papers  (2023-08-07T05:22:33Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  We introduce a novel all-pair message passing scheme for efficiently propagating node signals between arbitrary nodes. The efficient computation is enabled by a kernerlized Gumbel-Softmax operator. Experiments demonstrate the promising efficacy of the method in various tasks including node classification on graphs.
  arXiv  Detail & Related papers  (2023-06-14T09:21:15Z)
• Localized Contrastive Learning on Graphs [110.54606263711385]
  We introduce a simple yet effective contrastive model named Localized Graph Contrastive Learning (Local-GCL) In spite of its simplicity, Local-GCL achieves quite competitive performance in self-supervised node representation learning tasks on graphs with various scales and properties.
  arXiv  Detail & Related papers  (2022-12-08T23:36:00Z)
• Deep Manifold Learning with Graph Mining [80.84145791017968]
  We propose a novel graph deep model with a non-gradient decision layer for graph mining. The proposed model has achieved state-of-the-art performance compared to the current models.
  arXiv  Detail & Related papers  (2022-07-18T04:34:08Z)
• Bayesian Graph Contrastive Learning [55.36652660268726]
  We propose a novel perspective of graph contrastive learning methods showing random augmentations leads to encoders. Our proposed method represents each node by a distribution in the latent space in contrast to existing techniques which embed each node to a deterministic vector. We show a considerable improvement in performance compared to existing state-of-the-art methods on several benchmark datasets.
  arXiv  Detail & Related papers  (2021-12-15T01:45:32Z)
• Distributionally Robust Semi-Supervised Learning Over Graphs [68.29280230284712]
  Semi-supervised learning (SSL) over graph-structured data emerges in many network science applications. To efficiently manage learning over graphs, variants of graph neural networks (GNNs) have been developed recently. Despite their success in practice, most of existing methods are unable to handle graphs with uncertain nodal attributes. Challenges also arise due to distributional uncertainties associated with data acquired by noisy measurements. A distributionally robust learning framework is developed, where the objective is to train models that exhibit quantifiable robustness against perturbations.
  arXiv  Detail & Related papers  (2021-10-20T14:23:54Z)
• Graphon based Clustering and Testing of Networks: Algorithms and Theory [11.3700474413248]
  Network-valued data are encountered in a wide range of applications and pose challenges in learning. We present two clustering algorithms that achieve state-of-the-art results. We further study the applicability of the proposed distance for graph two-sample testing problems.
  arXiv  Detail & Related papers  (2021-10-06T13:14:44Z)
• Learning Sparse Graph with Minimax Concave Penalty under Gaussian Markov Random Fields [51.07460861448716]
  This paper presents a convex-analytic framework to learn from data. We show that a triangular convexity decomposition is guaranteed by a transform of the corresponding to its upper part.
  arXiv  Detail & Related papers  (2021-09-17T17:46:12Z)
• Learning Graphs from Smooth Signals under Moment Uncertainty [23.868075779606425]
  We consider the problem of inferring the graph structure from a given set of graph signals. Traditional graph learning models do not take this distributional uncertainty into account.
  arXiv  Detail & Related papers  (2021-05-12T06:47: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.