$v_{i}(i=1,\cdots,|S|)$ represent the $i$-th amino acid in the sequence. Let
$\mathcal{E}_{s}$ and $\mathcal{E}_{e}$ denote sequence hyperedge and spatial
hyperedge, respectively. Then, we design an edge-dependent vertex-weight
matrix $\mathbf{Q}$ for capturing the more granular high-order relationships
of proteins below (actually, our models H-GCN and H-SSGC allow one to design a
more comprehensive $\mathbf{Q}$ for learning proteins better):

$\displaystyle Q(v,e)=\left\\{\begin{array}[]{cl}1,&\text{if }v\in
e\operatorname{and}e\in\mathcal{E}_{s}\\\
\operatorname{exp}(\frac{-d(v,v_{c})}{\gamma\hat{d}_{v_{c}}^{2}}),&\text{if
}v\in e\operatorname{and}e\in\mathcal{E}_{e}\\\
0,&\text{otherwise}\end{array}\right.$ (49)

where $d(v,v_{c})<\epsilon$ is the euclidean distance between an amino acid
$v$ and the centroid amino acid $v_{c}$ in the hyperedge and $\hat{d}_{v_{c}}$
is the average distance between $v_{c}$ and the other amino acids
$\\{v_{i}\\}_{i\neq c}$. $\gamma$ is a hyper-parameter to control the
flatness. Here we just design an edge-dependent vertex-weights matrix
$\mathbf{Q}$ for satisfying the condition (2) in Thm. 2.4 (i.e.
$\mathbf{Q}_{1}=\mathbf{Q}_{2}=\mathbf{Q}$). Note that this $\mathbf{Q}$
matrix pays more attention to the information of the sequence.

##### Experimental settings

In our experiment, we set $\tau=6$ and $\epsilon=8\mathring{A}$. The initial
node features, following Baldassarre et al. (2020), are composed of amino acid
types and 3D spatial features including dihedral angles, surface accessibility
and secondary structure type generated by DSSP (Kabsch & Sander, 1983). Note
that both Quality Assessment and Fold Classification include graph-level
tasks, which means we should add global pooling layers to readout the node
representations from H-GNNs.

Here, for the sake of simplicity, we adopt the permutation-invariant operator
mean pooling and a single layer MLP as Readout layers to obtain a global
hypergraph embedding and add the softmax (classification) or sigmoid
(regression) activation function before output.

####  F.5.1 Protein Fold Classification

##### Datasets and settings

The dataset that we used for training, validation and test is SCOPe 1.75 data
set of Hou et al. (2018). This dataset includes 16,712 proteins covering 7
structural classes with total of 1195 folds. The 3D structures of proteins are
obtained from SCOpe 1.75 database (Murzin et al., 1995), in which each protein
save in a PDB file. The datasets have three test sets: 1) Fold, where proteins
from the same superfamily do not appear in the training set; 2) Family, in
which proteins from the same family are not present in the training set; 3)
Family, where proteins from the same family that are present in the training
set.

For baselines, we include sequence-based methods pre-trained unsupervised on
millions of protein sequences: Rao et al. (2019); Bepler & Berger (2018);
Strodthoff et al. (2020), 3D structure based model: Kipf & Welling (2017b);
Diehl (2019); Baldassarre et al. (2020) and Gligorijevic et al. (2020), who
process the sequence with LSTM first and then apply GCNN. The accuracy of the
above baselines is reused from Hermosilla et al. (2021) reported. We adopt
Adam optimizer to minimize the cross-entropy loss of our methods. Hyper-
parameters search range can see Table 5.

Table 11: Comparison of our method to others on protein Quality Assessment
tasks. At the residue level, We report Pearson correlation across all residues
of all decoys of all targets ($R$) and Pearson correlation all residues of per
decoys and then average all decoys ($R_{decoy}$) with LDDT scores. At the
global level, we report Pearson correlation across all decoys of all targets
($R$) and Pearson correlation per target and then average over all targets
($R_{target}$) with GDT$\\_$TS scores.

Test set | Methods | GDT$\\_$TS | LDDT
---|---|---|---
$R$ | $R_{target}$ | $R$ | $R_{model}$
CASP13 | HGNN | 0.714 | 0.622 | 0.651 | 0.337
H-GCN (ours) | 0.718 | 0.620 | 0.657 | 0.352
H-SSGC (ours) | 0.628 | 0.565 | 0.654 | 0.435
CASP12 | VoroMQA | - | 0.557 | - | -
RWplus | - | 0.313 | - | -
3D CNN | - | 0.607 | - | -
AngularQA | 0.651 | 0.439 | - | -
HGNN | 0.667 | 0.582 | 0.632 | 0.319
H-GCN (ours) | 0.737 | 0.609 | 0.656 | 0.340
H-SSGC (ours) | 0.760 | 0.554 | 0.678 | 0.449

####  F.5.2 Protein Quality Assessment (QA).

We add this additional experiments for providing a new tasks to evaluate the
hypergraph algorithms and verfy our framework can be used for Protein QA
tasks.

Protein QA is used to estimate the quality of computational protein models in
terms of divergence from their native structure. It is a regression task
aiming to predict how close the decoys to the unknown, native structure.

Inspired by Baldassarre et al. (2020), we train our models on Global Distance
Test Score (Zemla, 2003), which is the global-level score, and the Local
Distance Difference Test (Mariani et al., 2013), an amino-acids-level score.
The loss function of QA is defined as the Mean Squared Error (MSE) losses:

$\displaystyle\mathcal{L}_{g}=MSE(\mathcal{P}_{pred}^{g}-\operatorname{GDT\\_TS})\qquad\mathcal{L}_{l}=\sum_{i=1}^{|S|}MSE(\mathcal{P}_{pred_{i}}^{l}-\operatorname{LDDT}_{i})$
(50)

where $\mathcal{P}^{g}_{pred}$ and $\mathcal{P}^{l}_{pred}$ denote predicted
score of global and local respectively.

Table 12: summary of CASP datasets

Dataset | Targets | Decoys | Usage
---|---|---|---
CASP 10 | 103 | 26254 | Train
CASP 11 | 85 | 12563 | Train
CASP 12 | 40 | 6924 | Test
CASP 13 | 82 | 12336 | Train

##### Dataset and settings

We use the data from past years’ editions of CASP, including CASP10-13. We
randomly split the CASP10, CASP11, CASP13 for training and validation, with
ratio training: validation = 9:1. CASP 12 is set aside for testing against
other methods. More details about the datasets can be found in Table 12. For
the baseline, we compare our methods with other start-of-the-art methods,
including random walk-based methods : RWplus (Zhang & Zhang, 2010), sequence-
based methods: AngularQA (Conover et al., 2019), and 3D structrue-based
methods: VOroMQA (Olechnovivc & Venclovas, 2017), 3DCNN (Derevyanko et al.,
2018). The results of these baselines we reused from Baldassarre et al. (2020)
reports. Another baseline HGNN (Feng et al., 2019) is reproduced by us with
same training strategy as our methods.

Because our hypergraph based methods can jointly learn node and graph
embeddings, the losses in Eq. Eq. (50) can be weighted as
$\mathcal{L}_{total}=\mu\mathcal{L}_{l}+(1-\mu)\mathcal{L}_{g}$ and co-
optimized by Adam Optimizer with $L_{2}$ regularization, where $\mu=0.5$ in
our experiment. We use grid search to select hyper-parameters and more details
can be found in Table 6.

In addition, we use CASP10-12 for training and valuation, CASP 13 for testing
to further evaluate the efficiency of our methods (the range of hyper-
parameters can see Table 7), and the results are shown in Table 11.

##### Results of Protein QA.

Table 11 shows that our methods outperform most of SOTAs, which demonstrates
our methods can learn protein more efficiently. The outstanding performance of
H-SSGC indicates that it is able to jointly learn better the node and graph
level representation. But H-SSGC trained to predict only global scores obtains
$R=$ 0.712, which suggests that the local information can help the assessment
of the global quality.

###  F.6 Over-Smoothing Analysis.

Table 13 reveal that HyperGCN, HGNN and our H-GCN all suffer from severe over-
smoothing issue, limiting the power of neural network to capture high-order
relationships.

The results show that H-SSGC and H-GCN inherits the properties of SSGC Zhu &
Koniusz (2021) and GCN Kipf & Welling (2017b) when the model layers are deep.
H-GCN suffer from over-smoothing issue while H-SSGC significantly alleviates
the performance descending with the increase of layers. Given the same layers,
it can be observed that our H-SSGC almost outperforms the other methods for
all cases, especially at a deep layer, which demonstrates the benefits of deep
model and the long-range information around hypergraph. Furthermore, It should
be noted that the optimal layer numbers $K$ of our H-SSGC are generally larger
than other models, due to the only one linear layer avoids the over-fitting
problem.

Table 13: Summary of classification accuracy (%) results with various depths.
In our H-SSGC, the number of layers is equivalent to $K$ in (16). We report
mean test accuracy over 10 train-test splits.

Dataset |  Method | Layers
---|---|---
2 |  4 |  8 |  16 |  32 |  64
Cora (co-authorship) |  HyperGCN |  60.66 |  57.50 |  31.09 |  31.10 |  30.09 |  31.09
HGNN |  69.23 |  67.23 |  60.17 |  29.28 |  27.15 |  26.62
H-GCN (ours) |  74.79 |  72.86 |  63.99 |  31.03 |  30.46 |  31.09
H-SSGC (ours) |  74.60 |  75.78 |  75.70 |  75.04 |  75.26 |  74.79
DBLP (co-authorship) |  HyperGCN |  84.82 |  54.65 |  22.37 |  23.96 |  23.04 |  24.13
HGNN |  88.55 |  88.28 |  85.38 |  27.64 |  27.62 |  27.56
H-GCN (ours) |  89.04 |  88.90 |  85.15 |  27.61 |  27.61 |  27.62
H-SSGC (ours) |  86.63 |  88.26 |  89.00 |  89.17 |  89.05 |  88.60
Cora (co-citation) |  HyperGCN |  62.35 |  58.29 |  31.09 |  31.17 |  31.09 |  29.68
HGNN |  55.60 |  55.72 |  42.10 |  26.16 |  24.40 |  24.43
H-GCN (ours) |  69.03 |  69.45 |  57.37 |  28.21 |  26.27 |  26.95
H-SSGC (ours) |  62.21 |  64.57 |  67.59 |  68.96 |  69.37 |  68.15
Pubmed (co-citation) |  HyperGCN |  68.12 |  63.59 |  39.99 |  39.97 |  40.01 |  40.02
HGNN |  46.41 |  47.16 |  40.93 |  40.24 |  40.30 |  40.29
H-GCN (ours) |  75.37 |  74.76 |  60.65 |  40.38 |  40.31 |  40.42
H-SSGC (ours) |  74.39 |  74.91 |  74.41 |  73.90 |  72.79 |  71.49
Citeseer (co-citation) |  HyperGCN |  56.94 |  36.75 |  20.72 |  20.41 |  20.16 |  18.95
HGNN |  39.93 |  38.98 |  36.67 |  19.91 |  19.86 |  19.79
H-GCN (ours) |  62.67 |  61.50 |  49.94 |  21.95 |  21.84 |  21.93
H-SSGC (ours) |  61.63 |  62.75 |  63.86 |  64.62 |  65.14 |  65.10

###  F.7 Ablation Analysis

Table 14: Test accuracy (%) and standard deviation for 10 random seeds. w/o
$\mathbf{Q}$ represents replacing EDVWs $\mathbf{Q}$ with EIVWs $\mathbf{H}$.
(p-value is gained by the t-test)

Methods |  | NTU | ModelNet40
---|---|---|---
H-GCN | w/o $\mathbf{Q}$ | 84.93$\pm$0.31 | 97.18$\pm$0.20
w/ $\mathbf{Q}$ | 85.15$\pm$0.34$\uparrow_{0.78}$ | 97.28$\pm$0.15$\uparrow_{0.1}$
p-value | 0.0739 | 0.1110
H-SSGC | w/o $\mathbf{Q}$ | 83.03$\pm$0.30 | 96.82$\pm$0.10
w/ $\mathbf{Q}$ | 84.13$\pm$0.29$\uparrow_{1.1}$ | 96.94$\pm$0.06$\uparrow_{0.12}$
p-value | 5.63e-8 | 0.0015
H-GCNII | w/o $\mathbf{Q}$ | 85.04$\pm$0.29 | 97.62$\pm$0.07
w/ $\mathbf{Q}$ | 85.17$\pm$0.36$\uparrow_{0.13}$ | 97.75$\pm$0.07$\uparrow_{0.13}$
p-value | 0.1928 | 0.0003

Effect of EDVWs. We conduct an ablation study to verify that our framework is
expert in EDVW-hypergraph learning. The results in Tabel 14 indicate that our
methods can make use of the EDVWs to achieve better performance. Meanwhile,
’w/ $\mathbf{Q}$’ outperforms ’w/o $\mathbf{Q}$’ significantly, indicating
that our H-GNNs models successfully mine the information in the vertex
weights.

Table 15: classification accuracy $\pm$ standard deviation) with different
$\rho(x)$ used in Eq. (5). ($\phi(x)$ is Gaussian PDF.)

Dataset | Methods | Random | $x^{-1}$ | $x^{0}$ | $x^{1}$ | $\operatorname{sigmoid}(x)$ | $\phi(x)$ | $\log(x)$ | $\exp(x)$ | $\exp(-x)$
---|---|---|---|---|---|---|---|---|---|---
coauthorship/cora | H-APPNP | 75.21$\pm$0.6 | 76.38$\pm$0.8 | 75.51$\pm$1.0 | 75.06$\pm$0.9 | 75.49$\pm$1.0 | 75.78$\pm$0.6 | 75.18$\pm$0.9 | 74.16$\pm$0.8 | 64.6$\pm$1.4
cocitation/pubmed | H-APPNP | 75.43$\pm$1.0 | 75.31$\pm$1.1 | 75.46$\pm$1.0 | 75.29$\pm$1.2 | 75.45$\pm$1.0 | 75.47$\pm$1.1 | 75.40$\pm$1.1 | 74.44$\pm$1.4 | 73.54$\pm$1.3
coauthorship/cora | H-GCNII | 75.68$\pm$0.8 | 76.21$\pm$1.0 | 75.57$\pm$0.8 | 75.39$\pm$0.8 | 75.64$\pm$1.0 | 76.15$\pm$0.9 | 75.29$\pm$0.8 | 74.64$\pm$0.9 | 65.47$\pm$1.0
cocitation/pubmed | H-GCNII | 75.50$\pm$1.2 | 75.79$\pm$1.1 | 75.74$\pm$1.3 | 74.85$\pm$1.4 | 75.61$\pm$1.4 | 74.64$\pm$0.9 | 75.39$\pm$1.3 | 73.62$\pm$1.9 | 74.68$\pm$1.2

Effect of Different $\rho$. We investigate the performance of the proposed
method with different $\rho$ on citation datasets. As illustrated in Table 15,
H-GNNs have different performances under various $\rho$, indicating the $\rho$
can influence the performance of neural networks by the random walk.
Meanwhile, the $x^{-1}$ achieves a satisfactory performance. This can be
explained as follows. In co-authorship graphs, papers with a larger number of
co-authors are often the result of collaborations between researchers from
various fields, and therefore will not be as predictive as papers with fewer
authors. The co-citation graph enjoys a similar explanation.

##### Effect of Re-normalization Trick.

In order to verify the effectiveness of our proposed edge-dependent vertex
weight $\mathbf{Q}$ and the necessity of re-normalization trick, we conduct an
ablation analysis and report the results in Table 16. Specially, w/o
$\mathbf{Q}$ is a variant of our methods that replaces the edge-dependent
vertex weight $\mathbf{Q}$ with the edge-independent vertex weight matrix
$\mathbf{H}$. w/o renormalization represents the variants without re-
normalization trick. Form the reported results we can learn that both
$\mathbf{Q}$ and renormalization are efficient for hypergpraph learning,
respectively. Moreover, on Cora and Pubmed, the performance gap between w/o
renormalization and with both H-GCN reveals the advantage of renormalization
on disconnected hypergraph dataset. This phenomenon is mainly caused by the
row in the adjacent matrix corresponding to an isolated point is 0 (Figure 4),
resulting in a direct loss of its vertex information (Figure 4). And the
renormalization trick adding the self-loop to matrix $\mathbf{K}$ can maintain
the features of isolated vertices during aggregation. Compared with H-GCN, the
performance impact of renormalization on H-SSGC seems to be smaller. This is
because we add initial features to the information gathered by the neighbors,
which reduces the information loss of isolated vertices.

Table 16: Test accuracy (%) of our methods for ablation analysis. We report
mean $\pm$standard deviation. Cora and Pubmed are the datasets that do not
contain $\mathbf{Q}$, so we just report the w/o renormalization results. NTU
and ModelNet40 constructed by Feng et al. (2019) are both connected hypergraph
networks in this work.

methods | - | Cora (co-authorship) | Pubmed (co-citation) | NTU | ModelNet40
---|---|---|---|---|---
H-GCN | with both | 74.79$\pm$0.91 | 75.37$\pm$1.2 | 85.15$\pm$0.34 | 97.28$\pm$0.15
w/o $\mathbf{Q}$ | - | - | 84.93$\pm$0.31 | 97.18$\pm$0.20
w/o renormalization | 69.23$\pm$1.6 | 46.41$\pm$0.70 | 84.85$\pm$0.30 | 97.20$\pm$0.15
w/o both | - | - | 84.21$\pm$0.25 | 97.15$\pm$0.14
H-SSGC | with both | 75.91$\pm$0.75 | 74.60$\pm$1.4 | 83.35$\pm$0.30 | 97.74$\pm$0.05
w/o $\mathbf{Q}$ | - | - | 82.84$\pm$0.40 | 97.65$\pm$0.08
w/o renormalization | 75.76$\pm$0.69 | 73.83$\pm$2.1 | 82.92$\pm$0.47 | 97.74$\pm$0.05
w/o both | - | - | 82.55$\pm$0.46 | 97.69$\pm$0.07

###  F.8 Running Time and Computational Complexity

The H-GNNs has same theoretical computational complexity as the undigraph NNs.
For example, the computational cost of H-GCN is$\mathcal{O}(|E|d)$, where
$|E|$ is the total edge count in equivalent undigraph. Each sparse matrix
multiplication $\tilde{\mathbf{T}}\mathbf{X}$ costs $|E|d$. And the
computational of HGNN is the same as H-GCN.

Then, we compare the running time of our H-GNNs with existing models in Table
17 and the results illustrate that our methods are of the same order of
magnitude as SOTA’s approach UniGNN and outperform the HyperGCN and HGAT.

Table 17: The average training time per epoch with different methods on
citation network classification task is shown below and timings are measured
in seconds. The float in parentheses is the standard deviation.

Methods | cora coauthorship | dblp coauthorship | cora cocitation | pubmed cocitation | citeseer cocitation
---|---|---|---|---|---
HyperGCN | 0.150$\pm$0.058 | 1.181$\pm$0.071 | 0.151$\pm$0.029 | 1.203$\pm$0.104 | 0.130$\pm$0.029
HGNN | 0.005$\pm$0.002 | 0.081$\pm$0.006 | 0.005$\pm$0.040 | 0.008$\pm$0.002 | 0.005$\pm$0.002
UniGNN | 0.014$\pm$0.044 | 0.042$\pm$0.040 | 0.014$\pm$0.042 | 0.023$\pm$0.043 | 0.0168$\pm$0.043
HNHN | 0.001$\pm$0.0026 | 0.007$\pm$0.014 | 0.0010$\pm$0.004 | 0.009$\pm$0.006 | 0.001$\pm$0.003
HGAT | 0.381$\pm$0.080 | OOM | 0.279$\pm$0.083 | 1.329$\pm$0.016 | 0.286$\pm$0.087
H-ChebNet | 0.027$\pm$0.005 | 0.063$\pm$0.001 | 0.073$\pm$0.008 | 0.050$\pm$0.019 | 0.067$\pm$0.0198
H-SSGC | 0.055$\pm$0.001 | 0.291$\pm$0.001 | 0.205$\pm$0.003 | 0.135$\pm$0.056 | 0.193$\pm$0.057
H-GCN | 0.005$\pm$0.036 | 0.020$\pm$0.079 | 0.005$\pm$0.039 | 0.011$\pm$0.075 | 0.081$\pm$0.091
H-APPNP | 0.147$\pm$0.013 | 1.017$\pm$0.080 | 0.033$\pm$0.006 | 0.319$\pm$0.037 | 0.123$\pm$0.011
H-GCNII | 0.141$\pm$0.01 | 0.252$\pm$0.017 | 0.135$\pm$0.013 | 0.121$\pm$0.014 | 0.079$\pm$0.004

###  F.9 Comparison between edge-dependent vertex weights and hypergraph
attention

The node-level and edge-level attention in HGAT Ding et al. (2020) can be
considered as the learnable EDVWs. we visualize EDVWs in Figure 6.

####  F.9.1 Visual Object.

Figure 6: The edge-dependent vertex weights of NTU2012 dataset (MVCNN feature
+ MVCNN structure). The figure on the left represents the distance-based
vertex weights matrix $\mathbf{Q}~{}$ used in H-GCN. The middle
($\mathbf{Q}_{1}$ ) and right ($\mathbf{Q}_{2}$) denote the node-level and
edge-level attention coefficient matrix of HGAT (Ding et al., 2020),
respectively.


# Estimation of function’s supports under arithmetic constraints

Norbert Hegyvári  Norbert Hegyvári, ELTE TTK, Eötvös University, Institute of
Mathematics, H-1117 Pázmány st. 1/c, Budapest, Hungary and Alfréd Rényi
Institute of Mathematics, Hungarian Academy of Science, H-1364 Budapest,
P.O.Box 127<EMAIL_ADDRESS>
###### Abstract.

The well-known $|supp(f)||supp(\widehat{f}|\geq|G|$ inequality gives lower
estimation of each supports. In the present paper we give upper estimation
under arithmetic constrains. The main notion will be the additive energy which
plays a central role in additive combinatorics. We prove an uncertainty
inequality that shows a trade-off between the total changes of the indicator
function of a subset $A\subseteq\mathbb{F}^{n}_{2}$ and the additive energy of
$A$ and the Fourier spectrum.

MSC 2020:11B75, 06E30, 11L99

Keywords: Additive Combinatorics, Boolean functions, Fourier analysis,

##  1\. Introduction

A classical uncertainty principle says that

(1) $|supp(f)||supp(\widehat{f}|\geq|G|,$

where $G$ is a finite abelian group, $f$ acts on $G$ and $\widehat{f}$ is the
Fourier transform of $f$. Roughly speaking if $|supp(f)|$ is ”small’, then
$|supp(\widehat{f}|$ should be ”big” and vice versa. In fact (1) gives a
quantitative lower bound for the other support too. But if one of the supports
is ”medium” size, it does not follow that the other support is ”medium” size.

We can ask whether is there any other relation between the two supports? For
example, is there a slowly increasing function $F$ for which $|supp(f)|\leq
F(|supp(\widehat{f}|)$? Certainly (1) shows that we should not expect such a
relationship in general. However, one might expect that if we assume some
structure on $supp(f)$, we might expect to get such a relation. The aim of
this note is to provide such an estimation. The two links that help us come
from additive combinatorics and theoretical computer science. (see section 2
and 3).

In the present paper $G$ will be $\mathbb{F}^{n}_{2}$, where $\mathbb{F}_{2}$
is the finite field with $2$ elements. Let $A\subseteq\mathbb{F}^{n}_{2}$. Let
$f$ be the indicator of $A$, i.e. let

$f(x)=\left\\{\begin{array}[]{lr}1&x\in A\\\ 0&x\notin A\end{array}\right.,$

so $A=supp(f)$ is the support of $f$ and this type of function is said to be
Boolean, since it maps from $\\{0,1\\}^{n}$ to $\\{0,1\\}$.

There are many other interesting uncertainty inequalities; we mention just
two: the Heisenberg uncertainty principle for conjugate variables in quantum
mechanics and a useful inequality in prime fields; if
$f:\mathbb{Z}_{p}\mapsto\mathbb{Z}_{p}$, then
$|\operatorname{supp}f|+|\operatorname{supp}\widehat{f}|\geq p$, where $p$ is
the characteristic of the prime field.

In the last decades there are several interplay between complexity theory and
additive combinatorics. One of the most interesting example is connection
between notions in computer sciences and the Gowers norm (see e.g. [3, 6]).
Another interesting example is an additive communication complexity problem
which is supported by an example of Behrend on the maximal density of a set
not containing three-term arithmetic progression (see e.g. [2]).

##  2\. Preliminaries, Notations

The first concept we will discuss comes from additive combinatorics. Let
$\mathbb{F}^{n}_{2}$ be the $n-$dimensional vector space with characteristic
$2$. For a set $A\subseteq\mathbb{F}^{n}_{2}$, the additive energy of $A$ is
defined as the number of quadruples $(a_{1},a_{2},a_{3},a_{4})$ for which
$a_{1}+a_{2}=a_{3}+a_{4}$, formally $E(A):=|\\{(a_{1},a_{2},a_{3},a_{4})\in
A^{4}:\ a_{1}+a_{2}=a_{3}+a_{4}\\}|$. Clearly $|A|^{2}\ll E(A)\ll|A|^{3}$
holds, since the quadruple $(a_{1},a_{2},a_{1},a_{2})$ is always a solution
and given $a_{1},a_{2},a_{3}$ the term $a_{4}$ is uniquely determined by them.
(We will use the notation $|X|\ll|Y|$ to denote the estimate $|X|\leq C|Y|$
for some absolute constant $C>0$). This concept was introduced by Terence Tao,
and plays a central role in additive combinatorics. (See, e.g., [4, 5].)

Let $f:\\{0,1\\}^{n}\to\\{0,1\\}$ and $g:\\{0,1\\}^{n}\to\\{0,1\\}$ be two
functions. The expected value of $f$ is

$\mathbb{E}(f):=\frac{1}{2^{n}}\sum_{x\in\\{0,1\\}^{n}}f(x),$

and the inner product of $f$ and $g$ is $\langle f,g\rangle:=\mathbb{E}(fg)$.
For $S\subseteq[n]$ the corresponding vector is
$x=(x_{1},x_{2},\dots,x_{n})\in\\{0,1\\}^{n}$ namely $x_{i}=1$ if $i\in S$ and
$x_{i}=0$ otherwise. A basis function or character is defined by
$\chi_{x}(y):=(-1)^{\langle x,y\rangle_{2}}$, where $\langle
x,y\rangle_{2}:=\sum_{i=1}^{n}x_{i}y_{i}\pmod{2}$.

For functions $f$ and $g$ their convolution is defined by $f\ast
g(x):=\mathbb{E}f(y)g(x+y)$. It is easy to verify that the convolution is
associative: $f\ast(g\ast h)=(f\ast g)\ast h$.

For a set $S\subseteq[n]$ ($[n]:=\\{1,2,\dots,n\\}$), the Fourier transform of
$f$ is $\widehat{f}(S)=\langle f,\chi_{S}\rangle$.

For the Fourier transform the following are true:

$(i)\ \langle f,g\rangle=\sum_{r\in\\{0,1\\}^{n}}\widehat{f}(r)\widehat{g}(r)\
\text{(Plancherel)}$ $(ii)\ \|f\|_{2}^{2}=\mathbb{E}(f^{2})=\langle
f,f\rangle=\sum_{r\in\\{0,1\\}^{n}}\widehat{f}^{2}(r)\ \text{(Parseval)}$

So by the Parseval formula for the indicator function we have

(2) $\sum_{r\in\\{0,1\\}^{n}}\widehat{A}^{2}(r)=\frac{1}{2^{n}}|A|$

.

The second link comes from computer science. The influence $Inf_{i}(f)$ of the
$i^{th}$ variable on a Boolean function $f$ is the probability
$\operatorname{Inf}_{i}(f)=\Pr_{x\in\\{0,1\\}^{n}}[f(x)\neq f(x+e_{i})]$,
where $x$ is uniformly distributed over $\\{0,1\\}^{n}$, and $f(x+e_{i})$
means that we change the $i^{th}$ coordinate of $x$ to the opposite, (i.e. 0
to 1 or 1 to 0). The total influence of $f$ is defined to be
$I(f):=\sum_{i}\operatorname{Inf}_{i}(f)$.

We write $supp(\widehat{f}(S))=\\{S\subseteq[n]:\widehat{f}(S)\neq 0\\}$.

##  3\. An uncertainty inequality

As in the introduction we mentioned one might expect that
$|supp(f)|\leq|supp(\widehat{f}|^{B}$ for some $B>0$ if we assume some
structure on $supp(f)$. In the next theorem, we will show that the additive
energy is the hidden quantity that provides this connection between the two
supports.

We prove

######  Theorem 3.1.

Let $A:=supp(f)$, where $f:\mathbb{F}^{n}_{2}\mapsto\\{0,1\\}$. Assume that
$E(A)=|A|^{2+\eta}/n$ ($0<\eta<1$). We have

$|supp(f)|\ll|supp(\widehat{f})|^{\frac{2}{1-\eta}}$

if $supp(f)$ is large enough (e.g. $n/|supp(f)|\to 0$ as $n\to\infty$).

We will derive this theorem form our main result:

######  Theorem 3.2.

Let $f:\\{0,1\\}^{n}\to\\{0,1\\}$ and $A\subseteq\\{0,1\\}^{n}$ be its
support, i.e. let $A=f^{-1}(1)$. Denote by $E(A)$ the additive energy of $A$.
Then

(3) $\frac{3|A|^{3}}{128E(A)}<I(f)|supp(\widehat{f})|^{2}.$

Theorem 3.1 follows now from $I(f)\leq n$.

###### Proof of Theorem 3.2.

We consider the truncated sum of $\sum_{S}\widehat{f}^{2}(S)$ as follows: let
$0<R$ be any real number chosen be later. By (2) we get

$\frac{1}{2^{n}}|A|=\sum_{S\subseteq[n]}\widehat{f}^{2}(S)\leq\sum^{\lfloor
R\rfloor}_{S\subseteq[n];|S|=1}(1-|S|/R)\widehat{f}^{2}(S)+\frac{1}{R}\sum_{S\subseteq[n]}|S|\widehat{f}^{2}(S).$

Now we need the following (see e.g. [1])

######  Lemma 3.3.

For every Boolean function we have
$I(f)=4\sum_{S\subseteq[n]}|S|\widehat{f}^{2}(S)$

###### Proof.

Recall that $Inf_{i}(f)=\mathbb{E}_{x}[(f(x)-f((x+e_{i}))^{2}]$. Take now the
Fourier representations of $f(x)$ and $f(x+e_{i})$ we have
$|f(x)-f(x+e_{i})|=2\sum_{i\in S}\widehat{f}(S)(-1)^{\langle S,x\rangle}$.
Indeed, we have two cases; if $i\not\in S$, a term in $f(x)$ cancels the term
in $f(x+e_{i})$. If $i\in S$ it will be the double. Expanding the expectation
we have

$Inf_{i}(f)=\mathbb{E}_{x}[f(x)-f((x+e_{i}))^{2}]=\langle(f(x)-f(x+e_{i}),f(x)-f(x+e_{i})\rangle=$
$=4\langle\sum_{i\in S}\widehat{f}(S)\chi_{S},\sum_{i\in
T}\widehat{f}(T)\chi_{T}\rangle=4\sum_{i\in S}|\widehat{f}(S)|^{2}.$

Finally

$I(f)=\sum_{i}I_{i}(f)=4\sum_{i}\sum_{i\in S}|\widehat{f}(S)|^{2}=$
$=4\sum_{S}\sum_{i}|\widehat{f}(S)|^{2}=4\sum_{S}|S||\widehat{f}(S)|^{2}.$

∎

So we have

$\frac{1}{2^{n}}|A|\leq\sum_{S\in supp(\widehat{f})}\sum^{\lfloor
R\rfloor}_{|S|=1}(1-|S|/R)\widehat{f}^{2}(S)+\frac{1}{4R}I(f)\leq|supp(\widehat{f})|\sum^{\lfloor
R\rfloor}_{|S|=1}(1-|S|/R)\widehat{f}^{2}(S)+\frac{1}{4R}I(f),$

Now let us use the Cauchy inequality for $\sum^{\lfloor
R\rfloor}_{|S|=1}(1-|S|/R)\widehat{f}^{2}(S)$. We obtain

$\sum^{\lfloor
R\rfloor}_{|S|=1}(1-|S|/R)\widehat{f}^{2}(S)\leq\sqrt{\sum^{\lfloor
R\rfloor}_{|S|=1}(1-|S|/R)^{2}}\sqrt{\sum_{S\subseteq[n]}\widehat{f}^{4}(S)}.$

Now we state a well-known lemma (see e.g. in [1]):

######  Lemma 3.4.

(4)
$\frac{1}{2^{3n}}E(A)=\mathbb{E}_{x,y,z}(f(x)f(y)f(z)f(x+y+z))=\sum_{r}\widehat{f}^{4}(r).$

For sake of completeness we give the short proof.

###### Proof.

First note that in $\mathbb{F}_{2}$, $x+(x+y+z)=y+z$ holds, thus we have

$\mathbb{E}_{x,y,z}(f(x)f(y)f(z)f(x+y+z))=$
$=\frac{1}{2^{3n}}|\\{(a_{1},a_{2},a_{3},a_{4})\in A^{4}:\
a_{1}+a_{2}=a_{3}+a_{4}\\}|=\frac{1}{2^{3n}}E(A).$

Furthermore using that $\mathbb{E}_{z}(f(z)f(x+y+z))=f\ast f(x+y)$, we have

$\mathbb{E}_{x,y,z}(f(x)f(y)f(z)f(x+y+z))=\mathbb{E}_{x}(f(x)\mathbb{E}_{y}(f(y)\mathbb{E}_{z}(f(z)f(x+y+z))))=$
$=\mathbb{E}_{x}(f(x)\mathbb{E}_{y}(f(y)f\ast
f(x+y)))=\mathbb{E}_{x}(f(x)(f\ast(f\ast f(x)))).$

Write briefly $f_{3}\ast(r)$ instead of $(f\ast(f\ast f))(r)$. By the
Plancherel formula, the associative of the convolution, and the Fourier
transformation of a convolution we have

$\mathbb{E}_{x,y,z}(f(x)f(y)f(z)f(x+y+z))=\sum_{r}[\widehat{f\cdot
f_{3}\ast(r)}]=$
$=\sum_{r}\widehat{f}(r)\widehat{f_{3}\ast(r)}=\sum_{r}\widehat{f}(r)\widehat{f}^{3}(r)=\sum_{r}\widehat{f}^{4}(r).$

Let $A:=f^{-1}(1)$. Then $\sum_{r}\widehat{f}^{4}(r)=\frac{1}{2^{3n}}E(A)$. As
we detected $\sum_{r}\widehat{f}^{4}(r)$ can be written as
$\mathbb{E}_{x,y,z}(f(x)f(y)f(z)f(x+y+z))$ and we are done.

∎

Expanding the sum $\sum^{\lfloor R\rfloor}_{|S|=1}(1-|S|/R)^{2}$ and by the
elementary summation we have

$\sum^{\lfloor R\rfloor}_{|S|=1}(1-|S|/R)^{2}\leq\frac{R}{3}$

Summing up

(5)
$\frac{1}{2^{n}}|A|=\sum_{S\subseteq[n]}\widehat{f}^{2}(S)\leq|supp(\widehat{f})|\sqrt{\frac{R}{3}}\sqrt{\frac{1}{2^{3n}}E(A)}+\frac{1}{4R}I(f).$

The first term is an increasing, the second term is an decreasing function of
$R$. So when the two terms are the same, i.e. when
$|supp(\widehat{f})|\sqrt{\frac{R}{3}}\sqrt{\frac{1}{2^{3n}}E(A)}=\frac{1}{4R}I(f)$
(and where the bound is optimal), we get for $R$:

$R=\sqrt[3]{\frac{3\cdot{2^{3n}}I^{2}(f)}{16E(A)|supp(\widehat{f})|^{2}}}.$

Thus by (5) we have

$\frac{1}{2^{n}}|A|\leq
2\frac{1}{R}I(f)=2\sqrt[3]{\frac{16E(A)|supp(\widehat{f})|^{2}}{3\cdot{2^{3n}}I^{2}(f)}}I(f).$

Taking the cube we obtain our result. ∎

Acknowledgement. This work was supported by the National Research, Development
and Innovation Fund of Hungary through project no. grant K-129335.

## References

  * [1] Ryan O’Donnell, _Analysis of Boolean Functions, p.22 Exercise 1.29b_ , Cambridge University Press, 2014
  * [2] A. Rao, A. Yehudayoff, Communication Complexity, available in https://homes.cs.washington.edu/ anuprao/pubs/book.pdf
  * [3] A. Samorodnitsky, L. Trevisan, Gowers Uniformity, Influence of Variables, and PCPs, STOC’06., arXiv:math/0510264v1 [math.CO]
  * [4] Ilya Shkredov, Energies and Structure of Additive Sets, The Electronic Journal of Combinatorics, Volume 21, Issue 3 (2014), Article Number P3.44
  * [5] Terry Tao, Van Vu, _Additive Combinatorics._ Cambridge University Press, Cambridge 2006
  * [6] L. Trevisan, Earliest Connections of Additive Combinatorics and Computer Science, available in https://lucatrevisan.wordpress.com/2009/04/17/earliest-connections-of-additive-combinatorics-and-computer-science/


# Belief Propagation as Diffusion

Olivier Peltre
<EMAIL_ADDRESS>
Université d’Artois, Faculté Jean Perrin (LML)
Rue Jean Souvraz 62307 LENS CEDEX

(2021)

###### Abstract

We introduce novel belief propagation algorithms to estimate the marginals of
a high dimensional probability distribution. They involve natural
(co)homological constructions relevant for a localised description of
statistical systems.

## Introduction

Message-passing algorithms such as belief propagation (BP) are parallel
computing schemes that try to estimate the marginals of a high dimensional
probability distribution. They are used in various areas involving the
statistics of a large number of interacting random variables, such as
computational thermodynamics [5, 10], artificial intelligence [11, 21, 15],
computer vision [18] and communications processing [3, 4].

We have shown the existence of a non-linear correspondence between BP
algorithms and discrete integrators of a new form of continuous-time diffusion
equations on belief networks [13, 14]. Practical contributions include (a)
regularised BP algorithms for any time step or diffusivity111 This coefficient
$\varepsilon$ would appear as an exponent of messages in the usual
multiplicative writing of BP equations. Diffusivity relates energy density
gradients to heat fluxes in physics, as in
$\vec{\varphi}=-\varepsilon\cdot\vec{\nabla}(u)$.  coefficient
$0<\varepsilon<1$, and (b) a canonical Bethe diffusion flux that regularises
GBP messages by new Möbius inversion formulas in degree 1222 Generalised
belief propagation = BP on hypergraphs, see [21] for the algorithm. Our
algorithm 2 exponentiates their messages $m_{\alpha\beta}$ by the coefficients
$c_{\alpha}\in\mathbb{Z}$ appearing in the Bethe-Kikuchi local approximation
of free energy. .

The purpose of this text is to describe the structure of belief networks as
concisely as possible, with the geometric operations that appear in our
rewriting of BP equations. An open-sourced python implementation, hosted on
github at opeltre/topos was also used to conduct benchmarks showing the
importance of chosing $\varepsilon<1$.

In the following, we denote by:

  * $-$

$\Omega=\\{i,j,k,\dots\\}$ a finite set of indices (e.g. atoms, neurons,
pixels, bits …)

  * $-$

$x_{i}$ the microstate of atom $i$, valued in a finite set $E_{i}$

  * $-$

$x_{\Omega}$ the microstate of the global system, valued in
$E_{\Omega}=\prod_{i\in\Omega}E_{i}$

The statistical state of the system is described by a probability distribution
$p_{\Omega}$ on $E_{\Omega}$. We write
$\Delta_{\Omega}=\mathrm{Prob}(E_{\Omega})$ for the convex space of
statistical states.

##  1 Graphical Models

######  Definition 1.1.

A hypergraph $(\Omega,K)$ is a set of vertices $\Omega$ and a set of faces333
Also called hyperedges, or regions. A graph is a hypergraph with only
hyperedges of cardinality 2. A simplicial complex is a hypergraph such that
any subset of a face is also a face. A lattice is a hypergraph closed under
$\cap$ and $\cup$. We shall mostly be interested in semi-lattices, closed only
under intersection, of which simplicial complexes are a special case.
$K\subseteq\mathcal{P}(\Omega)$.

Let us denote by $x_{\alpha}$ the microstate of a face
$\alpha\subseteq\Omega$, valued in $E_{\alpha}=\prod_{i\in\alpha}E_{\alpha}$.
For every $\beta\subseteq\alpha$ in $\mathcal{P}(\Omega)$, we have a canonical
projection or restriction444 The contravariant functor
$E:\mathcal{P}(\Omega)^{op}\to\mathbf{Set}$ of microstates defines a sheaf of
sets over $\Omega$.  map:

$\pi^{\beta\alpha}:E_{\alpha}\to E_{\beta}$

We simply write $x_{\beta}$ for the restriction of $x_{\alpha}$ to a subface
$\beta$ of $\alpha$.

######  Definition 1.2.

A graphical model $p_{\Omega}\in\Delta_{\Omega}$ on the hypergraph
$(\Omega,K)$ is a positive probability distribution on $E_{\Omega}$ that
factorises as a product of positive local factors over faces:

$p_{\Omega}(x_{\Omega})=\frac{1}{Z_{\Omega}}\prod_{\alpha\in
K}f_{\alpha}(x_{\alpha})=\frac{1}{Z_{\Omega}}\operatorname{e}^{-\sum_{\alpha}h_{\alpha}(x_{\alpha})}$

We denote by $\Delta_{K}\subseteq\Delta_{\Omega}$ the subspace of graphical
models on $(\Omega,K)$.

Fig 1. Graphical model $p_{ijkl}(x_{ijkl})=f_{ijk}(x_{ijk})\cdot
f_{ikl}(x_{ikl})\cdot f_{jkl}(x_{jkl})$ with its factor graph representation
(middle) on a simplicial complex $K$ formed by joining 3 triangles at a common
vertex and called 2-horn $\Lambda^{2}$ of the 3-simplex (left). The situation
is equivalent when $K$ is a three-fold covering of $\Omega$ by intersecting
regions $\alpha,\alpha^{\prime},\alpha^{\prime\prime}$ (right).

A graphical model $p_{\Omega}$ for $(\Omega,K)$ is also called Gibbs state of
the associated energy function or hamiltonian
$H_{\Omega}:E_{\Omega}\to\mathbb{R}$:

$H_{\Omega}(x_{\Omega})=\sum_{\alpha\in K}h_{\alpha}(x_{\alpha})$

The normalisation factor of the Gibbs density $\operatorname{e}^{-H_{\Omega}}$
is computed by the partition function
$Z_{\Omega}=\sum_{x_{\Omega}}\operatorname{e}^{-H_{\Omega}(x_{\Omega})}$. The
free energy $F_{\Omega}=-\ln Z_{\Omega}$ and partition function generate most
relevant statistical quantities in their derivatives555 Letting $\mu_{H}$
denote the image by $H$ of the counting measure on microstates,
$Z^{\theta}_{\Omega}=\int_{\lambda\in\mathbb{R}}\operatorname{e}^{-\theta\lambda}\mu_{H}(d\lambda)$
is the Laplace transform of $\mu_{H}$ with respect to inverse temperature
$\theta=1/{k_{B}T}$. In [14] we more generally consider free energy as a
functional $A_{\Omega}\to\mathbb{R}$ whose differential at $H_{\Omega}\in
A_{\Omega}$ is the Gibbs state $p_{\Omega}\in A_{\Omega}^{*}$. . They are
however not computable in practice, the sum over microstates scaling
exponentially in the number of atoms.

Message-passing algorithms rely on local structures induced by $K$ to estimate
marginals, providing with an efficient alternative [5, 10] to Markov Chain
Monte Carlo methods such as Hinton’s contrastive divergence algorithm commonly
used for training restricted Boltzmann machines [17, 15]. They are also
related to local variational principles involved in the estimation of
$F_{\Omega}$ [21, 13, 14] by Bethe approximation [2, 5].

We showed in [14] that message-passing explores a subspace of potentials
$(u_{\alpha})$ related to equivalent factorisations of $p_{\Omega}$, until an
associated collection of local probabilities $(q_{\alpha})$ is consistent. Two
fundamental operations constraining this non-linear correspondence are
introduced below. They consist of a differential $d$ associated to a
consistency constraint, and its adjoint boundary $\delta=d^{*}$ enforcing a
dual energy conservation constraint. These operators relate graphical models
to a statistical (co)homology theory, in addition to generating the BP
equations.

##  2 Marginal Consistency

In the following, we suppose given a hypergraph $(\Omega,K)$ closed under
intersection:

$\alpha\cap\beta\in K\quad\mathrm{\quad for\;all\quad}\quad\alpha,\beta\in K$

We denote by $\Delta_{\alpha}$ the space of probability distributions on
$E_{\alpha}$ for all $\alpha\in K$. Given a graphical model
$p_{\Omega}\in\Delta_{\Omega}$, the purpose of belief propagation algorithms
is to efficiently approximate the collection of true marginals
$p_{\alpha}\in\Delta_{\alpha}$ for $\alpha\in K$ by local beliefs
$q_{\alpha}\in\Delta_{\alpha}$, in a space $\Delta_{0}$ of dimension typically
much smaller than $\Delta_{\Omega}$.

######  Definition 2.1.

We call belief over $(\Omega,K)$ a collection $q\in\Delta_{0}$ of local
probabilities over faces, where:

$\Delta_{0}=\prod_{\alpha\in K}\Delta_{\alpha}$

######  Definition 2.2.

For every $\beta\subseteq\alpha$ the marginal or partial integration map
$\Sigma^{\beta\alpha}:\Delta_{\alpha}\to\Delta_{\beta}$ is defined by:

$\Sigma^{\beta\alpha}q_{\alpha}(x_{\beta})=\sum_{y\in
E_{\alpha\setminus\beta}}q_{\alpha}(x_{\beta},y)$

######  Definition 2.3.

Consistent beliefs span the convex subset $\Gamma\subseteq\Delta_{0}$ defined
by marginal consistency constraints666 Equivalently, $\Gamma$ is the
projective limit of the functor $\Delta:K^{op}\to\mathbf{Top}$ defined by
local probabilities and marginal projections, or space of global sections of
the sheaf of topological spaces $\Delta$ over $(\Omega,K)$. :

$q_{\beta}=\Sigma^{\beta\alpha}(q_{\alpha})\quad\mathrm{\quad
for\;all\quad}\;\beta\subseteq\alpha$

The true marginals $(p_{\alpha})\in\Delta_{0}$ of a global density
$p_{\Omega}\in\Delta_{\Omega}$ are always consistent. However their symbolic
definition $p_{\alpha}=\Sigma^{\alpha\Omega}p_{\Omega}$ involves a sum over
fibers of $E_{\Omega\setminus\alpha}$, not tractable in practice. Message-
passing algorithms instead explore a parameterised family of beliefs
$q\in\Delta_{0}$ until meeting the consistency constraint surface
$\Gamma\subseteq\Delta_{0}$.

Let us denote by $A_{\alpha}^{*}$ the space of linear measures on $E_{\alpha}$
for all $\alpha\subseteq\Omega$, and by:

$\Sigma^{\beta\alpha}:A^{*}_{\alpha}\to A^{*}_{\beta}$

the partial integration map.

######  Definition 2.4.

We call $n$-density over $(\Omega,K)$ an element $\lambda\in A_{n}^{*}$ of
local measures indexed by ordered chains of faces, where:

$A_{n}^{*}=\prod_{\alpha_{0}\supset\dots\supset\alpha_{n}}A_{\alpha_{n}}^{*}$

The marginal consistency constraints are expressed by a differential
operator777 Cohomology sequences of this kind were considered by Grothendieck
and Verdier [19], see also [8].  $d$ on the graded vector space
$A_{\bullet}^{*}=\prod_{n}A_{n}^{*}$ of densities over $(\Omega,K)$:

$\bcd
A_{0}^{*}\rightarrow{d}&A_{1}^{*}\rightarrow{d}\dots\rightarrow{d}A_{n}^{*}\ecd$

######  Definition 2.5.

The differential $d:A_{0}^{*}\to A_{1}^{*}$ acts on a density
$(\lambda_{\alpha})\in A_{0}^{*}$ by:

$d(\lambda)_{\alpha\beta}=\lambda_{\beta}-\Sigma^{\beta\alpha}\lambda_{\alpha}$

Consistent densities $\lambda\in[A_{0}^{*}]$ satisfy $d\lambda=0$, and called
$0$-cocycles.

The space of consistent beliefs $\Gamma\subseteq[A_{0}^{*}]$ is the
intersection of $\operatorname{Ker}(d)$ with $\Delta_{0}\subseteq A_{0}^{*}$.
True marginals define a convex map $\Delta_{\Omega}\to\Gamma$, restriction888
Note the image of $\Delta_{\Omega}$ inside $\Gamma$ can be a strict convex
polytope of $\Gamma$, and consistent $q\in\Gamma$ do not always admit a
positive preimage $q_{\Omega}\in\Delta_{\Omega}$ [20, 1].  of a linear
surjection $A^{*}_{\Omega}\to[A_{0}^{*}]$. Consistent beliefs $q\in\Gamma$
acting as for global distributions $p_{\Omega}\in\Delta_{\Omega}$, marginal
diffusion iterates over a smooth subspace of $\Delta_{0}$, diffeomorphic to
equivalent parameterisations of a graphical model $p_{\Omega}$, until
eventually reaching $\Gamma$.

##  3 Energy Conservation

Graphical models parameterise a low dimensional subspace of $\Delta_{\Omega}$,
but definition 1.2 is not injective in the local factors $f_{\alpha}$ or local
potentials $u_{\alpha}=-\ln f_{\alpha}$. The fibers of this parameterisation
can be described linearly at the level of potentials, and correspond to
homology classes of the codifferential operator $\delta=d^{*}$.

We denote by $A_{\alpha}$ the algebra of real functions on $E_{\alpha}$ for
all $\alpha\subseteq\Omega$, and by:

$j_{\alpha\beta}:A_{\alpha}\to A_{\beta}$

the natural extension999 Functions on $E_{\beta}=\prod_{j\in\beta}E_{j}$ can
be viewed as functions on $E_{\alpha}=\prod_{i\in\alpha}$ that do not depend
on the state of $x_{i}$ for $i\in\alpha\setminus\beta$. Therefore $A_{\beta}$
is essentially a subspace of $A_{\alpha}$ and $j_{\alpha\beta}$ an inclusion.
of functions pulled from $E_{\beta}$ to $E_{\alpha}$ by the restriction
$x_{\alpha}\mapsto x_{\beta}$.

######  Definition 3.1.

We let $\delta=d^{*}$ denote the adjoint of $d$, defined by duality:

$\bcd
A_{0}&A_{1}\leftarrow[swap]{\delta}\dots\leftarrow[swap]{\delta}A_{n}\leftarrow[swap]{\delta}\ecd$

######  Proposition 3.2.

The divergence $\delta:A_{1}\to A_{0}$ dual of $d:A_{0}^{*}\to A_{1}^{*}$,
acts on $\varphi\in A_{1}$ by:

$\delta(\varphi)_{\beta}=\sum_{\alpha\supseteq\beta}\varphi_{\alpha\beta}-\sum_{\gamma\subseteq\beta}j_{\beta\gamma}\varphi_{\beta\gamma}$

###### Proof.

Let $\lambda\in A_{0}^{*}$ and $\varphi\in A_{1}$. The duality bracket
$A_{0}^{*}\otimes A_{0}\to\mathbb{R}$ is naturally defined by sum of local
duality brackets $A_{\beta}^{*}\otimes A_{\beta}\to\mathbb{R}$, which
correspond to integration of local measures against observables:

$\langle\,\lambda\,|\,\delta\varphi\,\rangle=\sum_{\beta\in
K}\langle\,\lambda_{\beta}\,|\,\delta\varphi_{\beta}\,\rangle=\sum_{\beta\in
K}\sum_{x_{\beta}\in
E_{\beta}}\lambda_{\beta}(x_{\beta})\delta\varphi_{\beta}(x_{\beta})$

Substituting with the expression of $\delta\varphi$ we get101010 In this
substitution, we simply wrote $\varphi_{\beta\gamma}(x_{\gamma})$ for
$j_{\beta\gamma}(\varphi_{\beta\gamma})(x_{\beta})$, as
$j_{\beta\gamma}:A_{\gamma}\to A_{\beta}$ is an inclusion. :

$\begin{split}\langle\,\lambda\,|\,\delta\varphi\,\rangle&=\sum_{\beta\in
K}\>\sum_{x_{\beta}\in
E_{\beta}}\lambda_{\beta}(x_{\beta})\Big{(}\sum_{\alpha\supseteq\beta}\varphi_{\alpha\beta}(x_{\beta})-\sum_{\gamma\subseteq\beta}\varphi_{\beta\gamma}(x_{\gamma})\Big{)}\\\\[8.00003pt]
&=\sum_{\alpha\supseteq\beta}\>\sum_{x_{\beta}\in
E_{\beta}}\varphi_{\alpha\beta}(x_{\beta})\lambda_{\beta}(x_{\beta})-\sum_{\beta\supseteq\gamma}\>\sum_{x_{\gamma}\in
E_{\gamma}}\varphi_{\beta\gamma}(x_{\gamma})\sum_{y\in
E_{\beta\setminus\gamma}}\lambda_{\beta}(x_{\gamma},y)\end{split}$

The factorisation of the rightmost sum by $\varphi_{\beta\gamma}(x_{\gamma})$
reflects the duality of $\Sigma^{\beta\alpha}$ with $j_{\beta\gamma}$.
Relabeling summation indices $\beta\supseteq\gamma$ as $\alpha\supseteq\beta$,
we finally get:

$\sum_{\alpha\supseteq\beta}\langle\,\lambda_{\beta}\,|\,\varphi_{\alpha\beta}\,\rangle-\sum_{\beta\supseteq\gamma}\langle\,\Sigma^{\gamma\beta}\lambda_{\beta}\,|\,\varphi_{\beta\gamma}\,\rangle=\sum_{\alpha\supseteq\beta}\langle\,\lambda_{\beta}-\Sigma^{\beta\alpha}\lambda_{\alpha}\,|\,\varphi_{\alpha\beta}\,\rangle\\\
$

So that
$\langle\,\lambda\,|\,\delta\varphi\,\rangle=\langle\,d\lambda\,|\,\varphi\,\rangle$
for all $\lambda\in A_{0}^{*}$ and all $\varphi\in A_{1}$. ∎

Consider the total energy map $\zeta_{\Omega}:A_{0}\to A_{\Omega}$ defined by:

$\zeta_{\Omega}(u)=\sum_{\alpha\in K}u_{\alpha}$

We have left injections $j_{\Omega\alpha}$ implicit, viewing each
$A_{\alpha}\subseteq A_{\Omega}$ as a subalgebra of $A_{\Omega}$. Denoting by
$A_{K}\subseteq A_{\Omega}$ the image of $\zeta_{\Omega}$, a graphical model
$p_{\Omega}\in\Delta_{K}$ is then associated to $u\in A_{0}$ by normalising
the Gibbs density $\operatorname{e}^{-\zeta_{\Omega}(u)}$, as in 1.2.

######  Theorem 3.3.

For all $u,u^{\prime}\in A_{0}$ the following are equivalent [14, Chapter 5]:

  * $-$

conservation of total energy
$\sum_{\alpha}u^{\prime}_{\alpha}=\sum_{\alpha}u_{\alpha}$ in $A_{\Omega}$,

  * $-$

there exists $\varphi\in A_{1}$ such that $u^{\prime}=u+\delta\varphi$ in
$A_{0}$.

Theorem 3.3 states that $\operatorname{Ker}(\zeta_{\Omega})$ coincides with
the image of the divergence $\delta A_{1}\subseteq A_{0}$. The subspace of
total energies $\operatorname{Im}(\zeta_{\Omega})\simeq
A_{0}/\operatorname{Ker}(\zeta_{\Omega})$ is therefore isomorphic to the
quotient $[A_{0}]=A_{0}/\delta A_{1}$, formed by homology classes of
potentials $[u]=u+\delta A_{1}\subseteq A_{0}$. Global observables of
$A_{K}\subseteq A_{\Omega}$ can thus be represented by equivalence classes of
local potentials in $[A_{0}]$, homology under $\delta$ giving a local
characterisation for the fibers of $\zeta_{\Omega}$.

##  4 Diffusions

The local approach to the marginal estimation problem, given
$p_{\Omega}=\frac{1}{Z_{\Omega}}\operatorname{e}^{-H_{\Omega}}$, consists of
using a low dimensional map $A_{0}\to\Delta_{0}$ as substitute for the high
dimensional parameterisation $A_{\Omega}\to\Delta_{\Omega}$, until parameters
$u\in A_{0}$ define a consistent belief $q\in\Gamma$ whose components
$q_{\alpha}\in\Delta_{\alpha}$ estimate the true marginals $p_{\alpha}$ of
$p_{\Omega}$.

$\bcd\Delta_{\Omega}\rightarrow&\Gamma\rightarrow[hook]\Delta_{0}\\\
A_{\Omega}\uar\left[A_{0}\right]\uar[swap,dashed]\leftarrow[hook]A_{0}\leftarrow[twoheads]\uar[swap]\ecd$

Assume the hamiltonian is defined by $H_{\Omega}=\sum_{\alpha}h_{\alpha}$ for
given $h\in A_{0}$. According to theorem 3.3, parameters $u\in A_{0}$ will
define the same total energy if and only if:

$u=h+\delta\varphi$

for some heat flux $\varphi\in\delta A_{1}$. The energy conservation
constraint $[u]=[h]$ therefore restricts parameters to fibers of the bottom-
right arrow in the above diagram. The rightmost arrow $A_{0}\to\Delta_{0}$ is
given by the equations:

$q_{\alpha}=\frac{1}{Z_{\alpha}}\operatorname{e}^{-U_{\alpha}}\quad\mathrm{\quad
where\quad}\quad U_{\alpha}=\sum_{\beta\subseteq\alpha}u_{\beta}$ (1)

The image of $[h]$ in $\Delta_{0}$ is a smooth non-linear manifold of
$\Delta_{0}\subseteq A_{0}^{*}$, which may intersect the convex polytope
$\Gamma=\operatorname{Ker}(d)\cap\Delta_{0}$ of consistent beliefs an unknown
number of times. Such consistent beliefs in $\Gamma\subseteq\Delta_{0}$ are
the fixed points of belief propagation algorithms. The central dashed vertical
arrow therefore represents what they try to compute, although no privileged
$q\in\Gamma$ may be defined from $[h]\in A_{0}$ in general.

######  Definition 4.1.

Given a flux functional $\Phi:A_{0}\to A_{1}$, we call diffusion associated to
$\Phi$ the vector field $\delta\Phi$ on $A_{0}$ defined by:

$\frac{du}{dt}=\delta\Phi(u)$ (2)

Letting $q\in\Delta_{0}$ be defined by (1), we say that $\Phi$ is consistent
if $q\in\Gamma\Rightarrow\Phi(u)=0$, and that $\Phi$ is faithful if it is
consistent and $\Phi(u)=0\Rightarrow q\in\Gamma$.

Consistent flux functionals $\Phi$ are constructed by composition with two
remarkable operators $\zeta:A_{0}\to A_{0}$, mapping potentials to local
hamiltonians $u\mapsto U$, and $\mathpzc{D}:A_{0}\to A_{1}$, a non-linear
analog of the differential $d:A_{0}^{*}\to A_{1}^{*}$, measuring inconsistency
of the local beliefs defined by $U\mapsto q$ in (1). The definition of
$\mathpzc{D}$ involves a conditional form of free energy
$\mathbb{F}^{\beta\alpha}:A_{\alpha}\to A_{\beta}$, which generates
conditional expectation maps with respect to local beliefs by
differentiation111111 The tangent map of $\mathpzc{D}$ in turn yields
differential operators $\nabla_{q}:A_{0}\to A_{1}\to\dots$ for all
$q\in\Gamma$, whose kernels characterise tangent fibers ${\rm T}_{q}\Gamma$
pulled by the non-linear parameterisation (1), see [14, Chapter 6]. .

######  Definition 4.2.

We call effective energy the smooth map
$\mathbb{F}^{\beta\alpha}:A_{\alpha}\to A_{\beta}$ defined by:

$\mathbb{F}^{\beta\alpha}(U_{\alpha}\;|\;x_{\beta})=-\ln\sum_{y\in
E_{\alpha\setminus\beta}}\operatorname{e}^{-U_{\alpha}(x_{\beta},y)}$

and effective energy gradient the smooth map $\mathpzc{D}:A_{0}\to A_{1}$
defined by:

$\mathpzc{D}(U)_{\alpha\beta}=U_{\beta}-\mathbb{F}^{\beta\alpha}(U_{\alpha})$

Letting $q=\operatorname{e}^{-U}$ denote local Gibbs densities, note that
$q\in\Gamma\Leftrightarrow\mathpzc{D}(U)=0$ by:

$\mathpzc{D}(U)_{\alpha\beta}=\ln\bigg{[}\>\frac{\Sigma^{\beta\alpha}q_{\alpha}}{q_{\beta}}\>\bigg{]}$

The map $u\mapsto U$ is a fundamental automorphism $\zeta$ of $A_{0}$,
inherited from the partial order structure of $K$. Möbius inversion formulas
define its inverse $\mu=\zeta^{-1}$ [16, 7, 14]. We have extended $\zeta$ and
$\mu$ to automorphisms on the full complex $A_{\bullet}$ in [14, Chapter 3],
in particular, $\zeta$ and $\mu$ also act naturally on $A_{1}$.

######  Definition 4.3.

The zeta transform $\zeta:A_{0}\to A_{0}$ is defined by:

$\zeta(u)_{\alpha}=\sum_{\beta\subseteq\alpha}u_{\beta}$

The flux functional $\Phi=-\mathpzc{D}\circ\zeta$ is consistent and faithful
[14], meaning that $\delta\Phi$ is stationary on $u\in A_{0}$ if and only if
associated beliefs $q\in\Delta_{0}$ are consistent. This flux functional
yields the GBP equations of algorithm A (up to the normalisation step of line
3, ensuring normalisation of beliefs). It may however not be optimal.

We propose another flux functional $\phi=-\mu\circ\mathpzc{D}\circ\zeta$ by
degree-1 Möbius inversion on heat fluxes in algorithm B. It is remarkable that
the associated diffusion $\delta\phi$ involves only the coefficients
$c_{\alpha}\in\mathbb{Z}$ originally used by Bethe [2] to estimate the free
energy of statistical systems close to their critical temperature. These
coefficients also appear in the cluster variational problem [5, 9, 12] on free
energy, solved by fixed points of belief propagation and diffusion algorithms
[14, 21].

It remains open whether fixed points of Bethe diffusion are always consistent.
We were only able to prove this in a neighbourhood of the consistent manifold,
a property we called local faithfulness of the Bethe diffusion flux $\phi$,
see [14, Chapter 5]. Faithfulness proofs are non-trivial and we conjecture the
global faithfulness of $\phi$.

######  Definition 4.4.

The Bethe numbers $(c_{\alpha})\in\mathbb{Z}^{K}$ are uniquely defined by the
equations:

$\sum_{\alpha\supseteq\beta}c_{\alpha}=1\mathrm{\quad for\>\;all\quad}\beta\in
K$

Algorithms. GBP and Bethe Diffusions121212 Note the normalisation operation
$U_{\alpha}\leftarrow U_{\alpha}+\ln Z_{\alpha}$ line 3 in A. It is replaced
by line 4 in B, which takes care of harmonising normalisation factors by
eliminating redundancies in $\Phi$. The arrows $U_{\alpha}\leftarrow\dots$
suggest $\tt map$ operations that may be efficiently parallelised through
asynchronous streams, by locality of the associated operators
$\zeta,\mathpzc{D},\delta\dots$. Each stream performs local operations over
tensors in $A_{\alpha}$, whose dimensions depend on the cardinality of local
configuration spaces $E_{\alpha}=\prod_{i\in\alpha}E_{i}$. .

Input: |  potential ${\tt u}\in A_{0}$
---|---
|  diffusivity $\varepsilon>0$
|  number of iterations $\tt n_{it}$

Output: belief ${\tt q}\in\Delta_{0}$ |
---|---

A. ${\rm GBP}$ $\varepsilon$-diffusion
1: 2:for $\tt i=0\dots n_{it}$ do 3: $\tt
U_{\alpha}\leftarrow\zeta(u)_{\alpha}$ 4: $\tt U_{\alpha}\leftarrow
U_{\alpha}+\ln\Sigma\operatorname{e}^{-U_{\alpha}}$ 5:
$\Phi_{\alpha\beta}\tt\leftarrow-\mathpzc{D}(U)_{\alpha\beta}$ 6: 7: ${\tt
u_{\alpha}\leftarrow u_{\alpha}}+\varepsilon\cdot\delta(\Phi)_{\alpha}$ 8:end
for 9:$\tt q_{\alpha}\leftarrow\operatorname{e}^{-U_{\alpha}}$ 10:return ${\tt
q}$

B. Bethe $\varepsilon$-diffusion
1: 2:for $\tt i=0\dots n_{it}$ do 3: $\tt
U_{\alpha}\leftarrow\zeta(u)_{\alpha}$ 4: 5:
$\Phi_{\alpha\beta}\tt\leftarrow-\mathpzc{D}(U)_{\alpha\beta}$ 6:
$\phi_{\alpha\beta}\leftarrow{\tt c_{\alpha}}\cdot\Phi_{\alpha\beta}$ 7: $\tt
u_{\alpha}\leftarrow u_{\alpha}+\varepsilon\cdot\delta(\phi)_{\alpha}$ 8:end
for 9:$\tt q_{\alpha}\leftarrow\operatorname{e}^{-U_{\alpha}}$ 10:return ${\tt
q}$

Both algorithms consist of time-step $\varepsilon$ discrete Euler integrators
of diffusion equations of the form (2), for two different flux functionals.
Generalised belief propagation (GBP) is usually expressed multiplicatively for
$\varepsilon=1$ in terms of beliefs
$q_{\alpha}=\frac{1}{Z_{\alpha}}\operatorname{e}^{-U_{\alpha}}$ and messages
$m_{\alpha\beta}=\operatorname{e}^{-\varphi_{\alpha\beta}}$. A choice of
$\varepsilon<1$ would appear as an exponent in the product of messages by this
substitution. This is different from damping techniques [6] and has not been
previously considered to our knowledge.

Bethe numbers $c_{\alpha}$ would also appear as exponents of messages in the
multiplicative formulation of algorithm B. The combinatorial regularisation
offered by Bethe numbers stabilises divergent oscillations in non-constant
directions on hypergraphs, improving convergence of GBP diffusion at higher
diffusivities. When $K$ is a graph, the two algorithms are actually
equivalent, so that Bethe numbers only regularise normalisation factors in the
degree $\geq 2$ case.

Fig 2. Convergence of GBP and Bethe diffusions for different values of
diffusivity $0<\varepsilon<1$ and energy scales on the 2-horn, depicted in
figure 1. Both diffusions almost surely diverge for diffusivities
$\varepsilon\geq 1$, so that the usual GBP algorithm is not represented in
this table.

Figure 2 shows the results of experiments conducted on the simplest hypergraph
$K$ for which GBP does not surely converge to the unique solution $q\in[u]\cap
A_{0}^{\Gamma}$, the horn $\Lambda^{2}$ depicted in figure 1. Initial
potentials $u\in A_{0}$ were normally sampled according to
$h_{\alpha}(x_{\alpha})\sim\frac{1}{T}{\cal N}(0,1)$ at different temperatures
or energy scales $T>0$. For each value of $T$ and for each fixed diffusivity
$\varepsilon>0$, GBP and Bethe diffusion algorithms were run on random initial
conditions for ${\tt n_{it}}=10$ iterations. Consistency of the returned
beliefs, if any, was assessed in the effective gradient $\Phi$ to produce the
represented decay ratios. Diffusivity was then increased until the drop in
Bethe diffusion convergence, occuring significantly later than GBP diffusion
but before $\varepsilon<1$, reflecting the importance of using finer
integrators than usual $\varepsilon=1$ belief propagation algorithms.

The discretised diffusion $(1+\varepsilon\delta\Phi)^{n}$ may be compared to
the approximate integration of $\exp(-n\varepsilon x)$ as $(1-\varepsilon
x)^{n}$, which should only be done under the constraint $\varepsilon|x|<1$.
Assuming all eigenvalues of the linearised diffusion flow $\delta\Phi_{*}$ are
negative (as is the case in the neighbourhood of a stable potential), one
should still ensure $\varepsilon|\delta\Phi_{*}|<1$ to confidently estimate
the large time asymptotics of diffusion as
$\exp(n\varepsilon\delta\Phi)\simeq(1+\varepsilon\delta\Phi)^{n}$ and reach
$\Gamma$.

An open-sourced python implementation of the above algorithms, with
implementations of the (co)-chain complex $A_{\bullet}(K)$ for arbitrary
hypergraphs $K$, Bethe numbers, Bethe entropy and free energy functionals, and
other operations for designing marginal estimation algorithms is on github at
opeltre/topos.

## References

  * [1] S. Abramsky and A. Brandenburger, The Sheaf-theoretic structure of non-locality and contextuality, New Journal of Physics, 13 (2011).
  * [2] H. A. Bethe and W. L. Bragg, Statistical Theory of Superlattices, Proceedings of the Royal Society of London. Series A - Mathematical and Physical Sciences, 150 (1935), pp. 552–575.
  * [3] R. G. Gallager, Low-Density Parity-Check Codes, MIT Press, 1963.
  * [4] C. Jego and W. J. Gross, Turbo Decoding of Product Codes Using Adaptive Belief Propagation, IEEE Transactions on Communications, 57 (2009).
  * [5] R. Kikuchi, A Theory of Cooperative Phenomena, Phys. Rev., 81 (1951), pp. 988–1003.
  * [6] C. Knoll and F. Pernkopf, On Loopy Belief Propagation – Local Stability Analysis for Non-Vanishing Fields, in Uncertainty in Artificial Intelligence, 2017.
  * [7] T. Leinster, The Euler Characteristic of a Category, Documenta Mathematica, 13 (2008), pp. 21–49.
  * [8] I. Moerdijk, Classifying Spaces and Classifying Topoi, Springer, 1995\.
  * [9] T. Morita, Cluster Variation Method of Cooperative Phenomena and its Generalization I, Journal of the Physical Society of Japan, 12 (1957), pp. 753–755.
  * [10] M. Mézard and A. Montanari, Information, Physics and Computation, Oxford University Press, 2009.
  * [11] J. Pearl, Reverend Bayes on Inference Engines: A Distributed Hierachical Approach, in AAAI-82 Proceedings, 1982.
  * [12] A. Pelizzola, Cluster variation method in statisical physics and probabilistic graphical models, Journal of Physics A: Mathematical and General, 38 (2005).
  * [13] O. Peltre, A Homological Approach to Belief Propagation and Bethe Approximations, in Geometric Science of Information, 4th International Conference GSI 2019, Springer, 2019.
  * [14] , Message-Passing Algorithms and Homology.  PhD preprint, arXiv:2009.11631, 2020.
  * [15] W. Ping and A. Ihler, Belief Propagation in Conditional RBMs for Structured Prediction, in Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, vol. 54, 2017, pp. 1141–1149.
  * [16] G.-C. Rota, On the Foundations of Combinatorial Theory - I. Theory of Möbius Functions, Z. Warscheinlichkeitstheorie, 2 (1964), pp. 340–368.
  * [17] R. Salakhutdinov and G. Hinton, Deep Boltzmann Machines, in Proceedings of the Twelth International Conference on Artificial Intelligence and Statistics, D. van Dyk and M. Welling, eds., vol. 5 of Proceedings of Machine Learning Research, 2009, pp. 448–455.
  * [18] J. Sun, N.-N. Zheng, and H.-Y. Shum, Stereo Matching Using Belief Propagation, IEEE Transactions on Pattern Analysis and Machine Intelligence, 25 (2003).
  * [19] J.-L. Verdier and A. Grothendieck, V: Cohomologie dans les Topos, SGA-4, 2 (1972).
  * [20] N. Vorob’ev, Consistent Families of Measures and their Extensions, Theory of Probability and its Applications, 7 (1962), pp. 147–164.
  * [21] J. Yedidia, W. Freeman, and Y. Weiss, Constructing Free Energy Approximations and Generalized Belief Propagation Algorithms, IEEE Transactions on Information Theory, 51 (2005), pp. 2282–2312.