Approximate Fr\'echet Mean for Data Sets of Sparse Graphs

• URL: http://arxiv.org/abs/2105.04062v1
• Date: Mon, 10 May 2021 01:13:25 GMT
• Title: Approximate Fr\'echet Mean for Data Sets of Sparse Graphs
• Authors: Daniel Ferguson and Fran\c{c}ois G. Meyer
• Abstract summary: In this work, we equip a set of graph with the pseudometric matrix defined by the $ell$ norm between the eigenvalues of their respective adjacency. Unlike the edit distance, this pseudometric reveals structural changes at multiple scales, and is well adapted to studying various statistical problems on sets of graphs. We describe an algorithm to compute an approximation to the Fr'echet mean of a set of undirected unweighted graphs with a fixed size.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: To characterize the location (mean, median) of a set of graphs, one needs a notion of centrality that is adapted to metric spaces, since graph sets are not Euclidean spaces. A standard approach is to consider the Fr\'echet mean. In this work, we equip a set of graph with the pseudometric defined by the $\ell_2$ norm between the eigenvalues of their respective adjacency matrix . Unlike the edit distance, this pseudometric reveals structural changes at multiple scales, and is well adapted to studying various statistical problems on sets of graphs. We describe an algorithm to compute an approximation to the Fr\'echet mean of a set of undirected unweighted graphs with a fixed size.

Related papers

• Graph GOSPA metric: a metric to measure the discrepancy between graphs of different sizes [3.8823562292981393]
  This paper proposes a metric to measure the dissimilarity between graphs that may have a different number of nodes. The proposed graph GOSPA metric includes costs associated with node attribute errors for properly assigned nodes, missed and false nodes and edge mismatches between graphs.
  arXiv  Detail & Related papers  (2023-11-10T11:40:24Z)
• Graph Fourier MMD for Signals on Graphs [67.68356461123219]
  We propose a novel distance between distributions and signals on graphs. GFMMD is defined via an optimal witness function that is both smooth on the graph and maximizes difference in expectation. We showcase it on graph benchmark datasets as well as on single cell RNA-sequencing data analysis.
  arXiv  Detail & Related papers  (2023-06-05T00:01:17Z)
• Bures-Wasserstein Means of Graphs [60.42414991820453]
  We propose a novel framework for defining a graph mean via embeddings in the space of smooth graph signal distributions. By finding a mean in this embedding space, we can recover a mean graph that preserves structural information. We establish the existence and uniqueness of the novel graph mean, and provide an iterative algorithm for computing it.
  arXiv  Detail & Related papers  (2023-05-31T11:04:53Z)
• Embedding Graphs on Grassmann Manifold [31.42901131602713]
  This paper develops a new graph representation learning scheme, namely EGG, which embeds approximated second-order graph characteristics into a Grassmann manifold. The effectiveness of EGG is demonstrated using both clustering and classification tasks at the node level and graph level.
  arXiv  Detail & Related papers  (2022-05-30T12:56:24Z)
• Graph Spectral Embedding using the Geodesic Betweeness Centrality [76.27138343125985]
  We introduce the Graph Sylvester Embedding (GSE), an unsupervised graph representation of local similarity, connectivity, and global structure. GSE uses the solution of the Sylvester equation to capture both network structure and neighborhood proximity in a single representation.
  arXiv  Detail & Related papers  (2022-05-07T04:11:23Z)
• Theoretical analysis and computation of the sample Frechet mean for sets of large graphs based on spectral information [0.0]
  We equip a set of graphs with the pseudometric defined by the norm between the eigenvalues of their respective adjacency matrix. Unlike the edit distance, this pseudometric reveals structural changes at multiple scales. We describe an algorithm to compute an approximation to the sample Frechet mean of a set of undirected unweighted graphs with a fixed size.
  arXiv  Detail & Related papers  (2022-01-15T20:53:29Z)
• Some Algorithms on Exact, Approximate and Error-Tolerant Graph Matching [3.655021726150369]
  We present an extensive survey of various exact and inexact graph matching techniques. A category of graph matching algorithms is presented, which reduces the graph size by removing the less important nodes. We introduce a novel approach to measure graph similarity using geometric graphs.
  arXiv  Detail & Related papers  (2020-12-30T18:51:06Z)
• Articulated Shape Matching Using Laplacian Eigenfunctions and Unsupervised Point Registration [38.16866987817019]
  Spectral graph theory can be used to map these graphs onto lower dimensional spaces and match shapes by aligning their embeddings. We derive a new formulation that finds the best alignment between two congruent $K$-dimensional sets of points by selecting the best subset of eigenfunctions of the Laplacian matrix.
  arXiv  Detail & Related papers  (2020-12-14T08:49:25Z)
• Line Graph Neural Networks for Link Prediction [71.00689542259052]
  We consider the graph link prediction task, which is a classic graph analytical problem with many real-world applications. In this formalism, a link prediction problem is converted to a graph classification task. We propose to seek a radically different and novel path by making use of the line graphs in graph theory. In particular, each node in a line graph corresponds to a unique edge in the original graph. Therefore, link prediction problems in the original graph can be equivalently solved as a node classification problem in its corresponding line graph, instead of a graph classification task.
  arXiv  Detail & Related papers  (2020-10-20T05:54:31Z)
• Wasserstein-based Graph Alignment [56.84964475441094]
  We cast a new formulation for the one-to-many graph alignment problem, which aims at matching a node in the smaller graph with one or more nodes in the larger graph. We show that our method leads to significant improvements with respect to the state-of-the-art algorithms for each of these tasks.
  arXiv  Detail & Related papers  (2020-03-12T22:31:59Z)
• Semiparametric Nonlinear Bipartite Graph Representation Learning with Provable Guarantees [106.91654068632882]
  We consider the bipartite graph and formalize its representation learning problem as a statistical estimation problem of parameters in a semiparametric exponential family distribution. We show that the proposed objective is strongly convex in a neighborhood around the ground truth, so that a gradient descent-based method achieves linear convergence rate. Our estimator is robust to any model misspecification within the exponential family, which is validated in extensive experiments.
  arXiv  Detail & Related papers  (2020-03-02T16:40:36Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.