Casting graph isomorphism as a point set registration problem using a simplex embedding and sampling
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Articulated Shape Matching Using Laplacian Eigenfunctions and Unsupervised Point Registration
Matching articulated shapes represented by voxel-sets reduces to maximal sub-graph isomorphism when each set is described by a weighted graph. Spectral graph theory can be used to map these graphs onto lower dimensional …
ClusteringGraph Matching3D Shape Registration Using Spectral Graph Embedding and Probabilistic Matching
We address the problem of 3D shape registration and we propose a novel technique based on spectral graph theory and probabilistic matching. The task of 3D shape analysis involves tracking, recognition, registration, etc.…
Dimensionality ReductionGraph EmbeddingGraph MatchingMEDPNet: Achieving High-Precision Adaptive Registration for Complex Die Castings
Due to their complex spatial structure and diverse geometric features, achieving high-precision and robust point cloud registration for complex Die Castings has been a significant challenge in the die-casting industry. E…
Computational EfficiencyPoint Cloud RegistrationNeural Subgraph Isomorphism Counting
In this paper, we study a new graph learning problem: learning to count subgraph isomorphisms. Different from other traditional graph learning problems such as node classification and link prediction, subgraph isomorphis…
Domain AdaptationGraph LearningLink PredictionNode Classification+2Instruction Set and Language for Hypergraphs
We present IsalHG, a method for representing the structure of any finite, connected hypergraph of bounded hyperedge arity as a string over a compact instruction alphabet $Σ_{\mathrm{HG}}$. The encoding is executed by a s…