Graph

Decomposable graph

trilearn.graph.decomposable.all_dec_graphs(p)

Returns all decomposable graphs with p nodes [1].

Parameters:

p (int) – order of the graphs.

Returns:

all decomposable graphs with p nodes.

Return type:

list

Note

This will only work for small numbers of p (p~10).

Example

>>> glist = dlib.all_dec_graphs(3)
>>> for graph in glist:
...     print(graph.nodes)
...     print(graph.edges)
...
[0, 1, 2]
[]
[0, 1, 2]
[(0, 1), (0, 2)]
[0, 1, 2]
[(0, 2)]
[0, 1, 2]
[(0, 2), (1, 2)]
[0, 1, 2]
[(0, 1)]
[0, 1, 2]
[(0, 1), (1, 2)]
[0, 1, 2]
[(1, 2)]
[0, 1, 2]
[(0, 1), (0, 2), (1, 2)]

References

[1]

En referens..

trilearn.graph.decomposable.gen_AR_graph(n_dim, width=2)

Generates a graph with k-band adjacency matrix

Parameters:

n_dim (NetworkX graph) – Number of nodes.

Returns:

A graph with k-band adjacency matrix. Can represent depdndence structure in a AR2 model.

Return type:

NetworkX graph

Example

>>> g = dlib.gen_AR_graph(5)
>>> g.nodes
NodeView((0, 1, 2, 3, 4))
>>> g.edges
EdgeView([(0, 1), (0, 2), (1, 2), (1, 3), (2, 3), (2, 4), (3, 4)])

trilearn.graph.decomposable.junction_tree(graph)

Returns a junction tree representation of graph.

Parameters:

graph (NetworkX graph) – A decomposable graph

Returns:

A junction tree.

Return type:

NetworkX graph

Example

>>> g = dlib.sample_dec_graph(5)
>>> t = dlib.junction_tree(g)
>>> t.nodes
NodeView((frozenset([4]), frozenset([2, 3]), frozenset([0, 1, 3])))
>>> t.edges
EdgeView([(frozenset([4]), frozenset([2, 3])), (frozenset([2, 3]), frozenset([0, 1, 3]))])

trilearn.graph.decomposable.n_junction_trees(graph)

Count then number of junctino trees for graph.

Parameters:

graph (NetworkX graph) – A decomposable graph.

Returns:

Number of junction trees for graph.

Return type:

int

Example

>>> g = dlib.sample_random_AR_graph(5,3)
>>> g.nodes
NodeView((0, 1, 2, 3, 4))
>>> g.edges
EdgeView([(0, 1), (0, 2), (1, 2), (2, 3), (3, 4)])
>>>  dlib.separators(g)
{frozenset([2]): set([(frozenset([2, 3]), frozenset([0, 1, 2]))]), frozenset([3]): set([(frozenset([2, 3]), frozenset([3, 4]))])}
>>> lib.n_junction_trees(g)
1.0

trilearn.graph.decomposable.naive_decomposable_graph(n)

Naive implementation for generating a random decomposable graph. Note that this will only for for small numbers (~10) of n.

Parameters:

n (int) – order of the samples graph.

Returns:

A decomposable graph.

Return type:

NetworkX graph

Example

>>> g = dlib.naive_decomposable_graph(4)
>>> g.edges
EdgeView([(0, 1), (0, 3)])
>>> g.nodes
NodeView((0, 1, 2, 3))

trilearn.graph.decomposable.peo(graph)

Returns a perfect elimination order of graph.

Parameters:

graph (NetworkX graph) – a decomposable graph.

Returns:

a perfect elimination order of graph.

Example

>>> from trilearn.graph import decomposable as dlib
>>> g = dlib.naive_decomposable_graph(5)
>>> dlib.peo(g)
([frozenset([1, 2]), frozenset([1, 3, 4]), frozenset([0, 1, 3])], [None, frozenset([1]), frozenset([1, 3])], [frozenset([1, 2]), frozenset([1, 2, 3, 4]), frozenset([0, 1, 2, 3, 4])], [frozenset([2]), frozenset([2, 4])], [frozenset([1, 2]), frozenset([3, 4]), frozenset([0])])

trilearn.graph.decomposable.sample(order, alpha=0.5, beta=0.5)

Generates a random decomposable graph using the Christmas tree algorithm.

Parameters:

• internal_nodes (list) – list of internal nodes in the generated graph.

• alpha (float) – Subtree kernel parameter

• beta (float) – Subtree kernel parameter

• directory (string) – Path to where the plots should be saved.

Returns:

A decomposable graph.

Return type:

NetworkX graph

Example

>>> g = dlib.sample_dec_graph(5)
>>> g.edges
EdgeView([(0, 1), (0, 3), (1, 3), (2, 3)])
>>> g.nodes
NodeView((0, 1, 2, 3, 4))

trilearn.graph.decomposable.sample_dec_graph(internal_nodes, alpha=0.5, beta=0.5, directory='.')

Generates a random decomposable graph using the Christmas tree algorithm.

Parameters:

• internal_nodes (list) – list of internal nodes in the generated graph.

• alpha (float) – Subtree kernel parameter

• beta (float) – Subtree kernel parameter

• directory (string) – Path to where the plots should be saved.

Returns:

A decomposable graph.

Return type:

NetworkX graph

Example

>>> g = dlib.sample_dec_graph(5)
>>> g.edges
EdgeView([(0, 1), (0, 3), (1, 3), (2, 3)])
>>> g.nodes
NodeView((0, 1, 2, 3, 4))

trilearn.graph.decomposable.sample_random_AR_graph(n_dim, max_bandwidth)

Sample graph with adjancency matrix with varying bandwidth.

Parameters:

• n_dim (int) – number of nodes.

• max_bandwidth (int) – Maximum band width.

Returns:

A graph with band adjancency matrix.

Return type:

Networkx graph

Example

>>> g = dlib.sample_random_AR_graph(5,3)
>>> g.nodes
NodeView((0, 1, 2, 3, 4))
>>> g.edges
EdgeView([(0, 1), (0, 2), (1, 2), (2, 3), (3, 4)])

trilearn.graph.decomposable.separators(graph)

Returns the separators of graph.

Parameters:

graph (NetworkX graph) – A decomposable graph.

Returns:

A dict with separators as keys an their corresponding edges as values.

Return type:

dict

Example

>>> g = dlib.sample_random_AR_graph(5,3)
>>> g.nodes
NodeView((0, 1, 2, 3, 4))
>>> g.edges
EdgeView([(0, 1), (0, 2), (1, 2), (2, 3), (3, 4)])
>>>  dlib.separators(g)
{frozenset([2]): set([(frozenset([2, 3]), frozenset([0, 1, 2]))]), frozenset([3]): set([(frozenset([2, 3]), frozenset([3, 4]))])}

Empirical graph distribution

class trilearn.graph.empirical_graph_distribution.GraphDistribution

Bases: object

A discrete graph distribution.

add_graph(graph, prob)

Adds graph to the distribution. It graph does not exists,then graph gets probability prob, otherwise prob is added to the existing probability.

from_json(js_distribution)

heatmap()

mode(number=1)

pdf(graph)

read_from_dict(dict_distr)

Format: {nx.Graph(): probability,…}

to_json(dist_id, optional={})

Distribution is list of pairs of json_graphs and corresponding probabilities.

Undirected graph

Graph related functions.

trilearn.graph.graph.from_json_file(filename)

From json graph to graph.

Parameters:

filename (string) – Filename of json graph.

Returns:

NetworkX version of the json graph.

Return type:

NetworksX graph

trilearn.graph.graph.graph_to_tuple(graph)

Takes a NetworkX graph and returns a tuplized adjacency matrix.

Parameters:

graph (NetworkX graph) – A graph

Returns:

A flattened adjacency matrix in tuple format.

Return type:

tuple

Example

>>> g.nodes
NodeView((0, 1, 2, 3, 4))
>>> g.edges
EdgeView([(0, 1), (0, 2), (1, 2), (2, 3), (3, 4)])
>>> glib.graph_to_tuple(g)
(0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0)

trilearn.graph.graph.hash_graph(graph)

A hash value of the tupelized version of graph.

Parameters:

graph (NetworkX graph) – A graph

Returns:

A hash value of a graph.

Return type:

int

Example

>>> g = dlib.sample(5)
>>> g.nodes
NodeView((0, 1, 2, 3, 4))
>>> g.edges
EdgeView([(0, 1), (0, 3), (1, 2), (1, 3), (2, 3)])
>>> glib.hash_graph(g)
249771633555694270

trilearn.graph.graph.plot(graph, filename, layout='dot')

Plots a networkx graph and saves it to filename.

Parameters:

• graph (NetworkX graph) – A graph.

• filename (string) – The filename.

trilearn.graph.graph.plot_adjmat(graph, cbar=False)

Plots the adjecency matrix of graph.

Parameters:

graph (NetworkX graph) – A graph.

trilearn.graph.graph.replace_node(graph, node, new_node)

Replaces node by new_node in graph.

Parameters:

• graph (NetworkX graph) – A graph.

• node (hashable object) – A node.

• new_node (hashable object) – Another node.

trilearn.graph.graph.true_distribution(seqdist, filename)

Calculating true distribution for a graph with 6 nodes.

Parameters:

• seqdist (SequentialDistribution) – A (Sequential) distribution for a decomposable graph.

• filename (string) – Filename to save marginal edge distribtion.

Returns:

The graph distribution evaluated for each graph.

Return type:

dict

trilearn.graph.graph.tuple_to_graph(vecmat)

Takes a tuple of the rows in an adjacency matrix and returns a nx.graph. This is a kind of serialization of a graph.

Parameters:

vecmat (tuple) – tuple of the rows in an adjacency matrix.

Returns:

NetworkX graph

Connect/disconnect cliques

trilearn.graph.greenthomas.connect_a(tree, S, X, Y, CX, CY)

trilearn.graph.greenthomas.connect_b(tree, S, X, Y, CX, CY)

trilearn.graph.greenthomas.connect_c(tree, S, X, Y, CX, CY)

trilearn.graph.greenthomas.connect_d(tree, S, X, Y, CX, CY)

trilearn.graph.greenthomas.connect_logprob(num_seps, X, Y, CX, CY)

trilearn.graph.greenthomas.connect_move(tree)

trilearn.graph.greenthomas.connect_select_subsets(tree)

trilearn.graph.greenthomas.disconnect_a(tree, c, X, Y, CX, CY, XSneig, YSneig)

trilearn.graph.greenthomas.disconnect_b(tree, c, X, Y, CX, CY)

trilearn.graph.greenthomas.disconnect_c(tree, c, X, Y, CX, CY)

trilearn.graph.greenthomas.disconnect_d(tree, c, X, Y, CX, CY)

trilearn.graph.greenthomas.disconnect_get_CXCY(C, X, Y, NX, NY)

trilearn.graph.greenthomas.disconnect_get_neighbors(tree, C, X, Y)

trilearn.graph.greenthomas.disconnect_logprob_a(num_cliques, X, Y, S, N)

trilearn.graph.greenthomas.disconnect_logprob_bcd(num_cliques, X, Y, S)

trilearn.graph.greenthomas.disconnect_move(tree)

trilearn.graph.greenthomas.disconnect_select_subsets(tree, c)

Junction tree

Functions related to junction trees.

class trilearn.graph.junction_tree.JunctionTree(data=None, **attr)

Bases: Graph

add_edge(u_of_edge, v_of_edge, **attr)

Add an edge between u and v.

The nodes u and v will be automatically added if they are not already in the graph.

Edge attributes can be specified with keywords or by directly accessing the edge’s attribute dictionary. See examples below.

Parameters:

• u_of_edge (nodes) – Nodes can be, for example, strings or numbers. Nodes must be hashable (and not None) Python objects.

• v_of_edge (nodes) – Nodes can be, for example, strings or numbers. Nodes must be hashable (and not None) Python objects.

• attr (keyword arguments, optional) – Edge data (or labels or objects) can be assigned using keyword arguments.

See also

add_edges_from

add a collection of edges

Notes

Adding an edge that already exists updates the edge data.

Many NetworkX algorithms designed for weighted graphs use an edge attribute (by default weight) to hold a numerical value.

Examples

The following all add the edge e=(1, 2) to graph G:

>>> G = nx.Graph()  # or DiGraph, MultiGraph, MultiDiGraph, etc
>>> e = (1, 2)
>>> G.add_edge(1, 2)  # explicit two-node form
>>> G.add_edge(*e)  # single edge as tuple of two nodes
>>> G.add_edges_from([(1, 2)])  # add edges from iterable container

Associate data to edges using keywords:

>>> G.add_edge(1, 2, weight=3)
>>> G.add_edge(1, 3, weight=7, capacity=15, length=342.7)

For non-string attribute keys, use subscript notation.

>>> G.add_edge(1, 2)
>>> G[1][2].update({0: 5})
>>> G.edges[1, 2].update({0: 5})

add_edges_from(ebunch_to_add, **attr)

Add all the edges in ebunch_to_add.

Parameters:

• ebunch_to_add (container of edges) – Each edge given in the container will be added to the graph. The edges must be given as 2-tuples (u, v) or 3-tuples (u, v, d) where d is a dictionary containing edge data.

• attr (keyword arguments, optional) – Edge data (or labels or objects) can be assigned using keyword arguments.

See also

add_edge

add a single edge

add_weighted_edges_from

convenient way to add weighted edges

Notes

Adding the same edge twice has no effect but any edge data will be updated when each duplicate edge is added.

Edge attributes specified in an ebunch take precedence over attributes specified via keyword arguments.

When adding edges from an iterator over the graph you are changing, a RuntimeError can be raised with message: RuntimeError: dictionary changed size during iteration. This happens when the graph’s underlying dictionary is modified during iteration. To avoid this error, evaluate the iterator into a separate object, e.g. by using list(iterator_of_edges), and pass this object to G.add_edges_from.

Examples

>>> G = nx.Graph()  # or DiGraph, MultiGraph, MultiDiGraph, etc
>>> G.add_edges_from([(0, 1), (1, 2)])  # using a list of edge tuples
>>> e = zip(range(0, 3), range(1, 4))
>>> G.add_edges_from(e)  # Add the path graph 0-1-2-3

Associate data to edges

>>> G.add_edges_from([(1, 2), (2, 3)], weight=3)
>>> G.add_edges_from([(3, 4), (1, 4)], label="WN2898")

Evaluate an iterator over a graph if using it to modify the same graph

>>> G = nx.Graph([(1, 2), (2, 3), (3, 4)])
>>> # Grow graph by one new node, adding edges to all existing nodes.
>>> # wrong way - will raise RuntimeError
>>> # G.add_edges_from(((5, n) for n in G.nodes))
>>> # correct way - note that there will be no self-edge for node 5
>>> G.add_edges_from(list((5, n) for n in G.nodes))

connected_component_vertices()

connected_components()

fresh_copy()

Return a fresh copy graph with the same data structure.

A fresh copy has no nodes, edges or graph attributes. It is the same data structure as the current graph. This method is typically used to create an empty version of the graph.

Notes

If you subclass the base class you should overwrite this method to return your class of graph.

get_separators()

log_n_junction_trees(seps)

Log of the number of junction tree obtained by cutting at seps.

Parameters:

seps (list) – List of separators

Returns:

Log number of junction trees obtained by cutting at seps.

Return type:

float

log_nu(sep)

remove_edge(u, v)

Remove the edge between u and v.

Parameters:

• u (nodes) – Remove the edge between nodes u and v.

• v (nodes) – Remove the edge between nodes u and v.

Raises:

NetworkXError – If there is not an edge between u and v.

See also

remove_edges_from

remove a collection of edges

Examples

>>> G = nx.path_graph(4)  # or DiGraph, etc
>>> G.remove_edge(0, 1)
>>> e = (1, 2)
>>> G.remove_edge(*e)  # unpacks e from an edge tuple
>>> e = (2, 3, {"weight": 7})  # an edge with attribute data
>>> G.remove_edge(*e[:2])  # select first part of edge tuple

remove_edges_from(ebunch)

Remove all edges specified in ebunch.

Parameters:

ebunch (list or container of edge tuples) –

Each edge given in the list or container will be removed from the graph. The edges can be:

• 2-tuples (u, v) edge between u and v.

• 3-tuples (u, v, k) where k is ignored.

See also

remove_edge

remove a single edge

Notes

Will fail silently if an edge in ebunch is not in the graph.

Examples

>>> G = nx.path_graph(4)  # or DiGraph, MultiGraph, MultiDiGraph, etc
>>> ebunch = [(1, 2), (2, 3)]
>>> G.remove_edges_from(ebunch)

remove_node(n)

Remove node n.

Removes the node n and all adjacent edges. Attempting to remove a nonexistent node will raise an exception.

Parameters:

n (node) – A node in the graph

Raises:

NetworkXError – If n is not in the graph.

See also

remove_nodes_from

Examples

>>> G = nx.path_graph(3)  # or DiGraph, MultiGraph, MultiDiGraph, etc
>>> list(G.edges)
[(0, 1), (1, 2)]
>>> G.remove_node(1)
>>> list(G.edges)
[]

to_graph()

Returns the graph underlying this junction tree.

Returns:

The underlying graph.

Return type:

NetworkX graph

Example

>>> np.random.seed(1)
>>> t = jtlib.sample(5)
>>> t.edges
EdgeView([(frozenset([1, 2]), frozenset([4])), (frozenset([1, 2]), frozenset([0, 2])), (frozenset([0, 2]), frozenset([3]))])
>>> t.nodes
NodeView((frozenset([1, 2]), frozenset([4]), frozenset([0, 2]), frozenset([3])))
>>> g = t.to_graph()
>>> g.nodes
NodeView((0, 1, 2, 3, 4))
>>> g.edges
EdgeView([(0, 2), (1, 2)])

tuple()

trilearn.graph.junction_tree.forest_induced_by_sep(tree, s)

Returns the forest created from the subtree induced by s

and cut at the separator that equals s. This is the forest named F in

Parameters:

• tree (NetworkX graph) – A junction tree

• s (set) – A separator of tree

Returns:

The forest created from the subtree induced by s and cut at the separator that equals s.

Return type:

NetworkX graph

trilearn.graph.junction_tree.from_prufer(a)

Prufer sequence to tree

trilearn.graph.junction_tree.graph(tree)

Returns the graph underlying the junction tree.

Parameters:

tree (NetworkX graph) – A junction tree

Returns:

NetworkX graph

trilearn.graph.junction_tree.induced_subtree_nodes(tree, node, visited, sep)

trilearn.graph.junction_tree.is_junction_tree(tree)

Checks the junction tree property of tree.

Parameters:

tree (NetworkX graph) – A junction tree.

Returns:

True if tree is a junction tree.

Return type:

bool

trilearn.graph.junction_tree.jt_to_prufer(tree)

trilearn.graph.junction_tree.log_n_junction_trees(tree, S)

Returns the number of junction trees equivalent to tree where trees is cut as the separators in S. is S i the full set of separators in tree, this is the number of junction trees equivalent to tree.

Parameters:

• tree (NetworkX graph) – A junction tree

• S (list) – List of separators of tree

Returns:

float

trilearn.graph.junction_tree.log_n_junction_trees_update_ratio(new_separators, from_tree, to_tree)

Returns the log of the ratio of number of junction trees of from_tree and to_tree.

Parameters:

• from_tree (NetworkX graph) – A junction tree

• to_tree (NetworkX graph) – A junction tree

• new_separators (dict) – The separators generated by the CTA.

• log_old_mu (float) – Log of the number of junction trees of from_tree.

Returns:

log(mu(to_tree)/mu(from_tree))

Return type:

float

trilearn.graph.junction_tree.log_nu(tree, s)

Returns the number of equivalent junction trees for tree where

tree is cut at the separator s and then constructed again.

Parameters:

• tree (NetworkX graph) – A junction tree

• s (set) – A separator of tree

Returns:

float

trilearn.graph.junction_tree.n_junction_trees(p)

Returns the number of junction trees with p internal nodes.

Parameters:

p (int) – number of internal nodes

trilearn.graph.junction_tree.n_junction_trees_update(new_separators, from_tree, to_tree, log_old_mu)

Returns the new log mu where to_tree has been generated from from_tree2

Parameters:

• from_tree (NetworkX graph) – A junction tree

• to_tree (NetworkX graph) – A junction tree

• new_separators (dict) – The separators generated by the CTA.

• log_old_mu – Log of the number of junction trees of from_tree.

trilearn.graph.junction_tree.n_subtrees(tree, sep)

trilearn.graph.junction_tree.n_subtrees_aux(tree, node, sep, visited, start_nodes)

trilearn.graph.junction_tree.peo(tree)

Returns a perfect elimination order and corresponding cliques, separators, histories, , rests for tree.

Parameters:

tree (NetworkX graph) – A junction tree.

Returns:

A tuple of form (C, S, H, A, R), where the elemenst are lists of Cliques, Separators, Histories, , Rests, from a perfect elimination order.

Return type:

tuple

trilearn.graph.junction_tree.random_tree_from_forest(F, edge_label='')

Returns a random tree from the forest F.

Parameters:

• F (NetworkX graph) – A forest.

• edge_label (string) – Labels for the edges.

trilearn.graph.junction_tree.randomize(tree)

Returns a random junction tree equivalent to tree.

Parameters:

• tree (NetworkX graph) – A junction tree

• s (set) – A separator of tree

Returns:

NetworkX graph

trilearn.graph.junction_tree.randomize_at_sep(tree, s)

Returns a junction tree equivalent to tree where tree is cut at s and then reconstructed at random.

Parameters:

• tree (NetworkX graph) – A junction tree

• s (set) – A separator of tree

Returns:

NetworkX graph

trilearn.graph.junction_tree.sample(internal_nodes, alpha=0.5, beta=0.5, only_tree=False)

Generates a junction tree with order internal nodes with the junction tree expander.

Parameters:

• internal_nodes (int) – number of nodes in the underlying graph

• alpha (float) – parameter for the subtree kernel

• beta (float) – parameter for the subtree kernel

• directory (string) – path to

Returns:

a junction tree

Return type:

NetworkX graph

trilearn.graph.junction_tree.separators(tree)

Returns a dictionary of separators and corresponding

edges in the junction tree tree.

Parameters:

tree (NetworkX graph) – A junction tree

Returns:

Example {sep1: [sep1_edge1, sep1_edge2, …], sep2: […]}

Return type:

dict

trilearn.graph.junction_tree.subtree_induced_by_subset(tree, s)

Returns the subtree of tree induced by the nodes containing the set s.

Parameters:

• tree (NetworkX graph) – A junction tree.

• s (set) – Subset of the node in the underlying graph of T.

Example

>>> t = jtlib.sample(5)
>>> t.nodes
NodeView((frozenset([0, 4]), frozenset([3]), frozenset([1, 2, 4])))
>>> t.edges
EdgeView([(frozenset([0, 4]), frozenset([1, 2, 4])), (frozenset([3]), frozenset([1, 2, 4]))])
>>> subt = jtlib.subtree_induced_by_subset(t, frozenset([1]))
>>> subt.nodes
NodeView((frozenset([1, 2, 4]),))
>>> t.edges
EdgeView([(frozenset([0, 4]), frozenset([1, 2, 4])), (frozenset([3]), frozenset([1, 2, 4]))])

trilearn.graph.junction_tree.to_prufer(tree)

Generate Prufer sequence for tree.

Parameters:

tree (NetwokrX.Graph) – a tree.

Returns:

the Prufer sequence.

Return type:

list

Junction tree collapser

trilearn.graph.junction_tree_collapser.backward_jt_traj_sample(perms_traj, tree)

Samples a backward trajectory of junction trees in the order defined by perms_traj.

Parameters:

• perm_traj (list) – list of m-combinations with up to p nodes, where p is the number of nodes on the graph of tree.

• tree (NetworkX graph) – a junction tree.

Returns:

list of junction trees containing nodes in perm_traj

Return type:

list

trilearn.graph.junction_tree_collapser.log_count_origins(tree, old_tree, node)

The (log) number of possible junction trees with the internal node, node removed that tree could have been built from using the CTA.

Parameters:

• tree (nx graph) – junction tree

• old_tree (nx graph) – junction tree, where node is removed from tree

• node (int) – Node in underlying graph

Returns:

log of the number of possible junction trees with the internal node p removed that tree could have been built from using the CTA.

Return type:

int

trilearn.graph.junction_tree_collapser.log_pdf(tree, old_tree, node=None)

Parameters:

• tree (nx graph) – junction tree

• old_tree (nx graph) – junction tree, where node is removed from tree

• node (int) – Node in underlying graph

trilearn.graph.junction_tree_collapser.possible_origins(tree, node)

For each clique in the subtree spanned by those containing node, a list of neighbors from which the corresponding clique could adhere from is returned.

Parameters:

• tree (NetworkX graph) – a junction tree

• node (int) – a node for the underlying graph of tree

Returns:

dict of new cliques containing node and the cliques from which each new cliques could have emerged from

Return type:

dict

trilearn.graph.junction_tree_collapser.possible_origins_and_sets(tree, node)

For each clique in the subtree spanned by those containing node, a list of neighbors from which the corresponding clique could adhere from is returned.

Parameters:

• tree (NetworkX graph) – a junction tree

• node (int) – a node for the underlying graph of tree

Returns:

dict of new cliques containing node and the cliques from which each new cliques could have emerged from

Return type:

dict

trilearn.graph.junction_tree_collapser.sample(tree, node)

Removes node from the underlying decomposable graph of tree.

two cases: If node was isolated, any junction tree representation of g(tree){node} is randomized at the empty separator. Otherwise, the origin node of each clique containing node is chosen deterministically.

Parameters:

• tree (NetworkX graph) – a junction tree

• node (int) – a node for the underlying graph of tree

Returns:

a junction tree

Return type:

NetworkX graph

trilearn.graph.junction_tree_collapser.sample_new(tree, node)

Removes node from the underlying decomposable graph of tree.

two cases: If node was isolated, any junction tree representation of g(tree){node} is randomized at the empty separator. Otherwise, the origin node of each clique containing node is chosen deterministically.

Parameters:

• tree (NetworkX graph) – a junction tree

• node (int) – a node for the underlying graph of tree

Returns:

a junction tree

Return type:

NetworkX graph

trilearn.graph.junction_tree_collapser.support(tree, node)

Removes node from the underlying decomposable graph of tree.

two cases: If node was isolated, any junction tree representation of g(tree){node} is randomized at the empty separator. Otherwise, the origin node of each clique containing node is chosen deterministically.

Parameters:

• tree (NetworkX graph) – a junction tree

• node (int) – a node for the underlying graph of tree

Returns:

a junction tree

Return type:

NetworkX graph

trilearn.graph.junction_tree_collapser.support_subtree_nodes(tree, node)

Junction tree expander

trilearn.graph.junction_tree_expander.get_subtree_nodes(T1, T2, new)

If the junction tree T1 is expanded to T2 by one internal node new, then the subtree chosen in T1 is (almost) unique. Also, the subtree of T2 containing new is unique. This returns a dictionary of the cliques in the induced subtree of T2 as keys and the emerging cliques in T1 as values.

Parameters:

• T1 (NetworkX graph) – a junction tree

• T2 (NetworkX graph) – a junction tree

• new (int) – the new node

Returns:

a dictionary of the cliques in the induced subtree of T2 as keys and the emerging cliques in T1 as values.

Return type:

dict

trilearn.graph.junction_tree_expander.pdf(tree1, tree2, alpha, beta, new)

CT kernel probability K(tree1, tree2)

Parameters:

• tree1 (NetworkX graph) – A junction tree

• tree2 (NetworkX graph) – A junction tree

• alpha (float) – Parameter for the subtree kernel

• beta (float) – Parameter for the subtree kernel

Returns:

probability of generating tree2 from tree1

Return type:

float

trilearn.graph.junction_tree_expander.sample(tree, i, alpha=0.5, beta=0.5, only_tree=True)

Expands the junciton tree tree with the internal node i.

Parameters:

• tree (NetworkX graph) – a junction tree

• i (int) – new node to be added to the underlying graph of tree

• alpha (float) – parameter for the subtree kernel

• beta (float) – parameter for the subtree kernel

• only_tree (bool) – Return only the new tree if true.

Returns:

A tuple having the following entries:

• tree_new - A junction tree based on tree with the extra internal node i.

• K_st - Transition probability from tree to tree_new

• old_cliques - Dict with the cliques in the subtree used in the transition.

• old_separators - Dict with the cliques in the subtree used in the transition.

• new_cliques,

• new_separators

If only_tree is True, only tree_new is returned.

Return type:

(JunctionTree, float, dict, dict, dict, dict)

Example

>>> import numpy as np
>>> np.random.seed(1)
>>> t = jtlib.sample(5)
>>> t2 = jtelib.sample(t, 5)
>>> t2.nodes
NodeView((frozenset([1, 2]), frozenset([4]), frozenset([5]), frozenset([0, 2]), frozenset([3])))
>>> t2.edges
EdgeView([(frozenset([1, 2]), frozenset([4])), (frozenset([1, 2]), frozenset([0, 2])),
(frozenset([4]), frozenset([3])), (frozenset([5]), frozenset([3]))])
>>> (tree_new, K_st, old_cliques, old_separators, new_cliques, new_separators) = jtelib.sample(t, 5, only_tree=False)
>>> tree_new
<trilearn.graph.junction_tree.JunctionTree object at 0x7fc479893b50>
>>> K_st
0.01
>>> old_cliques
set([])
>>> old_separators
{}
>>> new_cliques
set([frozenset([5])])
>>> new_separators
{frozenset([]): [(frozenset([5]), frozenset([1, 2]))]}

trilearn.graph.junction_tree_expander.sample_cond_on_subtree_nodes(new, tree, subtree_nodes, subtree_edges, subtree_adjlist)

Returns a random CT from tree given subtree.

Parameters:

• n (int) – Node to be added to the graph of tree.

• tree (NetworkX graph) – A junction tree.

• subtree (NetworkX graph) – A subtree of tree.

Returns:

a junction tree expanded from tree where n has been added to subtree.

Return type:

(NetworkX graph)

trilearn.graph.junction_tree_expander.subtree_cond_pdf(tree1, tree2, tree2_subtree_nodes, new)

Returns the probability of generating tree2 from tree1 where the subtree is defined by tree2_subtree_nodes.

Parameters:

• tree1 (NetworkX graph) – A junction tree

• tree2 (NetworkX graph) – A junction tree expanded from tree1

• tree2_subtree_nodes – Contains the cliques in the subgraph of tree2 with the corresponding cliques in tree1.

Returns:

Probability of generating tree2 from tree1 where the subtree is defined by tree2_subtree_nodes.

Return type:

float

Subtree sampler

trilearn.graph.subtree_sampler.pdf(subtree, T, alpha, beta)

Returns the probability of the subtree subtree generated by random_subtree(T, alpha, beta).

Parameters:

• T (NetworkX graph) – A tree

• subtree (NetworkX graph) – a subtree of T drawn by the subtree kernel

• alpha (float) – Subtree kernel parameter

• beta (float) – Subtree kernel parameter

Returns:

float

trilearn.graph.subtree_sampler.random_subtree(T, alpha, beta, subtree_mark)

Random subtree of T according to Algorithm X in [1].

Parameters:

• alpha (float) – probability of continuing to a neighbor

• beta (float) – probability of non empty subtree

• T (NetworkX graph) – the tree of which the subtree is taken

Returns:

A subtree of T

References

[1] F. Rios J., Ohlsson, T. Pavlenko Bayesian structure learning in graphical models using sequential Monte Carlo.

Graph trajectory

A class for handling Markov chains produced from e.g. MCMC.

class trilearn.graph.trajectory.Trajectory

Bases: object

Class for handling trajectories of decomposable graphical models.

add_sample(graph, time, logl=None)

Add graph to the trajectory.

Parameters:

• graph (NetworkX graph) –

• time (list) – List of times it took to generate each sample

empirical_distribution(from_index=0)

from_json(mcmc_json)

get_adjvec_trajectory()

graph_diff_trajectory_df(labels)

log_likelihood(from_index=0)

maximum_likelihood_graph()

read_file(filename)

Reads a trajectory from json-file.

set_sampling_method(method)

set_sequential_distribution(seqdist)

Set the SequentialJTDistribution for the graphs in the trajectory

Parameters:

seqdist (SequentialJTDistribution) – A sequential distribution

set_time(generation_time)

set_trajectory(trajectory)

Set the trajectory of graphs.

Parameters:

trajectory (Trajectory) – An MCMC trajectory of graphs.

size(from_index=0)

Plots the auto-correlation function of the graph size (number of edges) :param from_index: Burn-in period, default=0. :type from_index: int

to_json(optional={})

write_adjvec_trajectory(filename)

Writes the trajectory of adjacency matrices to file.

write_file(filename=None, optional={})

Writes a Trajectory together with the corresponding sequential distribution to a json-file.