arXiv research

A novel 3D shape registration method using spectral graph embedding and probabilistic matching.

We present a parallelized bijective graph matching algorithm that leverages seeds and is designed to match very large graphs. Our algorithm combines spectral graph embedding with existing state-of-the-art seeded graph matching procedures. We justify our approach by proving that modestly correlated, large stochastic blo…

Graph matching aims at finding the vertex correspondence between two unlabeled graphs that maximizes the total edge weight correlation. This amounts to solving a computationally intractable quadratic assignment problem. In this paper we propose a new spectral method, GRAph Matching by Pairwise eigen-Alignments (GRAMPA)…

We analyze a new spectral graph matching algorithm, GRAph Matching by Pairwise eigen-Alignments (GRAMPA), for recovering the latent vertex correspondence between two unlabeled, edge-correlated weighted graphs. Extending the exact recovery guarantees established in the companion paper for Gaussian weights, in this work,…

The paper introduces a quantum state system to count perfect matchings in graphs.

Graph spectra have been successfully used to classify network types, compute the similarity between graphs, and determine the number of communities in a network. For large graphs, where an eigen-decomposition is infeasible, iterative moment matched approximations to the spectra and kernel smoothing are typically used. …

SPECTRE uses spectral conditioning to generate larger graphs without mode collapse.

Spectral clustering achieves strong consistency in the stochastic block model under certain conditions.

Consistent spectral clustering with fairness constraints on representation graphs.

While many multiple graph inference methodologies operate under the implicit assumption that an explicit vertex correspondence is known across the vertex sets of the graphs, in practice these correspondences may only be partially or errorfully known. Herein, we provide an information theoretic foundation for understand…

This paper tackles matching two complete graphs with correlated edge weights in geometric models.

New spectral algorithm estimates random graph parameters robustly against corrupted nodes.

We consider the problem of learning from a similarity matrix (such as spectral clustering and lowd imensional embedding), when computing pairwise similarities are costly, and only a limited number of entries can be observed. We provide a theoretical analysis using standard notions of graph approximation, significantly …

Paper tackles robust graph matching in dense graphs with AMP type algorithm.

Graph curvature measured by inverse resistance distance.

Data vectors are obtained from multiple domains. They are feature vectors of images or vector representations of words. Domains may have different numbers of data vectors with different dimensions. These data vectors from multiple domains are projected to a common space by linear transformations in order to search clos…

While the harmonic function solution performs well in many semi-supervised learning (SSL) tasks, it is known to scale poorly with the number of samples. Recent successful and scalable methods, such as the eigenfunction method focus on efficiently approximating the whole spectrum of the graph Laplacian constructed from …

FAST selects coresets more efficiently by matching distributions in the frequency domain.

This paper refines understanding of decentralized learning by considering graph topology.

Improved spectral clustering via Gromov-Wasserstein Learning.

Spectral clustering is one of the most effective clustering approaches that capture hidden cluster structures in the data. However, it does not scale well to large-scale problems due to its quadratic complexity in constructing similarity graphs and computing subsequent eigendecomposition. Although a number of methods h…

New algorithm finds sparse matrices on Stiefel manifold for optimisation.

Paper extends tail bounds to high-dimensional random objects on Riemannian manifolds.

We present graph attention networks (GATs), novel neural network architectures that operate on graph-structured data, leveraging masked self-attentional layers to address the shortcomings of prior methods based on graph convolutions or their approximations. By stacking layers in which nodes are able to attend over thei…

SIGMA model improves graph matching across various applications.

Proves accuracy guarantees for self-supervised learning with correlated positive pairs.

Root Laplacian Eigenmaps help in spectral embedding of graphs.

This paper uses the relationship between graph conductance and spectral clustering to study (i) the failures of spectral clustering and (ii) the benefits of regularization. The explanation is simple. Sparse and stochastic graphs create a lot of small trees that are connected to the core of the graph by only one edge. G…

Introduces Spectral Graph Network combining spatial and spectral message passing.

Enhanced spectral clustering for geometric graphs improves clustering accuracy.

Method finds multiple noisy graph templates in large graphs.

Graph convolutional networks(GCNs) have become the most popular approaches for graph data in these days because of their powerful ability to extract features from graph. GCNs approaches are divided into two categories, spectral-based and spatial-based. As the earliest convolutional networks for graph data, spectral-bas…

Proves generic existence of spectral networks for many cases.

Laplacian Eigenvectors of the graph constructed from a data set are used in many spectral manifold learning algorithms such as diffusion maps and spectral clustering. Given a graph constructed from a random sample of a $d$-dimensional compact submanifold $M$ in $\mathbb{R}^D$, we establish the spectral convergence rate…

Paper proposes a new method for population-wise matching of sulcal graphs.

Proposes a Gaussian process for graph signals using adaptive spectral kernels.

Spectral algorithms are graph partitioning algorithms that partition a node set of a graph into groups by using a spectral embedding map. Clustering techniques based on the algorithms are referred to as spectral clustering and are widely used in data analysis. To gain a better understanding of why spectral clustering i…

Graph classification improved using spectral features and wavelet filters.

The strength of association between a pair of data vectors is represented by a nonnegative real number, called matching weight. For dimensionality reduction, we consider a linear transformation of data vectors, and define a matching error as the weighted sum of squared distances between transformed vectors with respect…

The paper bridges spectral and spatial graph convolutions, improving model capacity and transferability.

Paper revisits graph-CNNs using Laplace-Beltrami spectral filters and polynomials.

Given two graphs, the graph matching problem is to align the two vertex sets so as to minimize the number of adjacency disagreements between the two graphs. The seeded graph matching problem is the graph matching problem when we are first given a partial alignment that we are tasked with completing. In this paper, we m…

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 work, for the first time, we present a highly-scalable spectral approach (GRASPEL) for learning large…

NeuroMatch efficiently matches subgraphs in large graphs using neural networks.

Proposes methods to recover labels from shuffled networks using graph averages.

The paper defines surface area for graphs and derives spectral estimates.

Spectral clustering for directed graphs using likelihood estimation.

Novel Haar-Laplacian for directed graphs enhances spectral graph applications.