Inference¶

Two-graph hypothesis testing¶

graspologic.inference.density_test(A1, A2, method='fisher')[source]¶

Compares two networks by testing whether the global connection probabilities (densites) for the two networks are equal under an Erdos-Renyi model assumption.

Parameters:

A1: np.array, int: The adjacency matrix for network 1. Will be treated as a binary network, regardless of whether it was weighted.
A2: np.array, int: Adjacency matrix for network 2. Will be treated as a binary network, regardless of whether it was weighted.
method: string, optional, default="fisher": Specifies the statistical test to be used. The default option is "fisher", which uses Fisher's exact test, but the user may also enter "chi2" to use a chi-squared test. Fisher's exact test is more appropriate when the expected number of edges are small.

Returns:

DensityTestResult: namedtuple

This named tuple returns the following data:

stat: float

The statistic for the test specified by method.

pvalue: float

The p-value for the test specified by method.

misc: dict

Dictionary containing a number of computed statistics for the network comparison performed:

"probability1", float
The probability of an edge (density) in network 1 (\(p_1\)).

"probability2", float
The probability of an edge (density) in network 2 (\(p_2\)).

"observed1", pd.DataFrame
The total number of edge connections for network 1.

"observed2", pd.DataFrame
The total number of edge connections for network 2.

"possible1", pd.DataFrame
The total number of possible edges for network 1.

"possible2", pd.DataFrame
The total number of possible edges for network 1.

Parameters:

A1 (ndarray | csr_array) --
A2 (ndarray | csr_array) --
method (Literal['score', 'fisher', 'chi2']) --

Return type:

DensityTestResult

Notes

Under the Erdos-Renyi model, edges are generated independently with probability \(p\). \(p\) is also known as the network density. This function tests whether the probability of an edge in network 1 (\(p_1\)) is significantly different from that in network 2 (\(p_2\)), by assuming that both networks came from an Erdos-Renyi model. In other words, the null hypothesis is

\[H_0: p_1 = p_2\]

And the alternative hypothesis is

\[H_A: p_1 \neq p_2\]

This test makes several assumptions about the data and test (which could easily be loosened in future versions):

We assume that the networks are directed. If the networks are undirected (and the adjacency matrices are thus symmetric), then edges would be counted twice, which would lead to an incorrect calculation of the edge probability. We believe passing in the upper or lower triangle of the adjacency matrix would solve this, but this has not been tested.

We assume that the networks are loopless, that is we do not consider the probability of an edge existing between a node and itself. This can be weakened and made an option in future versions.

We only implement the alternative hypothesis of "not equals" (two-sided); future versions could implement the one-sided alternative hypotheses.

References

[1]

Pedigo, B.D., Powell, M., Bridgeford, E.W., Winding, M., Priebe, C.E., Vogelstein, J.T. "Generative network modeling reveals quantitative definitions of bilateral symmetry exhibited by a whole insect brain connectome," eLife (2023): e83739.

graspologic.inference.group_connection_test(A1, A2, labels1, labels2, density_adjustment=False, method='score', combine_method='tippett', correct_method='bonferroni', alpha=0.05)[source]¶

Compares two networks by testing whether edge probabilities between groups are significantly different for the two networks under a stochastic block model assumption.

This function requires the group labels in both networks to be known and to have the same categories; although the exact number of nodes belonging to each group does not need to be identical. Note that using group labels inferred from the data may yield an invalid test.

This function also permits the user to test whether one network's group connection probabilities are a constant multiple of the other's (see density_adjustment parameter).

Parameters:

A1: np.array, shape(n1,n1): The adjacency matrix for network 1. Will be treated as a binary network, regardless of whether it was weighted.
A2 np.array, shape(n2,n2): The adjacency matrix for network 2. Will be treated as a binary network, regardless of whether it was weighted.
labels1: array-like, shape (n1,): The group labels for each node in network 1.
labels2: array-like, shape (n2,): The group labels for each node in network 2.
density_adjustment: boolean, optional: Whether to perform a density adjustment procedure. If True, will test the null hypothesis that the group-to-group connection probabilities of one network are a constant multiple of those of the other network. Otherwise, no density adjustment will be performed.
method: str, optional: Specifies the statistical test to be performed to compare each of the group-to-group connection probabilities. By default, this performs the score test (essentially equivalent to chi-squared test when density_adjustment=False), but the user may also enter "chi2" to perform the chi-squared test, or "fisher" for Fisher's exact test.
combine_method: str, optional: Specifies the method for combining p-values (see Notes and [1] for more details). Default is "tippett" for Tippett's method (recommended), but the user can also enter any other method supported by scipy.stats.combine_pvalues().
correct_method: str, optional: Specifies the method for correcting for multiple comparisons. Default value is "holm" to use the Holm-Bonferroni correction method, but many others are possible (see statsmodels.stats.multitest.multipletests() for more details and options).
alpha: float, optional: The significance threshold. By default, this is the conventional value of 0.05 but any value on the interval \([0,1]\) can be entered. This only affects the results in misc['rejections'].

Returns:

GroupTestResult: namedtuple

A tuple containing the following data:

stat: float

The statistic computed by the method chosen for combining p-values (see combine_method).

pvalue: float

The p-value for the overall network-to-network comparison using under a stochastic block model assumption. Note that this is the p-value for the comparison of the entire group-to-group connection matrices (i.e., \(B_1\) and \(B_2\)).

misc: dict

A dictionary containing a number of statistics relating to the individual group-to-group connection comparisons.

"uncorrected_pvalues", pd.DataFrame
The p-values for each group-to-group connection comparison, before correction for multiple comparisons.

"stats", pd.DataFrame
The test statistics for each of the group-to-group comparisons, depending on method.

"probabilities1", pd.DataFrame
This contains the B_hat values computed in fit_sbm above for network 1, i.e. the hypothesized group connection density for each group-to-group connection for network 1.

"probabilities2", pd.DataFrame
Same as above, but for network 2.

"observed1", pd.DataFrame
The total number of observed group-to-group edge connections for network 1.

"observed2", pd.DataFrame
Same as above, but for network 2.

"possible1", pd.DataFrame
The total number of possible edges for each group-to-group pair in network 1.

"possible2", pd.DataFrame
Same as above, but for network 2.

"group_counts1", pd.Series
Contains total number of nodes corresponding to each group label for network 1.

"group_counts2", pd.Series
Same as above, for network 2

"null_ratio", float
If the "density adjustment" parameter is set to "true", this variable contains the null hypothesis for the quotient of odds ratios for the group-to-group connection densities for the two networks. In other words, it contains the hypothesized factor by which network 1 is "more dense" or "less dense" than network 2. If "density adjustment" is set to "false", this simply returns a value of 1.0.

"n_tests", int
This variable contains the number of group-to-group comparisons performed by the function.

"rejections", pd.DataFrame
Contains a square matrix of boolean variables. The side length of the matrix is equal to the number of distinct group labels. An entry in the matrix is "true" if the null hypothesis, i.e. that the group-to-group connection density corresponding to the row and column of the matrix is equal for both networks (with or without a density adjustment factor), is rejected. In simpler terms, an entry is only "true" if the group-to-group density is statistically different between the two networks for the connection from the group corresponding to the row of the matrix to the group corresponding to the column of the matrix.

"corrected_pvalues", pd.DataFrame
Contains the p-values for the group-to-group connection densities after correction using the chosen correction_method.

Parameters:

A1 (ndarray | csr_array) --
A2 (ndarray | csr_array) --
labels1 (ndarray | List) --
labels2 (ndarray | List) --
density_adjustment (bool | float) --
method (Literal['score', 'fisher', 'chi2']) --
combine_method (str) --
correct_method (str) --
alpha (float) --

Return type:

GroupTestResult

Notes

Under a stochastic block model assumption, the probability of observing an edge from any node in group \(i\) to any node in group \(j\) is given by \(B_{ij}\), where \(B\) is a \(K \times K\) matrix of connection probabilities if there are \(K\) groups. This test assumes that both networks came from a stochastic block model with the same number of groups, and a fixed assignment of nodes to groups. The null hypothesis is that the group-to-group connection probabilities are the same

\[H_0: B_1 = B_2\]

The alternative hypothesis is that they are not the same

\[H_A: B_1 \neq B_2\]

Note that this alternative includes the case where even just one of these group-to-group connection probabilities are different between the two networks. The test is conducted by first comparing each group-to-group connection via its own test, i.e.,

\[H_0: {B_{1}}_{ij} = {B_{2}}_{ij}\]

\[H_A: {B_{1}}_{ij} \neq {B_{2}}_{ij}\]

The p-values for each of these individual comparisons are stored in misc['uncorrected_pvalues'], and after multiple comparisons correction, in misc['corrected_pvalues']. The test statistic and p-value returned by this test are for the overall comparison of the entire group-to-group connection matrices. These are computed by appropriately combining the p-values for each of the individual comparisons. For more details, see [1].

When density_adjustment is set to True, the null hypothesis is adjusted to account for the fact that the group-to-group connection densities may be different only up to a multiplicative factor which sets the densities of the two networks the same in expectation. In other words, the null and alternative hypotheses are adjusted to be

\[H_0: B_1 = c B_2\]

\[H_A: B_1 \neq c B_2\]

where \(c\) is a constant which sets the densities of the two networks the same.

Note that in cases where one of the networks has no edges in a particular group-to-group connection, it is nonsensical to run a statistical test for that particular connection. In these cases, the p-values for that individual comparison are set to np.nan, and that test is not included in the overall test statistic or multiple comparison correction.

This test makes several assumptions about the data and test (which could easily be loosened in future versions):

We assume that the networks are directed. If the networks are undirected (and the adjacency matrices are thus symmetric), then edges would be counted twice, which would lead to an incorrect calculation of the edge probability. We believe passing in the upper or lower triangle of the adjacency matrix would solve this, but this has not been tested.

We assume that the networks are loopless, that is we do not consider the probability of an edge existing between a node and itself. This can be weakened and made an option in future versions.

We only implement the alternative hypothesis of "not equals" (two-sided); future versions could implement the one-sided alternative hypotheses.

References

[1] (1,2)

Pedigo, B.D., Powell, M., Bridgeford, E.W., Winding, M., Priebe, C.E., Vogelstein, J.T. "Generative network modeling reveals quantitative definitions of bilateral symmetry exhibited by a whole insect brain connectome," eLife (2023): e83739.

graspologic.inference.latent_position_test(A1, A2, embedding='ase', n_components=None, test_case='rotation', n_bootstraps=500, workers=1)[source]¶

Two-sample hypothesis test for the problem of determining whether two random dot product graphs have the same latent positions.

This test assumes that the two input graphs are vertex aligned, that is, there is a known mapping between vertices in the two graphs and the input graphs have their vertices sorted in the same order. Currently, the function only supports undirected graphs.

Parameters:

A1, A2nx.Graph, nx.DiGraph, nx.MultiDiGraph, nx.MultiGraph, np.ndarray

The two graphs to run a hypothesis test on. If np.ndarray, shape must be (n_vertices, n_vertices) for both graphs, where n_vertices is the same for both

embeddingstring, { 'ase' (default), 'omnibus'}

String describing the embedding method to use:

'ase'
Embed each graph separately using adjacency spectral embedding and use Procrustes to align the embeddings.
'omnibus'
Embed all graphs simultaneously using omnibus embedding.

n_componentsNone (default), or int

Number of embedding dimensions. If None, the optimal embedding dimensions are found by the Zhu and Godsi algorithm.

test_casestring, {'rotation' (default), 'scalar-rotation', 'diagonal-rotation'}

describes the exact form of the hypothesis to test when using 'ase' or 'lse' as an embedding method. Ignored if using 'omnibus'. Given two latent positions, \(X_1\) and \(X_2\), and an orthogonal rotation matrix \(R\) that minimizes \(||X_1 - X_2 R||_F\):

'rotation'
\[H_o: X_1 = X_2 R\]
'scalar-rotation'
\[H_o: X_1 = c X_2 R\]

where \(c\) is a scalar, \(c > 0\)
'diagonal-rotation'
\[H_o: X_1 = D X_2 R\]

where \(D\) is an arbitrary diagonal matrix

n_bootstrapsint, optional (default 500)

Number of bootstrap simulations to run to generate the null distribution

workersint (default=1)

Number of workers to use. If more than 1, parallelizes the bootstrap simulations. Supply -1 to use all cores available.

Returns:

statfloat

The observed difference between the embedded positions of the two input graphs after an alignment (the type of alignment depends on test_case)

pvaluefloat

The overall p value from the test; this is the max of 'p_value_1' and 'p_value_2'

misc_dictdictionary

A collection of other statistics obtained from the latent position test

'p_value_1', 'p_value_2'float
The p value estimate from the null distributions from sample 1 and sample 2
'null_distribution_1', 'null_distribution_2'np.ndarray (n_bootstraps,)
The distribution of T statistics generated under the null, using the first and and second input graph, respectively. The latent positions of each sample graph are used independently to sample random dot product graphs, so two null distributions are generated

Parameters:

A1 (ndarray | csr_array | Graph) --
A2 (ndarray | csr_array | Graph) --
embedding (typing_extensions.Literal[ase, omnibus]) --
n_components (int | None) --
test_case (typing_extensions.Literal[rotation, scalar-rotation, diagonal-rotation]) --
n_bootstraps (int) --
workers (int) --

Return type:

lpt_result

See also

graspologic.embed.AdjacencySpectralEmbed
graspologic.embed.OmnibusEmbed
graspologic.embed.select_svd

References

[1]

Tang, M., A. Athreya, D. Sussman, V. Lyzinski, Y. Park, Priebe, C.E. "A Semiparametric Two-Sample Hypothesis Testing Problem for Random Graphs" Journal of Computational and Graphical Statistics, Vol. 26(2), 2017

graspologic.inference.latent_distribution_test(A1, A2, test='dcorr', metric='euclidean', n_components=None, n_bootstraps=500, random_state=None, workers=None, size_correction=True, pooled=False, align_type='sign_flips', align_kws={}, input_graph=True)[source]¶

Two-sample hypothesis test for the problem of determining whether two random dot product graphs have the same distributions of latent positions.

This test can operate on two graphs where there is no known matching between the vertices of the two graphs, or even when the number of vertices is different. Currently, testing is only supported for undirected graphs.

Parameters:

A1, A2variable (see description of 'input_graph')

The two graphs, or their embeddings to run a hypothesis test on. Expected variable type and shape depends on input_graph attribute

teststr (default="dcorr")

Backend hypothesis test to use, one of ["cca", "dcorr", "hhg", "rv", "hsic", "mgc"]. These tests are typically used for independence testing, but here they are used for a two-sample hypothesis test on the latent positions of two graphs. See hyppo.ksample.KSample for more information.

metricstr or function (default="euclidean")

Distance or a kernel metric to use, either a callable or a valid string. Kernel metrics (e.g. "gaussian") must be used with kernel-based HSIC test and distances (e.g. "euclidean") with all other tests. If a callable, then it should behave similarly to either sklearn.metrics.pairwise_distances() or to sklearn.metrics.pairwise.pairwise_kernels().

Valid strings for distance metric are, as defined in sklearn.metrics.pairwise_distances(),

From scikit-learn: ["euclidean", "cityblock", "cosine", "l1", "l2", "manhattan"].

From scipy.spatial.distance: ["braycurtis", "canberra", "chebyshev", "correlation", "dice", "hamming", "jaccard", "kulsinski", "mahalanobis", "minkowski", "rogerstanimoto", "russellrao", "seuclidean", "sokalmichener", "sokalsneath", "sqeuclidean", "yule"] See the documentation for scipy.spatial.distance for details on these metrics.

Valid strings for kernel metric are, as defined in sklearn.metrics.pairwise.pairwise_kernels(),

["additive_chi2", "chi2", "linear", "poly", "polynomial", "rbf", "laplacian", "sigmoid", "cosine"]

Note "rbf" and "gaussian" are the same metric, which will use an adaptively selected bandwidth.

n_componentsint or None (default=None)

Number of embedding dimensions. If None, the optimal embedding dimensions are found by the Zhu and Godsi algorithm. See select_svd() for more information. This argument is ignored if input_graph is False.

n_bootstrapsint (default=200)

Number of bootstrap iterations for the backend hypothesis test. See hyppo.ksample.KSample for more information.

random_state{None, int, ~np.random.RandomState, ~np.random.Generator}

This parameter defines the object to use for drawing random variates. If random_state is None the ~np.random.RandomState singleton is used. If random_state is an int, a new RandomState instance is used, seeded with random_state. If random_state is already a RandomState or Generator instance, then that object is used. Default is None.

workersint or None (default=None)

Number of workers to use. If more than 1, parallelizes the code. Supply -1 to use all cores available. None is a marker for 'unset' that will be interpreted as workers=1 (sequential execution) unless the call is performed under a Joblib parallel_backend context manager that sets another value for workers. See :class:joblib.Parallel for more details.

size_correctionbool (default=True)

Ignored when the two graphs have the same number of vertices. The test degrades in validity as the number of vertices of the two graphs diverge from each other, unless a correction is performed.

True
Whenever the two graphs have different numbers of vertices, estimates the plug-in estimator for the variance and uses it to correct the embedding of the larger graph.
False
Does not perform any modifications (not recommended).

pooledbool (default=False)

Ignored whenever the two graphs have the same number of vertices or size_correction is set to False. In order to correct the adjacency spectral embedding used in the test, it is needed to estimate the variance for each of the latent position estimates in the larger graph, which requires to compute different sample moments. These moments can be computed either over the larger graph (False), or over both graphs (True). Setting it to True should not affect the behavior of the test under the null hypothesis, but it is not clear whether it has more power or less power under which alternatives. Generally not recomended, as it is untested and included for experimental purposes.

align_typestr, {'sign_flips' (default), 'seedless_procrustes'} or None

Random dot product graphs have an inherent non-identifiability, associated with their latent positions. Thus, two embeddings of different graphs may not be orthogonally aligned. Without this accounted for, two embeddings of different graphs may appear different, even if the distributions of the true latent positions are the same. There are several options in terms of how this can be addresssed:

'sign_flips'
A simple heuristic that flips the signs of one of the embeddings, if the medians of the two embeddings in that dimension differ from each other. See graspologic.align.SignFlips for more information on this procedure. In the limit, this is guaranteed to lead to a valid test, as long as matrix \(X^T X\), where \(X\) is the latent positions does not have repeated non-zero eigenvalues. This may, however, result in an invalid test in the finite sample case if the some eigenvalues are same or close.
'seedless_procrustes'
An algorithm that learns an orthogonal alignment matrix. This procedure is slower than sign flips, but is guaranteed to yield a valid test in the limit, and also makes the test more valid in some finite sample cases, in which the eigenvalues are very close to each other. See graspologic.align.SignFlips for more information on the procedure.
None
Do not use any alignment technique. This is strongly not recommended, as it may often result in a test that is not valid.

align_kwsdict

Keyword arguments for the aligner of choice, either graspologic.align.SignFlips or graspologic.align.SeedlessProcrustes, depending on the align_type. See respective classes for more information.

input_graphbool (default=True)

Flag whether to expect two full graphs, or the embeddings.

True
This function expects graphs, either as NetworkX graph objects or as adjacency matrices, provided as ndarrays of size (n, n) and (m, m). They will be embedded using adjacency spectral embeddings.
False
This function expects adjacency spectral embeddings of the graphs, they must be ndarrays of size (n, d) and (m, d), where d must be same. n_components attribute is ignored in this case.

Returns:

statfloat

The observed difference between the embedded latent positions of the two input graphs.

pvaluefloat

The overall p value from the test.

misc_dictdictionary

A collection of other statistics obtained from the latent position test

null_distributionndarray, shape (n_bootstraps,)
The distribution of T statistics generated under the null.
n_componentsint
Number of embedding dimensions.
Qarray, size (d, d)
Final orthogonal matrix, used to modify X.

Parameters:

A1 (ndarray | csr_array | Graph) --
A2 (ndarray | csr_array | Graph) --
test (typing_extensions.Literal[cca, dcorr, hhg, rv, hsic, mgc]) --
metric (str | Callable) --
n_components (int | None) --
n_bootstraps (int) --
random_state (int | RandomState | Generator | None) --
workers (int | None) --
size_correction (bool) --
pooled (bool) --
align_type (typing_extensions.Literal[sign_flips, seedless_procrustes] | None) --
align_kws (Dict[str, Any]) --
input_graph (bool) --

Return type:

ldt_result

References

[1]

Tang, M., Athreya, A., Sussman, D. L., Lyzinski, V., & Priebe, C. E. (2017). "A nonparametric two-sample hypothesis testing problem for random graphs." Bernoulli, 23(3), 1599-1630.

[2]

Panda, S., Palaniappan, S., Xiong, J., Bridgeford, E., Mehta, R., Shen, C., & Vogelstein, J. (2019). "hyppo: A Comprehensive Multivariate Hypothesis Testing Python Package." arXiv:1907.02088.

[3]

Alyakin, A. A., Agterberg, J., Helm, H. S., Priebe, C. E. (2020). "Correcting a Nonparametric Two-sample Graph Hypothesis Test for Graphs with Different Numbers of Vertices" arXiv:2008.09434