GRASP: Graph Alignment through Spectral Signatures
What is the best way to match the nodes of two graphs? This graph alignment problem generalizes graph isomorphism and arises in applications from social network analysis to bioinformatics. Some solutions assume that auxiliary information on known matches or node or edge attributes is available, or utilize arbitrary graph features. Such methods fare poorly in the pure form of the problem, in which only graph structures are given. Other proposals translate the problem to one of aligning node embeddings, yet, by doing so, provide only a single-scale view of the graph. In this paper, we transfer the shape-analysis concept of functional maps from the continuous to the discrete case, and treat the graph alignment problem as a special case of the problem of finding a mapping between functions on graphs. We present GRASP, a method that first establishes a correspondence between functions derived from Laplacian matrix eigenvectors, which capture multiscale structural characteristics, and then exploits this correspondence to align nodes. Our experimental study, featuring noise levels higher than anything used in previous studies, shows that GRASP outperforms state-of-the-art methods for graph alignment across noise levels and graph types.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
GRASPEL: Graph Spectral Learning at Scale
Learning meaningful graphs from data plays important roles in many data mining and machine learning tasks, such as data representation and analysis, dimension reduction, data clustering, and visualization, etc. In this w…
BIG-bench Machine LearningClusteringDimensionality ReductionGraph LearningGraph Learning via Spectral Densification
Graph learning plays important role in many data mining and machine learning tasks, such as manifold learning, data representation and analysis, dimensionality reduction, data clustering, and visualization, etc. For the …
BIG-bench Machine LearningClusteringDimensionality ReductionGraph LearningStable and Informative Spectral Signatures for Graph Matching
In this paper, we consider the approximate weighted graph matching problem and introduce stable and informative first and second order compatibility terms suitable for inclusion into the popular integer quadratic program…
Graph MatchingInformativenessA Graph Signal Processing Framework for Hallucination Detection in Large Language Models
Large language models achieve impressive results but distinguishing factual reasoning from hallucinations remains challenging. We propose a spectral analysis framework that models transformer layers as dynamic graphs ind…
GRASPED: Graph Anomaly Detection using Autoencoder with Spectral Encoder and Decoder (Full Version)
Graph machine learning has been widely explored in various domains, such as community detection, transaction analysis, and recommendation systems. In these applications, anomaly detection plays an important role. Recentl…
Graph Anomaly DetectionRecommendation SystemsCommunity Detection