Structural feature alignment to make sensible comparisons and reduce parameter-space dimensionality

To properly compare networks, if we have the opportunity, it would be favorable to set reconstruction-method parameters to align certain observable properties, so that we aren't comparing apples to oranges - i.e., so that the graph distance metric is actually comparing reconstruction methods, rather than two distinct parameterizations of two reconstruction methods. Although in general this is very difficult, due to the enormous set of possible observable values to match up (although we'd probably only want to align "low-order" observables, like network-wide averages, etc.), an excellent such opportunity does seem to present itself:

Several of the reconstruction methods involve a thresholding procedure being applied to some matrix with all entries being in general nonzero, yielding an unweighted adjacency matrix. For example, thresholding the correlation matrix of all nodewise time series, or thresholding the matrix of mutual information among pairs of time series. The important thing about this procedure is that it directly impacts the average degree of the reconstructed network, and in general over a range of threshold values we'll be able to pick a link-density yielding networks ranging anywhere from an empty graph (threshold higher than any matrix values) to a complete graph (threshold lower than any matrix values). This is great news, because it means

that we can reconstruct such networks according to basically the most natural "low-order" observable (the average degree), making the resulting graph distances attributable to the differences in more interesting structural features, and
because it implies a restriction among the threshold-parameter values across methods - effectively reducing the dimensionality of the parameter space (the "joint" parameter space of all threshold-values for different methods) to a single number! also,
if we can determine the correspondences between threshold-values required to match up network link-densities, we likely can write them all as a function of the average degree of the networks, in other words, making the average degree itself the parameter we can tune directly.

How does this sound? Of course this technique only applies to reconstruction methods that directly involve a thresholding procedure, but perhaps we should consider trying to "align" reconstructed networks by average degree (or some other features) regardless, although for those other methods it could be difficult. Questions to all: which of your methods involve a thresholding step? I'm aware of two (correlation & mutual info), but I got the impression that there were more. Any additional thoughts on this topic or related issues? Are there any other notable opportunities of this kind, or in general, instances where a parameter of the method has a direct impact on some graph properties?

@sdmccabe

I'm going to answer in three different levels.

On a theoretical level, I like it, and I invite anyone who wants to try to figure out how the choice of parameters affects average degree to do so. However, I doubt this will be easy in any non-trivial method.

On a paper-writing level, I think this is the least we must do in order to, as you say, have our comparisons be meaningful. Instead of theoretically (prev level) we can do this computationally and just run a bunch of experiments that map out as a function of parameters.

On a code level, I like this a bit less. How do you foresee this can/should change the current codebase? There was the idea of adding a whole separate subpackage named netrd/utilities, which would include some unified thresholding functions. If so, we can just implement your suggestion separate from the algorithm implementations. I think this is the path of least resistance. However, I don't think this is the best way to go from a library design perspective. What we would really want is to have something like reconstruction_object.fit(TS, avgk=target_average_degree). I think this one needs more thinking/designing...

@sdmccabe thoughts?

@jkbren can probably answer which methods involve thresholding.

Re: implementation. For all methods that do invoke explicit thresholding, what I think could be the best implementation choice is, assuming 3. of the original post is possible, to simply have the mean degree as a parameter for the reconstruction method - making it more of a transparent/meaningful script for an arbitrary user to run. Also, self-containedness is good - but this might lead to a lot of repeated code snippets across methods.

An example of the effect of increasing the threshold on the mean degree of the associated network:

The shape of the curve is somewhat general in that it will always start at N-1 and end on 0, as the reconstructed network goes from the complete graph to the empty graph. The shape of the intermediate curve depends only on the empirical distribution of element-values of the pre-thresholded matrix.

This can be included to obtain the original threshold parameter in terms of the degree:

def threshold_from_degree(deg,M):
    """
    Compute the required threshold (tau) in order to yield a reconstructed graph of mean degree deg.
    Params
    ------
    deg (int): Target degree for which the appropriate threshold will be computed
    M (np.ndarray): Pre-thresholded NxN array
    Returns
    ------
    tau (float): Required threshold for A=np.array(I<tau,dtype=int) to have an average of deg ones per row/column

    """
    N=len(M)
    A=np.ones((N,N)) # start with a complete graph (lowest possible threshold)
    for tau in sorted(M.flatten()): # consider increasingly large entry-values
        A[M==tau]=0 # remove edges of weight less than the current entry
        if np.mean(np.sum(A,1))<deg: # stop once the matrix is trimmed down to mean degree deg
            break
    return tau # return this critical threshold value

The only change to the rest of the code is having "deg" as an input argument rather than "tau", and adding the line

tau=threshold_from_degree(deg,I)

directly before the thresholding procedure.

I think this is resolved by #93.

Navigation Menu

Repository navigation

Structural feature alignment to make sensible comparisons and reduce parameter-space dimensionality #36

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Structural feature alignment to make sensible comparisons and reduce parameter-space dimensionality #36

Description

Activity

leotrs commented on Jan 18, 2019

hartle commented on Jan 18, 2019

hartle commented on Jan 18, 2019

hartle commented on Jan 19, 2019

sdmccabe commented on Feb 18, 2019

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions