5
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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}$).

$\endgroup$
2
  • $\begingroup$ Would you please define "scope of a node". It isn't clear how it differs from a neighbourhood. $\endgroup$
    – Galen
    Sep 23 at 13:23
  • $\begingroup$ 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$. $\endgroup$ Sep 24 at 10:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.