Graph-Cover-based Characterization of the Bethe Partition Function of Double-Edge Factor Graphs

• URL: http://arxiv.org/abs/2506.16250v1
• Date: Thu, 19 Jun 2025 12:08:54 GMT
• Title: Graph-Cover-based Characterization of the Bethe Partition Function of Double-Edge Factor Graphs
• Authors: Yuwen Huang, Pascal O. Vontobel,
• Abstract summary: We study factor graphs (DE-FGs) and their partition functions.<n> Approximating the partition function of a DE-FG is more difficult than for an S-FG, as it involves summing complex values instead of non-negative real values.<n>We provide a characterization of the Bethe partition function in terms of finite graph covers for a class of DE-FGs that satisfy a specific, easily checkable condition.
• Score: 13.182797149468204
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: For standard factor graphs (S-FGs) with non-negative real-valued local functions, Vontobel provided a combinatorial characterization of the Bethe approximation of the partition function, also known as the Bethe partition function, using finite graph covers. The proof of this characterization, i.e., the graph-cover theorem for S-FGs, heavily relied on the method of types. In this paper, we study double-edge factor graphs (DE-FGs), a class of factor graphs where each local function takes complex values and satisfies some positive semi-definiteness constraints. DE-FGs and their partition functions are particularly relevant for quantum information processing. Approximating the partition function of a DE-FG is more difficult than for an S-FG, as it involves summing complex values instead of non-negative real values. We develop the sum-product algorithm (SPA) fixed-point-based Bethe approximation of the partition function. However, one cannot directly apply the method of types to prove a similar combinatorial characterization as in the case of S-FGs. We provide a combinatorial characterization of the Bethe partition function in terms of finite graph covers for a class of DE-FGs that satisfy a specific, easily checkable condition. Towards proving this characterization, we apply a suitable loop-calculus transform (LCT) to these graphs. Originally, the LCT was introduced by Chertkov and Chernyak as a special linear transform for S-FGs and later extended by Mori. Our proposed LCT is applicable for both DE-FGs and S-FGs and generalizes prior versions by handling zero-valued SPA fixed-point message components, which are common in DE-FGs. Supported by numerical results, we conjecture that this combinatorial characterization of the Bethe partition function in terms of finite graph covers holds more broadly for DE-FGs.

Related papers

• Eliminating Feature Ambiguity for Few-Shot Segmentation [95.9916573435427]
  Recent advancements in few-shot segmentation (FSS) have exploited pixel-by-pixel matching between query and support features. This paper presents a novel plug-in termed ambiguity elimination network (AENet), which can be plugged into any existing cross attention-based FSS methods.
  arXiv  Detail & Related papers  (2024-07-13T10:33:03Z)
• Learning Regularized Graphon Mean-Field Games with Unknown Graphons [155.38727464526923]
  We design reinforcement learning algorithms for Graphon Mean-Field Games (GMFGs) We aim to learn the Nash Equilibrium (NE) of the regularized GMFGs when the graphons are unknown. These algorithms are the first specifically designed for learning graphons from sampled agents.
  arXiv  Detail & Related papers  (2023-10-26T16:19:24Z)
• The G-invariant graph Laplacian [12.676094208872842]
  We consider data sets whose data points lie on a manifold that is closed under the action of a known unitary Lie group G. We construct the graph Laplacian by incorporating the distances between all the pairs of points generated by the action of G on the data set. We show that the G-GL converges to the Laplace-Beltrami operator on the data manifold, while enjoying a significantly improved convergence rate.
  arXiv  Detail & Related papers  (2023-03-29T20:07:07Z)
• Collaborative likelihood-ratio estimation over graphs [55.98760097296213]
  Graph-based Relative Unconstrained Least-squares Importance Fitting (GRULSIF) We develop this idea in a concrete non-parametric method that we call Graph-based Relative Unconstrained Least-squares Importance Fitting (GRULSIF) We derive convergence rates for our collaborative approach that highlights the role played by variables such as the number of available observations per node, the size of the graph, and how accurately the graph structure encodes the similarity between tasks.
  arXiv  Detail & Related papers  (2022-05-28T15:37:03Z)
• 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)
• Factor Graphs for Quantum Information Processing [3.04585143845864]
  We are interested in generalizing factor graphs and the relevant methods toward describing quantum systems. Two generalizations of classical graphical models are investigated, namely double-edge factor graphs (DeFGs) and quantum factor graphs (QFGs)
  arXiv  Detail & Related papers  (2022-03-23T13:44:34Z)
• Finite-Function-Encoding Quantum States [52.77024349608834]
  We introduce finite-function-encoding (FFE) states which encode arbitrary $d$-valued logic functions. We investigate some of their structural properties.
  arXiv  Detail & Related papers  (2020-12-01T13:53:23Z)
• Exponentially Weighted l_2 Regularization Strategy in Constructing Reinforced Second-order Fuzzy Rule-based Model [72.57056258027336]
  In the conventional Takagi-Sugeno-Kang (TSK)-type fuzzy models, constant or linear functions are usually utilized as the consequent parts of the fuzzy rules. We introduce an exponential weight approach inspired by the weight function theory encountered in harmonic analysis.
  arXiv  Detail & Related papers  (2020-07-02T15:42:15Z)
• Characteristic Functions on Graphs: Birds of a Feather, from Statistical Descriptors to Parametric Models [8.147652597876862]
  We introduce FEATHER, a computationally efficient algorithm to calculate a specific variant of characteristic functions. We argue that features extracted by FEATHER are useful for node level machine learning tasks. Experiments on real world large datasets show that our proposed algorithm creates high quality representations.
  arXiv  Detail & Related papers  (2020-05-16T11:47:05Z)

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.