topobench.transforms.liftings.graph2hypergraph package#

Graph2HypergraphLifting module with automated exports.

class ExpanderGraphLifting(node_degree, **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.

__init__(node_degree, **kwargs)#

lift_topology(data)#

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 Graph2HypergraphLifting(**kwargs)#

Bases: GraphLifting

Abstract class for lifting graphs to hypergraphs.

Parameters:

**kwargsoptional: Additional arguments for the class.

__init__(**kwargs)#

class HypergraphFormanRicciCurvatureLifting(network_type='weighted', threshold_type='quantile', threshold_direction='above', threshold=0.1, **kwargs)#

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.

__init__(network_type='weighted', threshold_type='quantile', threshold_direction='above', threshold=0.1, **kwargs)#

lift_topology(data)#

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 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.

__init__(k_value=1, **kwargs)#

lift_topology(data)#

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 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.

__init__(k_value=1, loop=True, **kwargs)#

lift_topology(data)#

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 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.

__init__(graph_kernel='heat', feat_kernel='identity', C='prod', fraction=0.5, **kwargs)#

lift_topology(data)#

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.

class 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.

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.

__init__(filter_attr='laplacian', resolution=10, gain=0.3, filter_func=None, **kwargs)#

lift_topology(data)#

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.

class ModularityMaximizationLifting(num_communities=2, k_neighbors=3, **kwargs)#

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.

__init__(num_communities=2, k_neighbors=3, **kwargs)#

detect_communities(b)#

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)#

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)#

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)#

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.

topobench.transforms.liftings.graph2hypergraph package#

Submodules#