Triangle Lasso for Simultaneous Clustering and Optimization in Graph Datasets

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

Abstract

Recently, network lasso has drawn significant attention due to its remarkable performance in simultaneous clustering and optimization. However, it often suffers from imperfect data, such as noise or missing values, yielding sub-optimal solutions. This is because it determines instance similarity directly from features, which are easily corrupted. In this paper, we propose the Triangle Lasso to overcome these limitations. Triangle Lasso identifies similar instances based on their graph neighbors: if two instances share many common neighbors, they are more likely to be similar. This topological approach remains robust even when individual instance profiles are noisy. We develop an efficient algorithm based on the Alternating Direction Method of Multipliers (ADMM) for moderately accurate solutions and a dual method for high-accuracy solutions with low additional time consumption. Extensive numerical experiments demonstrate that Triangle Lasso is robust to imperfect data and outperforms state-of-the-art methods in practical data analysis tasks.

Introduction: The Challenge of Imperfect Data

In machine learning, simultaneous clustering and optimization is a powerful paradigm, exemplified by the Network Lasso. This approach allows for the training of local models—such as predicting house prices or stock trends—while grouping similar entities together to share information. However, the standard Network Lasso has a significant vulnerability: it relies heavily on feature similarity to establish connections. When data is noisy or contains missing values, these feature-based connections break down, leading to poor clustering and inaccurate predictions.

To address this, researchers have introduced the Triangle Lasso. Instead of relying solely on potentially corrupted features, this framework leverages the inherent topology of the graph. By focusing on "shared neighbors," the model can infer similarity even when the direct data for a specific node is unreliable.

Methodology: Leveraging Graph Topology

The core innovation of the Triangle Lasso is its use of graph triangles to regularize the optimization problem. In a standard network-based model, a penalty is applied to the difference between the parameters of two connected nodes. Triangle Lasso enhances this by increasing the penalty based on the number of shared neighbors between nodes.

The Triangle Lasso uses shared neighbors (triangles) to maintain robust similarity measures even when a vertex is noisy.

As shown in the figure above, even if vertex $i$ is "noisy" (having corrupted or missing features), its strong topological connection to vertex $j$ through shared neighbors suggests they should belong to the same cluster. This "topology as a buffer" strategy ensures that the global structure of the network guides the local optimization.

Optimization Framework

To solve the resulting convex optimization problem, the authors propose two distinct paths:

  1. ADMM (Alternating Direction Method of Multipliers): A general-purpose solver designed for speed and scalability, providing moderately accurate solutions suitable for large-scale datasets.
  2. Dual Method: By transforming the problem into a Second-Order Cone Programming (SOCP) problem in the dual space, the authors achieve high-accuracy solutions. This method is particularly efficient for sparse graphs, as it reduces the number of variables the optimizer must track.

Experimental Results

The Triangle Lasso was tested against several real-world datasets characterized by high noise or missing features, including real estate transactions (RET), tennis match outcomes (AOM), and Wikipedia usage in education (wiki4HE).

Robustness in Real Estate Prediction

In the Sacramento housing dataset (RET), which contained 17% missing features, the Triangle Lasso significantly outperformed the standard Network Lasso. As noise levels increased, the Triangle Lasso maintained a much lower Mean Square Error (MSE). The model successfully identified geographical clusters where housing price factors were similar, despite the imperfect data.

Clustering results on the Sacramento housing dataset, showing how the regularization parameter alpha controls the granularity of the clusters.

Efficiency and Community Detection

Beyond regression, the method showed strong performance in community detection on large networks like Amazon and DBLP (over 300k nodes). It proved more deterministic and less sensitive to initial conditions than traditional algorithms like PageRank-based methods. Furthermore, the ADMM implementation provided significant speedups, handling thousands of instances where previous iterative methods struggled.

Conclusion and Future Directions

The Triangle Lasso represents a significant step forward in making simultaneous clustering and optimization robust for real-world applications. By shifting the focus from noisy features to stable graph topology, it provides a reliable framework for analyzing imperfect datasets.

While highly effective for sparse networks, future work will focus on scaling the dual method for dense graphs, potentially through graph partitioning techniques. Additionally, automating the selection of the regularization parameter $\alpha$ remains an open area for further refinement.

Summary updated

Abstract

Recently, network lasso has drawn many attentions 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. Triangle lasso finds the similar instances according to their neighbours. If two instances have many common neighbours, 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 Xinwang Liu and En Zhu 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},
}
Figure