Causal Density Dimension

[santiagoginero]

Changes

• Create utility function GraphDimension, which, given a causal graph, a method for estimation, and a pair of vertices in the graph, will return an estimate for the dimension of the graph.

• Currently, the method supported is FlatCausalDiamondRelationProbability, which is based on the Myrheim-Meyer dimension estimation algorithm. This method comes from Causal Set Theory and works by counting the number of causal relations and events in an interval of the graph defined as the intersection of the past of one event with the future of another (making use of AcyclicGraphTake). A ratio between said number of events and number of relations is a function solely of the dimension of the manifold into which the causal graph embeds. Thus, GraphDimension solves this expression of dimension (which can be found in GraphDimension.md), returning the estimation value.

• Modified AcyclicGraphTake so as to generalize the error messages it displays.

Comments

• In the FlatCausalDiamondRelationProbability method, if the events (vertices) provided are causally disconnected or are the same event, the function will return infinity.

---

This change is 

[santiagoginero]

Finally passed lint tests!

[santiagoginero]

Should we then still use the name GraphDimension and change the usage to, e.g.:

SetUsage @ "
GraphDimension[graph$, method$, subregion$] gives an estimate of the dimension of a subregion of the graph graph$ \
specified by subregion$, using the method method$.
";

And then, depending on the method, modify the error messages such that, for instance, in the case of the "Ball Radius" method, the message would read something like:

The argument at postion 3 of GraphDimension[graph, "BallRadius", {}] should be a list of a vertex and a radius.

[taliesinb]

I think I'm happy with the name CausalGraphDimension. What do we think about using the word Estimate here? EstimateCausalGraphDimension? Aren't these things generally called "dimension estimators"?

As for the design principle: yes, the enum value of one argument shouldn't change the meaning of another positional argument. That's definitely a no-no.

The way around it is to combine the two arguments into a single data-carrying argument (like how eg NetEncoder works), so that the "spooky action at a distance" is now contained within one argument:

CausalGraphDimension[graph, {"FlatCausalDiamondWhatever", v1, v2}]

CausalGraphDimension[graph, {"BallVolume", v, r}]

and then you just list the possible enum tuples and their argument structure in a table in the doc page (and in SetUsage too if you want to use the markdown-style table feature there)

[santiagoginero]

I quite like the single data-carrying argument because it conveys that the different specifications of the region in the graph, i.e. either the two vertices or the vertex and radius, are related to the method itself. And I also agree with the name CausalGraphDimension.

So if @maxitg also agrees, I can make this change.

[maxitg]

@taliesinb, @SantiagoGiner, do we expect other argument structures for CausalGraphDimension? "BallVolume" is for spatial hypergraphs, which would be a different function in this case.

Also, some estimators might have other arguments such as causal chain length, which is not necessarily a problem, but it might be awkward to put them in the same list with vertices.

One very simple thing we can do to avoid this problem entirely until we have more information is that we can require causal diamond as an input to this function, and thus require users to use AcyclicGraphTake, e.g.,

CausalGraphDimension[AcyclicGraphTake[graph, {v1, v2}], "FlatSpacetimeCausalRelationDensity"]

Also, I'm not against Estimate, although it seems a bit redundant since that's the only thing we can do.

[maxitg]

The more I think about it, the more I realize that this is really quite complicated which makes me agree more with @taliesinb's original suggestion of trying to keep this as simple as possible.

Maybe it should just be something like this?

CausalChainDensityDimension @ AcyclicGraphTake[graph, v1, v2]

or even

CausalDensityDimension @ AcyclicGraphTake[graph, v1, v2]

I realize it does not say "flat" anywhere, but maybe it's not such a bad default. We can then extend it with additional arguments as needed:

CausalDensityDimension[curvature, chainLength] @ AcyclicGraphTake[graph, v1, v2]

And if we manage to make it work for non-causal-diamonds, it can naturally be extended to take any graphs as arguments:

CausalDensityDimension[0., 2] @ graph

CausalDensity (CausalChainDensity) refers to Myrheim-Meyer, so, e.g., Midpoint-scaling will get a different function. And we pretty much know already that the only parameters to Myrheim-Meyer are the chain length and the manifold which causal chain density is compared against (the sane cases of which are probably limited to a single number, i.e., the curvature, corresponding to flat, de Sitter and anti-de Sitter spaces). If we start comparing to more complicated manifold, we'll probably need a whole new setup anyway.

[santiagoginero]

I don't know if I really like the fact that the user would have to explicitly use AcyclicGraphTake. I agree with the points that the format we have now doesn't really generalize well for other cases. Thus, why don't we more simply create one specific standalone function that simply uses the Myerheim-Meyer method for flat spacetimes, that is, something like:

FlatCausalDiamondDimension[graph, {v1, v2}]

That way we can have something specific and which shares the format of AcyclicGraphTake.

[maxitg]

@SantiagoGiner, but then how will you call the function that computes, say, a midpoint scaling dimension instead?

Plus, with this naming convention, we might end up getting a whole grid of functions (API defactorization) such as FlatCausalDiamondDimenion, DeSitterCausalDiamondDimension, FlatLightConeDimension, DeSitterLightConeDimension, etc.

But I think it would make sense to do something like this:

CausalDensityDimension[graph, {v1, v2}]

which can then be extended as needed into

CausalDensityDimension[0., 2][graph, {v1, v2}]

and

CausalDensityDimension @ graph

And, by the way, I think it would be nice to support the last syntax already in case graph is already a causal diamond (in a separate PR).

[santiagoginero]

@maxitg I very much like that convention. It is specific yet also generalizable, as you say. If we are settled on it I can then change the name of the function.

And yes, I definitely think that it would be good to support the latter syntax—I can submit a separate PR later.

[maxitg]

@SantiagoGiner, I think so. It would be nice to get @taliesinb's opinion, but he might not be available until Sunday, and I think we essentially settled on his original design just with a different name.

[santiagoginero]

@maxitg Yes, I agree. Also, should CausalDensityDimension also accept methods as GraphDimension does? I.e. how would we differentiate between each method? And should we continue to use FlatCausalDiamondRelationProbability for the flat Myrheim-Meyer estimation?

[maxitg]

“CausalDensity” is the method name. The other one would be, e.g., MidpointScalingDimension.

[santiagoginero]

Just completed the appropriate changes!

[santiagoginero]

Yes, that's true. Good catch!