Casting graph isomorphism as a point set registration problem using a simplex embedding and sampling

• URL: http://arxiv.org/abs/2111.09696v1
• Date: Mon, 15 Nov 2021 12:16:21 GMT
• Title: Casting graph isomorphism as a point set registration problem using a simplex embedding and sampling
• Authors: Yigit Oktar
• Abstract summary: A graph can be represented as a point set in enough dimensions using a simplex embedding and sampling. The isomorphism of them corresponds to the existence of a perfect registration between the point set forms of the graphs. The related idea of equivalence classes suggests that graph canonization may be an important tool in tackling graph isomorphism problem.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Graph isomorphism is an important problem as its worst-case time complexity is not yet fully understood. In this study, we try to draw parallels between a related optimization problem called point set registration. A graph can be represented as a point set in enough dimensions using a simplex embedding and sampling. Given two graphs, the isomorphism of them corresponds to the existence of a perfect registration between the point set forms of the graphs. In the case of non-isomorphism, the point set form optimization result can be used as a distance measure between two graphs having the same number of vertices and edges. The related idea of equivalence classes suggests that graph canonization may be an important tool in tackling graph isomorphism problem and an orthogonal transformation invariant feature extraction based on this high dimensional point set representation may be fruitful. The concepts presented can also be extended to automorphism, and subgraph isomorphism problems and can also be applied on hypergraphs with certain modifications.

Related papers

• SAT-Based Algorithms for Regular Graph Pattern Matching [40.86962847131912]
  We propose a generalization of graph isomorphism that allows one to check complex structural properties. This specification is given in the form of a Regular Graph Pattern (ReGaP), a special type of graph inspired by regular expressions. We propose a SAT-based algorithm for checking if a target graph matches a given ReGaP.
  arXiv  Detail & Related papers  (2023-12-15T18:12:44Z)
• 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)
• 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)
• Harnessing spectral representations for subgraph alignment [15.86857474914914]
  We propose a spectral representation for maps that is compact, easy to compute, robust to topological changes, easy to plug into existing pipelines, and is especially effective for subgraph alignment problems. We report for the first time a surprising phenomenon where the partiality arising in the subgraph alignment task is manifested as a special structure of the map coefficients.
  arXiv  Detail & Related papers  (2022-05-30T09:03:28Z)
• Scaling up graph homomorphism for classification via sampling [1.662966122370634]
  We study the use of graph homomorphism density features as a scalable alternative to homomorphism numbers. We propose a high-performance implementation of a simple sampling algorithm which computes additive approximations of homomorphism densities.
  arXiv  Detail & Related papers  (2021-04-08T20:25:37Z)
• Impossibility of Partial Recovery in the Graph Alignment Problem [3.5880535198436156]
  We show an average-case and noisy version of the well-known NP-hard graph isomorphism problem. For the correlated Erd"os-R'enyi model, we prove an impossibility result for partial recovery in the sparse regime. Our bound is tight in the noiseless case (the graph isomorphism problem) and we conjecture that it is still tight with noise.
  arXiv  Detail & Related papers  (2021-02-04T15:26:48Z)
• Articulated Shape Matching Using Laplacian Eigenfunctions and Unsupervised Point Registration [38.16866987817019]
  Spectral graph theory can be used to map these graphs onto lower dimensional spaces and match shapes by aligning their embeddings. We derive a new formulation that finds the best alignment between two congruent $K$-dimensional sets of points by selecting the best subset of eigenfunctions of the Laplacian matrix.
  arXiv  Detail & Related papers  (2020-12-14T08:49:25Z)
• Multilayer Clustered Graph Learning [66.94201299553336]
  We use contrastive loss as a data fidelity term, in order to properly aggregate the observed layers into a representative graph. Experiments show that our method leads to a clustered clusters w.r.t. We learn a clustering algorithm for solving clustering problems.
  arXiv  Detail & Related papers  (2020-10-29T09:58:02Z)
• Line Graph Neural Networks for Link Prediction [71.00689542259052]
  We consider the graph link prediction task, which is a classic graph analytical problem with many real-world applications. In this formalism, a link prediction problem is converted to a graph classification task. We propose to seek a radically different and novel path by making use of the line graphs in graph theory. In particular, each node in a line graph corresponds to a unique edge in the original graph. Therefore, link prediction problems in the original graph can be equivalently solved as a node classification problem in its corresponding line graph, instead of a graph classification task.
  arXiv  Detail & Related papers  (2020-10-20T05:54:31Z)
• Hamiltonian systems, Toda lattices, Solitons, Lax Pairs on weighted Z-graded graphs [62.997667081978825]
  We identify conditions which allow one to lift one dimensional solutions to solutions on graphs. We show that even for a simple example of a topologically interesting graph the corresponding non-trivial Lax pairs and associated unitary transformations do not lift to a Lax pair on the Z-graded graph.
  arXiv  Detail & Related papers  (2020-08-11T17:58:13Z)
• 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.