Package edu.cmu.tetrad.search

Class SvarFges

java.lang.Object

edu.cmu.tetrad.search.SvarFges

All Implemented Interfaces:

IGraphSearch, DagScorer

public final class SvarFges
extends Object
implements IGraphSearch, DagScorer

Adapts FGES for the time series setting, assuming the data is generated by a SVAR (structural vector autoregression). The main difference is that time order is imposed, and if an edge is removed, it will also remove all homologous edges to preserve the time-repeating structure assumed by SvarFCI. Based on (but not identical to) code by Entner and Hoyer for their 2010 paper. Modified by dmalinsky 4/21/2016.

The references are as follows:

Malinsky, D., & Spirtes, P. (2018, August). Causal structure learning from multivariate time series in settings with unmeasured confounding. In Proceedings of 2018 ACM SIGKDD workshop on causal discovery (pp. 23-47). PMLR.

Entner, D., & Hoyer, P. O. (2010). On causal discovery from time series data using FCI. Probabilistic graphical models, 121-128.

This class is configured to respect knowledge of forbidden and required edges, including knowledge of temporal tiers.

Version:

$Id: $Id

Author:

danielmalinsky

See Also:

• Fges
• Knowledge
• SvarFci

Constructor Summary

Constructors

Constructor	Description
SvarFges(Score score)	Construct a Score and pass it in here.

Method Summary

Modifier and Type	Method	Description
void	addSimilarEdges(Node x, Node y)	Adds similar edges between two nodes.
Graph	getAdjacencies()	Retrieves the adjacency graph.
long	getElapsedTime()	Returns the elapsed time of the search.
Graph	getExternalGraph()	Getter for the field externalGraph.
Knowledge	getKnowledge()	Getter for the field knowledge.
int	getMaxIndegree()	The maximum of parents any nodes can have in the output pattern.
int	getMinChunk(int n)	Returns the minimum number of operations to perform before parallelizing.
String	getNameNoLag(Object obj)	Retrieves the name from the given object without any lag.
int	getnumCPDAGsToStore()	Getter for the field numCPDAGsToStore.
PrintStream	getOut()	Getter for the field out.
double	getScore(Graph dag)	Returns the score of the given DAG.
void	removeSimilarEdges(Node x, Node y)	Removes similar edges between two nodes.
double	scoreDag(Graph dag)	Calculates the score of a Directed Acyclic Graph (DAG).
Graph	search()	Greedy equivalence search: Start from the empty graph, add edges till the model is significant.
void	setAdjacencies(Graph adjacencies)	Sets the set of preset adjacencies for the algorithm; edges not in this adjacencies graph will not be added.
void	setExternalGraph(Graph externalGraph)	Sets the initial graph.
void	setFaithfulnessAssumed(boolean faithfulnessAssumed)	Set to true if it is assumed that all path pairs with one length 1 path do not cancel.
void	setKnowledge(Knowledge knowledge)	Sets the background knowledge.
void	setMaxIndegree(int maxIndegree)	The maximum of parents any nodes can have in the output pattern.
void	setNumCPDAGsToStore(int numCPDAGsToStore)	Sets the number of patterns to store.
void	setOut(PrintStream out)	Sets the output stream that output (except for log output) should be sent to.
void	setTrueGraph(Graph trueGraph)	Sets the true graph, which will result in some edges in output graphs being marked with asterisks.
void	setVerbose(boolean verbose)	Sets whether verbose output should be produced.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

SvarFges

public SvarFges(Score score)

Construct a Score and pass it in here. The totalScore should return a positive value in case of conditional dependence and a negative values in case of conditional independence. See Chickering (2002), locally consistent scoring criterion.

Parameters:

score - a Score object

Method Details

search

public Graph search()
             throws InterruptedException

Greedy equivalence search: Start from the empty graph, add edges till the model is significant. Then start deleting edges till a minimum is achieved.

Specified by:

search in interface IGraphSearch

Returns:

the resulting CPDAG.

Throws:

InterruptedException - if any.

setFaithfulnessAssumed

public void setFaithfulnessAssumed(boolean faithfulnessAssumed)

Set to true if it is assumed that all path pairs with one length 1 path do not cancel.

Parameters:

faithfulnessAssumed - a boolean

getKnowledge

public Knowledge getKnowledge()

Getter for the field knowledge.

Returns:

the background knowledge.

setKnowledge

public void setKnowledge(Knowledge knowledge)

Sets the background knowledge.

Parameters:

knowledge - the knowledge object, specifying forbidden and required edges.

getElapsedTime

public long getElapsedTime()

Returns the elapsed time of the search.

Returns:

This time.

setTrueGraph

public void setTrueGraph(Graph trueGraph)

Sets the true graph, which will result in some edges in output graphs being marked with asterisks.

Parameters:

trueGraph - the true graph.

getScore

public double getScore(Graph dag)

Returns the score of the given DAG.

Parameters:

dag - the dag to score.

Returns:

the totalScore of the given DAG, up to a constant.

getnumCPDAGsToStore

public int getnumCPDAGsToStore()

Getter for the field numCPDAGsToStore.

Returns:

the number of patterns to store.

setNumCPDAGsToStore

public void setNumCPDAGsToStore(int numCPDAGsToStore)

Sets the number of patterns to store. This should be set to zero for fast search.

Parameters:

numCPDAGsToStore - a int

getExternalGraph

public Graph getExternalGraph()

Getter for the field externalGraph.

Returns:

the initial graph for the search. The search is initialized to this graph and proceeds from there.

setExternalGraph

public void setExternalGraph(Graph externalGraph)

Sets the initial graph.

Parameters:

externalGraph - the initial graph.

setVerbose

public void setVerbose(boolean verbose)

Sets whether verbose output should be produced.

Parameters:

verbose - true if verbose output should be produced.

getOut

public PrintStream getOut()

Getter for the field out.

Returns:

the output stream that output (except for log output) should be sent to.

setOut

public void setOut(PrintStream out)

Sets the output stream that output (except for log output) should be sent to. By detault System.out.

Parameters:

out - the output stream.

getAdjacencies

public Graph getAdjacencies()

Retrieves the adjacency graph.

Returns:

the adjacency graph.

setAdjacencies

public void setAdjacencies(Graph adjacencies)

Sets the set of preset adjacencies for the algorithm; edges not in this adjacencies graph will not be added.

Parameters:

adjacencies - the adjacencies graph.

getMaxIndegree

public int getMaxIndegree()

The maximum of parents any nodes can have in the output pattern.

Returns:

-1 for unlimited.

setMaxIndegree

public void setMaxIndegree(int maxIndegree)

The maximum of parents any nodes can have in the output pattern.

Parameters:

maxIndegree - -1 for unlimited.

getMinChunk

public int getMinChunk(int n)

Returns the minimum number of operations to perform before parallelizing.

Parameters:

n - The total number of operations to be performed.

Returns:

The minimum number of operations to do before parallelizing.

scoreDag

public double scoreDag(Graph dag)

Calculates the score of a Directed Acyclic Graph (DAG).

Specified by:

scoreDag in interface DagScorer

Parameters:

dag - The Directed Acyclic Graph to calculate the score for.

Returns:

The score of the DAG.

getNameNoLag

public String getNameNoLag(Object obj)

Retrieves the name from the given object without any lag.

Parameters:

obj - the object from which to retrieve the name

Returns:

the name extracted from the object

addSimilarEdges

public void addSimilarEdges(Node x,
 Node y)

Adds similar edges between two nodes.

Parameters:

x - The first node.

y - The second node.

removeSimilarEdges

public void removeSimilarEdges(Node x,
 Node y)

Removes similar edges between two nodes.

Parameters:

x - the first node

y - the second node