SIGMA: A Structural Inconsistency Reducing Graph Matching Algorithm

• URL: http://arxiv.org/abs/2202.02797v1
• Date: Sun, 6 Feb 2022 15:18:37 GMT
• Title: SIGMA: A Structural Inconsistency Reducing Graph Matching Algorithm
• Authors: Weijie Liu, Chao Zhang, Nenggan Zheng, Hui Qian
• Abstract summary: 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.
• Score: 21.1095092767297
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Graph matching finds the correspondence of nodes across two correlated graphs and lies at the core of many applications. When graph side information is not available, the node correspondence is estimated on the sole basis of network topologies. In this paper, we propose a novel criterion to measure the graph matching accuracy, structural inconsistency (SI), which is defined based on the network topological structure. Specifically, SI incorporates the heat diffusion wavelet to accommodate the multi-hop structure of the graphs. Based on SI, we propose a Structural Inconsistency reducing Graph Matching Algorithm (SIGMA), which improves the alignment scores of node pairs that have low SI values in each iteration. Under suitable assumptions, SIGMA can reduce SI values of true counterparts. Furthermore, we demonstrate 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. Extensive experiments show that our method outperforms state-of-the-art methods.

Related papers

• SEGMN: A Structure-Enhanced Graph Matching Network for Graph Similarity Learning [4.506862318909861]
  Graph similarity computation (GSC) aims to quantify the similarity score between two graphs. We propose a structure-enhanced graph matching network (SEGMN) The dual embedding learning module incorporates adjacent edge representation into each node to achieve a structure-enhanced representation. The structure perception matching module achieves cross-graph structure enhancement through assignment graph convolution.
  arXiv  Detail & Related papers  (2024-11-06T02:45:16Z)
• Geodesic Distance Between Graphs: A Spectral Metric for Assessing the Stability of Graph Neural Networks [4.110108749051657]
  We introduce a Graph Geodesic Distance (GGD) metric for assessing the generalization and stability of Graph Neural Networks (GNNs) We show that the proposed GGD metric can effectively quantify dissimilarities between two graphs by encapsulating their differences in key structural (spectral) properties. The proposed GGD metric shows significantly improved performance for stability evaluation of GNNs especially when only partial node features are available.
  arXiv  Detail & Related papers  (2024-06-15T04:47:40Z)
• Simplifying Node Classification on Heterophilous Graphs with Compatible Label Propagation [6.071760028190454]
  We show that a well-known graph algorithm, Label Propagation, combined with a shallow neural network can achieve comparable performance to GNNs in semi-supervised node classification on graphs with high homophily. In this paper, we show that this approach falls short on graphs with low homophily, where nodes often connect to the nodes of the opposite classes. Our algorithm first learns the class compatibility matrix and then aggregates label predictions using LP algorithm weighted by class compatibilities.
  arXiv  Detail & Related papers  (2022-05-19T08:34:34Z)
• Graph Spectral Embedding using the Geodesic Betweeness Centrality [76.27138343125985]
  We introduce the Graph Sylvester Embedding (GSE), an unsupervised graph representation of local similarity, connectivity, and global structure. GSE uses the solution of the Sylvester equation to capture both network structure and neighborhood proximity in a single representation.
  arXiv  Detail & Related papers  (2022-05-07T04:11:23Z)
• 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)
• Sparse Partial Least Squares for Coarse Noisy Graph Alignment [10.172041234280865]
  Graph signal processing (GSP) provides a powerful framework for analyzing signals arising in a variety of domains. We propose a novel regularized partial least squares method which both incorporates the observed graph structures and imposes sparsity in order to reflect the underlying block community structure.
  arXiv  Detail & Related papers  (2021-04-06T21:52:15Z)
• Accurate Learning of Graph Representations with Graph Multiset Pooling [45.72542969364438]
  We propose a Graph Multiset Transformer (GMT) that captures the interaction between nodes according to their structural dependencies. Our experimental results show that GMT significantly outperforms state-of-the-art graph pooling methods on graph classification benchmarks.
  arXiv  Detail & Related papers  (2021-02-23T07:45:58Z)
• node2coords: Graph Representation Learning with Wasserstein Barycenters [59.07120857271367]
  We introduce node2coords, a representation learning algorithm for graphs. It learns simultaneously a low-dimensional space and coordinates for the nodes in that space. Experimental results demonstrate that the representations learned with node2coords are interpretable.
  arXiv  Detail & Related papers  (2020-07-31T13:14:25Z)
• Inverse Graph Identification: Can We Identify Node Labels Given Graph Labels? [89.13567439679709]
  Graph Identification (GI) has long been researched in graph learning and is essential in certain applications. This paper defines a novel problem dubbed Inverse Graph Identification (IGI) We propose a simple yet effective method that makes the node-level message passing process using Graph Attention Network (GAT) under the protocol of GI.
  arXiv  Detail & Related papers  (2020-07-12T12:06:17Z)
• Graph Pooling with Node Proximity for Hierarchical Representation Learning [80.62181998314547]
  We propose a novel graph pooling strategy that leverages node proximity to improve the hierarchical representation learning of graph data with their multi-hop topology. Results show that the proposed graph pooling strategy is able to achieve state-of-the-art performance on a collection of public graph classification benchmark datasets.
  arXiv  Detail & Related papers  (2020-06-19T13:09:44Z)
• Wasserstein-based Graph Alignment [56.84964475441094]
  We cast a new formulation for the one-to-many graph alignment problem, which aims at matching a node in the smaller graph with one or more nodes in the larger graph. We show that our method leads to significant improvements with respect to the state-of-the-art algorithms for each of these tasks.
  arXiv  Detail & Related papers  (2020-03-12T22:31:59Z)

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.