Harnessing the mathematics of matrix decomposition to solve planted and maximum clique problem
Why this work is in the frame
A frame that forgets how it found something cannot be audited. These are the routes that admitted this work.
Bibliographic record
Abstract
We consider the problem of identifying a maximum clique in a given graph. We have proposed a mathematical model for this problem. The model resembles the matrix decomposition of the adjacency matrix of a given graph. The objective function of the mathematical model includes a weighted $\ell_{1}$-norm of the sparse matrix of the decomposition, which has an advantage over the known $\ell_{1}-$norm in reducing the error. The use of dynamically changing the weights for the $\ell_{1}$-norm has been motivated. We have used proximal operators within the iterates of the ADMM (alternating direction method of multipliers) algorithm to solve the optimization problem. Convergence of the proposed ADMM algorithm has been provided. The theoretical guarantee of the maximum clique in the form of the low-rank matrix has also been established using the golfing scheme to construct approximate dual certificates. We have constructed conditions that guarantee the recovery and uniqueness of the solution, as well as a tight bound on the dual matrix that validates optimality conditions. Numerical results for planted cliques are presented showing clear advantages of our model when compared with two recent mathematical models. Results are also presented for randomly generated graphs with minimal errors. These errors are found using a formula we have proposed based on the size of the clique. Moreover, we have applied our algorithm to real-world graphs for which cliques have been recovered successfully. The validity of these clique sizes comes from the decomposition of input graph into a rank-one matrix (corresponds to the clique) and a sparse matrix.
Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.
Full frame distilled prediction
Teacher imitationNot calibrated prevalence, not ground truth. Human validation pending. Learned from the 10,348 direct Codex labels and 10,348 direct Gemma labels. Candidate is the union of thresholded teacher heads; consensus is their intersection. These outputs are machine_predicted_unvalidated and are not human labels or direct frontier model labels.
Codex and Gemma teacher scores by category
| Category | Codex | Gemma |
|---|---|---|
| Metaresearch | 0.000 | 0.000 |
| Meta-epidemiology (narrow) | 0.000 | 0.000 |
| Meta-epidemiology (broad) | 0.000 | 0.000 |
| Bibliometrics | 0.000 | 0.001 |
| Science and technology studies | 0.000 | 0.000 |
| Scholarly communication | 0.000 | 0.000 |
| Open science | 0.001 | 0.002 |
| Research integrity | 0.000 | 0.000 |
| Insufficient payload (model declined to judge) | 0.000 | 0.000 |
Machine scores (provisional)
The two teacher heads of the student model, read on this work. A score orders the frame for review; it never asserts a category, and the validation status ships verbatim with every row.
Baseline scores from an immature model (maturity gate not passed, 7 training rounds). Scores rank; they never assert a category.
score_only:v0-immature-baseline · verbatim from the scoring run: score_only means the number may rank works, and no category label ships from it