Triangle Lasso for Simultaneous Clustering and Optimization in Graph Datasets

Yawei Zhao, Kai Xu, En Zhu, Xinwang Liu, Xinzhong Zhu, Jianping Yin

In the world of machine learning, we often want to do two things at once: optimize a local model (like predicting a house price) and cluster similar instances together. This is the bread and butter of the Network Lasso. However, Network Lasso has a "glass jaw"—it relies heavily on feature similarity. If your data is noisy, missing values, or otherwise "imperfect," the clustering fails, and the optimization suffers.

A team of researchers has proposed a more robust alternative: the Triangle Lasso. By looking at the "friends of friends" in a graph, they’ve found a way to maintain high performance even when the underlying data is a mess.

TL;DR

Triangle Lasso is a robust optimization framework that uses graph triangles (shared neighbors) to improve simultaneous clustering and regression. By penalizing differences between nodes that share common neighbors more heavily, it remains accurate even when feature data is noisy or missing, outperforming the standard Network Lasso in both accuracy and efficiency.

What Problem Does This Paper Address?

The authors target the problem of imperfect data in simultaneous clustering and optimization.

Imagine predicting house prices across a city. Houses in the same district should have similar price-weighting factors (e.g., how much "number of rooms" affects the price). Network Lasso tries to learn these weights by looking at a graph of houses. If two houses are connected, it encourages them to have the same weights.

The catch? Network Lasso usually builds this graph based on features. If the "true cost" or "square footage" data is missing or noisy, the algorithm might fail to see that two houses are actually in the same neighborhood. The authors argue that graph topology—specifically the existence of triangles (shared neighbors)—is a much more stable signal for similarity than raw, noisy features.

Methods

The core innovation is the Triangle Lasso formulation. It modifies the standard sum-of-norms regularization used in convex clustering.

  1. Triangle-Based Regularization: Instead of just penalizing the difference between two connected nodes ($v_i$ and $v_j$), the Triangle Lasso increases the penalty if those nodes share common neighbors ($v_k$). If $v_i$ and $v_j$ are part of many triangles, the algorithm "forces" them to be more similar. This makes the model robust: even if $v_i$ has noisy features, the fact that it shares many neighbors with $v_j$ tells the model they should likely belong to the same cluster.
  2. Two Optimization Paths:
    • ADMM (Alternating Direction Method of Multipliers): Developed for "moderately accurate" solutions. It is highly efficient and serves as the general-purpose solver for large datasets.
  3. Dual Method: The authors transform the problem into a Second-Order Cone Programming (SOCP) problem in the dual space. This method is designed to find highly accurate solutions and is particularly efficient when the graph is sparse.

Datasets

The authors evaluated their method across a diverse set of real-world scenarios:

  • RET (Real Estate Transactions): Predicting house prices in Sacramento (17% missing features).
  • AOM (AusOpen-men-2013): Predicting tennis match winners (17.1% missing values).
  • wiki4HE: Survey data on Wikipedia use in education (16.6% missing values).
  • DJI (Dow Jones Index): Weekly stock data with 20% synthetic noise added.
  • cpusmall: Computer system activity measures.
  • Community Detection: Large-scale networks including com-Amazon (334k nodes) and com-DBLP (317k nodes).

Key Insights and Ideas

  • Topology as a Buffer: The "aha moment" is that local graph structure acts as a buffer against feature noise. In a social or physical network, if two entities share many mutual connections, they are statistically likely to be similar, regardless of what their (potentially corrupted) individual profiles say.
  • The $Q$ Matrix: The authors introduce an auxiliary matrix $Q$ that encodes the "triangle" information. This allows them to wrap complex topological relationships into a standard-looking convex optimization problem.
  • Dual Space Efficiency: For sparse graphs, solving the problem in the dual space is significantly faster because it reduces the number of variables the optimizer needs to track compared to the primal space.

Key Results

  • Superior Robustness: In the Sacramento housing (RET) task, Triangle Lasso achieved a significantly lower Mean Square Error (MSE) than Network Lasso as the noise level ($\sigma$) increased from 1 to 5.
  • Speedups: On the cpusmall dataset, the Triangle Lasso-ADMM was orders of magnitude faster than the basic ADMM implementation, handling thousands of instances where previous methods struggled.
  • Community Detection: Triangle Lasso outperformed state-of-the-art community detection algorithms (like HKs and PPRs) on F1 scores, especially when the graph was "perturbed" (random edges added/removed). It proved to be more deterministic and less sensitive to initial "seed" nodes.

Limitations and Future Work

  • Dense Graph Bottleneck: While the Dual method is great for sparse graphs, its efficiency drops sharply as the graph becomes dense. The authors note that in very dense networks, the weights become "highly non-separable," making the linear equations difficult to solve.
  • Hyperparameter Sensitivity: The model relies on $\alpha$ (the regularization coefficient). While the paper shows how varying $\alpha$ creates a "cluster path," choosing the optimal $\alpha$ for a specific task still requires tuning.
  • Future Directions: The authors suggest exploring graph partitioning—dividing a massive dense graph into smaller sub-graphs—to allow the Dual method to scale to even larger, more complex datasets.

Summary updated

Abstract

Recently, network lasso has dawn much attention due to its remarkable performance on simultaneous clustering and optimization. However, it usually suffers from the imperfect data (noise, missing values, etc.), and yields sub-optimal solutions. The reason is that it finds the similar instances according to their features directly, which is usually impacted by the imperfect data, and thus returns sub-optimal results. In this paper, we propose triangle lasso to avoid its disadvantage for graph datasets. In a graph dataset, each instance is represented by a vertex. If two instances have many common adjacent vertices, they tend to become similar. Although some instances are profiled by the imperfect data, it is still able to find the similar counterparts. Furthermore, we develop an efficient algorithm based on Alternating Direction Method of Multipliers (ADMM) to obtain a moderately accurate solution. In addition, we present a dual method to obtain the accurate solution with the low additional time consumption. We demonstrate through extensive numerical experiments that triangle lasso is robust to the imperfect data. It usually yields a better performance than the state-of-the-art method when performing data analysis tasks in practical scenarios.
BibTeX
@article{zhao2019triangle,
  author = {Yawei Zhao and Kai Xu and En Zhu and Xinwang Liu and Xinzhong Zhu and Jianping Yin},
  title = {{Triangle Lasso for Simultaneous Clustering and Optimization in Graph Datasets}},
  journal = {IEEE Trans. Knowl. Data Eng.},
  year = {2019},
  url = {https://openreview.net/forum?id=-FQWFc1qle},
}

Loading related content...

Figure