Detecting correlated trees helps align sparse graphs.
problem Detecting correlation between trees for sparse random graphs.
method MPAlign message-passing algorithm for graph alignment.
result MPAlign succeeds in polynomial time for partial alignment.
Graph alignment in two correlated random graphs refers to the task of identifying the correspondence between vertex sets of the graphs. Recent results have characterized the exact information-theoretic threshold for graph alignment in correlated Erdős-Rényi graphs. However, very little is known about the existence of e…
A novel method for comparing graphs of different sizes using Wasserstein distance.
problem Comparing non-aligned graphs of varying sizes.
method Optimal transport in graph comparison framework, solving a one-to-many assignment problem.
result Significant improvements in graph alignment and classification tasks.
Bayesian framework proves thresholds for multi-graph alignment feasibility.
problem Determining when multi-graph alignment is statistically possible.
method Developed a Bayesian estimation framework over metric spaces.
result Identified thresholds for Gaussian and sparse Erdős-Rényi models.
This paper studies aligning knowledge graphs from different sources or languages. Most existing methods train supervised methods for the alignment, which usually require a large number of aligned knowledge triplets. However, such a large number of aligned knowledge triplets may not be available or are expensive to obta…
Graph-Relational Domain Adaptation (GRDA) adapts domains based on their graph structure.
problem Uniform alignment of domains ignores topological structures.
method Uses a domain graph to encode adjacency and a novel graph discriminator.
result Empirically shows improved generalization and domain information incorporation.
Proposes a method for coarse graph alignment using sparse partial least squares.
problem Aligning graphs with community structures when there's no natural one-to-one mapping.
method Sparse partial least squares method incorporating observed graph structures and imposing sparsity.
result Demonstrates effectiveness in simulations.
Statistical-computational gap found in aligning multiple Gaussian graphs.
problem Aligning multiple Gaussian graphs with unknown signals.
method Generalized informational threshold and computational barrier analysis.
result Existence of a statistical-computational gap in multiple Gaussian graph alignment.
Study on matching nodes between graphs to preserve edges, focusing on limits and algorithms.
problem Matching nodes between graphs to preserve most edges, especially in random graphs.
method Investigates fundamental limits and designs algorithms to recover alignments in planted graphs.
result High probability guarantees on the success or failure of graph alignment algorithms.
G-CREWE efficiently aligns large networks using node embeddings and compression.
problem Efficiently aligning large networks for various applications.
method Uses node embeddings and compression to align networks at fine and coarse resolutions.
result G-CREWE achieves efficient and accurate network alignment, twice as fast as existing methods.
DHGAK aligns substructures for better graph kernel performance.
problem Limited performance of traditional graph kernels due to missing substructure similarities.
method Hierarchically aligns relational substructures in deep embedding space, assigning same feature maps in RKHS.
result DHGAK outperforms state-of-the-art graph kernels on various benchmarks.
New method separates graph structure from node attributes to recover lost signal.
problem Standard representation learning on attributed graphs merges incompatible metric spaces, leading to geometrically flawed alignment.
method Custom variational autoencoder that separates manifold learning from structural alignment.
result Transforms geometric conflict into interpretable structural descriptor, uncovering connectivity patterns and anomalies.
Researchers prove it's impossible to partially recover graph alignments in certain conditions.
problem Recovering vertex correspondence between two random graphs with correlated edges.
method Used the probabilistic method to build automorphisms between tree components of a subcritical Erdös-Rényi graph.
result Proved an impossibility result for partial recovery in the sparse regime with constant average degree and correlation.
NTKs explain GNNs' alignment for graph prediction.
problem Understanding GNNs' alignment for graph prediction.
method Analyzing NTKs and alignment in GNNs, focusing on cross-covariance.
result Optimizing alignment in GNNs optimizes graph representation.
Clustering and community detection with multiple graphs have typically focused on aligned graphs, where there is a mapping between nodes across the graphs (e.g., multi-view, multi-layer, temporal graphs). However, there are numerous application areas with multiple graphs that are only partially aligned, or even unalign…
This paper improves GNN robustness by aligning feature and adjacency matrix learning.
problem Improving robustness of graph neural networks (GNN) in noisy graph data.
method Proposes a novel regularized GSL approach that aligns feature information and graph information, incorporating sparse dimensional reduction.
result Demonstrates superior performance in noisy graph structures compared to competitive baselines.
Geometric Graph Alignment enhances IoT intrusion detection using NID data.
problem Data scarcity hinders IoT intrusion detection accuracy.
method Geometric Graph Alignment (GGA) approach to transfer knowledge between network intrusion detection and IoT intrusion detection domains.
result GGA approach boosts IoT intrusion detection performance on multiple datasets.
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…
Graph Neural Networks align with dynamic programming, improving algorithmic reasoning.
problem Demonstrate and quantify alignment between GNNs and dynamic programming.
method Category theory and abstract algebra methods to expose intricate connection.
result Showed GNNs align with dynamic programming beyond individual algorithms.
Estimates multiple networks using graphons for non-aligned graphs.
problem Estimating topology of multiple networks from nodal observations.
method Combining maximum likelihood penalty with graphon estimation schemes.
result Validated performance against competing methods in synthetic and real-world datasets.
Two semi-supervised manifold alignment methods improve cross-domain classification.
problem Aligning data from multiple sources for better analysis.
method SPUD and MASH methods using graph integration and diffusion.
result SPUD and MASH methods outperform existing methods in cross-domain classification.
New graph kernel scales well with graph size and number, achieving state-of-the-art performance.
problem Graph kernels lose structure information when representing graphs.
method Proposes a positive-definite global alignment graph kernel using random features and random graph embeddings.
result Achieves quasi-linear scalability with respect to graph size and number.
Can neural networks learn to compare graphs without feature engineering? In this paper, we show that it is possible to learn representations for graph similarity with neither domain knowledge nor supervision (i.e.\ feature engineering or labeled graphs). We propose Deep Divergence Graph Kernels, an unsupervised method …
Proposes methods to recover labels from shuffled networks using graph averages.
problem Recovering labels from a shuffled network using graph averages.
method Cluster networks into classes, then match the new graph to cluster-averages, minimizing the graph matching objective function.
result Higher fidelity matching performance when clustering networks into different classes.
We present a novel framework based on optimal transport for the challenging problem of comparing graphs. Specifically, we exploit the probabilistic distribution of smooth graph signals defined with respect to the graph topology. This allows us to derive an explicit expression of the Wasserstein distance between graph s…
We show that the classification performance of graph convolutional networks (GCNs) is related to the alignment between features, graph, and ground truth, which we quantify using a subspace alignment measure (SAM) corresponding to the Frobenius norm of the matrix of pairwise chordal distances between three subspaces ass…
Paper analyzes Birkhoff relaxation for graph alignment, providing theoretical guarantees.
problem Finding vertex correspondence between two graphs to maximize edge overlap.
method Birkhoff relaxation as a convex relaxation of the quadratic assignment problem (QAP).
result Theoretical guarantees on the performance of Birkhoff relaxation under specific conditions.
In this paper, we develop a novel Backtrackless Aligned-Spatial Graph Convolutional Network (BASGCN) model to learn effective features for graph classification. Our idea is to transform arbitrary-sized graphs into fixed-sized backtrackless aligned grid structures and define a new spatial graph convolution operation ass…
Paper introduces a new metric to select optimal Graph Shift Operator for GNNs.
problem Empirical selection of Graph Shift Operator remains challenging.
method Introduces a novel alignment gain metric connecting geometric distortion to generalization bounds via spectral proxy.
result Provides a principled, computation-efficient criterion to rank and select optimal GSO.
Novel framework for efficient entity alignment labeling.
problem Efficient labeling of entity alignments in knowledge graphs.
method Active and passive learning strategies to select informative instances.
result Passive learning achieves comparable performance to active learning.
Study benchmarks embedding-based entity alignment methods for KGs.
problem Align entities across different KGs using embeddings.
method Survey and categorize 23 embedding-based methods, propose new KG sampling algorithm, develop open-source library.
result Understood strengths and limitations of embedding-based methods.
Improved graph matching algorithm robust to noise.
problem Finding a bijection between vertex sets of two graphs.
method Uses multistage signature vectors to match vertices.
result Recover matching exactly with high probability for α ≤ 1 / ( log log n ) C α\le 1 / (\log \log n)^C α ≤ 1/ ( log log n ) C . Partial recovery of node mappings between correlated graphs is possible under specific conditions.
problem Recovering a one-to-one mapping between nodes of two correlated graphs with a fraction of correct matches.
method Analyzing the graph isomorphism problem as a noisy version, considering Erdős-Rényi graphs, and providing conditions for partial recovery.
result Necessary and sufficient conditions for partial recovery of node mappings in correlated graphs are given.
A fast metric learning framework using Gershgorin disc alignment.
problem Learning effective metrics for graph-based data.
method Fast projection-free metric learning via Gershgorin disc alignment.
result Efficiently computed graph metric matrices outperform competing methods.
Sharp threshold found for aligning Gaussian-weighted graphs.
problem Reconstructing planted permutations in Gaussian-weighted graphs.
method Analysis of MAP estimator and second moment method.
result Sharp information-theoretic threshold for exact recovery.
An efficient algorithm for aligning diffusion trees to networks with information asymmetry.
problem Aligning diffusion trees to networks with information asymmetry.
method Tree correlation tests for extracting alignment information.
result Explicit lower bounds on the probability of correct matches for each vertex on the diffusion tree.
Paper studies vertex correspondence recovery in correlated graphs with node features.
problem Recovering hidden vertex correspondence between two correlated graphs with observed edge weights and node features.
method Introduced featured correlated Gaussian Wigner model and proposed QPAlign algorithm for quadratic programming relaxation.
result Characterized optimal information-theoretic thresholds for exact and partial recovery of latent mapping.
A new method for aligning datasets without known correspondences.
problem Aligning datasets from different domains without labeled correspondences.
method Integrates MDS and Wasserstein Procrustes for joint optimization of embeddings and correspondences.
result Maps datasets to a common low-dimensional space without labeled correspondences.
In this paper, we develop a new aligned vertex convolutional network model to learn multi-scale local-level vertex features for graph classification. Our idea is to transform the graphs of arbitrary sizes into fixed-sized aligned vertex grid structures, and define a new vertex convolution operation by adopting a set of…
The paper explores statistical limits for detecting correlation in tree structures.
problem Detecting correlation between two tree structures.
method Investigates conditions for existence of one-sided tests in the limit of large tree depth.
result Identifies a phase transition at correlation parameter s = α s = \sqrt{α} s = α , where tests exist for s > α s > \sqrt{α} s > α . New method for matching bipartite and unipartite graphs without collapsing.
problem Matching between bipartite and unipartite networks without losing information.
method Formulated as an undirected graphical model, aligns graphs without collapsing.
result Consistent method with conditions for exact recovery of matching solution.
New method for finding function correspondences in binary programs.
problem Finding a correspondence between functions of two binary programs.
method Formulated as a network alignment problem and solved using belief propagation.
result QBinDiff prototype outperforms state-of-the-art diffing tools.
Robust GW distance improves graph data alignment.
problem Outliers in GW distance lead to inaccurate comparisons.
method Optimistically perturbed marginal constraints within a Kullback-Leibler divergence-based ambiguity set.
result RGW reduces inaccuracies in graph data alignment.
GCN model fails to match KG entities as expected.
problem Entity alignment in Knowledge Graphs using GCN.
method Used Graph Convolutional Network (GCN) for entity alignment in KGs.
result Implementation of GCN model differs from original paper, requiring additional tricks.
A new metric learning framework for signed graphs using Gershgorin disc alignment.
problem Learning Mahalanobis metrics from signed graphs efficiently.
method Proposes a fast metric learning framework using Gershgorin disc perfect alignment (GDPA) to circumvent full eigen-decomposition.
result Proves that Gershgorin disc left-ends of similarity transform are perfectly aligned at the smallest eigenvalue, enabling efficient optimization.
Rewiring GNNs to optimize community and feature alignment improves their performance.
problem Improving GNNs' performance by addressing over-squashing and generalization issues.
method Three rewiring strategies: ComMa, FeaSt, and ComFy, targeting community structure, node labels, and their alignment.
result Rewiring strategies enhance GNNs' performance by optimizing label-community alignment.
Graph alignment problem solved with convex relaxations for correlated matrices.
problem Recovering hidden vertex permutations from correlated Gaussian matrices.
method Convex relaxations of the quadratic assignment problem over doubly stochastic matrices.
result The solution of the convex relaxation concentrates around the ground-truth permutation matrix for certain correlation parameters.
GraphQ system uses GNNs to search for subgraph patterns in graphs.
problem Efficiently identifying and matching subgraph patterns in graph data.
method Graph neural networks (GNNs) for encoding graph data and NeuroAlign for node alignment.
result NeuroAlign improves node-alignment accuracy by 19-29% compared to baseline GNNs.