RaftGP: Random Fast Graph Partitioning

We first extract informative features from the key components regarding graph structures in classic GP objectives. For NCut minimization defined in (2), ${\bf{M}}\equiv{\bf{D}}^{-0.5}{\bf{A}}{\bf{D}}^{-0.5}$ in the Laplacian matrix ${\bf{L}}$ is used to describe the graph topology. For modularity maximization, the modularity matrix ${\bf{Q}}$ in (4) is the primary component regarding graph structures.

In particular, $\{{\bf{M}},{\bf{Q}}\}$ can be considered as a reweighting of the original neighbor structures described by the adjacency matrix ${\bf{A}}$, where the similarity between $({\bf{M}}_{i,:},{\bf{M}}_{j,:})$ (or $({\bf{Q}}_{i,:},{\bf{Q}}_{j,:})$) indicates the neighbor similarity between nodes $(v_{i},v_{j})$. In general, nodes $(v_{i},v_{j})$ with a higher neighbor similarity (i.e., denser local linkage) are more likely to be partitioned into the same block. Hence, we believe that $\{{\bf{M}},{\bf{Q}}\}$ encode key characteristics about the community structures of a graph. Tian et al. [20] and Yang et al. [21] have also validated the potential of ${\bf{M}}$ and ${\bf{Q}}$ to derive community-preserving embeddings via deep auto-encoders. Instead of using auto-encoders, we propose a more efficient strategy to extract community-preserving features (denoted by ${\bf{Y}}\in\mathbb{R}^{N\times L}$) from $\{{\bf{M}},{\bf{Q}}\}$, with the feature dimensionality $L\ll N$.

Since most real-world graphs have sparse topology, ${\bf{M}}$ can be treated as a sparse matrix. However, ${\bf{Q}}$ is still a dense matrix. To fully utilize the sparsity of topology, we introduce a reduced modularity matrix $\bf{\tilde{Q}}\in\mathbb{R}^{N\times N}$, where ${\bf{\tilde{Q}}}_{ij}={\bf{Q}}_{ij}$ if $(v_{i},v_{j})\in E$ and ${\bf{\tilde{Q}}}_{ij}=0$ otherwise. Although the reduction of ${\bf{Q}}$ may lose some information, our experiments demonstrated that ${\bf{\tilde{Q}}}$ is enough to derive informative community-preserving embeddings to support high-quality GP.

Let ${\bf{X}}\in\{{\bf{M}},{\bf{\tilde{Q}}}\}$ be the structural component from NCut minimization or modularity maximization, which induces two variants of RaftGP. We extract the features ${\bf{Y}}$ via

where ${\bf{Y}}_{i,:}$ is the extracted feature of node $v_{i}$. Concretely, (5) is the Gaussian random projection [14] of ${\bf{X}}\in\mathbb{R}^{N\times N}$, an efficient dimension reduction technique that can preserve the geometry structures (e.g., in terms of distances) of input features in finite-dimensional $l_{1}$ [22] and $l_{2}$ [23] spaces with rigorous theoretical guarantees. For instance, nodes $(v_{i},v_{j})$ with close $({\bf{X}}_{i,:},{\bf{X}}_{j,:})$ are guaranteed to have close $({\bf{Y}}_{i,:},{\bf{Y}}_{j,:})$.

Since ${\bf{X}}$ is sparse, the time complexity of random projection is $O(|E|L)$ by using the sparse-dense matrix multiplication. Given a graph ${G}$, the complexities to compute ${\bf{M}}$ and ${\bf{\tilde{Q}}}$ are both $O(|E|)$. In summary, the overall complexity of the random feature extraction step is $O(|E|L)$.

Although the extracted features (described by ${\bf{Y}}\in\mathbb{R}^{N\times L}$) have the initial ability to encode characteristics about community structures, we derive the final community-preserving embeddings (denoted by ${\bf{Z}}\in\mathbb{R}^{N\times d}$) by feeding ${\bf{Y}}$ into a multi-layer GNN, which further enhances the extracted features via the feature aggregation of GNN while reducing the feature dimensionality to $d<L$. We adopt GCN [24] to build the multi-layer GNN because it is easy to implement and has a low complexity of feature aggregation.

Let ${\bf{Z}}^{(k-1)}\in\mathbb{R}^{N\times L_{k-1}}$ and ${\bf{Z}}^{(k)}\in\mathbb{R}^{N\times L_{k}}$ be the input and output of the $k$-th GNN layer, where ${\bf{Z}}^{(0)}={\bf{Y}}$; $L_{k-1}$ and $L_{k}$ are the input and output feature dimensionality. The $k$-th GNN layer can be described as

where ${\bf{Z}}_{i,:}^{(k)}$ is the (intermediate) representation of node $v_{i}$; $f_{\rm{act}}(\cdot)$ is an activation function to be specified (e.g., tanh in our implementation); ${\bf{\hat{A}}}\equiv{\bf{A}}+{\bf{I}}_{N}$ is the adjacency matrix with self-edges; ${\bf{\hat{D}}}$ is the degree diagonal matrix of ${\bf{\hat{A}}}$; ${\bf{W}}^{(k)}\in\mathbb{R}^{L_{k-1}\times L_{k}}$ is a trainable parameter. In particular, ${\bf{Z}}_{i,:}^{(k)}$ is the non-linear aggregation (i.e., weighted mean) of features w.r.t. $\{v_{i}\}\cup{\mathop{\rm N}\nolimits}({v_{i}})$ from the previous layer, with ${\mathop{\rm N}\nolimits}({v_{i}})$ as the neighbor set of $v_{i}$. The feature aggregation forces nodes $(v_{i},v_{j})$ with similar neighbor sets $({\mathop{\rm N}\nolimits}({v_{i}}),{\mathop{\rm N}\nolimits}({v_{j}}))$ (i.e., dense local linkage) to have similar features $({\bf{Z}}_{i,:}^{(k)},{\bf{Z}}_{j,:}^{(k)})$, thus enhancing the ability to encode characteristics regarding community structures. The multi-layer structure can further extend the feature aggregation to the local topology induced by multi-hop neighbors.

Before feeding ${\bf{Z}}^{(k)}$ into the next GNN layer, we recommend conducting the row-wise $l_{2}$-normalization via ${\bf{Z}}_{i,:}^{(k)}\leftarrow{\bf{Z}}_{i,:}^{(k)}/|{\bf{Z}}_{i,:}^{(k)}{|_{2}}$, which controls the scale of the (intermediate) representation of each node $v_{i}$. We treat the normalized representations from the last GNN layer (denoted by ${\bf{Z}}\in\mathbb{R}^{N\times d}$) as the final community-preserving embeddings. In the rest of this paper, we use ${\bf{z}}_{i}\in\mathbb{R}^{d}$ to represent the embedding of $v_{i}$.

The powerful inference abilities of some state-of-the-art GNN-based GP methods (e.g., ClusterNet [17], LGNN [18], and ICD [19]) rely on the offline training of model parameters (e.g., $\{{\bf{W}}^{(k)}\}$) via the time-consuming gradient descent.

Inspired by the efficient random projection described in (5), we consider an extreme design of RaftGP, where we do not apply any training procedures to the multi-layer GNN. Our experiments demonstrate that one feedforward propagation through a randomly initialized GNN without any training is enough for RaftGP to derive informative community-preserving embeddings and support high-quality GP. A reasonable interpretation is that each GNN layer described in (6) can be considered as a special random projection similar to (5). In the $k$-th layer, the geometric properties (e.g., relative distances) between the aggregated representations (i.e., ${{{\bf{\hat{D}}}}^{-0.5}}{\bf{\hat{A}}}{{{\bf{\hat{D}}}}^{-0.5}}{{\bf{Z}}^{(k-1)}}$) can be preserved with theoretical guarantees, even though it is multiplied by a random matrix ${\bf{W}}^{(k)}$ and mapped to another space with lower dimensionality. The nonlinear activation and $l_{2}$-normalization will also not largely change the geometric properties.

For the GNN feature aggregation in (6), one can treat ${\bf{\hat{D}}}^{-0.5}{\bf{\hat{A}}}{\bf{\hat{D}}}^{-0.5}$ as a sparse matrix and use the efficient sparse-dense matrix multiplication for implementation. In this setting, the complexity of GNN feedforward propagation is $O(|E|L+NL{L_{1}}+|E|{L_{1}}+N{L_{1}}{L_{2}}+\cdots)=O(|E|L+NL{L_{1}})$, where we usually set $L_{k}>L_{k+1}$. Assume that $\{L,L_{1}\}$ have the same magnitude with the embedding dimensionality $d$. The complexity of the embedding derivation step is $O(|E|d+Nd^{2})$.

Graph embedding is a unified framework that can support various inference tasks by combining the derived embeddings $\{{\bf{z}}_{i}\}$ with specific downstream modules. To enable RaftGP to support the GP task stated in Definition 1, the model selection problem (i.e., determining a proper number of blocks $K$) is critical. We introduce an efficient hierarchical model selection algorithm based on a novel local modularity metric.

Different from the standard modularity on $G[U]$ which considers only edges induced by $U$, local modularity also takes account of the edges from $U$ to $V-U$. When partitioning a subgraph, local modularity keeps its interaction with the remaining graph and thus ensures that we do not further partition a true block into sub-blocks.

Our hierarchical model selection procedure based on the local modularity metric is summarized in LABEL:alg:recursion. We demonstrate it by an example (Fig. 1). For a set of nodes $U\subseteq V$ to be partitioned, we first compute the local modularity $m_{1}$ that treats ${U}$ as a single block (i.e., Line 1). The $K$Means clustering algorithm is then applied to embeddings $\{{\bf{z}}_{i}|v_{i}\in U\}$ (i.e., Line 1), which tries to divide ${U}$ into two blocks $\{U_{1},U_{2}\}$ based on the distances between embeddings. One can also compute the local modularity $m_{2}$ w.r.t. the partition of $\{U_{1},U_{2}\}$ (i.e., Line 1). We then introduce a heuristic stopping rule based on the sizes of $\{U_{1},U_{2}\}$ and values of $\{m_{1},m_{2}\}$. Concretely, we adopt the set $U$ as a new block, if $|U_{1}|$ or $|U_{2}|$ are less than or equal to a threshold $\epsilon$ (i.e., $\epsilon=5$ in our implementation) or $m_{1}>m_{2}$ (i.e., Lines 1,1). Otherwise, we repeat the aforementioned procedures to further partition $U_{1}$ and $U_{2}$ (i.e., Lines 1, 1).

In particular, the stopping rule in Line 1 can effectively avoid partitioning $U$ into too small or imbalanced blocks (e.g., with $|U_{1}|<\epsilon$ or $|U_{2}|<\epsilon$). Consistent with the modularity maximization objective, it also tries to avoid the decrease of modularity after the partitioning.

The complexity of this algorithm depends on the quality of the embedding. If the embedding is of good quality so that the $K$Means algorithm always partitions the node set $U$ into two balanced sets, we need to run the $K$Means algorithm on a total of $O(N\log N)$ nodes. The complexity in this case is $O(NT\log N)$ where $T$ is the number of iterations in $K$Means. In the worst case, the set $U$ is always partitioned into a single block and the remaining blocks. In this case, the $K$Means algorithm is run on $O(KN)$ nodes where $K$ is the number of blocks. The complexity in this case is $O(KTN)$.

The aforementioned designs of RaftGP can be easily extended to streaming graphs. Let $E^{\prime}$ be the set of newly added edges in the streaming setting. Since the addition of $E^{\prime}$ only changes the degrees of at most $2|E^{\prime}|$ nodes, one can use an incremental strategy to update the input statistics ${\bf{X}}\in\{{\bf{M}},{\bf{\tilde{Q}}}\}$ with a complexity of $O(|E^{\prime}|)$. Let $V^{\prime}$ be the set of nodes incident to $E^{\prime}$. Note that only the multi-hop neighbors of $V^{\prime}$ (denoted by $V^{\prime\prime}$) will participate in the GNN feature aggregation of $V^{\prime}$. Let $E^{\prime\prime}$ be the set of edges induced by $V^{\prime}\cup V^{\prime\prime}$. One can also incrementally update embeddings $\{{\bf{z}}_{i}\}$ via the random projection and GNN feedforward propagation induced by $(V^{\prime}\cup V^{\prime\prime},E^{\prime\prime})$. Therefore, the overall complexity of embedding derivation is $O(|E^{\prime\prime}|d+|V^{\prime}\cup V^{\prime\prime}|d)$, where we usually have $|E^{\prime\prime}|<|E|$ and $|V^{\prime}\cup V^{\prime\prime}|<N$.

For the hierarchical model selection, one can formulate the partitioning procedure as a tree, where each tree node represents a subset of nodes (i.e., $U\subseteq V$) to be partitioned; the children of this tree node represent a partition of $U$ (e.g., $(U_{1},U_{2})$); each leaf corresponds to a block $C_{r}$. The tree structure allows one to update only a tree path (path from a leaf to the root) once the embedding ${\bf{z}}_{i}$ of node $v_{i}$ is updated.

The average quality metrics and runtime over five generated graphs w.r.t. each setting of $N$ are reported in Table II, where the quality metrics of RaftGP are in bold if they perform the best; OOT and OOM denote the out-of-time and out-of-memory exceptions. In addition to the total runtime, Table III reports the time of (i) random feature extraction, (ii) embedding derivation (i.e., GNN feedforward propagation), and (iii) model selection for RaftGP.

Note that RaftGP does not include any training procedures. Surprisingly, both variants of RaftGP can achieve the best quality metrics in most cases, significantly outperforming MC-SBM, GMod, SMod, and BP-SBM. It verifies our discussions in Section III-B that one feedforward propagation through a random initialized GNN is a special random projection with the geometric properties of the aggregated features preserved, and thus can still derive informative embeddings. Although Par-SBM has close quality and slightly faster runtime compared with RaftGP when $N$ is small, our methods can achieve much better quality metrics in cases with larger $N$s. In this sense, we believe that RaftGP can achieve a better trade-off between quality and efficiency especially when $N$ is large.

On all the datasets, the two variants of RaftGP have close quality metrics with best performance. It validates our motivation of using ${\bf{M}}$ and ${\bf{\tilde{Q}}}$ (extracted from the NCut minimization and modularity maximization objectives) as informative statistics for the derivation of community-preserving embeddings.

As in Table III, model selection is the major bottleneck for both variants of RaftGP, which accounts for more than $80$% of the total runtime. It implies that the random feature extraction and GNN-based embedding derivation are efficient designs for RaftGP with runtime better than Par-SBM.

We also validated the effects of (i) random feature extraction and (ii) embedding derivation (with GNN) of RaftGP by removing the corresponding components. In case (i), ${\bf{X}}\in\{{\bf{M}},{\bf{\tilde{Q}}}\}$ was directly used as the input of GNN (without random projection). In case (ii), we directly treated the features ${\bf{Y}}$ derived via random projection as the embedding input of model selection (without using GNN). Results of our ablation study on all the datasets are shown in Table IV.

Although case (i) can achieve the quality competitive to the original RaftGP model when $N$ is small, we encounter the OOM exception when $N\geq$ 5E4. It indicates that the Gaussian random projection can reduce the feature dimensionality while preserving the key geometric properties of input features as discussed in Section III-A. Moreover, the GNN-based embedding derivation is essential to ensure the high quality of RaftGP because there are significant quality declines in case (ii) with the increase of $N$. It verifies our discussions in Section III-B that the feature aggregation of GNN can enhance the ability of RaftGP to preserve community structures.