Mixed-Order Spectral Clustering for Networks
Yan Ge, Haiping Lu, and Pan Peng
University of Sheffield, Sheffield, UK{yge5,h.lu,p.peng}@sheffield.ac.uk

Abstract. 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 arelimited to considering a single order. This novel research paper proposesa new Mixed-Order Spectral Clustering (MOSC) approach to model bothsecond-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, withtheoretical performance guarantee. MOSC-RW combines first-order andsecond-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 five real-world networks show that
MOSC-GL with automatically determined mixing parameter improves
by 5.4% over the best competing algorithm in average normalised mutual
information (NMI) of four networks with low triangle density. For theremaining PBlogs network with high triangle density, MOSC-RW with
automatically determined mixing parameter improves by 18.9 times overthe best competing algorithm in NMI.
Keywords: Spectral clustering · Network analysis · Higher-order structures · Mixed-order structures

1

Introduction

Networks (a.k.a. graphs) are important data structures that abstract relations
between discrete objects, such as social networks and brain networks [4]. 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 [6, 27].
Clustering aims to divide a data set into clusters (or communities) such thatthe nodes assigned to a particular cluster are similar or well connected in somepredefined sense [9, 23, 26]. It helps us reveal functional groups hidden in data.
As a popular clustering method, conventional spectral clustering (SC) [20, 24]
encodes pairwise similarity into an adjacency matrix. Such encoding inherently

2

Y. Ge et al.

(a) A network.

(b) Edges.

(c) Triangles.

(d) Mixed.

Fig. 1. Motivation: the second and third order structures in (a) can not be fully captured by edge/triangle adjacency matrix in (b)/(c). Our proposed mixed adjacency
matrix in (d) can capture both.

restricts SC to second-order structures [4], such as undirected or directed edges
connecting two nodes.1 However, in many real-world networks, the minimal andfunctional 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 [21], which we call ahigher-order structure.
Higher-order structures consist of at least three nodes (e.g., triangles, 4-vertex
cliques) [4]. It can directly capture interaction among three or more nodes. Whenclustering 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 andsignificantly improve our understanding of underlying networks. For example,
triangular structures, with three reciprocated edges connecting three nodes, play
important roles in brain networks [30] and social networks [12, 13]. 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 [28]. Thus, the application candrive 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 five approaches: 1)
an adjacency tensor can be constructed to encode higher-order structures andthen reduced to a matrix to apply conventional SC [10, 11], developed in therelated hypergraph clustering problem; 2) a transition tensor can be constructedbased on random walk and then reduced to a matrix for conventional SC [3, 34];3) a counting and reweighting scheme can be employed to capture higher-order
structures and reveal clusters [4, 17, 32]; 4) higher-order local clustering canbe used to mitigate computation cost problem [16, 37, 39]; 5) some network
embedding methods [25, 31] preserve the higher-order proximity that considers
relationship between more than two nodes, which can be applied to clustering.
However, it should be noted that most networks have both second-order andhigher-order structures, and both can be important. Existing conventional andthird-order SC methods model only either second-order or third-order structures,
but not both. Second-order SC does not take triangles into consideration, while1

Edges are considered as first-order structures in [3] but second-order structuresin [39]. We follow the terminologies in the latter [39] so that the “order” here refers
to the number of nodes involved in a particular structure.

Mixed-Order Spectral Clustering for Networks

3

third-order SC loses information of some edges, in particular, those that do notbelong to any triangle. A simple example is given by the network in Fig. 1(a),which contains both edges and triangles. In Figs. 1(b) and 1(c), which correspondto the representations used by second-order and third-order SC, respectively,
each entry indicates the number of edges and triangles involving two nodes ofFig. 1(a). As the figures show: Second-order SC fails to capture the importance
between nodes 2 and 3, but they participate in more triangles than any other two
adjacent nodes (say 1 and 2), which is not reflected in Fig. 1(b); Third-order SC
fails to model the importance of the relation between nodes 4 and 5, but there
does exist an edge between them (and thus is more important than any two
non-adjacent nodes, say nodes 2 and 5), which was missed in Fig. 1(c).
In this paper, we propose a new Mixed-Order Spectral Clustering (MOSC) to
preserve structures of different orders simultaneously, as in Fig. 1(d). 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 three contributions as following:
1. 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 mixedorder 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. 3.1 and Sec. 3.2.
2. Automatic model selection. We propose cut-criteria-based and triangledensity-based strategies to automatically determine the mixing parameter(ranging from 0 to 1) that is the only hyperparameter in MOSC. See Sec. 3.4.
3. Structure-aware error metrics. We propose structure-aware error metrics to gain insights on the quality of structure preservation. Existing works
on higher-order structure clustering use evaluation metrics that focus on
mis-clustered nodes [11, 32, 37]. However, mis-clustered nodes do not havea monotonic relationship with mis-clustered structures so they may fail toreflect the errors in structures. See Sec. 3.5.

2

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., A, and tensors bycalligraphic letters, e.g., A. Let G = (V, E) be an undirected unweighted graph(network) with V = {v1 , v2 , . . . , vn } being the set of n vertices (nodes), i.e., n= |V|, and E being the set of edges connecting two vertices.
2.1

Normalised Graph Laplacian

Let W ∈ Rn×n be an unweighted adjacency matrix of G where W(i, j) = 1 if
(vi , vj ) ∈ E, otherwise W(i, j) = 0. The degree matrix D is a diagonal matrix

4

Y. Ge et al.

Pnwith diagonal entries D(i, i) = j=1 W(i, j), which is the degree of vertex vi .
Let N = D − W denote the Laplacian matrix of G. The normalised Laplacian11of G is defined as L = D− 2 ND− 2 [33].
Let WT be triangle adjacency matrix of G with its entry (i, j) being thenumber of triangles containing vertices i and j, which leads to a corresponding
weighted graph GT [4]. Similarly, we can define the triangle Laplacian as NT =−1

−1

DT − WT P
and the normalised triangle Laplacian as LT = DT 2 NT DT 2 , wheren
DT (i, i) = j=1 WT (i, j).
2.2First-Order and Second-Order Random Walks

We define a second-order transition matrix P by normalising the adjacency matrix W to represent edge structures as P = D−1 W [20]. The entry Pij represents
the probability of jumping from vertex vi to vj in one step. The transition matrix
P represents a first-order random walk process on graph G [20].
To define second-order random walks, Benson et al. [3] firstly define a symmetric adjacency tensor T ∈ Rn×n×n such that the connectivity information forthree vertices {vi , vj , vk }∈ V can be represented explicitly in this tensor. Thus,
T encodes triangle structures in G as:(
1 vi , vj , vk form a triangle,
T (i, j, k) =(1)0otherwise.
Next, they form a transition tensor P as
P(i, j, k) = T (i, j, k)/nX

T (i, m, k),

(2)

m=1

Pn
Pn
where m=1 T (i, m, k) 6= 0, and 1 ≤ i, j, k ≤ n. For m=1 T (i, m, k) = 0, Benson et al. [3] set P(i, j, k) to n1 . Here, P(i, j, k) represents a transition probabilityof a second-order random walk. And the probability of jumping to state i relieson the last two states j and k [35].
2.3

Spectral Clustering Basics and Cut Criteria

Bi-partitioning SC (Algorithm 1) first constructs a matrix B to encode structuresin the input graph G [33]. It then computes a dominant eigenvector v of B, thus
making use of its spectrum. Each entry of v corresponds to a vertex. Next, we sortvertices by the values v(i) (or appropriately normalised values) and consider theset Tu consisting of the first u vertices in the sorted list, for each 1 ≤ u ≤ n − 1.
Then the algorithm finds S = arg minTu τ (Tu ), called the sweep cut w.r.t. somecut criterion τ [15]. The choice of the cut criterion can affect the quality ofoutput clusters [15].
As the last step of SC, sweep cut aims to optimise a cut criterion to obtain good clustering results. Most cut criteria have two main objectives: 1) toMixed-Order Spectral Clustering for Networks

5

Algorithm 1 Bi-partitioning Spectral Clustering
1: Matrix B encodes structures of the input graph G.
2: Compute a dominant eigenvector v of B.
3: v ← sorted ordering of v or a normalised version of sorted v.
4: {S, S̄} ← sweep cut of v w.r.t. a cut criterion.

preserve a rich set of structures within S and S̄, and 2) to avoid structures
being broken due to partitioning of S and S̄ [33]. Moreover, different cut criteria serve to preserve different structures, such as second-order cut criteria (e.g.,
2nd-conductance [27]) for the preservation of the edge structure and third-ordercut criteria (e.g., 3rd-conductance [3]) for the preservation of triangle structure.
Besides sweep cut, k-means [19] is another popular choice for finding the final
partitions.
2.4

Cheeger Inequalities

Given G = (V, E) and a subset S ⊆ V, let S̄ denote the complement of S. Let
cut2 (S; G) denote the edge cut of S, i.e., the number of edges between S and S̄ in
G. Let vol2 (S; G) denote the edge volume of S, i.e., the total degrees of vertices
2 (S;G).
in S. The edge conductance of S is defined as φ2 (S; G) = min{vol2cut(S;G),vol2 (S̄;G)}The classical Cheeger inequality below relates the conductance of the sweep cutof SC to the minimum conductance value of the graph [7].
Lemma 1 (Second-Order Cheeger Inequality). Let v be the second smallest eigenvector of L. Let T ∗ be the psweep cut of D−1/2 v w.r.t. cut criterion
φ2 (·; G). It holds that φ2 (T ∗ ; G) ≤ 2 φ∗2 , where φ∗2 = minS⊆V φ2 (S; G) is theminimum conductance over any set of vertices.
Let cut3 (S; G) denote the triangle cut of S, i.e., the number of triangles thathave at least one endpoint in S and at least one endpoint in S̄. Let vol3 (S; G)
denote the triangle volume of S, i.e., the number of triangle endpoints in S. The
3 (S;G). It
triangle conductance [3] of S is defined as φ3 (S; G) = min{vol3cut(S;G),vol3 (S̄;G)}is further proved in [4] that for any S ⊆ V , φ3 (S; G) = φ2 (S; GT ), which leads
to the following third-order Cheeger inequality.
Lemma 2 (Third-order Cheeger Inequality). Let v be the second smallest−1/2
eigenvector of LT . Let T ∗ denote thepsweep cut of DT v w.r.t. cut criteria∗∗∗
φ2 (·; GT ). It holds that φ3 (T ; G) ≤ 4 φ3 , where φ3 = minS⊆V φ3 (S; G).

3

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

6

Y. Ge et al.

Algorithm 2 MOSC via Graph Laplacian (MOSC-GL)
Input: G = (V, E), mixing parameter λOutput: Two node sets S, S̄
1: Compute the normalized mixed-order Laplacian LX as defined in Eq. (3)2: Compute the second smallest eigenvector v of LX .
−1

3: v ← sorted ordering of DX 2 v.
4: {S, S̄} ← sweep cut on v w.r.t. a cut criterion.

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-order and second-order random walks,providing a probabilistic interpretation. Next, we develop an automatic hyperparameter determination scheme and define new structure-aware error metrics.
3.1

MOSC Based on Graph Laplacian (MOSC-GL)

MOSC-GL introduces a mixed-order adjacency matrix WX that linearly combines the edge adjacency matrix W and the triangle adjacency matrix WT , witha mixing parameter λ ∈ [0, 1]. WX can be seen as a weighted adjacency matrix
of a weighted graph GX , on which we can apply conventional SC (Algorithm 1).
Specifically, we first construct the matrix WX and the corresponding diagonal
degree matrix DX as:
WX = (1 − λ)WT + λW,

DX = (1 − λ)DT + λD.

Let GX denote an undirected weighted graph with adjacency matrix WX ,we can define a mixed-order Laplacian NX and its normalised version LX as:
NX = DX − WX = (1 − λ)NT + λN,−1−1

LX = DX 2 NX DX 2 .

(3)Then, we compute the eigenvector corresponding to the second smallest eigenvalue of LX and perform the sweep cut to find the partition with the smallest edge conductance in GX . The MOSC-GL algorithm is summarised in Algorithm 2.
When λ = 1, MOSC-GL is equivalent to SC by Ng et al. [24] and only considers second-order structures. When λ = 0, MOSC-GL is equivalent to motifbased SC [4]. MOSC-GL maintains the advantages of traditional SC: computational efficiency, ease of implementation and mathematical guarantee on thenear-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
cutX (S; G) = (1 − λ)cut3 (S; G) + λcut2 (S; G),
volX (S; G) = (1 − λ)vol3 (S; G) + λvol2 (S; G),Mixed-Order Spectral Clustering for Networks

7

respectively. Then, we define the mixed-order conductance of S as:
φX (S; G) =cutX (S; G),
min(volX (S; G), volX (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 samecluster 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 2 is a good approximation.
Theorem 1 (Mixed-order Cheeger Inequality). Given an undirected graphG, let T ∗ denote the set outputted by MOSC-GL (Algorithm 2) w.r.t. the cut
criterion φ2 (·; GX ). Let φ∗ = minS⊆V φX (S; G) be the minimum mixed-order√conductance over any set of vertices. Then it holds that φX (T ∗ ; G) ≤ 2 2φ∗ .
Proof. It suffices for us to prove that for any set S,
1
φ2 (S; GX ) ≤ φX (S; G) ≤ 2φ2 (S; GX ).
2(4)Assume for now that
inequality (4) holds. By Lemma 1, the set T ∗
√ the
∗
∗
satisfies φ2 (T ; GX ) ≤ 2 ψ , where ψ ∗ = minS⊆V φ2 (S; GX ). Let R be the set
with φX (R; G) = φ∗ = minS⊆V φX (S; G). Then by inequality (4), we havepp
φX (T ∗ ; G) ≤ 2φ2 (T ∗ ; GX ) ≤ 2 ψ ∗ ≤ 2 φ2 (R; GX )p
p
≤ 2 2φX (R; G) = 2 2φ∗ .
This will then finish the proof. Thus, we only need to prove the inequality (4).
By Lemma 4 in [4], we have cut3 (S; G) = 12 cut2 (S; GT ). This gives that
cutX (S; G) = (1−λ)cut3 (S; G)+λcut2 (S; G) = (1−λ) 21 cut2 (S; GT )+λcut2 (S; G).
By Lemma 1 in [4], we have vol3 (S; G) = 21 vol2 (S; GT ). This gives that
volX (S; G) = (1−λ)vol3 (S; G)+λvol2 (S; G) = (1−λ) 12 vol2 (S; GT )+λvol2 (S; G).
Since the adjacency matrix of GX is a linear combination of the adjacency
matrix of GT and the adjacency matrix of G, i.e., WX = (1 − λ)WT + λW,
we have that cut2 (S; GX ) = (1 − λ)cut2 (S; GT ) + λcut2 (S; G), vol2 (S; GX ) =(1 − λ)vol2 (S; GT ) + λvol2 (S; G).
The above equations imply that for any set S, it holds that 21 cut2 (S; GX ) ≤cutX (S; G) ≤ cut2 (S; GX ), 12 vol2 (S; GX ) ≤ volX (S; G) ≤ vol2 (S; GX ).
The last inequality also implies that for any S, 21 vol2 (S̄; GX ) ≤ volX (S̄; G) ≤vol2 (S̄; GX ). Therefore, by the definition of φX (S; G), we havecut2 (S; GX )= 2φ2 (S; GX ),1min( 2 vol2 (S; GX ), 21 vol2 (S̄; GX ))11
2 cut2 (S; GX )φX (S; G) ≥= φ2 (S; GX ).
2
min(vol2 (S; GX ), vol2 (S̄; GX ))φX (S; G) ≤This completes the proof of the inequality (4).

8

Y. Ge et al.

Complexity analysis. The computational time of MOSC-GL is dominatedby the time to form WX and compute the second eigenvector of LX . The former
requires finding all triangles in the graph, which can be as large as O(n3 ) for acomplete graph. While most real networks are far from complete so the actual
complexity is much lower than O(n3 ). For the latter, it suffices to use power
iteration to find an approximate eigenvector, with each iteration at Õ(g), whereg denotes the number of non-zero entries in LX .
3.2

MOSC Based on Random Walks (MOSC-RW)

Alternatively, we can develop MOSC under the random walks framework. Edgeor triangle-based 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 graphedge 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 [33]. Similarly, for a set S with triangle
volume at most half of the total graph triangle volume, the triangle conductanceof 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 [3]. This motives us to directly combine random walks fromedge and triangle connections to perform MOSC. Therefore, we propose MOSCRW 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
PnT (Eq. (1)), we
define a third-order transition tensor P (Eq.(2)). In the case m=1 T (i, m, k) =0, we set P(i, j, k) with 0. Let Tk ∈ Rn×n denote the kth n × n block of P, i.e.,
Tk = P(:, :, k). Next, we average {Tk , k = 1, ..., n} to reduce P to a similarity
matrix A:
n
1X
Tk .
A=
n
k=1

−1

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

(5)Thus, we obtain the MOSC-RW algorithm with standard SC steps on H, assummarised in Algorithm 3.
When λ = 1, MOSC-RW is equivalent to conventional SC by Shi and Meila [29]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 et al. [3]. In the intermediate case, λ controls the trade-off.
Interpretation. Now we interpret the model (Eq. (5)) as a mixed-order
random walks process. At every step, the random walker chooses either a firstorder (with probability λ) or a second-order (with probability (1 − λ)) randomMixed-Order Spectral Clustering for Networks

9

Algorithm 3 MOSC via Random Walks (MOSC-RW)
Input: G = (V, E), mixing parameter λOutput: Two node sets S, S̄
1: Compute the matrix H as defined in Eq (5).
2: Compute the second largest eigenvector v of H.
3: v ← sorted ordering of v
4: {S, S̄} ← sweep cut of v w.r.t. a cut criterion.

walk. For the first-order random walk, the walker jumps from the current node i
1. For the second-order random
to a neighbour j with probability P(i, j) = D(i,i)
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 n1 , then in
the case that some neighbour k of i is sampled and i, j, k forms a triangle, thewalker jumps from i to j with probability 1/WT (i, k), where WT (i, k) is thenumber of triangles containing both i and k.
Complexity analysis. The running time of MOSC-RW is again dominatedby the time of finding all the triangles and the approximate eigenvector, andthus 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.
3.3

Multiple Clusters and Higher-order Cheeger Inequalities

To cluster a network into k > 2 clusters based on mixed-order structures, MOSCGL and MOSC-RW follow the conventional SC [33]. Specifically, MOSC-GL
treats the first k row-normalised eigenvectors of LX 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 [4] and [14], 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 [14].
3.4

Automatic Determination of λThe mixing parameter λ is the only hyperparameter in MOSC. To improve theusability, we design schemes to automatically determine its best value λ∗ froma set Λ based on the quality of output clusters [5, 15, 36]. For bi-partitioning
networks, the cut criterion used to obtain output clusters can help determine
the best λ∗ from Λ. For multiple partitioning networks, we can use the sum of
triangle densities of individual clusters to determine the best λ∗ from Λ.
Specifically, for each λ0 ∈ Λ, let {Sλ0 , Sλ0 } denote the MOSC bi-partitioning
clusters obtained with λ = λ0 . For a specific minimisation or maximisation cut

10

Y. Ge et al.

criterion τ (e.g., edge conductance φ2 ), we choose λ to be the one that optimises
τ , i.e.,λ∗ = arg min
τ (Sλ0 ) or λ∗ = arg max
τ (Sλ0 ),
0
0
λ ∈Λ

λ ∈Λ

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

λ = arg max
0
λ ∈Λ

k
X
c=1

P

vi ,vj ,vk ∈Sc (λ0 ) T (i, j, k),
6|Sc (λ0 )|where Sc (λ0 ) denotes the c-th cluster resulted from λ0 , and the factor 1/6 is used
to avoid repeated count of triangles in an undirected graph.

3.5

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-clusterednodes [11] or related metrics (e.g., normalised mutual information (NMI) [2]). We
denote the ground-truth partition of G with k clusters as S∗ = {S1∗ , S2∗ , . . . , Sk∗ }and a candidate partition to be evaluated as S = P{S1 , S2 , . . . , Sk }. The mismink∗c=1 |Sc ⊕Sσ(c) |, which meaclustered node metric is defined as N (S∗ , S) = σ|V|sures the difference between two partitions S∗ and S, 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 (Fig. 3 inSec. 4.2) show that mis-clustered nodes do not have a monotonic relationshipwith mis-clustered edges or triangles. That is, a smaller number of mis-clusterd
nodes does not imply a smaller number of mis-clustered edges or triangles, andvice versa. This motivates us to propose two new error metrics E and T thatmeasure 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 asPk
E (S∗ , S) =Pk∗∗
c=1 EN (Sc ) − max
c=1 EN (Sc ∩ Sσ(c) )
σ
|E|

,

(6)

where EN (S) and |E| are the number of edges in S and G respectively. We candefine T similarly by replacing EN (S) and |E| in Eq. (6) with TN (S) and |T|,
where TN (S) and |T| are the number of triangles in S and G.

Mixed-Order Spectral Clustering for Networks

4

11

Experiments

This section aims to evaluate MOSC against existing SC methods. In addition,
we will examine the effect of hyperparameter λ, and gain insights from the newly
designed error metrics and show computational time.
4.1

Experimental Settings

Datasets. The experiments were conducted on five popular real-world networks
with very different triangle densities: 1) Zachary’s karate club (Zachary) [38],2) Dolphin social network (Dolphin) [18], 3) American college football (Football) [22], 4) U.S. politics books (Polbooks) [22], and 5) Political blogs (PBlogs) [1].
The above networks have ground-truth communities. Their statistics are summarised in Table 1.
Compared algorithms. We evaluate MOSC-GL and MOSC-RW against
the following five state-of-the-art methods, including both edge-based SC andtriangle-based SC: 1) SC-Shi [29], 2) SC-Ng [24], 3) Tensor Spectral Clustering (TSC) [3], 4) Higher-order SVD (HOSVD) [10], and 5) Motif-based SC(MSC) [4] / Tensor Trace Maximisation (TTM) [11] (We have verified that
TTM and MSC are equivalent).
We study two versions for each MOSC: 1) MOSC (λ = 0.5): MOSC with afixed (recommended) λ value of 0.5; 2) MOSC (Auto-λ): MOSC with automatically determined λ. We set λ values from 0 to 1 with step 0.1.
Evaluation metrics. We use the proposed structure-aware metrics, misclustered edges (E ) and triangles (T ). We also use two popular metrics, misclustered nodes (N ) [11] and NMI [2].
Selection of cut criteria. We study seven different cut criteria covering
second-order ones: 1) 2nd-conductance [27], 2) 2nd-Ncut [29], 3) 2nd-expansion [8],and third-order ones: 4) 3rd-conductance [3], 5) 3rd-Ncut [17], 6) 3rd-expansion [3],7) 3rd-Nassociation [11] and also k-means [19]. By doing this, second-order methods can use third-order cut criteria (e.g., SC-Shi+3rd-conductance), and thirdorder methods can use second-order cut criteria (e.g., TSC+2nd-Ncut). For faircomparison, we show the performance of all algorithms with the best cut criteria
for bi-partitioning networks. For multi-partitioning networks, all algorithms use
k-means.
Reproducibility. We used Matlab implementation of compared algorithms
released by the authors of MSC,2 HOSVD,3 and TSC via multilinear PageRank.4
We followed guidance from the original papers to set their hyperparameters. All
experiments were performed on a Linux machine with one 2.4GHz Intel Coreand 16G memory. We have released the Matlab implementation for MOSC.52

https://github.com/arbenson/higher-order-organization-matlab
http://sml.csa.iisc.ernet.in/SML/code/Feb16TensorTraceMax.zip
4
https://github.com/dgleich/mlpagerank
5
https://bitbucket.org/Yan_Sheffield/mosc/
3

12

Y. Ge et al.

Table 1. Statistics of the five networks. PBlogs has significantly higher triangle density
than the others. #Interaction edges are the number of edges among the ground-truth
communities.
Network |V||E|

Zachary
34
78
Dolphin
62
159
Polbooks 105 441
Football 115 613
PBlogs1,490 16,716

4.2

Triangle density #Communities #Interaction edges
1.32
1.53
5.33
7.04
67.80

2
2
3
12
2

11
6
70
219
1,576

Performance Comparison

The clustering results on five networks are summarised in Table 2. We have threeobservations:
1. MOSC-GL(Auto-λ) improves by 5.4% (from 0.796 to 0.839) over the bestcompeting algorithm (SC-Shi) in average NMI of four networks with low
triangle density. For the remaining PBlogs with high triangle density, MOSCRW(Auto-λ) improves by 18.9 times (from 0.023 to 0.458) over the bestcompeting algorithm (MSC). It demonstrates that automatic determinationof λ is effective in these scenarios. We visualise the obtained clusters by
MOSC-GL(Auto-λ) for Polbooks in Fig. 2.
2. MOSC-GL and MOSC-RW have different performance w.r.t triangle densityof networks. We will give a discussion at the end of this section.
3. The value of mis-clustered node (N ) does not have a monotonic relationship with the value of mis-clustered edge (E )/triangle (T ). Fig. 3 shows
an example that HOSVD vs. TSC on N has non-monotonic relationshipwith T . Specifically, TSC achieves lower value of error nodes than that of
HOSVD, but it loses more triangles than HOSVD. It demonstrates that themis-clustered node cannot reflect errors in structures, while our proposed
structure-aware metrics (E /T ) can gain insights on the quality of structure preservation.
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, WT candominate WX in WX = (1 − λ)WT + λW, especially for dense networks. Each
entry of WT denotes the number of triangles containing the corresponding edge
while W is a binary matrix. Therefore, for most non-zero pairs (i, j), WT (i, j)
is much larger than W(i, j), especially for dense networks, which makes determining the appropriate λ more difficult. In contrast, MOSC-RW does not havesuch issue since A and P are normalised and thus they are in similar scales before the linear combination. According to the above, we recommend MOSC-GL
for networks with low triangle density while MOSC-RW for networks with hightriangle density.

Mixed-Order Spectral Clustering for Networks

13

Table 2. Clustering performance of algorithms with the best cut criteria. The bestis in bold and the second best is underlined. A larger NMI indicates a better result,while a smaller N /E /T indicates a better result. Note that there are ties. Avg. NMI
is the average NMI for each algorithm on the first four datasets.

PBlogsDolphin

Polbooks

FootballZachary

Edge based
Triangle based
MOSC-RW
MOSC-GL
Method SC-Shi SC-Ng HOSVD MSC TSC λ = 0.5 Auto-λ λ = 0.5 Auto-λ
NMI 0.837 0.837 0.069 0.732 0.677 0.837 0.837 0.837 0.837
N
0.029 0.029 0.412 0.059 0.059 0.029 0.029 0.029 0.029
E
0.026 0.026 0.436 0.038 0.038 0.026 0.026 0.026 0.026
T
0.022 0.022 0.356 0.022 0.022 0.022 0.022 0.022 0.022
NMI 0.883 0.905 0.896 0.924 0.866
0.924 0.924 0.900 0.931
N
0.200 0.130 0.139 0.087 0.226
0.087 0.087 0.130 0.078
E
0.103 0.060 0.059 0.011 0.114 0.011 0.011 0.059 0.011
T
0.122 0.062 0.048 0.002 0.136 0.002 0.002 0.048 0.002
NMI 0.575 0.542 0.092 0.542 0.180
0.575 0.575 0.563 0.589
N
0.162 0.171 0.533 0.171 0.524 0.162 0.162 0.162 0.162
E
0.061 0.075 0.420 0.077 0.637
0.061 0.061 0.063 0.048
T
0.013 0.018 0.418 0.014 0.686
0.013 0.013 0.013 0.002
NMI 0.889 0.889 0.081 0.536 0.582
0.889 0.889 0.889 1.000
N
0.016 0.016 0.306 0.113 0.097
0.016 0.016 0.016 0.000
E
0.006 0.006 0.270 0.063 0.050
0.006 0.006 0.006 0.000
T
0.000 0.000 0.305 0.000 0.011 0.000 0.000 0.000 0.000
Avg. NMI 0.796 0.793 0.285 0.684 0.576
0.806 0.806 0.797 0.839
NMI 0.007 0.007 0.014 0.023
0.012 0.458 0.098 0.016
N
0.450 0.491 0.454 0.412
0.442 0.154 0.321 0.434
E
0.437 0.437 0.437 0.434
0.437 0.011 0.437 0.437
T
0.360 0.360 0.360 0.360
0.360 0.005 0.360 0.360
0.7
HOSVD
TSC

0.6

0.5

0.4

0.3
N

T

Fig. 2. Communities in Polbooks detected Fig. 3. Non-monotonic relationship beby MOSC-GL(Auto-λ).
tween N and T on Polbooks.

4.3

Effect of λThe mixing parameter λ is the only hyperparamter in MOSC. To gain insightof MOSC, we conduct sensitivity analysis on λ as shown in Fig. 4 w.r.t. NMI.
We can see that the choice of λ can significantly affect the performance while
there are large regions of stable performance as well. This was the motivation

14

Y. Ge et al.
0.94

0.92

1

0.5

0.8

0.4

0.6

NMI

0.9

0.88

MOSC-GL

0.3

NMI

NMI

0.4

0.2

0.2

0.1

MOSC-GL
MOSC-RW

MOSC-RW
0.86

0

0

0.2

0.4

0.6

0.8

1

0
0

(a) Football

MOSC-GL
MOSC-RW

0.2

0.4

0.6

0.8

1

0

(b) Dolphin

0.2

0.4

0.6

0.8

1

(c) PBlogs

Fig. 4. Sensitivity analysis of λ on Football, Dolphin and PBlogs w.r.t NMI.

Computational time (s)10 2SC-Shi
SC-Ng
HOSVD
MSC
MOSC-RW
MOSC-GL

10 1

10 0

10 -1

10 -2

Zachary

Dolphin

PBlogsFig. 5. Computational time (in log scale).

of developing schemes to automatically determine the best λ. For PBlogs, Table 2 shows that MOSC-RW achieves significantly better performance than theothers. From Fig. 4(c), MOSC-RW does not have good performance for large λvalues (>0.4). Fortunately, benefiting from automatic λ determination scheme,
an outstanding performance has been achieved.

4.4

Computational Time

Figure 5 compares the computational time of different methods on three networks, where k-means was used to obtain the final clusters to avoid the effectof cut criteria. MOSC-GL is more efficient than MOSC-RW in all cases because
MOSC-GL does not have tensor construction and tensor dimension reduction.
For PBlogs, HOSVD and MOSC-RW are time-consuming, because both involve
tensor construction and operations that are much more expensive than that in
networks with low triangle density. SC-shi and SC-Ng are slower than MOSCRW and MOSC-GL on Zachary and Dolphin since they use use more time onconverging of k-means step. But for PBlogs that is dense and large, MOSC-RW
spends lots of time on constructing the triangle tensor while MOSC-GL is scalable to construct the triangle matrix. Our future work will apply our algorithms
to large network datasets.

Mixed-Order Spectral Clustering for Networks

515

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 andproposed new structure-aware error metrics for structure evaluation. Experiments on five real-world networks showed that MOSC algorithms outperform
existing SC methods on the whole.

Acknowledgement
This work is supported by the Amazon Research Awards. This article solely
reflects the opinions and conclusions of its authors and not Amazon.

References
1. Adamic, L.A., Glance, N.: The political blogosphere and the 2004 us election:
divided they blog. In: Proceedings of the 3rd International Workshop on Link
Discovery. pp. 36–43. ACM (2005)
2. Ana, L., Jain, A.K.: Robust data clustering. In: CVPR. vol. 2, pp. II–II (2003)
3. Benson, A.R., Gleich, D.F., Leskovec, J.: Tensor spectral clustering for partitioning
higher-order network structures. In: SDM. pp. 118–126. SIAM (2015)
4. Benson, A.R., Gleich, D.F., Leskovec, J.: Higher-order organization of complex
networks. Science 353(6295), 163–166 (2016)
5. Chakraborty, T., Dalmia, A., Mukherjee, A., Ganguly, N.: Metrics for community
analysis: A survey. ACM Computing Surveys (CSUR) 50(4), 54 (2017)
6. Clauset, A., Newman, M.E., Moore, C.: Finding community structure in very large
networks. Physical Review E 70(6), 066111 (2004)
7. Fiedler, M.: Algebraic connectivity of graphs. Czechoslovak Mathematical Journal
23(2), 298–305 (1973)
8. Flake, G.W., Tarjan, R.E., Tsioutsiouliklis, K.: Graph clustering and minimum cuttrees. Internet Mathematics 1(4), 385–408 (2004)
9. Fortunato, S.: Community detection in graphs. Physics Reports 486, 75–174 (2010)
10. Ghoshdastidar, D., Dukkipati, A.: Consistency of spectral partitioning of uniform
hypergraphs under planted partition model. In: NIPS (2014)
11. Ghoshdastidar, D., Dukkipati, A.: Uniform hypergraph partitioning: Provable tensor methods and sampling techniques. JMLR 18(50), 1–41 (2017)
12. Granovetter, M.S.: The strength of weak ties. In: Social Networks, pp. 347–367.
Elsevier (1977)
13. Kossinets, G., Watts, D.J.: Empirical analysis of an evolving social network. Science311(5757), 88–90 (2006)
14. Lee, J.R., Gharan, S.O., Trevisan, L.: Multiway spectral partitioning and higherorder cheeger inequalities. Journal of the ACM (JACM) 61(6), 37 (2014)

16

Y. Ge et al.

15. Leskovec, J., Lang, K.J., Mahoney, M.: Empirical comparison of algorithms for
network community detection. In: WWW. pp. 631–640. ACM (2010)
16. Li, P., He, N., Milenkovic, O.: Quadratic decomposable submodular function minimization. In: NIPS. pp. 1062–1072 (2018)
17. Li, P., Milenkovic, O.: Inhomogoenous hypergraph clustering with applications. In:
NIPS. pp. 2305–2315 (2017)
18. Lusseau, D.: The emergent properties of a dolphin social network. Proceedings of
the Royal Society of London B: Biological Sciences 270, S186–S188 (2003)
19. MacQueen, J., et al.: Some methods for classification and analysis of multivariate
observations. In: Proceedings of the Fifth Berkeley Symposium on Mathematical
Statistics and Probability. vol. 1, pp. 281–297. Oakland, CA, USA (1967)
20. Meila, M., Shi, J.: Learning segmentation by random walks. In: NIPS (2001)
21. Milo, R., Shen-Orr, S., Itzkovitz, S., Kashtan, N., Chklovskii, D., Alon, U.: Network
motifs: simple building blocks of complex networks. Science 298(5594) (2002)
22. Newman, M.E.: Modularity and community structure in networks. Proceedings of
the National Academy of Sciences 103(23), 8577–8582 (2006)
23. Newman, M.E.: Communities, modules and large-scale structure in networks. Nature Physics 8(1) (2012)
24. Ng, A.Y., Jordan, M.I., Weiss, Y.: On spectral clustering: Analysis and an algorithm. In: NIPS. pp. 849–856 (2002)
25. Ou, M., Cui, P., Pei, J., Zhang, Z., Zhu, W.: Asymmetric transitivity preserving
graph embedding. In: KDD. pp. 1105–1114. ACM (2016)26. Porter, M.A., Onnela, J.P., Mucha, P.J.: Communities in networks. Notices of the
AMS 56(9), 1082–1097 (2009)27. Schaeffer, S.E.: Graph clustering. Computer Science Review 1(1), 27–64 (2007)
28. Serrour, B., Arenas, A., Gómez, S.: Detecting communities of triangles in complex
networks using spectral optimization. Computer Communications 34(5) (2011)
29. Shi, J., Malik, J.: Normalized cuts and image segmentation. IEEE Trans. on PAMI
22(8), 888–905 (2000)
30. Sporns, O., Kötter, R.: Motifs in brain networks. PLoS Biology 2(11), e369 (2004)
31. Tang, J., Qu, M., Wang, M., Zhang, M., Yan, J., Mei, Q.: Line: Large-scale information network embedding. In: WWW. pp. 1067–1077 (2015)
32. Tsourakakis, C.E., Pachocki, J., Mitzenmacher, M.: Scalable motif-aware graphclustering. In: WWW. pp. 1451–1460 (2017)
33. Von Luxburg, U.: A tutorial on spectral clustering. Statistics and Computing
17(4), 395–416 (2007)
34. Wu, T., Benson, A.R., Gleich, D.F.: General tensor spectral co-clustering forhigher-order data. In: NIPS. pp. 2559–2567 (2016)
35. Xu, J., Wickramarathne, T.L., Chawla, N.V.: Representing higher-order dependencies in networks. Science Advances 2(5), e1600028 (2016)36. Yang, J., Leskovec, J.: Defining and evaluating network communities based on
ground-truth. Knowledge and Information Systems 42(1), 181–213 (2015)37. Yin, H., Benson, A.R., Leskovec, J., Gleich, D.F.: Local higher-order graph clustering. In: KDD. pp. 555–564. ACM (2017)
38. Zachary, W.W.: An information flow model for conflict and fission in small groups.
Journal of Anthropological Research 33(4), 452–473 (1977)
39. Zhou, D., Zhang, S., Yildirim, M.Y., Alcorn, S., Tong, H., Davulcu, H., He, J.: A
local algorithm for structure-preserving graph cut. In: KDD. pp. 655–664 (2017)