topobench.transforms.liftings.graph2hypergraph package#

Submodules#

topobench.transforms.liftings.graph2hypergraph.base module#

Abstract class for lifting graphs to hypergraphs.

class topobench.transforms.liftings.graph2hypergraph.base.Graph2HypergraphLifting(**kwargs)[source]#

Bases: GraphLifting

Abstract class for lifting graphs to hypergraphs.

Parameters:

**kwargsoptional: Additional arguments for the class.

topobench.transforms.liftings.graph2hypergraph.expander_graph_lifting module#

This module implements the ExpanderGraphLifting class.

class topobench.transforms.liftings.graph2hypergraph.expander_graph_lifting.ExpanderGraphLifting(node_degree: int, **kwargs)[source]#

Bases: Graph2HypergraphLifting

Lift graphs to expander (hyper)graph. More precisely, the expander is a random Ramanujan graph.

Parameters:

node_degreeint: The desired node degree of the expander graph. Must be even.
**kwargsoptional: Additional arguments for the class.

lift_topology(data: Data) → dict[source]#

Lift the topology of a graph to an expander hypergraph.

Parameters:

datatorch_geometric.data.Data: The input data to be lifted.

Returns:

dict: The lifted topology.

topobench.transforms.liftings.graph2hypergraph.expander_graph_lifting.maybe_regular_expander(n, d, *, create_using=None, max_tries=100, seed=None)[source]#

Utility for creating a random regular expander.

Returns a random $d$-regular graph on $n$ nodes which is an expander graph with very good probability.

Parameters:

nint: The number of nodes.
dint: The degree of each node.
create_usingGraph Instance or Constructor: Indicator of type of graph to return. If a Graph-type instance, then clear and use it. If a constructor, call it to create an empty graph. Use the Graph constructor by default.
max_triesint. (default: 100): The number of allowed loops when generating each independent cycle
seed(default: None): Seed used to set random number generation state. See :ref`Randomness<randomness>`.

Returns:

Ggraph: The constructed undirected graph.

Raises:

NetworkXError: If $d % 2 != 0$ as the degree must be even. If $n - 1$ is less than $ 2d $ as the graph is complete at most. If max_tries is reached

topobench.transforms.liftings.graph2hypergraph.forman_ricci_curvature_lifting module#

This module implements the HypergraphFormanRicciCurvatureLifting class.

class topobench.transforms.liftings.graph2hypergraph.forman_ricci_curvature_lifting.HypergraphFormanRicciCurvatureLifting(network_type: str = 'weighted', threshold_type: str = 'quantile', threshold_direction: str = 'above', threshold: float = 0.1, **kwargs)[source]#

Bases: Graph2HypergraphLifting

Lift graphs to hypergraph domain using Forman-Ricci curvature based backbone estimation.

This lifting identifies a network’s structure-preserving, coarse geometry, i.e. its backbones, which lend themselves specifically to model information flows across wide areas of the network via hyperedges. To identify this coarse geometry we apply Forman-Ricci curvature to the original graph. Forman-Ricci curvature defines an edge-based network characteristic that reveals properties of a graph’s community structure. In particular high absolute Forman-Ricci curvature exhibits a network’s backbone, a coarse, structure preserving graph geometry that forms connections between major communities, most suitable to form hyperedges. In addition, Forman-Ricci curvature was found to be especially useful for network analysis since its intuitive notion allows for efficient computation that scales to large networks sizes.

Parameters:

network_typestr, optional: Network type may be weighted or unweighted. Default is “weighted”.
threshold_typestr, optional: Type of threshold (either based on quantile or absolute). Default is “quantile”.
threshold_directionstr, optional: Direction whether to prune values above or below threshold. Default is “above”.
thresholdfloat, optional: Absolute value or quantile to estimate cutoff threshold from Forman-Ricci curvature distribution to prune network and reveal backbone. Default is 0.1.
**kwargsdict, optional: Additional arguments for the class.

lift_topology(data: Data) → dict[source]#

Lift the topology of a graph to hypergraph domain using Forman-Ricci curvature based backbone estimation.

Parameters:

datatorch_geometric.data.Data: The input data to be lifted.

Returns:

dict: The lifted topology.

topobench.transforms.liftings.graph2hypergraph.kernel_lifting module#

This module implements the HypergraphKernelLifting class.

class topobench.transforms.liftings.graph2hypergraph.kernel_lifting.HypergraphKernelLifting(graph_kernel='heat', feat_kernel='identity', C='prod', fraction=0.5, **kwargs)[source]#

Bases: Graph2HypergraphLifting

Lift graphs to hypergraph domain by the kernel over graphs (features can be included).

Parameters:

graph_kernelstr or callable: The kernel function to be applied to the graph topology, if a string, it specifies a predefined kernel type. Currently, only “heat” is supported. If a callable, it should be a function that takes the graph Laplacian and additional kwargs as input and returns a kernel matrix.
feat_kernelstr or callable: The kernel function to be applied to the features, if a string, it specifies a predefined kernel type. Currently, only “identity” is supported. If a callable, it should be a function that takes the features and additional kwargs as input and returns a kernel matrix.
Cstr or callable: Default is “heat”.
fractionfloat: The fraction of the kernel to be considered for the hypergraph construction. Default is 0.5.
**kwargsoptional: Additional arguments for the class.

lift_topology(data: Data) → dict[str, Tensor][source]#

Lift the topology of a graph to hypergraph domain by considering the kernel over vertices or alternatively features.

In a most generic form the kernel looks like: $$K = C(K_v(v, v^{prime}) K_x(x, x^{prime})),$$ where $K_v$ is a kernel over the graph (graph_kernel), $K_x$ is a kernel over the features (feat_kernel), and C is the function to combine those (for instance sum or prod).

Parameters:

datatorch_geometric.data.Data: The input data to be lifted.

Returns:

typing.Dict[str, torch.Tensor]: The lifted topology.

Raises:

ValueError: if the input is incomplete or in incorrect format.

topobench.transforms.liftings.graph2hypergraph.kernel_lifting.get_combination(c_name_or_func: Callable | str) → Callable[source]#

Return a combination function based on the specified type or function.

Parameters:

c_name_or_funcstr or callable

The combination method to use. This can be: - A string specifying a predefined combination type:

“prod”: Returns a function that computes the element-wise product of two inputs.

“sum”: Returns a function that computes the element-wise sum of two inputs.

A callable: A custom combination function that takes two arguments (A and B) and combines them.

Returns:

callable: A function that combines two inputs based on the specified combination type or custom function. The returned function takes two parameters, A and B, which can be scalars, tensors, or other compatible types, and returns their combined result.

Raises:

ValueError: If c_name_or_func is a string that does not match any supported predefined combination type.

Examples

Example with the “prod” combination:

>>> prod_fn = get_combination("prod")
>>> result = prod_fn(2, 3)
>>> print(result)
6

Example with the “sum” combination:

>>> sum_fn = get_combination("sum")
>>> result = sum_fn(2, 3)
>>> print(result)
5

Example with a custom combination function:

>>> def custom_combination(A, B):
...     return A - B
>>> custom_fn = get_combination(custom_combination)
>>> result = custom_fn(7, 4)
>>> print(result)
3

topobench.transforms.liftings.graph2hypergraph.kernel_lifting.get_feat_kernel(features, kernel: str | Callable = 'identity', **kwargs)[source]#

Compute a kernel matrix for the given features based on the specified kernel type.

Parameters:

featurestorch.Tensor: A 2D tensor representing the features for which the kernel matrix is to be computed. Each row corresponds to a feature vector.
kernelstr or callable, optional: Specifies the type of kernel to apply or a custom kernel function. - If a string, it specifies a predefined kernel type. Currently, only “identity” is supported. The “identity” kernel returns an identity matrix of size (N, N), where N is the number of features. - If a callable, it should be a function that takes features and additional keyword arguments (**kwargs) as input and returns a kernel matrix. Default is “identity”.
**kwargsdict, optional: Additional keyword arguments required by the custom kernel function if kernel is a callable.

Returns:

torch.Tensor: The computed kernel matrix. If kernel=”identity”, the result is an identity matrix of size (N, N). If kernel is a callable, the result is determined by the custom kernel function.

Raises:

ValueError: If kernel is a string but not one of the supported kernel types (currently only “identity”).

Examples

Example with the “identity” kernel:

>>> import torch
>>> features = torch.randn(5, 3)  # 5 features with 3 dimensions each
>>> kernel_matrix = get_feat_kernel(features, "identity")
>>> print(kernel_matrix)

Example with a custom kernel function:

>>> def custom_kernel_fn(features, **kwargs):
...     # Example: return a random kernel matrix of appropriate size
...     return torch.rand(features.shape[0], features.shape[0])
>>> kernel_matrix = get_feat_kernel(features, custom_kernel_fn)
>>> print(kernel_matrix)

topobench.transforms.liftings.graph2hypergraph.kernel_lifting.get_graph_kernel(laplacian, kernel: str | Callable = 'heat', **kwargs)[source]#

Return a graph kernel.

Parameters:

laplaciantorch.Tensor: The graph Laplacian (alternatively can be the normalized graph Laplacian).
kernelstr or callable: Either the name of a kernel or a callable kernel function.
**kwargsdict: Additional keyword arguments representing the hyperparameters of the kernel. These should be passed to the kernel function.

Returns:

torch.Tensor: A graph kernel for the provided Laplacian matrix.

topobench.transforms.liftings.graph2hypergraph.kernel_lifting.graph_heat_kernel(laplacian: Tensor, t: float = 1.0) → Tensor[source]#

Return graph heat kernel $$K = exp(-t L)$$.

Parameters:

laplaciantorch.Tensor: The graph Laplacian (alternatively can be the normalized graph Laplacian).
tfloat: The temperature parameter for the heat kernel.

Returns:

torch.Tensor: The heat kernel.

topobench.transforms.liftings.graph2hypergraph.kernel_lifting.graph_matern_kernel(laplacian: Tensor, nu: int = 1, kappa: int = 1) → Tensor[source]#

Return graph Matérn kernel.

Parameters:

laplaciantorch.Tensor: The graph Laplacian (alternatively can be the normalized graph Laplacian).
nufloat: Smoothness parameter of the kernel.
kappaint: Lengthscale parameter of the kernel.

Returns:

torch.Tensor: The Matérn kernel matrix K = (2*nu / kappa^2 * I + L)^(-nu).

Notes

I represents the identity matrix and L is the graph Laplacian.

topobench.transforms.liftings.graph2hypergraph.khop_lifting module#

This module implements the k-hop lifting of graphs to hypergraphs.

class topobench.transforms.liftings.graph2hypergraph.khop_lifting.HypergraphKHopLifting(k_value=1, **kwargs)[source]#

Bases: Graph2HypergraphLifting

Lift graph to hypergraphs by considering k-hop neighborhoods.

The class transforms graphs to hypergraph domain by considering k-hop neighborhoods of a node. This lifting extracts a number of hyperedges equal to the number of nodes in the graph.

Parameters:

k_valueint, optional: The number of hops to consider. Default is 1.
**kwargsoptional: Additional arguments for the class.

lift_topology(data: Data) → dict[source]#

Lift a graphs to hypergraphs by considering k-hop neighborhoods.

Parameters:

datatorch_geometric.data.Data: The input data to be lifted.

Returns:

dict: The lifted topology.

topobench.transforms.liftings.graph2hypergraph.knn_lifting module#

This module implements the HypergraphKNNLifting class.

class topobench.transforms.liftings.graph2hypergraph.knn_lifting.HypergraphKNNLifting(k_value=1, loop=True, **kwargs)[source]#

Bases: Graph2HypergraphLifting

Lift graphs to hypergraph domain by considering k-nearest neighbors.

Parameters:

k_valueint, optional: The number of nearest neighbors to consider. Must be positive. Default is 1.
loopbool, optional: If True the hyperedges will contain the node they were created from.
**kwargsoptional: Additional arguments for the class.

Raises:

ValueError: If k_value is less than 1.
TypeError: If k_value is not an integer or if loop is not a boolean.

lift_topology(data: Data) → dict[source]#

Lift a graph to hypergraph by considering k-nearest neighbors.

Parameters:

datatorch_geometric.data.Data: The input data to be lifted.

Returns:

dict: The lifted topology.

topobench.transforms.liftings.graph2hypergraph.mapper_lifting module#

This module implements the MapperCover class.

class topobench.transforms.liftings.graph2hypergraph.mapper_lifting.MapperCover(resolution=10, gain=0.3)[source]#

Bases: object

The MapperCover class computes the cover used in constructing the Mapper for the MapperLifting class.

Parameters:

resolutionint, optional: The number of intervals in the MapperCover. Default is 10.
gainfloat, optional: The proportion of overlap between consectutive intervals in the MapperCover and should be value between 0 and 0.5. Default is 0.3.

Attributes:

cover_intervals(resolution, 2) Tensor: A tensor containing each interval in the MapperCover.

fit_transform(filtered_data)[source]#

Construct an interval cover over filtered data.

Parameters:

filtered_data(n_sample, 1) Tensor: Filtered data to construct the Mapper cover.

Returns:

< (n_sample, resolution) boolean Tensor.: Mask which identifies which data points are in each cover set. Covers which are empty are removed so output tensor has at most size (n_sample, resolution).

class topobench.transforms.liftings.graph2hypergraph.mapper_lifting.MapperLifting(filter_attr='laplacian', resolution=10, gain=0.3, filter_func=None, **kwargs)[source]#

Bases: Graph2HypergraphLifting

Lift graphs to hypergraph domain using a Mapper construction for CC-pooling.

Parameters:

filter_attrstr, optional: Name of the filter functional to filter data to 1-dimensional subspace. The filter attribute can be “laplacican”, “svd”, “pca”, “feature_sum”, “position_sum”. You may also define your own filter_attr string if the filter_func parameter is defined. Default is “laplacian”.
resolutionint, optional: The number of intervals to construct the MapperCover. Default is 10.
gainfloat, optional: The percentage of overlap between consectutive intervals in MapperCover and should be a value between 0 and 0.5. Default is 0.3.
filter_funcobject, optional: Filter function used for Mapper construction. Self defined lambda function or transform to filter data. Function must output an (n_sample, 1) Tensor. If filter_func is not None, user must define filter_attr as a string not already listed above. Default is None.
**kwargsoptional: Additional arguments for the class.

Attributes:

filtered_datadict: Filtered data used to compute the Mapper lifting. Dictionary is of the form {filter_attr: filter_func(data)}.
cover(k, resolution) boolean Tensor: Mask computed from the MapperCover class to compute the Mapper lifting with k < n_sample.
clustersdict: Distinct connected components in each cover set computed after fitting the Mapper cover. Dictionary has integer keys and tuple values of the form (cover_set_i, nodes_in_cluster). Each cluster is a rank 2 hyperedge in the hypergraph.

Notes

The following are common filter functions which can be called with filter_attr.

1. “laplacian” : Converts data to an undirected graph and then applies the torch_geometric.transforms.AddLaplacianEigenvectorPE(k=1) transform and projects onto the smallest nonzero eigenvector.

2. “svd” : Applies the torch_geometric.transforms.SVDFeatureReduction(out_channels=1) transform to the node feature matrix (ie. torch_geometric.Data.data.x) to project data to a 1-dimensional subspace.

3. “feature_pca” : Applies torch.pca_lowrank(q=1) transform to node feature matrix (ie. torch_geometric.Data.data.x) and then projects to the 1st principal component.

4. “position_pca” : Applies torch.pca_lowrank(q=1) transform to node position matrix (ie. torch_geometric.Data.data.pos) and then projects to the 1st principal component.

5. “feature_sum” : Applies torch.sum(dim=1) to the node feature matrix in the graph (ie. torch_geometric.Data.data.x).

6. “position_sum” : Applies torch.sum(dim=1) to the node position matrix in the graph (ie. torch_geometric.Data.data.pos).

You may also construct your own filter_attr and filter_func:

7. “my_filter_attr” : Name of a self defined function my_filter_func = lambda data : my_filter_func(data) where my_filter_func(data) outputs a (n_sample, 1) Tensor.

References

[1]

Hajij, M., Zamzmi, G., Papamarkou, T., Miolane, N., Guzmán-Sáenz, A., Ramamurthy, K. N., et al. (2022). Topological deep learning: Going beyond graph data. arXiv preprint arXiv:2206.00606.

lift_topology(data: Data) → dict[source]#

Lift the topology of a graph to hypergraph domain by Mapper on Graphs.

Parameters:

datatorch_geometric.data.Data: The input data to be lifted.

Returns:

dict: The lifted topology.

topobench.transforms.liftings.graph2hypergraph.modularity_maximization_lifting module#

This module implements the ModularityMaximizationLifting class.

class topobench.transforms.liftings.graph2hypergraph.modularity_maximization_lifting.ModularityMaximizationLifting(num_communities=2, k_neighbors=3, **kwargs)[source]#

Bases: Graph2HypergraphLifting

Lifts graphs to hypergraph domain using modularity maximization and community detection.

This method creates hyperedges based on the community structure of the graph and k-nearest neighbors within each community.

Parameters:

num_communitiesint, optional: The number of communities to detect. Default is 2.
k_neighborsint, optional: The number of nearest neighbors to consider within each community. Default is 3.
**kwargsoptional: Additional arguments for the base class.

detect_communities(b)[source]#

Detect communities using spectral clustering on the modularity matrix.

Parameters:

btorch.Tensor: The modularity matrix.

Returns:

torch.Tensor: The community assignments for each node.

kmeans(x, n_clusters, n_iterations=100)[source]#

Perform k-means clustering on the input data.

Note: This implementation uses random initialization, so results may vary between runs even for the same input data.

Parameters:

xtorch.Tensor: The input data to cluster.
n_clustersint: The number of clusters to form.
n_iterationsint, optional: The maximum number of iterations. Default is 100.

Returns:

torch.Tensor: The cluster assignments for each input point.

lift_topology(data: Data) → dict[source]#

Lift the graph topology to a hypergraph based on community structure and k-nearest neighbors.

Parameters:

datatorch_geometric.data.Data: The input graph data.

Returns:

dict: A dictionary containing the incidence matrix of the hypergraph, number of hyperedges, and the original node features.

modularity_matrix(data)[source]#

Compute the modularity matrix B of the graph.

B_ij = A_ij - (k_i * k_j) / (2m)

Parameters:

datatorch_geometric.data.Data: The input graph data.

Returns:

torch.Tensor: The modularity matrix B.

Module contents#

Graph2HypergraphLifting module with automated exports.

class topobench.transforms.liftings.graph2hypergraph.ExpanderGraphLifting(node_degree: int, **kwargs)#

Bases: Graph2HypergraphLifting

Lift graphs to expander (hyper)graph. More precisely, the expander is a random Ramanujan graph.

Parameters:

node_degreeint: The desired node degree of the expander graph. Must be even.
**kwargsoptional: Additional arguments for the class.

lift_topology(data: Data) → dict#

Lift the topology of a graph to an expander hypergraph.

Parameters:

datatorch_geometric.data.Data: The input data to be lifted.

Returns:

dict: The lifted topology.

class topobench.transforms.liftings.graph2hypergraph.Graph2HypergraphLifting(**kwargs)[source]#

Bases: GraphLifting

Abstract class for lifting graphs to hypergraphs.

Parameters:

**kwargsoptional: Additional arguments for the class.

class topobench.transforms.liftings.graph2hypergraph.HypergraphFormanRicciCurvatureLifting(network_type: str = 'weighted', threshold_type: str = 'quantile', threshold_direction: str = 'above', threshold: float = 0.1, **kwargs)#

Bases: Graph2HypergraphLifting

Lift graphs to hypergraph domain using Forman-Ricci curvature based backbone estimation.

Parameters:

network_typestr, optional: Network type may be weighted or unweighted. Default is “weighted”.
threshold_typestr, optional: Type of threshold (either based on quantile or absolute). Default is “quantile”.
threshold_directionstr, optional: Direction whether to prune values above or below threshold. Default is “above”.
thresholdfloat, optional: Absolute value or quantile to estimate cutoff threshold from Forman-Ricci curvature distribution to prune network and reveal backbone. Default is 0.1.
**kwargsdict, optional: Additional arguments for the class.

lift_topology(data: Data) → dict#

Lift the topology of a graph to hypergraph domain using Forman-Ricci curvature based backbone estimation.

Parameters:

datatorch_geometric.data.Data: The input data to be lifted.

Returns:

dict: The lifted topology.

class topobench.transforms.liftings.graph2hypergraph.HypergraphKHopLifting(k_value=1, **kwargs)#

Bases: Graph2HypergraphLifting

Lift graph to hypergraphs by considering k-hop neighborhoods.

The class transforms graphs to hypergraph domain by considering k-hop neighborhoods of a node. This lifting extracts a number of hyperedges equal to the number of nodes in the graph.

Parameters:

k_valueint, optional: The number of hops to consider. Default is 1.
**kwargsoptional: Additional arguments for the class.

lift_topology(data: Data) → dict#

Lift a graphs to hypergraphs by considering k-hop neighborhoods.

Parameters:

datatorch_geometric.data.Data: The input data to be lifted.

Returns:

dict: The lifted topology.

class topobench.transforms.liftings.graph2hypergraph.HypergraphKNNLifting(k_value=1, loop=True, **kwargs)#

Bases: Graph2HypergraphLifting

Lift graphs to hypergraph domain by considering k-nearest neighbors.

Parameters:

k_valueint, optional: The number of nearest neighbors to consider. Must be positive. Default is 1.
loopbool, optional: If True the hyperedges will contain the node they were created from.
**kwargsoptional: Additional arguments for the class.

Raises:

ValueError: If k_value is less than 1.
TypeError: If k_value is not an integer or if loop is not a boolean.

lift_topology(data: Data) → dict#

Lift a graph to hypergraph by considering k-nearest neighbors.

Parameters:

datatorch_geometric.data.Data: The input data to be lifted.

Returns:

dict: The lifted topology.

class topobench.transforms.liftings.graph2hypergraph.HypergraphKernelLifting(graph_kernel='heat', feat_kernel='identity', C='prod', fraction=0.5, **kwargs)#

Bases: Graph2HypergraphLifting

Lift graphs to hypergraph domain by the kernel over graphs (features can be included).

Parameters:

graph_kernelstr or callable: The kernel function to be applied to the graph topology, if a string, it specifies a predefined kernel type. Currently, only “heat” is supported. If a callable, it should be a function that takes the graph Laplacian and additional kwargs as input and returns a kernel matrix.
feat_kernelstr or callable: The kernel function to be applied to the features, if a string, it specifies a predefined kernel type. Currently, only “identity” is supported. If a callable, it should be a function that takes the features and additional kwargs as input and returns a kernel matrix.
Cstr or callable: Default is “heat”.
fractionfloat: The fraction of the kernel to be considered for the hypergraph construction. Default is 0.5.
**kwargsoptional: Additional arguments for the class.

lift_topology(data: Data) → dict[str, Tensor]#

Lift the topology of a graph to hypergraph domain by considering the kernel over vertices or alternatively features.

Parameters:

datatorch_geometric.data.Data: The input data to be lifted.

Returns:

typing.Dict[str, torch.Tensor]: The lifted topology.

Raises:

ValueError: if the input is incomplete or in incorrect format.

class topobench.transforms.liftings.graph2hypergraph.MapperLifting(filter_attr='laplacian', resolution=10, gain=0.3, filter_func=None, **kwargs)#

Bases: Graph2HypergraphLifting

Lift graphs to hypergraph domain using a Mapper construction for CC-pooling.

Parameters:

filter_attrstr, optional: Name of the filter functional to filter data to 1-dimensional subspace. The filter attribute can be “laplacican”, “svd”, “pca”, “feature_sum”, “position_sum”. You may also define your own filter_attr string if the filter_func parameter is defined. Default is “laplacian”.
resolutionint, optional: The number of intervals to construct the MapperCover. Default is 10.
gainfloat, optional: The percentage of overlap between consectutive intervals in MapperCover and should be a value between 0 and 0.5. Default is 0.3.
filter_funcobject, optional: Filter function used for Mapper construction. Self defined lambda function or transform to filter data. Function must output an (n_sample, 1) Tensor. If filter_func is not None, user must define filter_attr as a string not already listed above. Default is None.
**kwargsoptional: Additional arguments for the class.

Attributes:

filtered_datadict: Filtered data used to compute the Mapper lifting. Dictionary is of the form {filter_attr: filter_func(data)}.
cover(k, resolution) boolean Tensor: Mask computed from the MapperCover class to compute the Mapper lifting with k < n_sample.
clustersdict: Distinct connected components in each cover set computed after fitting the Mapper cover. Dictionary has integer keys and tuple values of the form (cover_set_i, nodes_in_cluster). Each cluster is a rank 2 hyperedge in the hypergraph.