Product Graph-based Higher Order Contextual Similarities for Inexact Subgraph Matching
Many algorithms formulate graph matching as an optimization of an objective function of pairwise quantification of nodes and edges of two graphs to be matched. Pairwise measurements usually consider local attributes but disregard contextual information involved in graph structures. We address this issue by proposing contextual similarities between pairs of nodes. This is done by considering the tensor product graph (TPG) of two graphs to be matched, where each node is an ordered pair of nodes of the operand graphs. Contextual similarities between a pair of nodes are computed by accumulating weighted walks (normalized pairwise similarities) terminating at the corresponding paired node in TPG. Once the contextual similarities are obtained, we formulate subgraph matching as a node and edge selection problem in TPG. We use contextual similarities to construct an objective function and optimize it with a linear programming approach. Since random walk formulation through TPG takes into account higher order information, it is not a surprise that we obtain more reliable similarities and better discrimination among the nodes and edges. Experimental results shown on synthetic as well as real benchmarks illustrate that higher order contextual similarities add discriminating power and allow one to find approximate solutions to the subgraph matching problem.
Code (0)
등록된 구현이 없습니다.
Tasks
Graph MatchingSimilar Papers 제목 키워드 기반
Semantics of higher-order probabilistic programs with conditioning
We present a denotational semantics for higher-order probabilistic programs in terms of linear operators between Banach spaces. Our semantics is rooted in the classical theory of Banach spaces and their tensor products, …
Neural Collaborative Filtering vs. Matrix Factorization Revisited
Embedding based models have been the state of the art in collaborative filtering for over a decade. Traditionally, the dot product or higher order equivalents have been used to combine two or more embeddings, e.g., most …
Collaborative FilteringLink PredictionRetrievalHigher-order Weighted Graph Convolutional Networks
Graph Convolution Network (GCN) has been recognized as one of the most effective graph models for semi-supervised learning, but it extracts merely the first-order or few-order neighborhood information through information…
Node ClassificationHigher order co-occurrence tensors for hypergraphs via face-splitting
A popular trick for computing a pairwise co-occurrence matrix is the product of an incidence matrix and its transpose. We present an analog for higher order tuple co-occurrences using the face-splitting product, or alter…
Building Contextual Knowledge Graphs for Personalized Learning Recommendations using Text Mining and Semantic Graph Completion
Modelling learning objects (LO) within their context enables the learner to advance from a basic, remembering-level, learning objective to a higher-order one, i.e., a level with an application- and analysis objective. Wh…
Knowledge GraphsRelation Extraction