# Factor graph

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Factor_graph
> Markdown URL: https://mediated.wiki/source/Factor_graph.md
> Source: https://en.wikipedia.org/wiki/Factor_graph
> Source revision: 1350436115
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{Short description|Function graph representing factorization}}
{{Distinguish|Graph factorization}}

{{No footnotes|date=August 2025}}
A '''factor graph''' is a [bipartite graph](/source/bipartite_graph) representing the [factorization](/source/factorization) of a [function](/source/function_(mathematics)).  In [probability theory](/source/probability_theory) and its applications, factor graphs are used to represent factorization of a [probability distribution function](/source/Probability_distribution_function_(disambiguation)), enabling efficient computations, such as the computation of [marginal distribution](/source/marginal_distribution)s through the [sum–product algorithm](/source/sum-product_algorithm). One of the important success stories of factor graphs and the sum–product algorithm is the [decoding](/source/code) of capacity-approaching [error-correcting code](/source/error-correcting_code)s, such as [LDPC](/source/LDPC) and [turbo codes](/source/turbo_codes).

Factor graphs generalize [constraint graph](/source/constraint_graph)s.  A factor whose value is either 0 or 1 is called a constraint. A constraint graph is a factor graph where all factors are constraints. The max-product algorithm for factor graphs can be viewed as a generalization of the [arc-consistency algorithm](/source/Local_consistency) for constraint processing.

==Definition==
A factor graph is a [bipartite graph](/source/bipartite_graph) representing the [factorization](/source/factorization) of a function. Given a factorization of a function <math>g(X_1,X_2,\dots,X_n)</math>,
:<math>g(X_1,X_2,\dots,X_n) = \prod_{j=1}^m f_j(S_j),</math>

where <math> S_j \subseteq \{X_1,X_2,\dots,X_n\}</math>, the corresponding factor graph <math> G=(X,F,E)</math> consists of variable vertices
<math>X=\{X_1,X_2,\dots,X_n\}</math>, factor [vertices](/source/vertex_(graph_theory)) <math>F=\{f_1,f_2,\dots,f_m\}</math>, and edges <math>E</math>. The edges depend on the factorization as follows: there is an undirected edge between factor vertex <math> f_j </math> and variable vertex <math> X_k </math> if <math> X_k \in S_j</math>. The function is tacitly assumed to be [real-valued](/source/real-valued): <math>g(X_1,X_2,\dots,X_n) \in \mathbb{R} </math>.

Factor graphs can be combined with message passing algorithms to efficiently compute certain characteristics of the function <math>g(X_1,X_2,\dots,X_n)</math>, such as the [marginal distribution](/source/marginal_distribution)s.

==Examples==
300px|right|thumb|An example factor graph

Consider a function that factorizes as follows:
:<math>g(X_1,X_2,X_3) = f_1(X_1)f_2(X_1,X_2)f_3(X_1,X_2)f_4(X_2,X_3)</math>,

with a corresponding factor graph shown on the right. Observe that the factor graph has a [cycle](/source/cycle_(graph_theory)). If we merge <math> f_2(X_1,X_2)f_3(X_1,X_2) </math> into a single factor, the resulting factor graph will be a [tree](/source/tree_(graph_theory)). This is an important distinction, as message passing algorithms are usually exact for trees, but only approximate for graphs with cycles.

==Message passing on factor graphs==
A popular message passing algorithm on factor graphs is the sum–product algorithm, which efficiently computes all the marginals of the individual variables of the function. In particular, the marginal of variable <math> X_k </math> is defined as
:<math> g_k(X_k) = \sum_{X_{\bar{k}}} g(X_1,X_2,\dots,X_n)</math>
where the notation <math>X_{\bar{k}} </math> means that the summation goes over all the variables, ''except'' <math> X_k </math>. The messages of the sum–product algorithm are conceptually computed in the vertices and passed along the edges. A message from or to a variable vertex is always a [function](/source/Function_(mathematics)) of that particular variable. For instance, when a variable is binary, the messages
over the edges incident to the corresponding vertex can be represented as vectors of length 2: the first entry is the message evaluated in 0, the second entry is the message evaluated in 1. When a variable belongs to the field of [real numbers](/source/real_numbers), messages can be arbitrary functions, and special care needs to be taken in their representation.

In practice, the sum–product algorithm is used for [statistical inference](/source/statistical_inference), where <math> g(X_1,X_2,\dots,X_n)</math> is a joint [distribution](/source/Probability_distribution) or a joint [likelihood function](/source/likelihood_function), and the factorization depends on the [conditional independencies](/source/conditional_independence) among the variables.

The [Hammersley–Clifford theorem](/source/Hammersley%E2%80%93Clifford_theorem) shows that other probabilistic models such as [Bayesian network](/source/Bayesian_network)s and [Markov network](/source/Markov_network)s can be represented as factor graphs; the latter representation is frequently used when performing inference over such networks using [belief propagation](/source/belief_propagation). On the other hand, Bayesian networks are more naturally suited for [generative model](/source/generative_model)s, as they can directly represent the causalities of the model.

==See also==
* [Belief propagation](/source/Belief_propagation)
* [Bayesian inference](/source/Bayesian_inference)
* [Bayesian programming](/source/Bayesian_programming)
* [Conditional probability](/source/Conditional_probability)
* [Markov network](/source/Markov_network)
* [Bayesian network](/source/Bayesian_network)
* [Hammersley–Clifford theorem](/source/Hammersley%E2%80%93Clifford_theorem)

==References== 
* {{Citation|contribution=Markov random fields in statistics |last=Clifford |year=1990 |editor1-last=Grimmett|editor1-first=G.R.|editor2-last=Welsh|editor2-first=D.J.A.|title=Disorder in Physical Systems, J.M. Hammersley Festschrift|pages=19–32|publisher=[Oxford University Press](/source/Oxford_University_Press)|url=http://www.statslab.cam.ac.uk/~grg/books/hammfest/3-pdc.ps |format=postscript |isbn=9780198532156}}
* {{Citation
    | last = Frey
    | first = Brendan J.
    | editor-last = Jain
    | editor-first = Nitin
    | contribution = Extending Factor Graphs so as to Unify Directed and Undirected Graphical Models
    | title = UAI'03, Proceedings of the 19th Conference in Uncertainty in Artificial Intelligence 
    | year = 2003 |isbn = 0127056645 |contribution-url= https://dl.acm.org/doi/abs/10.5555/2100584.2100615
    | pages = 257–264 | arxiv = 1212.2486
    | publisher = Morgan Kaufmann }}
* {{Citation
    | last1 = Kschischang
    | first1 = Frank R.
    | authorlink1=Frank Kschischang
    | first2 = Brendan J. |last2=Frey |first3= Hans-Andrea |last3=Loeliger
    | title = Factor Graphs and the Sum-Product Algorithm
    | journal = [IEEE Transactions on Information Theory](/source/IEEE_Transactions_on_Information_Theory)
    | volume = 47
    | issue = 2
    | pages = 498–519
    | year = 2001
    | citeseerx = 10.1.1.54.1570
    | doi = 10.1109/18.910572
    | bibcode = 2001ITIT...47..498K
 | postscript = . }}
* {{Citation
    | last = Wymeersch
    | first = Henk
    | title = Iterative Receiver Design
    | year = 2007
    | publisher = Cambridge University Press
    | url = http://www.cambridge.org/us/catalogue/catalogue.asp?isbn=9780521873154
    | isbn = 978-0-521-87315-4 }}

==Further reading==
* {{citation |url=http://www.isiweb.ee.ethz.ch/papers/arch/aloe-2004-spmagffg.pdf |title=An Introduction to Factor Graphs] |first=Hans-Andrea |last=Loeliger |journal=IEEE Signal Processing Magazine |date=January 2004 |volume=21 |issue=1 |pages=28–41 |doi=10.1109/MSP.2004.1267047 |bibcode=2004ISPM...21...28L|s2cid=7722934 }}
* [http://dimple.probprog.org/ dimple] {{Webarchive|url=https://web.archive.org/web/20160106225436/http://dimple.probprog.org/ |date=2016-01-06 }} an open-source tool for building and solving factor graphs in MATLAB.
* {{citation |url=http://people.binf.ku.dk/~thamelry/MLSB08/hal.pdf  |title=An introduction to Factor Graphs |first=Hans-Andrea |last=Loeliger |year=2008 }}

{{DEFAULTSORT:Factor Graph}}
Category:Graphical models
Category:Markov networks
Category:Application-specific graphs

---
Adapted from the Wikipedia article [Factor graph](https://en.wikipedia.org/wiki/Factor_graph) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Factor_graph?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.