Approximating the Log-Partition Function
- URL: http://arxiv.org/abs/2102.10196v1
- Date: Fri, 19 Feb 2021 22:57:32 GMT
- Title: Approximating the Log-Partition Function
- Authors: Romain Cosson, Devavrat Shah
- Abstract summary: We provide an approach to quantify the approximation ratio through the property of the underlying graph structure.
We provide a near lineartime variant that achieves an approximation ratio equal to the inverse of square-root of minimal effective resistance of the graph.
- Score: 16.59989033959959
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Variational approximation, such as mean-field (MF) and tree-reweighted (TRW),
provide a computationally efficient approximation of the log-partition function
for a generic graphical model. TRW provably provides an upper bound, but the
approximation ratio is generally not quantified.
As the primary contribution of this work, we provide an approach to quantify
the approximation ratio through the property of the underlying graph structure.
Specifically, we argue that (a variant of) TRW produces an estimate that is
within factor $\frac{1}{\sqrt{\kappa(G)}}$ of the true log-partition function
for any discrete pairwise graphical model over graph $G$, where $\kappa(G) \in
(0,1]$ captures how far $G$ is from tree structure with $\kappa(G) = 1$ for
trees and $2/N$ for the complete graph over $N$ vertices. As a consequence, the
approximation ratio is $1$ for trees, $\sqrt{(d+1)/2}$ for any graph with
maximum average degree $d$, and $\stackrel{\beta\to\infty}{\approx}
1+1/(2\beta)$ for graphs with girth (shortest cycle) at least $\beta \log N$.
In general, $\kappa(G)$ is the solution of a max-min problem associated with
$G$ that can be evaluated in polynomial time for any graph.
Using samples from the uniform distribution over the spanning trees of G, we
provide a near linear-time variant that achieves an approximation ratio equal
to the inverse of square-root of minimal (across edges) effective resistance of
the graph. We connect our results to the graph partition-based approximation
method and thus provide a unified perspective.
Keywords: variational inference, log-partition function, spanning tree
polytope, minimum effective resistance, min-max spanning tree, local inference
Related papers
- Graph Unfolding and Sampling for Transitory Video Summarization via Gershgorin Disc Alignment [48.137527345353625]
User-generated videos (UGVs) uploaded from mobile phones to social media sites like YouTube and TikTok are short and non-repetitive.
We summarize a transitory UGV into several discs in linear time via fast graph sampling based on Gershgorin disc alignment (GDA)
We show that our algorithm achieves comparable or better video summarization performance compared to state-of-the-art methods, at a substantially reduced complexity.
arXiv Detail & Related papers (2024-08-03T20:08:02Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
Under nonlinear measurements, most prior results are non-uniform, i.e., they hold with high probability for a fixed $mathbfx*$ rather than for all $mathbfx*$ simultaneously.
Our framework accommodates GCS with 1-bit/uniformly quantized observations and single index models as canonical examples.
We also develop a concentration inequality that produces tighter bounds for product processes whose index sets have low metric entropy.
arXiv Detail & Related papers (2023-09-25T17:54:19Z) - Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
Detection of a planted dense subgraph in a random graph is a fundamental statistical and computational problem.
We consider detecting the presence of a planted $Gr(ngamma, n-alpha)$ subhypergraph in a $Gr(n, n-beta) hypergraph.
Our results are already new in the graph case $r=2$, as we consider the subtle log-density regime where hardness based on average-case reductions is not known.
arXiv Detail & Related papers (2023-04-17T10:38:08Z) - Random graph matching at Otter's threshold via counting chandeliers [16.512416293014493]
We propose an efficient algorithm for graph matching based on similarity scores constructed from counting a certain family of weighted trees rooted at each.
This is the first graph matching algorithm that succeeds at an explicit constant correlation and applies to both sparse and dense graphs.
arXiv Detail & Related papers (2022-09-25T20:00:28Z) - 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) - Finding the KT partition of a weighted graph in near-linear time [1.572727650614088]
Kawarabayashi and Thorup gave a near-trivial time deterministic algorithm for minimum cut in a simple graph $G = (V,E)$.
We give a near-linear time randomized algorithm to find the $(1+varepsilon)$-KT partition of a weighted graph.
arXiv Detail & Related papers (2021-11-02T05:26:10Z) - Fast Graph Sampling for Short Video Summarization using Gershgorin Disc
Alignment [52.577757919003844]
We study the problem of efficiently summarizing a short video into several paragraphs, leveraging recent progress in fast graph sampling.
Experimental results show that our algorithm achieves comparable video summarization as state-of-the-art methods, at a substantially reduced complexity.
arXiv Detail & Related papers (2021-10-21T18:43:00Z) - Exact Matching of Random Graphs with Constant Correlation [2.578242050187029]
This paper deals with the problem of graph matching or network alignment for ErdHos--R'enyi graphs.
It can be viewed as a noisy average-case version of the graph isomorphism problem.
arXiv Detail & Related papers (2021-10-11T05:07:50Z) - Correlation detection in trees for partial graph alignment [3.5880535198436156]
We consider alignment of graphs, which consists in finding a mapping between the nodes of two graphs which preserves most of the edges.
Our approach is to compare local structures in the two graphs, matching two nodes if their neighborhoods are 'close enough' for correlated graphs.
This problem can be rephrased in terms of testing whether a pair of branching trees is drawn from either a product distribution, or a correlated distribution.
arXiv Detail & Related papers (2021-07-15T22:02:27Z) - Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization [59.65871549878937]
We prove that the practical single loop accelerated gradient tracking needs $O(fracgamma1-sigma_gamma)2sqrtfracLepsilon)$.
Our convergence rates improve significantly over the ones of $O(frac1epsilon5/7)$ and $O(fracLmu)5/7frac1 (1-sigma)1.5logfrac1epsilon)$.
arXiv Detail & Related papers (2021-04-06T15:34:14Z) - The Quantum Approximate Optimization Algorithm Needs to See the Whole
Graph: Worst Case Examples [6.810856082577402]
The Quantum Approximate Optimization Algorithm can be applied to search problems on graphs with a cost function that is a sum of terms corresponding to the edges.
We show that the QAOA with $(d-1)2p nA$ for any $A1$, can only achieve an approximation ratio of 1/2 for Max-Cut on bipartite random d-regular graphs for d large.
arXiv Detail & Related papers (2020-05-18T14:23:09Z)
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.