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.
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:
- ADMM (Alternating Direction Method of Multipliers): A general-purpose solver designed for speed and scalability, providing moderately accurate solutions suitable for large-scale datasets.
- 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.
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