What is a sepset in a probabilistic graphical model?

The terminology sepset is used quite often in the Probabilistic graphical models and causality. What does it mean and what is its relevance ?

The term sepset is used in connection with cluster graphs. A cluster graph is a graph with nodes $$C$$ including a subset of variables $$\{X_1, \dots, X_n\}$$.

A sepset $$S_{ij}$$ is the subset of variables between nodes $$C_i$$ and $$C_j$$ that are in the intersection of the scopes of both nodes (scope simply means the list of variables node $$C$$ depends on. I.e., $$S_{ij} \subseteq (Scope(C_i) \bigcap Scope(C_j)).$$

If $$C_i = \phi(A, B, C)$$ and $$C_j = \phi(B, C, D)$$, then possible sepsets are:

• $$S_{ij}^1 = \{\}$$ - this means there is no edge between $$C_i, C_j$$
• $$S_{ij}^2 = \{B\}$$
• $$S_{ij}^3 = \{C\}$$
• $$S_{ij}^4 = \{B,C\}$$

The relevance of sepsets is that they determine e.g. in belief propagation whether a node $$C_i$$ sends a message to $$C_j$$ about a given variable (they only send a message containing information about a variable if it is in $$S_{ij}$$).

• Would you please define "scope of a node". It isn't clear how it differs from a neighbourhood. Sep 23, 2021 at 13:23
• The scope of the node is the set of variables included in that node. E.g. if a node $X$ is described by potential $\phi(A, B)$, then the scope is $\{A,B\}$. Whereas the neighborhood is the set of the nodes connected to $X$. Sep 24, 2021 at 10:58