Multi-view Contrastive Graph Clustering

In plain words

Some datasets describe the same items in several ways at once. For example, papers can be linked by shared authors and also by shared topics, and each link type is a separate graph. Each item may also have its own list of keywords. Any single graph is noisy or incomplete, so clustering on one of them gives weaker groups.

This method first smooths the keyword features over each graph. Items that are connected then get similar feature values, and random noise is reduced. Next it learns one new graph from these smoothed features, in which items that look alike are linked. Views that help more get a larger say. A contrastive rule pulls each item toward its nearest neighbours and pushes it away from the rest, which makes the new graph easier to split into groups. The final groups come from this learned graph.

TL;DR

MCGC handles attributed graphs with several feature views and several graphs. It smooths features with a two-step graph filter, learns one consensus graph by alternating optimisation, and adds a graph-level contrastive term over each node's 10 nearest neighbours. The authors report the best ACC on all five benchmarks against shallow and deep baselines. The official code has several paper-versus-code gaps and a clustering-time label leak, so treat the numbers as author-reported.

Problem

Graph clustering methods for one graph do not handle several graphs with several feature views at once. Earlier multi-view methods treat either multiple graphs or multiple attribute views, not both §1 §2. The initial graph is often noisy or incomplete, which motivates learning a new graph §1. The authors argue that the views are complementary and share important factors such as geometry and semantics §1. The method smooths features over the graph before learning §3.2. The paper states that the learned graph is an N×N matrix, which is the main memory cost §7.

Method

MCGC runs in three stages §3: graph filtering, consensus graph learning with a per-view weight, and a graph-level contrastive regulariser. Optimisation alternates between the graph S and the view weights λ^v §3.5 alg. 1.

Notation §3.1. Each dataset has V views. View v has an adjacency matrix Ã^v (with self-loops added in the normalised form), a degree matrix D^v, and features X^v (N×d). The normalised adjacency is A^v = (D^v)^(-1/2)(Ã^v + I)(D^v)^(-1/2), and the Laplacian is L^v = I − A^v.

Graph filtering §3.2. Smoothed features H solve a Laplacian-regularised least-squares problem eq. 1. Its closed form is eq. 2. The method replaces the inverse by a Taylor expansion and uses the m-th order filter eq. 3. The text says this removes high-frequency noise while keeping graph geometry §3.2.

Graph learning §3.3. The consensus graph S is learned from the smoothed features by self-expression eq. 4. For V views, each view's reconstruction term is weighted by λ^v, and a regulariser on the weights is added eq. 5. The authors use the Frobenius norm of S as the regulariser on S eq. 4 eq. 5.

Graph contrastive regulariser §3.4. Unlike instance-level contrastive learning on augmented features, each node's k nearest neighbours in a view are positives, and the contrast is applied to the entries of S eq. 6. The regulariser J^v is a softmax-style loss over the row of S, with the denominator excluding the node itself. It pulls neighbours close and pushes non-neighbours apart §3.4.

Full objective §3.4. Combine the reconstruction terms and J^v across views, weighted by λ^v, with the weight regulariser eq. 7. The paper notes that MCGC builds the consensus graph from smoothed features rather than from raw data §3.4.

Optimisation §3.5. With λ fixed, the objective in S is minimised by gradient descent with Adam, using the gradient in eq. 9 to eq. 11. S is initialised by the solution of eq. 5 §3.5. With S fixed, each λ^v has a closed form eq. 13, from the simplified sub-problem eq. 12. The two steps alternate until convergence §3.5. The final affinity is the symmetrised, absolute-value graph C, which is then clustered alg. 1.

# MCGC  [alg. 1]
# Input:  adjacencies A~[v], features X[v], m, s, alpha, gamma, c
# Output: cluster labels for N nodes

def mcgc(adjacencies, features, m, s, alpha, gamma, c):
    # Initialise all view weights to one  [alg. 1]
    weights = ones(V)
    # Normalised adjacency and Laplacian per view  [§3.1] [alg. 1]
    for v in views:
        A[v] = normalise(adjacencies[v] + I)  # (N, N)
        L[v] = I - A[v]                       # (N, N)
    # Graph filtering: H[v] = (I - s L[v])^m X[v]  [§3.2] [eq. 3]
    for v in views:
        H[v] = filter(L[v], features[v], s, m)  # (N, d)
    # Initial consensus graph S*  [§3.5] [alg. 1]
    S = initial_consensus(H, weights, alpha)  # (N, N)
    # Alternate: update S, then the view weights  [§3.5] [alg. 1]
    while not converged:
        # Fix the weights, take one Adam step on S  [§3.5] [eq. 9]
        grad = gradient_S(S, H, weights, alpha)
        S = adam_step(S, grad)
        # Fix S, update each view weight  [§3.5] [eq. 13]
        for v in views:
            M[v] = frobenius(H[v].T - H[v].T @ S) + alpha * J[v](S)
            weights[v] = (-M[v] / gamma) ** (1 / (gamma - 1))
    # Symmetric affinity, then cluster into c groups  [alg. 1]
    C = (abs(S) + abs(S).T) / 2
    return cluster(C, c)

# Gradient of the S-objective for entry (i, j)  [eq. 9] [eq. 10] [eq. 11]
# n is the total number of neighbours across all views  [§3.5]
def gradient_entry(i, j, S, H, weights, neighbours, alpha, n):
    # Reconstruction part  [eq. 10]
    first = 0
    for v in views:
        first += weights[v] * (-2 * (H[v] @ H[v].T)[i, j]
                               + 2 * (H[v] @ H[v].T @ S)[i, j])
    # Contrastive part  [eq. 11]; K is the sum over p != i of exp(S[i, p])
    second = 0
    for v in views:
        if j in neighbours[v][i]:
            second += weights[v] * (-1 + n * exp(S[i, j]) / K[i])
        else:
            second += weights[v] * (n * exp(S[i, j]) / K[i])
    return first + alpha * second

Key equations, as written in the paper eq. 1 to eq. 13:

\min_H \|H - X\|_F^2 + s\,\mathrm{Tr}(H^\top L H) eq. 1

H = (I + sL)^{-1} X eq. 2

H = (I - sL)^m X eq. 3

\min_S \|H^\top - H^\top S\|_F^2 + \alpha \|S\|_F^2 eq. 4

\min_{S,\lambda^v} \sum_{v=1}^V \lambda^v\left(\|H^{v\top} - H^{v\top}S\|_F^2 + \alpha\|S\|_F^2\right) + \sum_{v=1}^V (\lambda^v)^\gamma eq. 5

\mathcal{J} = \sum_{i=1}^N \sum_{j \in \mathbb{N}_i^v} -\log \frac{\exp(S_{ij})}{\sum_{p \neq i}^N \exp(S_{ip})} eq. 6

\min_{S,\lambda^v} \sum_{v=1}^V \lambda^v\left(\|H^{v\top} - H^{v\top}S\|_F^2 + \alpha\,\mathcal{J}^v\right) + \sum_{v=1}^V (\lambda^v)^\gamma eq. 7

\min_S \sum_{v=1}^V \lambda^v\left(\|H^{v\top} - H^{v\top}S\|_F^2 + \alpha\,\mathcal{J}^v\right) eq. 8

\nabla^{(t)} = \nabla_1^{(t)} + \alpha\,\nabla_2^{(t)} eq. 9

\nabla_1^{(t)} = 2\sum_{v=1}^V \lambda^v\left(-[H^v H^{v\top}]_{ij} + [H^v H^{v\top} S^{(t-1)}]_{ij}\right) eq. 10

\nabla_2^{(t)} = \begin{cases} \sum_{v} \lambda^v\left(-1 + \dfrac{n\,\exp(S_{ij}^{(t-1)})}{K^{(t-1)}}\right), & j \in \mathbb{N}_i^v \\ \sum_{v} \lambda^v\,\dfrac{n\,\exp(S_{ij}^{(t-1)})}{K^{(t-1)}}, & \text{otherwise} \end{cases} eq. 11

\min_{\lambda^v} \sum_{v=1}^V \lambda^v M^v + \sum_{v=1}^V (\lambda^v)^\gamma, \quad M^v = \|H^{v\top} - H^{v\top}S\|_F^2 + \alpha\mathcal{J}^v eq. 12

\lambda^v = \left(\frac{-M^v}{\gamma}\right)^{\frac{1}{\gamma - 1}} eq. 13

Notes on these equations §3.5: K^(t−1) is defined as the sum over p ≠ i of exp(S_ip^(t−1)) §3.5. The paper says n is the total number of neighbours, with the neighbours of each graph all included §3.5. eq. 8 is the sub-problem with λ fixed, and eq. 9 is the derivative used in the Adam step alg. 1.

Algorithm 1 alg. 1 (paper's wording, summarised): inputs are the adjacencies, features, m, α, s, γ and the cluster count c. Set λ^v = 1; build A^v and L^v; filter each view with eq. 3; repeat the S update by Adam eq. 9 and the λ^v update eq. 13 until convergence; set C = (|S| + |S|ᵀ)/2; cluster C.

Hyperparameters

Learning rate defaults in the code are not in the paper: Adam.py.

Dataset statistics tab. 1:

The Amazon datasets build a second feature matrix by a Cartesian product, following the cited multi-view attribute GCN paper §4.1. The text gives no formula §4.1.

Results

Author-reported. Setup: five attributed multi-view graph benchmarks, metrics ACC, NMI, ARI and F1 §4.1. Baselines: LINE and GAE (best single view), PMNE, RMSC, SwMC, O2MA, O2MAC, MAGCN, COMPLETER and MVGRL §4.2. The authors copied part of the baseline numbers from the O2MA paper for fairness §4.2. MAGCN ran out of memory on Amazon computers tab. 3. MCGC* is the variant that uses only neighbours shared by all views §4.2. Repeats, seeds and variance are not stated.

tab. 2 Results on ACM, DBLP and IMDB:

tab. 3 Results on Amazon photos and Amazon computers ("--" is out of memory):

Headline claims in the text §4.3: MCGC improves ACC over GAE by more than 9%, 4% and 19% on ACM, DBLP and IMDB. The text also says the method beats O2MAC by almost 6%, 9% and 11% on ACC, NMI and F1 on average, and beats MAGCN by more than 20% on all metrics. Over MVGRL the text reports a 20% gain.

Ablations §5:

tab. 4 Results without the contrastive loss (MCGC w/o J, which uses the Frobenius term of eq. 5 instead):

tab. 5 Single-view and multi-view inputs, ACM and Amazon photos, with G1 and G2 the graphs and X the features. The best setting uses all views:

tab. 6 MCGC against MCGC- (no graph filtering; the reconstruction term uses the raw features X^v in place of H^v eq. 15):

The text says ACC drops by 0.8%, 1.3% and 0.8% on ACM, DBLP and IMDB without filtering §5.3. The table gives drops of 0.86, 1.36 and 0.73 ACC points.

Sensitivity §6: fig. 1 shows m in 1 to 5 and s in a range from 0.01 to 10 on ACM; small m and s give reasonable results. fig. 2 shows α from 10⁻³ to 10³ on ACM, DBLP and IMDB. The text says the method is not sensitive to α §6. fig. 3 shows the objective of eq. 7 falling quickly on ACM, DBLP and IMDB §6.

Paper vs code

Repository: https://github.com/Panern/MCGC, master branch, cloned at 9d77ffe346a61dc09b8363256472ac4f0551d532. The paper footnote links this repository §4.2, which is the basis for treating it as official. The repository holds five Python files, a config and a README. It does not match the paper in several places. Cited files are relative to the repository root. We did not run the code, because the shipped code imports modules and data that are not in the repository (see below).

What we searched: the paper's footnote link, the abstract and the arXiv comments (no other repository), then the author's GitHub user and the repository name. We found no second official repository.

1. Amazon branch crashes as written. The Amazon path reads X[3] from a list of three items main.py LoadData_MCGC.py. The loader returns attribute, attribute Gram matrix, adjacency. Paper: the Amazon datasets use two feature views and one graph §4.1.
2. Graph filtering uses one graph for all views. The non-Amazon branch loops over every graph but keeps only the last one's Laplacian, and each pass filters every view twice main.py. So filtering runs 2V times with the last graph. Paper: each view v is filtered as (I − sL^v)^m X^v with its own L^v eq. 3 alg. 1. The same initial feature matrix is copied to every view main.py.
3. Initial view weights. Code sets 1/V main.py. Paper: λ^v = 1 [alg. 1, line 1].
4. Neighbour count in the gradient. The code uses 10 neighbours per view in the contrastive gradient main.py, not the total across views. Paper: n is the total number of neighbours across all graphs §3.5 eq. 11.
5. View-weight update uses the best S, not the current one. main.py uses best_S, which is the best S seen so far. Paper: with S fixed, update λ^v from the current S §3.5 eq. 13. The code updates λ once per round of up to 100 epochs, after the S loop main.py main.py, not after each S step.
6. Initial S. For datasets other than ACM, the code uses a closed form with a α·L term and L = D − A, where D holds the inverse-square-root degrees Initialization.py Initialization.py. Paper: S is initialised with the solution of eq. 5 §3.5, which has no L term. For ACM the code loads ./Initialization/ACM_initialS.npy main.py. That file is not in the repository, so ACM cannot start from the shipped path.
7. Diagonal of S forced to zero. The code sets S_ii = 0 before each epoch main.py. Paper: not stated.
8. γ per dataset. Paper: γ = −4 for all datasets §4.2. Code: ACM −5, DBLP −4, IMDB −2, Amazon photos −1, Amazon computers −1 config.yaml. Its grid search covers −1 to −5 main.py.
9. Model selection uses ground-truth labels. The code computes ACC against the true labels after each epoch and keeps the epoch with the best ACC main.py. It records the best-epoch result for each (α, γ) grid point main.py; the code does not say which grid point is the one reported. The paper says only that α was tuned §6. Treat the tables as optimistic unless re-run with an unsupervised selection rule.
10. Learning rate. Paper: not stated. Code: the Adam defaults, learning rate 10⁻³, are used because no value is passed Adam.py main.py.
11. Neighbour selection. Code: the 10 nearest neighbours of each node by Euclidean distance on the smoothed features, excluding the node itself, cached as .npy files main.py. Paper: the distance metric is not stated.
12. Shared-neighbour variant (MCGC*). Paper: N_i is the intersection over views §4.2. The repository has no intersection step; neighbours are kept per view main.py main.py. We could not confirm how MCGC* was computed.
13. Second Amazon feature view. Paper: a Cartesian product following the cited multi-view GCN paper §4.1. Code: the Gram matrix of the attributes, X·Xᵀ LoadData_MCGC.py LoadData_MCGC.py.
14. Clustering on C. Paper: "clustering on C" alg. 1. Code: the top-c left singular vectors of C, then k-means with random_state=23 main.py. A spectral-clustering alternative is commented out main.py.
15. Stopping rule. Paper: until convergence §3.5. Code: a tolerance on the loss relative to its order of magnitude, a counter that stops after ten epochs without improvement, 100 epochs for each of three rounds main.py main.py.
16. Tracked objective omits the λ weights. The stopping loss adds the views without λ^v weights main.py. So the loss curve the code tracks is not the objective of eq. 7 that figure 3 plots §6.
17. Repository is incomplete. train_sym.py imports Metrics_O2MAC, but that folder contains only .new train_sym.py. Data folders are empty except ACM3025.mat; DBLP, IMDB and the Amazon .npz files are not in the repository LoadData_MCGC.py LoadData_MCGC.py LoadData_MCGC.py. main.py is the PyCharm template main.py. The code also uses np.int main.py and yaml.load without a loader main.py, which fail on current NumPy and PyYAML. The shipped code cannot run end to end as it stands.
18. README value. The README reports IMDB ACC as 61.13 README.md. That equals the paper's MCGC* value (0.6113), not MCGC (0.6182) tab. 2.

The code's reconstruction part of the gradient matches eq. 10 main.py.

Pitfalls

• Label leak in reported numbers. Any reimplementation that copies the code's selection will overstate results. Use an unsupervised rule (for example, the final objective) for α, γ and the epoch.
• Dense N×N state and per-pair loops. S is dense and N×N, which the paper states is the memory limit §7. The code also loops over all node pairs and views in Python for each gradient step main.py. Expect slow runs on the 13,381-node dataset.
• Weight formula is numerically sensitive. With γ < 0, λ^v = (−M^v/γ)^(1/(γ−1)). M^v includes αJ^v, so λ^v depends strongly on the scale of α and N. The weights are not normalised eq. 13 main.py.
• Filter parameters are not per view. Paper: m = 2 and s = 0.5 for all datasets §6. Code: the filter is a single Laplacian shared by all views (see Paper vs code 2).
• Self-loop and diagonal conventions. Paper: the normalised adjacency adds the identity §3.1. The softmax denominator in eq. 6 excludes p = i, but the paper does not say whether S_ii is constrained. The code sets it to zero.
• Absolute values in C. The affinity uses |S|, so signed entries of S are discarded before clustering alg. 1.
• Cluster count must be given. The method needs c alg. 1 inputs.
• Baselines partly copied. The paper copies some baseline numbers from O2MA for comparability §4.2. Results are not re-run under one protocol, and seeds, runs and variance are not stated.
• Ablation text and tables differ slightly. The text's ACC drops without filtering (0.8%, 1.3%, 0.8%) do not match tab. 6 (0.86, 1.36, 0.73 points). Use the tables.
• Bold markers. In tab. 2, DBLP ARI is bold for MCGC* (0.7995), not MCGC (0.7746). The IMDB F1 entry for MCGC w/o J (0.4444) is bold in tab. 4, above MCGC on IMDB F1 (0.4401). So "best on all metrics" in the text does not hold for every cell.

Lineage

• Builds on: graph filtering by a Laplacian-regularised smoothing problem §3.2 (cited as zhu2021interpreting and lin2021multi; the paper gives no arXiv ids); self-expression for graph learning §3.3; graph-level contrast on learned affinities, with a contrastive loss in the style of instance-level methods §2.
• Compared against: LINE, GAE, PMNE, RMSC, SwMC, O2MA and O2MAC (One2Multi graph autoencoder clustering), MAGCN, COMPLETER, MVGRL §4.2. O2MA and MAGCN are cited as the closest attributed multi-view graph clustering methods §1.
• Superseded by: not known from content in this wiki.