Structure from Voltage
- URL: http://arxiv.org/abs/2203.00063v2
- Date: Wed, 28 Jun 2023 18:42:20 GMT
- Title: Structure from Voltage
- Authors: Robi Bhattacharjee, Alex Cloninger, Yoav Freund, Andreas Oslandsbotn
- Abstract summary: Effective resistance (ER) is an attractive way to interrogate the structure of graphs.
We show that by using scaling resistances in a graph with $n$ vertices by $n2$, one gets a meaningful limit of the voltages and of effective resistances.
We also show that by adding a "ground" node to a metric graph one gets a simple and natural way to compute all of the distances from a chosen point to all other points.
- Score: 6.212269948361801
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Effective resistance (ER) is an attractive way to interrogate the structure
of graphs. It is an alternative to computing the eigen-vectors of the graph
Laplacian. Graph laplacians are used to find low dimensional structures in high
dimensional data. Here too, ER based analysis has advantages over eign-vector
based methods. Unfortunately Von Luxburg et al. (2010) show that, when vertices
correspond to a sample from a distribution over a metric space, the limit of
the ER between distant points converges to a trivial quantity that holds no
information about the structure of the graph. We show that by using scaling
resistances in a graph with $n$ vertices by $n^2$, one gets a meaningful limit
of the voltages and of effective resistances. We also show that by adding a
"ground" node to a metric graph one gets a simple and natural way to compute
all of the distances from a chosen point to all other points.
Related papers
- Force-directed graph embedding with hops distance [5.214207581551816]
We propose a novel force-directed graph embedding method that preserves graph topology and structural features.
Our method is intuitive, parallelizable, and highly scalable.
We evaluate our method on several graph analysis tasks and show that it achieves competitive performance compared to state-of-the-art unsupervised embedding techniques.
arXiv Detail & Related papers (2023-09-11T23:08:03Z) - Effective resistance in metric spaces [65.94598202303497]
Effective resistance (ER) is an attractive way to interrogate the structure of graphs.
We show that the ER between any two points converges to a trivial quantity as the size of the sample increases to infinity.
By keeping the regions fixed, we show analytically that the region-based ER converges to a non-trivial limit as the number of points increases to infinity.
arXiv Detail & Related papers (2023-06-27T17:43:18Z) - 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) - Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
We present two new classes of algorithms for efficient field integration on graphs encoding point clouds.
The first class, SeparatorFactorization(SF), leverages the bounded genus of point cloud mesh graphs, while the second class, RFDiffusion(RFD), uses popular epsilon-nearest-neighbor graph representations for point clouds.
arXiv Detail & Related papers (2023-02-02T08:33:36Z) - Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect
Alignment [51.74913666829224]
We show that for datasets with strong inherent anti-correlations, a suitable graph contains both positive and negative edge weights.
We propose a linear-time signed graph sampling method centered on the concept of balanced signed graphs.
Experimental results show that our signed graph sampling method outperformed existing fast sampling schemes noticeably on various datasets.
arXiv Detail & Related papers (2022-08-18T09:19:01Z) - Multiscale Graph Comparison via the Embedded Laplacian Distance [6.09170287691728]
We propose the Embedded Laplacian Distance (ELD) for comparing graphs of vastly different sizes.
Our approach first projects the graphs onto a common, low-dimensional Laplacian embedding space that respects graphical structure.
A distance can then be computed efficiently via a natural sliced Wasserstein approach.
arXiv Detail & Related papers (2022-01-28T12:13:08Z) - AnchorGAE: General Data Clustering via $O(n)$ Bipartite Graph
Convolution [79.44066256794187]
We show how to convert a non-graph dataset into a graph by introducing the generative graph model, which is used to build graph convolution networks (GCNs)
A bipartite graph constructed by anchors is updated dynamically to exploit the high-level information behind data.
We theoretically prove that the simple update will lead to degeneration and a specific strategy is accordingly designed.
arXiv Detail & Related papers (2021-11-12T07:08:13Z) - Improved Reconstruction of Random Geometric Graphs [3.930410971186142]
We consider the classic model of random geometric graphs where $n$ points are scattered uniformly in a square of area $n$.
We use a hybrid of graph distances and short-range estimates based on the number of common neighbors to estimate Euclidean distances.
Our method estimates Euclidean distances using a hybrid of graph distances and short-range estimates based on the number of common neighbors.
arXiv Detail & Related papers (2021-07-29T20:37:28Z) - 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) - Learning Sparse Graph Laplacian with K Eigenvector Prior via Iterative
GLASSO and Projection [58.5350491065936]
We consider a structural assumption on the graph Laplacian matrix $L$.
The first $K$ eigenvectors of $L$ are pre-selected, e.g., based on domain-specific criteria.
We design an efficient hybrid graphical lasso/projection algorithm to compute the most suitable graph Laplacian matrix $L* in H_u+$ given $barC$.
arXiv Detail & Related papers (2020-10-25T18:12:50Z)
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.