Technical Program

Paper Detail

Paper IDG.1.3
Paper Title Characterizing the Bethe Partition Function of Double-Edge Factor Graphs via Graph Covers
Authors Yuwen Huang, Pascal O Vontobel, The Chinese University of Hong Kong, China
Session G.1: Graph Analytics
Presentation Lecture
Track Graphs, Games, Sparsity, and Signal Processing
Manuscript  Click here to download the manuscript
Virtual Presentation  Click here to watch in the Virtual Symposium
Abstract For standard factor graphs (S-FGs), i.e., factor graphs with local functions taking on non-negative real values, Vontobel gave a characterization of the Bethe approximation to the partition function in terms of the partition function of finite graph covers. The proof of that statement heavily relied on the method of types. In this paper we give a similar characterization for so-called double-edge factor graphs (DE-FGs), which are a class of factor graphs where local functions take on complex values and have to satisfy some positive semi-definiteness constraints. Such factor graphs are of interest in quantum information processing. In general, approximating the partition function of DE-FGs is more challenging than for S-FGs because the partition function is a sum of complex values and not just a sum of non-negative real values. In particular, for proving the above-mentioned characterization of the Bethe approximation in terms of finite graph covers, one cannot use the method of types anymore. We overcome this challenge by applying the loop-calculus transform by Chertkov and Chernyak, along with using the symmetric-subspace transform, a novel technique for factor graphs that should be of interest beyond proving the main result of this paper. Currently, the characterization of the Bethe approximation of the partition function of DE-FGs is for DE-FGs satisfying an (easily checkable) condition. However, based on numerical results, we suspect that the characterization holds more broadly.

Plan Ahead


2021 IEEE International Symposium on Information Theory

11-16 July 2021 | Melbourne, Victoria, Australia

Visit Website!