Mixed-Order Spectral Clustering for Networks
Yan Ge Haiping Lu Pan Peng








Preprint
Shell et al.: Bare Demo of IEEEtran.cls for IEEE Journals











Mixed-Order Spectral Clustering for Networks
    Yan Ge, Haiping Lu, and Pan Peng
Yan Ge, Haiping Lu and Pan Peng are with the Department of Computer Science, University of Sheffield, U.K. (e-mail: yge5@sheffield.ac.uk, h.lu@sheffield.ac.uk and p.peng@sheffield.ac.uk). 
    December 30, 2023
=================================================================================================================================================================================================================================




Clustering is fundamental for gaining insights from complex networks, and spectral clustering (SC) is a popular approach. Conventional SC focuses on second-order structures (e.g., edges connecting two nodes) without direct consideration of higher-order structures (e.g., triangles and cliques). This has motivated SC extensions that directly consider higher-order structures. However, both approaches are limited to considering a single order. This paper proposes a new Mixed-Order Spectral Clustering (MOSC) approach to model both second-order and third-order structures simultaneously, with two MOSC methods developed based on Graph Laplacian (GL) and Random Walks (RW). MOSC-GL combines edge and triangle adjacency matrices, with theoretical performance guarantee. MOSC-RW combines first-order and second-order random walks for a probabilistic interpretation. We automatically determine the mixing parameter based on cut criteria or triangle density, and construct new structure-aware error metrics for performance evaluation. Experiments on real-world networks show 1) the superior performance of two MOSC methods over existing SC methods, 2) the effectiveness of the mixing parameter determination strategy, and 3) insights offered by the structure-aware error metrics.




Spectral clustering, network analysis, higher-order structures, mixed-order structures.




  










§ INTRODUCTION

Networks
 (a.k.a. graphs) are important data structures that abstract relations between discrete objects, such as social networks and brain networks <cit.>. A network is composed of nodes and edges representing node interactions. Clustering is an important and powerful tool in analysing network data, e.g., for community detection <cit.>. 

Clustering aims to
divide the data set into clusters (or communities) such that the nodes assigned to a particular cluster are similar or well connected in some predefined sense <cit.>. 
It helps us reveal functional groups hidden in data.
As a popular clustering method, conventional spectral clustering (SC) <cit.> encodes 
pairwise similarity into an adjacency matrix.
Such encoding inherently restricts SC to second-order structures <cit.>, such as undirected or directed edges connecting two nodes.[Edges are considered as first-order structures in <cit.> but second-order structures in <cit.>. We follow the terminologies in the latter <cit.> so that the “order” here refers to the number of nodes involved in a particular structure.] 
However, in many real-world networks, the minimal and functional structural unit of a network is not a simple edge but a small network subgraph (a.k.a. motif) that involves more than two nodes <cit.>, which we call a higher-order structure. 

Higher-order structures consist of at least three nodes (e.g., triangles, 4-vertex cliques) <cit.>. 
It can directly capture interaction among three or more nodes.
When clustering networks, higher-order structures can be regarded as fundamental units and algorithms can be designed to minimise cutting them in partitioning.
Clustering based on higher-order structures can help us gain new insights and significantly improve our understanding of underlying networks.
For example, triangular structures, with three reciprocated edges connecting three nodes, play important roles in brain networks <cit.> and social networks <cit.>. 
More importantly, higher-order structures allow for more flexible modelling. For instance, considering directions of edges, there exist
13 different third-order structures,
but only two different second-order structures <cit.>. Thus, the application can drive which
third-order structures to be preserved. 

Thus, there are emerging interests in directly modelling higher-order structures in network clustering. These works can be grouped into four approaches: 1) The first approach constructs an affinity tensor to encode higher-order structures and then reduces it to a matrix <cit.>, followed by conventional SC <cit.>. These methods, such as tensor trace maximisation (TTM) <cit.>, are developed in a closely related problem of hypergraph clustering that considers “hyperedges” connecting multiple nodes. 2) The second approach develops higher-order SC by constructing a transition tensor based on random walks model and then reduces it to a matrix for conventional SC, such as tensor spectral clustering (TSC) <cit.>. 
3) The third approach uses a counting and reweighting scheme to capture higher-order structures and reveal clusters <cit.>, such as motif-based SC (MSC) <cit.>.[We have verified that TTM and MSC are equivalent, nevertheless.] 
4) The fourth approach is higher-order local clustering aiming to  reduce computation cost <cit.>, such as  High-Order Structure Preserving Local Clustering (HOSPLOC) <cit.>. 




However, it should be noted that most networks have both second-order and higher-order structures, e.g., the network in Fig. <ref>, and both can be important. Existing conventional and third-order SC methods model only either second-order or third-order structures, but not both, as shown in Figs. <ref> and <ref>, which fail to properly model the importance between nodes 2 and 3, and nodes 4 and 5, respectively. In Figs. <ref> and <ref>, each entry indicates the number of edges and triangles involving two nodes of Fig. <ref>.






In this paper, we propose a new Mixed-Order Spectral Clustering (MOSC) to preserve structures of different orders simultaneously, as in Fig. <ref>. For clear and compact presentation, we focus on two undirected unweighted structures: edges (second-order structures) and triangles (third-order structures). 
Further extensions can be developed for mixing more than two orders, and/or orders higher than three.


We summarise our four contributions as following:


  * Mixed-order models. 
We develop two MOSC models: one based on Graph Laplacian (GL) and the other based on Random Walks (RW). MOSC-GL combines edge and triangle adjacency matrices to define a mixed-order Laplacian, with its theoretical performance guarantee derived by proving a mixed-order Cheeger inequality. MOSC-RW combines first-order and second-order RW models for a probabilistic interpretation. The final clusters are obtained via a sweep cut procedure or k-means. See Sec. <ref> and Sec. <ref>. 

  * Automatic model selection.
There is only one hyperparameter in MOSC, i.e., the mixing parameter (ranging from 0 to 1). We propose cut-criteria-based and triangle-density-based strategies to automatically determine the best mixing parameter. See Sec. <ref>. 

  * Structure-aware error metrics. Existing works on higher-order structure clustering use evaluation metrics focused on mis-clustered nodes <cit.>. 
However, mis-clustered nodes do not have a monotonic relationship with mis-clustered structures so they may fail to reflect the errors in structures. Therefore, we propose  structure-aware error metrics to gain insights on the quality of structure preservation. See Sec. <ref>. 

  * Cut criterion. A cut criterion evaluates the quality of output clusters.
Therefore, we study seven different sweep cut criteria (both second and third orders) and propose a new one by defining mixed-order conductance. We also propose an optimal cut to study the lower bound of error metrics and model quality. See Secs. <ref> and <ref>.























§ PRELIMINARIES



 §.§ Notations

We denote scalars by lowercase letters, e.g., a, 
vectors by lowercase boldface letters, e.g., a, matrices by  uppercase  boldface, e.g., 𝐀, and tensors by calligraphic letters, e.g., A. 
Let G = (V, E) be an undirected unweighted graph (network) with V = {v_1, v_2, …, v_n} being the set of n vertices (nodes), i.e., n = |V|, and E being the set of edges connecting two vertices.


 §.§ Normalised Graph Laplacian

Let 𝐖∈ ℝ^n× n 
be an unweighted adjacency matrix of G  
where 𝐖(i,j) = 1 if (v_i, v_j) 
∈E, otherwise 𝐖(i,j) = 0.
The degree matrix 𝐃 is a diagonal matrix with diagonal entries 𝐃(i,i) = ∑_j=1^n𝐖(i,j), which is the degree of vertex v_i.
Let 𝐍=𝐃-𝐖 denote the Laplacian matrix of G. The normalised Laplacian of G is defined as:

    𝐋 =
    𝐃^-1/2𝐍𝐃^-1/2.



Let 𝐖_T be triangle adjacency matrix  of G with its entry (i, j) being the number of triangles containing vertices i and j, which leads to a  corresponding weighted graph G_T  <cit.>. 
Similarly, we can define the triangle Laplacian as 𝐍_T=𝐃_T - 𝐖_T and the normalised triangle Laplacian as:

    𝐋_T = 𝐃_T^-1/2𝐍_T𝐃_T^-1/2,

 where 𝐃_T(i,i) = ∑^n_j = 1𝐖_T(i,j).



 §.§ First-Order Random Walks for Second-Order Structures

We define a second-order transition matrix 𝐏 by normalising the adjacency matrix 𝐖 to represent edge structures as <cit.>:

    𝐏 = 𝐃^-1𝐖.

The entry 𝐏_ij represents the probability of jumping from vertex v_i to v_j in one step.
The transition matrix 𝐏
represents a random walk process on graph G<cit.>. 
From random walk perspective, SC can be interpreted as trying to find
a partition of the graph such that the random walk stays long within the same cluster and
seldom jumps between clusters <cit.>. 



 §.§ Second-Order Random Walks for Third-Order Structures

Benson <cit.> extend the above using a three-dimensional transition tensor to encode triangle structures. 
They firstly define a symmetric adjacency tensor  T∈ ℝ^n× n× n
such that the connectivity information for three vertices  
{v_i, v_j, v_k}∈V can be represented explicitly in this tensor. All entries in  T with a permutation
of indices i, j, k  have the same value (hence symmetric). Thus, T encodes triangle structures 
in G as: 

    T (i, j, k)={
    1       v_i, v_j, v_k  form a triangle,
    
    0       otherwise..

Next, they form a third-order transition tensor P as: 

    P (i, j, k) =
    T(i, j, k) / ∑_m=1^n T(i, m, k),

where ∑_m=1^n T(i, m, k) ≠ 0, and  1 ≤ i, j, k
≤ n. For ∑_m=1^n T(i, m, k) = 0, 
Benson <cit.> set P (i, j, k) to 1/n.

Here, the entries of P represent the transition probabilities of the second-order random walks.
Each vertex in V is considered a distinguishable state.
And probability of jumping to state i relies on the last two states j and k<cit.>.
This probabilistic interpretation implies that random walks uniformly choose state i that forms a triangle with 
j and k. However, analysing P is challenging, e.g., finding its eigenvectors is NP-hard <cit.>, so it is often reduced to a similarity matrix to apply conventional SC procedures <cit.>.



 §.§ Spectral Clustering Basics

Bi-partitioning SC (Algorithm <ref>) first constructs a  matrix 𝐁 to encode structures in the input graph G. It then computes a dominant eigenvector v of 𝐁, thus making use of its spectrum. Each entry of v corresponds to a vertex. Next, we sort vertices by the values v(i) (or appropriately normalised values) and consider the set T_u consisting of the first u vertices in the sorted list, for each 1≤ u≤ n-1. Then the algorithm finds S=min_T_uτ(T_u), called the sweep cut w.r.t. some cut criterion τ. Table <ref> lists eight cut criteria, both second and third orders (edge and triangle based). We omit G in the criterion notation τ(S;G) in the table.

Matrix 𝐁 is a crucial part of SC. Conventional (i.e., second-order) SC starts with the adjacency matrix 𝐖 of G encoding edges (as in Fig. <ref>) and defines 𝐁 as 𝐖, the Laplacian matrix, or their normalised versions <cit.>. Third-order SC typically starts with a third-order tensor T encoding triangles, which can be reduced to a matrix 𝐁 (as in Fig. <ref>) to apply Algorithm <ref>.








	





 §.§ Cheeger Inequalities and Cut Criteria
 Given G = (V, E) and a subset S⊆V, let S̅ denote the complement of S. Let cut_2(S;G)
denote the edge cut of S, i.e, the number of edges between S and S̅ in G. 
Let vol_2(S;G) denote the edge volume of S, i.e., the total degrees of
vertices in S, and assoc_2(S;G) is the total degrees in the subgrapgh induced by vertices in S. The edge conductance of S is defined as


    ϕ_2(S;G)=cut_2(S;G)/min{vol_2(S;G),vol_2(S̅;G)}.

Other popular edge-based cut criteria are shown in Table <ref> (left column).
The classical Cheeger inequality below relates the conductance of the sweep cut of SC to the minimum conductance value of the graph <cit.>. 

Let v be the second smallest eigenvector of 𝐋. Let T^* be the sweep cut of 𝐃^-1/2v w.r.t. cut criterion ϕ_2(·;G). It holds that  

    ϕ_2(T^*;G)≤2√(ϕ_2^*),

 where ϕ_2^* = min_S⊂V ϕ_2(S;G)
is the minimum conductance over any set of vertices. 



Let cut_3(S;G) denote the triangle cut of S, i.e., the number of triangles that have at least one endpoint in S and at least one endpoint in S̅, and let assoc_3(S;G) count the number of vertices in triangles in the subgraph induced by vertices in S. Let vol_3(S;G) denote the triangle volume of S, i.e., the number of triangle endpoints in S.
The triangle conductance <cit.> of S is defined as

    ϕ_3(S;G)=cut_3(S;G)/min{vol_3(S;G),vol_3(S̅;G)}.

  It is further proved in <cit.> that for any S⊂ V, ϕ_3(S;G)=ϕ_2(S;G_T), which leads to the following third-order Cheeger inequality.  Other popular triangle-based cut criteria are summarised in Table <ref> (right column).



 
Let v be the second smallest eigenvector of 𝐋_T. Let T^* denote the sweep cut of 𝐃^-1/2_Tv w.r.t. cut criteria ϕ_2(·;G_T). It holds that  

    ϕ_3(T^*;G) ≤ 4 √(ϕ_3^*),

 where ϕ_3^* = min_S⊂V ϕ_3(S;G).


			



§ PROPOSED MIXED-ORDER APPROACH

To model both edge and triangle structures simultaneously, we introduce a new Mixed-Order SC (MOSC) approach, with two methods based on Graph Laplacian (GL) and Random Walks (RW). MOSC-GL combines the edge and triangle adjacency matrices, 
which leads to a mixed-order Cheeger inequality to provide a theoretical performance guarantee. MOSC-RW is developed under the random walks framework to combine the first and second order random walks, providing a probabilistic interpretation. 
Next, we develop an automatic hyperparameter determination scheme and define new structure-aware error metrics. Finally, we present a way to examine the lower bound of the clustering errors. 






 §.§ MOSC Based on Graph Laplacian (MOSC-GL)


MOSC-GL introduces a mixed-order adjacency matrix W_X that linearly combines the edge adjacency matrix W and the triangle adjacency matrix W_T,
with a mixing parameter λ∈ [0,1].  W_X can be seen as a weighted adjacency matrix of a weighted graph G_X, on which we can apply conventional SC (Algorithm <ref>). Specifically, we first construct the matrix W_X and the corresponding diagonal degree matrix D_X as

    W_X   =    (1-λ)W_T+λW, 
    D_X   =    (1-λ)D_T+λD.



Let G_X denote an undirected weighted graph with adjacency matrix W_X, we can define a mixed-order Laplacian N_X and its normalised  version L_X as:

    N_X   =   D_X - W_X=(1-λ)N_T + λN, 
    L_X   =   D_X^-1/2N_XD_X^-1/2.

Then, we compute the eigenvector corresponding to the second smallest eigenvalue of  L_X and perform the sweep cut to find the partition with the smallest edge conductance in G_X. The MOSC-GL algorithm is summarised in  Algorithm <ref>.  







When λ=1, MOSC-GL is equivalent to SC by Ng et al. <cit.> and only considers  second-order structures.
When λ=0, MOSC-GL is equivalent to motif-based SC <cit.>. MOSC-GL maintains the advantages of traditional SC: computational efficiency,
ease of implementation and mathematical guarantee on the near-optimality of resulting clusters, which we formalise and prove in the following. 

Performance guarantee.
Given a graph G and a vertex set S, we define its mixed-order cut and volume as 

    cut_X (S;G) = (1-λ)cut_3 (S;G) + λ cut_2 (S;G),

and

    vol_X (S;G) = (1-λ)vol_3 (S;G)+λ vol_2 (S;G),

respectively. Then,  we define the mixed-order conductance of S as: 

    ϕ_X (S;G)= cut_X (S;G)/min(vol_X (S;G), vol_X(S̅;G)),

which generalises edge and triangle conductance. A partition with small ϕ_X (S;G) corresponds to clusters with rich edge and triangle structures within the same cluster while few both structures crossing clusters. 
Finding the exact set of nodes S with the smallest ϕ_X is computationally infeasible. Nevertheless, we can derive a performance guarantee for MOSC-GL to show that the output set obtained from Algorithm <ref> is a good approximation.
To prove Theorem <ref>, we need the following Lemma.


Let G  = (V, E) be an undirected, unweighted graph and let G_T be 
the weighted graph for the triangle adjacency matrix. Then for any S ⊂ V, it holds that

    cut_3(S;G)   =   1/2 cut_2(S;G_T), 
    
    vol_3(S;G)   =   1/2 vol_2(S;G_T).


 
 
Given an undirected graph G, let T^* denote the set outputted by MOSC-GL (Algorithm <ref>) w.r.t. the cut criterion ϕ_2(·;G_X). Let ϕ_X^*=min_S⊆ Vϕ_X(S;G) be the minimum mixed-order conductance over any set of vertices. Then it holds that
	
    ϕ_X(T^*;G)  ≤ 2√(2ϕ_X^*).



It suffices for us to prove that for any set S, 

    1/2ϕ_2(S;G_X)≤ϕ_X(S;G) ≤ 2 ϕ_2(S;G_X).


Assume for now that the inequality (<ref>) holds. By Lemma <ref>, the set T^* satisfies  ϕ_2(T^*;G_X)≤ 2√(ψ^*), where ψ^*=min_S⊆ Vϕ_2(S;G_X). Let R be the set with ϕ_X(R;G)=ϕ_X^*=min_S⊆ Vϕ_X(S;G). Then by inequality (<ref>), we have 

    ϕ_X(T^*;G)   ≤    2ϕ_2(T^*;G_X)≤ 2√(ψ^*)≤ 2√(ϕ_2(R;G_X))
       ≤    2√(2ϕ_X(R;G))=2√(2ϕ_X^*).

This will then finish the proof. Therefore, we only need to prove the inequality (<ref>). We will make use of the Lemma 
<ref> from <cit.>.


By Lemma <ref>, we have

    cut_X (S;G) 
       =    (1-λ)cut_3 (S;G) + λ cut_2 (S;G)
       =   (1-λ) 1/2 cut_2(S;G_T) + λ cut_2 (S;G),


and

    vol_X(S;G) 
       =    (1-λ)vol_3 (S;G)+λ vol_2 (S;G) 
       =    (1-λ)1/2 vol_2(S;G_T)+λ vol_2 (S;G).


Since the adjacency matrix of G_X is a linear combination of the adjacency matrix of G_T and the adjacency matrix of G, i.e.,
W_X=(1-λ)W_T+λW, we have  

    cut_2(S;G_X)
       =   (1-λ)cut_2(S;G_T) +λ cut_2(S;G),
    
    vol_2(S;G_X)
       =   (1-λ)vol_2(S;G_T) +λ vol_2(S;G).


The above equations imply that for any set S, 

    1/2 cut_2(S;G_X)≤ cut_X(S;G) ≤ cut_2(S;G_X),
    1/2 vol_2(S;G_X)≤ vol_X(S;G) ≤ vol_2(S;G_X).


The last inequality also implies that for any S, 

    1/2 vol_2(S̅;G_X)≤ vol_X(S̅;G) ≤ vol_2(S̅;G_X).


Therefore, by the definition of ϕ_X(S;G), we have 

    ϕ_X(S;G)    ≤   cut_2(S;G_X)/min(1/2 vol_2(S;G_X), 1/2 vol_2(S̅;G_X))
       =    2 ϕ_2(S;G_X),
    ϕ_X(S;G)    ≥   1/2 cut_2(S;G_X)/min(vol_2(S;G_X), vol_2(S̅;G_X))
       =   1/2ϕ_2(S;G_X).

This completes the proof of the inequality (<ref>).


Complexity analysis.
The computational time of MOSC-GL is dominated by the time to form W_X and
compute the second eigenvector of L_X. The former requires finding all
triangles in the graph, which can be as large as O(n^3) for a complete graph. While most
real networks are far from complete so the actual complexity is much lower than O(n^3). For
the latter, it suffices to use power iteration to find an approximate eigenvector, with
each iteration at Õ(g), where g denotes the number of non-zero entries in
L_X.  




 §.§ MOSC Based on Random Walks (MOSC-RW)

Alternatively, we can develop MOSC under the random walks framework. 
Edge/triangle conductance can be viewed as a probability corresponding to the Markov chain. For a set S with edge volume at most half of the total graph edge volume, the edge conductance of S is the probability that a random walk will leave S conditioned upon being inside S, where the transition probabilities of the walk are defined by edge connections <cit.>. Similarly, for a set S with triangle volume at most half of the total graph triangle volume, the triangle conductance of S is the probability that a random walk will leave S conditioned upon being inside S, where the transition probabilities of the walk are defined by the triangle connections <cit.>. This motives us to directly combine random walks from edge and triangle connections to perform MOSC. Therefore, we propose MOSC-RW to consider both edge and triangle structures via the respective probability transition matrix and tensor, under the random walks framework.


Specifically, starting with the third-order adjacency tensor T, we define a third-order transition tensor P as Eq. (<ref>).
Each entry of P represents the transition probability of a random walk such that the probability of jumping to a state j depends on the last two states i and k <cit.>. In the case ∑_m=1^n T(i, m, k) = 0, 
we set P (i, j, k) with 0.

Let T_k∈ ℝ^n× n denote the kth n× n block of P, i.e., 

    T_k=P(:, :, k).

Next, we average {T_k, k=1, ..., n} to reduce P to a similarity matrix A:

    A  = 1/n∑_k = 1 ^nT_k.

Now recall that P=D^-1W denotes the probability transition matrix of random walks on the input graph. We construct a mixed-order similarity
matrix H by a weighted sum of 
A and P via a mixing parameter λ∈ [0, 1] as:

    H = (1 - λ) A + λP.

Thus, we obtain the MOSC-RW algorithm with standard SC steps on H, as summarised in Algorithm <ref>. 

When λ=1, MOSC-RW is equivalent to conventional SC by Shi and Meila <cit.> and considers only second-order structures.
MOSC-RW with λ=0 considers only third-order structures, which is a simplified (unweighted) version of tensor SC (TSC) by Benson <cit.>, so we name it as simplified TSC (STSC). In the intermediate case, λ controls the trade-off. 

Interpretation. Now we interpret the model (Eq. (<ref>)) as a mixed-order random walk process. At every step, the random walker chooses either a first-order (with probability λ) or a second-order (with probability (1- λ)) random walk. For the first-order random walk, the walker jumps from the current node i to a neighbour j with probability P(i,j)=1/D(i,i). For the second-order random walk in A, A(i,j) is the probability of the following random process: supposing the walker is at vertex i, it first samples a vertex k with probability 1/n, then in the case that some neighbour k of i is sampled and i,j,k forms a triangle, the walker jumps from i to j with probability 1/W_T(i,k), where W_T(i,k) is the number of triangles containing both i and k.













Complexity analysis. 
The running time of MOSC-RW is again dominated by the time of finding all the triangles and the approximate eigenvector, and thus asymptotically the same as the running time of MOSC-GL. However, since MOSC-RW involves tensor construction, normalisation and averaging, it is more complex than MOSC-GL in implementation.  





















 §.§ Multiple Clusters and Higher-order Cheeger Inequalities of MOSC

To cluster a network into k > 2 clusters based on 
mixed-order structures, MOSC-GL and MOSC-RW follow the conventional SC <cit.>. Specifically, MOSC-GL treats the first k row-normalised  eigenvectors of L_X 
as the embedding of nodes that can be clustered by k-means. Similarly, MOSC-RW uses the first k eigenvectors of H as the node embedding to perform k-means.

Regarding performance guarantee, following <cit.> and <cit.>,
MOSC-GL and MOSC-RW do not have performance guarantee with respect to higher-order
Cheeger inequalities. However, by replacing k-means with a different clustering algorithm, MOSC-GL can derive a theoretical performance guarantee <cit.>. 




 §.§ Automatic Determination of λ

The mixing parameter λ is the only hyperparameter in MOSC. 
To improve the usability, we design schemes to automatically determine its optimal value
λ^* from a set Λ based on the quality of output
clusters <cit.>. For
bi-partitioning networks, the cut criterion 
 used to obtain output clusters can help to determine the best λ^* from Λ. For multiple partitioning networks, 
we can use the sum of triangle densities of the individual cluster to determine the best λ^* from Λ. 

Specifically, for each λ'∈Λ, let {S_λ', S_λ'} denote the MOSC bi-partitioning clusters obtained with λ=λ'. 
For a specific minimisation or maximisation cut criterion τ (e.g., edge conductance ϕ_2), we choose  λ to be  the one that optimises τ, i.e.,  

    λ^* =   min _λ' ∈Λτ(S_λ')   or  λ^* =   max _λ' ∈Λτ(S_λ'),

respectively. 

For the case of multiple partitions, we propose a triangle-density-based scheme to determine λ as follows:

    λ^* =  max _λ' ∈Λ ∑_c = 1^k ∑_v_i,v_j,v_k  ∈S_c(λ')T(i, j, k)/6|S_c(λ')|,

where S_c(λ') denotes the c-th cluster resulted from λ', 
and the
factor 1/6 is used to avoid repeated count of triangles in an undirected graph.




 §.§ Structure-Aware Error Metrics
 
If we have ground-truth clusters available, we can use them to measure  performance of clustering algorithms. Existing works commonly use mis-clustered nodes <cit.> or related metrics (e.,g. NMI) <cit.>. We denote the ground-truth partition of G with k clusters as  𝕊^* = {S_1^*, S_2^*,…, S_k^*} and a candidate partition to be evaluated as 𝕊 = {S_1, S_2,…, S_k}. 
The mis-clustered node metric is defined as 

    ϵ_N(𝕊^*, 𝕊) = 
    σmin∑_c=1^k |  S_c^* ⊕S_σ(c)|,

which measures the difference between two partitions 𝕊^* and 𝕊, where σ indicates all possible permutations of {1, 2, …, k} and ⊕ denotes the symmetric difference between the two corresponding sets. A smaller ϵ_N indicates a more accurate partition.  











A limitation of the above metric is that it fails to truly reflect the errors made in preserving structures such as edges  or triangles. Our  studies show that mis-clustered nodes do not have a monotonic relationship with mis-clustered edges or triangles. That is, a smaller number of mis-clusterd nodes does not imply smaller number of mis-clustered edges or triangles, and vice versa. This motivates us to propose two new error metrics ϵ_E and ϵ_T that measure the mis-clustered edges and triangles, respectively. These new metrics can provide more insights in the preservation of edges and triangles. 

Specifically, we define ϵ_E as 

    ϵ_E(𝕊^*,𝕊)  = ∑_c=1^k E_N  (S^*_c) - 
    σmax∑_c=1^k  E_N  (S^*_c ∩S_σ(c))
    ,

where E_N(S) is the number of edges in S. We can define ϵ_T similarly by replacing E_N(S) in Eq. (<ref>) with T_N(S), where T_N(S) is the number of triangles in S. 






 §.§ Sweep Cut Error Lower Bound
 Supposing we have the ground-truth partition 𝕊^* and the sorted eigenvector v, we can examine the best possible partition, named as the optimal cut (Ocut). This Ocut can be obtained by performing sweep cut using an error metric (ϵ_N, ϵ_E or ϵ_T) computed from  partitions as the cut criteria, e.g., for ϵ_N, its Ocut is 

    Ocut_N(𝕊^*)= min_T_u: 1≤u≤n-1 ϵ_N (𝕊^*, {T_u, T_u}),

where T_u is the first u nodes from the sorted v.
Replacing ϵ_N with ϵ_E or ϵ_T gives Ocut_E(𝕊^*) or Ocut_T(𝕊^*). It is important to note that Ocut does not depend on any cut criterion.

Ocut can help us understand the potential and model quality of a particular SC algorithm. The computed Ocut can serve as its lower bound, indicating how far a partition result (without looking at the ground-truth) is from the best possible solution (looking at the ground-truth given the fixed sorted node order), or equivalently, how much potential improvement is possible. 

















§ EXPERIMENTS
 
This section aims to evaluate MOSC against existing SC methods. In addition, we will examine the effect of cut criteria and hyperparameter λ, and gain insights from the newly designed error metrics and optimal cut. 



 §.§ Experimental Settings






















Datasets. 
The experiments were conducted on two popular groups of networks
with very different triangle densities: 
1) five full real-world networks: Zachary's karate club
 (Zachary) <cit.>, Dolphin social
network (Dolphin) <cit.>, American college football (Football) <cit.>, U.S. politics books (Polbooks) <cit.> and Political blogs (PBlogs) <cit.>;
2) four complex real-world networks: DBLP, YouTube, Orkut, and LiveJournal (LJ) from
the Stanford Network Analysis Platform
(SNAP) <cit.>.[<https://snap.stanford.edu/data/index.html>]
 All networks have ground-truth communities available.
For the four 
SNAP networks, we extract paired communities to focus on bi-partitioning problems with the following procedures: 

	
  * For each network, we select communities with the top 500 highest triangle densities, among those communities having no more than 200 nodes (for DBLP, YouTube, and Orkut) or 100 nodes (for LJ) because it has high density;
	
  * For every community in the top list, we choose another community having the most connections with it, among all the other communities in the respective network (without limiting the community node size). These two communities form a bi-partitioning network.

In this way, we extracted 2,000 networks from SNAP. The statistics of networks are summarised in Table <ref>. 

Compared algorithms. 
We evaluate MOSC-GL and MOSC-RW against the following six state-of-the-art methods, including both edge-based SC and triangle-based SC, and both 
global and local methods.


  * SC-Shi <cit.>: 
Shi and Malik developed a method aiming to minimise Ncut_2 criterion via a generalised eigenvalue problem of Eq. (<ref>). 


  * SC-Ng <cit.>: Ng designed a method built upon <cit.>. Instead of using one dominant eigenvector,
it used the first k eigenvectors of L for performing k partitions and then an additional row normalisation step before k-means.


  * Tensor Spectral Clustering (TSC) <cit.>:  TSC
is a higher-order spectral clustering method developed by Benson They constructed a transition tensor P as in Eq. (<ref>) and used an expensive multilinear PageRank algorithm <cit.> to produce a vector as the weight for reducing the tensor to a matrix via weighted average, followed by conventional SC. 


  * Higher-order SVD (HOSVD) <cit.>: To address the hypergraph clustering problem, 
this method used an adjacency tensor T to encode hyperedge, which is equivalent to the adjacency tensor definition in Eq. (<ref>). T is then reduced to a matrix via computing a modelwise covariance matrix, followed by conventional SC.


  * Motif-based SC (MSC)  <cit.> / Tensor Trace Maximisation (TTM) <cit.>: 
MSC is a general higher-order spectral clustering method via re-weighting edges according to the number of motifs containing corresponding edges, followed by conventional SC. TTM is independently proposed but equivalent to MSC, which we have verified both analytically and experimentally.


  * HOSPLOC<cit.>: 
This is a higher-order local clustering method aiming for more efficient processing while taking higher-order network structures into account. 




We study three versions for each MOSC:


  * MOSC (λ=0.5): MOSC with a fixed (recommended) λ value of 0.5;

  * MOSC (Auto-λ): MOSC with automatically determined λ;

  * MOSC (O-λ): This version of MOSC  varies λ (with step 0.1) to find the optimal λ (O-λ) that gives the smallest clustering error (using the ground truth). It provides a reference of the best possible results, showing the potential of the MOSC model.

Additionally, for MOSC-RW, we study simplified TSC (STSC) when λ=0.

Evaluation metrics. We use the proposed structure-aware metrics, mis-clustered edges (ϵ_E) and triangles
(ϵ_T). We also use two popular metrics, mis-clustered nodes (Eq. (<ref>))
and normalised mutual information (NMI) <cit.>. For the SNAP networks, we show the average results of the 500 bi-partitioning networks.

To define NMI,
we need the Shannon entropy for 𝕊 that can be defined as H(𝕊) = -∑^k_c=1(n_S_c/n)log(n_S_c/n), where n_S_c is the number of vertices in community S_c. The mutual information between 𝕊 and 𝕊^* can be expressed as

    I(𝕊,𝕊^*) = ∑_c = 1^k∑_d=1^k n_S_cS^*_d/nlog(n_S_cS^*_d/n/(n_S_c/n)
    ×(n_S^*_d/n)),

where n_S_cS^*_d is the number of vertices shared by communities 
S_c and S_d^*. The NMI between two partitions 
𝕊 and 𝕊^* is defined as 

    NMI(𝕊,𝕊^*) = 2I(𝕊,𝕊^*)/H(𝕊)+H(𝕊^*).

If 𝕊 and 𝕊^* are identical, NMI(𝕊,𝕊^*) = 1. If 𝕊 and 𝕊^* are independent, NMI(𝕊,𝕊^*) = 0.

Reproducibility. We implemented compared algorithms using Matlab code released by the authors of  MSC,[<https://github.com/arbenson/higher-order-organization-matlab>] HOSVD,[<http://sml.csa.iisc.ernet.in/SML/code/Feb16TensorTraceMax.zip>] HOSPLOC,[<http://www.public.asu.edu/ dzhou23/Code/HOSPLOC.zip>] and TSC via multilinear PageRank.[<https://github.com/dgleich/mlpagerank>] We followed guidance from the original papers to set their hyperparameters. All experiments
were performed on a Linux machine with one 2.4GHz Intel Core and 16G memory.
 We have released the Matlab code for MOSC.[<https://bitbucket.org/Yan_Sheffield/mosc/>] 





 §.§ Effect of Cut Criteria
 
Firstly, we study the effect of cut criteria on clustering performance. Note that Nassoc_2 () and Ncut_2 () are equivalent <cit.>,  but Nassoc_3 () and Ncut_3 () are not (see Appendix). Thus, we have seven different cut criteria 
from Table <ref> and the proposed mixed-order conductance (ϕ_X) defined in Eq. (<ref>). We study their effect on all algorithms while
only reporting representative results from SC-Shi, HOSVD and MOSC-RW (λ=0.5) on YouTube.

 Fig. <ref> shows the results for the two metrics ϵ_N and 
ϵ_T, together with the Ocut values (the best possible cut, knowing the ground truth). We have the following observations:



  * Cut criteria have significant impact on the performance. Among all criteria, Nassoc_3 consistently gives the smallest ϵ_T for all algorithms on YouTube. 

  * The metric ϵ_N does not have a monotonic relationship with ϵ_T.
We show an example on YouTube in Fig. <ref>cutfig:subfig4
with respect to ϵ_N and ϵ_T. As we can see, 
HOSVD+Ncut_3 vs. SC-Shi+Conduct_2 on ϵ_N  has
opposite relationship on ϵ_T.

  * The Ocut of MOSC-RW outperforms those of SC-Shi and HOSVD on both metrics ϵ_N and ϵ_E in YouTube, indicating the greater potential of MOSC-RW (even with a fixed λ). Regarding Ocut of MOSC-GL, we will present the results in Sec. <ref>.

  * Nassoc_3 and Ncut_3 are indeed not equivalent, as to be proven in Appendix.





				
				
				
				
















 §.§ Effect of λ
 
The mixing parameter λ is the only hyperparamter in MOSC. 
To gain insight of MOSC, we conduct sensitivity analysis on λ as shown in
Fig. <ref> w.r.t. NMI, ϵ_N and ϵ_T. We have the following
observations:



  * The choice of λ can significantly affect the performance in all datasets. This was the motivation of developing schemes to  automatically determine the best λ.

  * Overall, MOSC-RW is more sensitive to λ than MOSC-GL.
We will explain the reason at the end of Sec. <ref>.














 §.§ Performance Comparison
 
We study the results of all algorithms in combination of all eight criteria and k-means (KM).
Figure <ref> shows that cut criteria can affect the performance of all algorithms. Therefore,
for fair comparison, we report the clustering results conducted by the  best criteria 
for each algorithm. The top two results are in bold (best) or underlined (second best), without considering the O-λ version since it uses the ground truth. O-λ is only used for gaining insights rather than direct performance comparison with existing methods.

Results on SNAP Networks. We show the performance of all 
clustering algorithms with the best cut criteria in terms of NMI, ϵ_N, ϵ_E, and ϵ_T on SNAP networks in Table <ref>. In addition, we report 
the best cut criteria.
The results for some settings of TSC and HOSPLOC are not available either due to long running time (not finished within 40 hours) or out of memory. In particular, the multilinear PageRank algorithm in TSC is very expensive. 

We have four observations:


  * MOSC-RW (λ = 0.5) achieves the best in 10 out of 16 settings; 

  * MOSC-RW outperforms MOSC-GL, although MOSC-GL achieves top two results in 4 settings.

  * Both MOSC-RW(λ = 0.5) and MOSC-GL(λ = 0.5) have better results than
MOSC-RW(Auto-λ) and MOSC-GL(Auto-λ). This demonstrates that a fixed 
mixing parameter is effective, but it also shows the automatic schemes are not effective
in these settings.

  * MOSC-RW(O-λ) has the highest NMI and lowest ϵ_N, ϵ_E, and ϵ_T in all 16 settings. This indicates potential future improvement by designing a better strategy to determine λ.

  * Third-order cut criteria outperform second-order cut criteria on the whole.
In all 16 settings, third-order cut criteria achieve the best performance in 8 settings among which
Nassoc_3 is the best in 6 settings. Second-order cut criteria achieves the best in 5 settings and k-means for 3 settings. 





Results on Full Networks.
We show the performance of all clustering algorithms with the best cut criteria for five full networks in terms of NMI, ϵ_N, ϵ_E, and ϵ_T in Table <ref>, except HOSPLOC,
for which we were not able to obtain comparable results.
We have three observations:


  * MOSC-GL (Auto-λ) achieves the best performance in 16 out of 20 settings, demonstrating that automatic determination of λ is effective in these settings. Specifically, for Dolphin,
MOSC-GL (Auto-λ) produces perfect results in all metrics. We visualise the obtained
clusters in Dolphin as shown in Fig. <ref>dolphin:subfig1.
For networks with
multiple clusters (Polbooks, Football), MOSC-GL (Auto-λ) is also superior to others. We visualise Football with the 12 clusters in Fig. <ref>football:subfig2.

  * MOSC-GL (Auto-λ) outperforms MOSC-RW (Auto-λ),
although MOSC-RW (Auto-λ) achieves the best results in 10 settings, which is still better than all existing SC algorithms (Note that there are ties).

  * MOSC-GL has better model quality than MOSC-RW based on Ocut. 
MOSC-GL (O-λ) achieves the highest NMI and lowest ϵ_N, ϵ_E, and ϵ_T in 15 out of 20 settings while
MOSC-RW (O-λ) achieves the best in 10 settings (again there are ties).


From the above results, we see that MOSC-GL and MOSC-RW have different performance on
networks with different triangle densities. MOSC-RW tends to be better for networks with 
high triangle densities while MOSC-GL tends to be better for networks with 
low triangle densities. For MOSC-GL, W_T can 
dominate W_X in W_X=(1-λ) W_T + λW,
especially for dense networks. Each entry of W_T denotes the number of
triangles containing the corresponding edge while W is a binary matrix.
Therefore, for most non-zero pairs (i,j), W_T(i,j) is much larger than
W(i,j) especially for dense networks. This can be the reason that MOSC-GL is less sensitive to tuning
λ, or finding the appropriate λ is more difficult. That is, W_X
tends to encode much less edge information. In contrast, MOSC-RW does not have such
issue since A and P are normalised and thus they are in similar scales
before linear combination. Therefore, 
 MOSC-RW has a better performance than MOSC-GL in SNAP networks and the dense full graph PBlogs. 





 §.§ Computational Time
 
Figure <ref> compares the computational time of different methods on YouTube,
LJ, PBlogs and Football, using k-means to obtain the final clusters to avoid the effect of cut criteria. We have the following observations:


  * Both HOSVD and MOSC-RW  involve tensor construction and operations so they  are both more time consuming, in particular on dense networks such as LJ and PBlogs, where HOSVD is the slowest and MOSC-RW is the second slowest. The reason is that HOSVD uses more a complicated dimension reduction method than
MOSC-RW.

  * MOSC-GL is more efficient than MOSC-RW in all cases and has similar efficiency
as conventional SC methods on the whole.






	






































§ CONCLUSION

This paper proposed two mixed-order spectral clustering (MOSC) methods, MOSC-GL and MOSC-RW, which model both second-order and third-order structures for network clustering. MOSC-GL combines edge and triangle adjacency matrices with theoretical performance guarantee. MOSC-RW combines first-order and second-order random walks with a probabilistic interpretation. We designed a scheme to automatically determine the mixing  parameter and new structure-aware error metrics for structure evaluation. We also defined an optimal cut to study the lower error bound for exploring potentials of MOSC. Experiments on 2,005 networks showed that MOSC algorithms outperform existing SC methods in most cases and the proposed mixed-order approach produces more superior clustering of networks.



§ PROOF OF THE RELATIONSHIP BETWEEN NCUT_3 AND NASSOC_3


Shi and Malik <cit.> showed that second-order normalised cut (Ncut_2) and association (Nassoc_2) are equivalent by the following equation: 

    Ncut_2 (S;G) = 2 - Nassoc_2 (S;G),

which indicates that the minimisation of Ncut_2 is equivalent to maximisation of Nassoc_2.
It inspires us to think about a question: does third-order normalised cut (Ncut_3) <cit.> and association (Nassoc_3) <cit.> have the similar  equivalence? 

Based on the definition of cut_3(S), we have the following equation <cit.> (omitting G): 


    cut_3(S,S̅)    =   1/3 (((vol_3(S) - assoc_3(S))
          +(vol_3(S̅) - assoc_3(S̅))).

Ncut_3 (S) <cit.> is defined as follows:

    Ncut_3 (S)    =
    cut_3(S,S̅)(1/vol_3(S)+
    1/vol_3(S̅)).

This gives that: 

    Ncut_3 (S)    =(vol_3(S) - assoc_3(S))
    +(vol_3(S̅) - assoc_3(S̅))/3 vol_3(S)
       +(vol_3(S) - assoc_3(S))
    +(vol_3(S̅) - assoc_3(S̅))/3 vol_3(S̅)
       =2/3 - 1/3(assoc_3(S)/vol_3(S)+
    assoc_3(S̅)/vol_3(S̅))
    
       +1/3 (vol_3(S̅)-assoc_3(S̅)̅/vol_3(S)+vol_3(S)-assoc_3(S)/vol_3(S̅))


The definition of Nassoc_3(S) <cit.> is given as:

    Nassoc_3(S) = assoc_3(S)/vol_3(S)+
    assoc_3(S̅)/vol_3(S̅)


The above equations indicate:


    Ncut_3 (S)   = 2/3 - 1/3Nassoc_3(S)
       
    + 1/3 (vol_3(S̅)-assoc_3(S̅)/vol_3(S)+vol_3(S)
    -assoc_3(S)/vol_3(S̅)).

From Eq. (<ref>), we can see that the third term in is not a constant. Therefore,
minimisation  of Ncut_3 is not equivalent to maximisation of Nassoc_3.





IEEEtran



















































