thgsp.bga¶

Harary ¶

Harary bipartite decomposition

Parameters:

A (SparseTensor) – The adjacency matrix
vtx_color (array_like, optional) – All valid type for np.asarray() is acceptable, including torch.Tensor on cpu. If None, this function will invoke thgsp.alg.dsatur() silently.
threshold (float, optional)

Returns:

bptG (List[lil_matrix]) – An array consisting of M bipartite subgraphs formatted as scipy.sparse.lil_matrix
beta (array) – beta[:,i] is the bipartite set indicator of i-th subgraph
beta_dist (array) – A table showing the relationship between beta and channels
new_vtx_color (array) – The node colors
mapper (dict) – Map new_vtx_color to the original ones. For example mapper={1:2, 2:3, 3:1} map 1,2 and 3-th color to 2,3 and 1, respectively.

OSGLM ¶

The oversampled bipartite graph approximation method proposed in [1]

Parameters:

A (SparseTensor) – The adjacent matrix of graph.
lc (int) – The ordinal of color marking the boundary such that all nodes with a smaller color ordinal are grouped into the low-pass channel while those with a larger color ordinal are in the high-pass channel.
vtx_color (iter) – The graph coloring result

Returns:

bptG (lil_matrix) – The oversampled graph(with additional nodes)
beta (np.ndarray)
append_nodes (np.ndarray) – The indices of those appended nodes
vtx_color (np.ndarray) – The node colors

References

admm_bga(A: Tensor, M: int = 1, alpha: float = 100.0, metric: str = 'fro21', cut_edge: bool = True, B0: Tensor | None = None, convergence_marker: float = 1e-08, check_step: int = 1000, verbose: bool = False, nonnegative: bool = True, rho: float = 0.01, eta: float = 1.01, max_iter: int = 100000, early_stop: bool = False, max_rho: float = 10000000000.0) → Tensor[source]¶

The program is to find the bipartite graph approximation via solving the following optimization problem [2] .

\[\begin{split}\begin{array}{ll} \min _{\left\{\mathbf{B}_{i}\right\}} & \sum_{i=1}^{L}\left\|\mathbf{ A}-\mathbf{B}_{i}\right\|_{F}^{2}+\alpha \sum_{i=1}^{L} \sum_{j \neq i} \operatorname{Tr}\left\{\mathbf{B}_{i}^{T} \mathbf{B}_{j}\right\} \\ \text { s.t. } & \mathbf{B}_{i} \in \mathcal{B} \end{array}\end{split}\]

Note

This algorithm does NOT guarantee bipartite output graphs in some cases. Nevertheless, the output graphs are almost bipartite,i.e., only a few edges violate the bipartiteness. One can use is_bipartite_fix() to fix the output under such circumstances.

Parameters:

A (Tensor(N x N)) – N is the number of graph nodes
M (int, optional) – The number of bipartite graphs to learn
alpha (float,optional) – The parameter which controls the orthogonality among learnt bipartite graphs
metric (str,optional) – The error metric between the learned bipartite graphs and the original graph
cut_edge (bool,optional) – If True, cut the edges in the learned bipartite graphs that not exist in the original graph
B0 (Tensor,optional) – The initialization of B
convergence_marker (float,optional) – the procedure converges if the error between B and A < this value
check_step (int,optional) – the step interval to display iteration information
verbose (bool,optional)
nonnegative (bool,optional) – If True, allow negative edge weight in the learned bipartite graphs B
rho (float,optional) – A step argument
eta (float,optional) – The update factor of rho
max_iter (int,optional) – The max ADMM iteration times
early_stop (bool,optional) – If True, the procedure will return B once all learned graphs are bipartite
max_rho (float,optional)

Returns:

B – The learnt bipartite subgraph(s)

Return type:

Tensor(M,N,N)

References

MFS ¶

amfs(A: SparseTensor, Sigma=None, level=None, delta=0.1, thresh_kld=1e-06, priority=True, verbose=False) → Tuple[List[lil_matrix], ndarray][source]¶

AMFS bipartite approximation for graph wavelet signal processing [3].

Parameters:

A (SparseTensor) – The adjacency matrix.
Sigma (scipy.spmatrix, optional) – The covariance matrix specified by the Laplacian matrix L. If None, \(\Sigma^{-1}=L+\delta I\)
level (int, optional) – The number of bipartite subgraphs, i.e., the decomposition level. If None, \(level=\lceil log_2( \mathcal{X}) \rceil\), where \(\mathcal{X}\) is the chromatic number of A.
delta (float, optional) – \(1/\delta\) is interpreted as the variance of the DC compnent. Refer to [4] for more details.
thresh_kld (float, optional) – Threshold of Kullback-Leibler divergence to perform AMFS decomposition.
priority (bool,optional) – If True, KLD holds priority.
verbose (bool,optional)

Returns:

bptG (List[SparseTensor]) – The bipartite subgraphs.
beta (Tensor(N, M)) – The indicator of bipartite sets

References

Greedy ¶

bga Utils ¶

beta2channel_mask(beta)[source]¶

Generate a (2^M, N) bool mask tensor to indicate which channel(color group) one node belongs to. All channels have disjoint node sets and hence the sum along the channel dimension returns a all-one(True) (N,) tensor.

Note

This function is a common approach to generate channel mask for multi-channel wavelet filterbank. Either coloring or numerical based bipartite approximation algorithm can employ this function.

Parameters:

beta (BoolTensor(N,M)) – Bipartite partition indicator tensor. N and M are the node and bipartite subgraph numbers, respectively.

Returns:

mask (BoolTensor(2**M,N)) – The indices of True in i-th row are nodes whose signal will be kept in i-th channel.
beta_dist (array(2**M,M))) – An array, see the doc of thgsp.filters.QmfCore for the details.

beta2color_group(beta, th=True)[source]¶

Actually, beta2channel_group is more exact since “color” here is not exact graph coloring. However we can take it as an approximation of graph coloring.

Parameters:

beta (BoolTensor(N,M)) – Bipartite partition indicator tensor. N and M are the node and bipartite subgraph numbers, respectively.
th (bool, optional) – If True, the value of returned dict is Tensor otherwise array.

Returns:

color_group (dict) – color_group[i] is a LongTensor (or array) of node indices colored with i-th color.
beta_dist (array) – An array, see the doc of thgsp.filters.QmfCore for the details.

beta_dist2channel_name(beta_dist, reverse=False)[source]¶

Generate the channel names(\(L\) or H) for each channel according to beta_dist. By default, 0 and 1 means H and L, respectively.

Parameters:

beta_dist (ByteTensor(2^M,M)) – An array, see the doc of thgsp.filters.Qmf for the details.
reverse (bool,optional) – If True, 0 means L.

Returns:

An array composed by H and L. Each row corresponds to one channel.

Return type:

array

bipartite_mask(bt, sparse=True)[source]¶

Generate a bool mask matrix which can extract a bipartite subgraph from any graph (represented by a matrix) .

Parameters:

bt (BoolTensor, array) – The indicator of two bipartite sets. All nodes within a same bipartite set is characterized by a same bool value, e.g.,True. Shape: (N,), N is the number of graph nodes.
sparse (bool) – If True, return lil_matrix.

Return type:

lil_matrix,

cohere_color_idx(colors, color_group)[source]¶

Parameters:

colors (Iterable) – Indices(ordinals) of colors. np.array([0,2,1]) means the 0,2,1-th color
color_group (dict) – color_group[i] is a np.ndarray of node indices colored with i-th color.

Returns:

A Composed by node ordinals which are colored by any one among the colors.

Return type:

LongTensor

is_bipartite_fix_th(A: Tensor, fix_flag: bool = False) → Tuple[bool, List[int], Tensor][source]¶

Check if a graph is bipartite using BFS-based 2-color coloring and furthermore can fix a graph to a bipartite one by deleting edges bridging two nodes colored with a same color.

Parameters:

A (Tensor) – The adjacency matrix
fix_flag (bool,optional) – If True, fix A to a bipartite graph by zeroing some elements in-place.

Returns:

flag (bool) – If True, the returned adjacency matrix represents a bipartite graph
vxt_color (list) – A list recording the vertex colors which are all 1 or 0.
A (Tensor) – The adjacency matrix of returned graph.

thgsp.bga¶

Harary¶

OSGLM¶

ADMM-based¶

MFS¶

Greedy¶

bga Utils¶

Harary ¶

OSGLM ¶

ADMM-based ¶

MFS ¶

Greedy ¶

bga Utils ¶