{"id":"https://openalex.org/W4400222407","doi":"https://doi.org/10.48550/arxiv.2406.19532","title":"Differentiable Quadratic Optimization For The Maximum Independent Set Problem","display_name":"Differentiable Quadratic Optimization For The Maximum Independent Set Problem","publication_year":2024,"publication_date":"2024-06-27","ids":{"openalex":"https://openalex.org/W4400222407","doi":"https://doi.org/10.48550/arxiv.2406.19532"},"language":"en","primary_location":{"id":"pmh:oai:arXiv.org:2406.19532","is_oa":true,"landing_page_url":"http://arxiv.org/abs/2406.19532","pdf_url":"https://arxiv.org/pdf/2406.19532","source":{"id":"https://openalex.org/S4306400194","display_name":"arXiv (Cornell University)","issn_l":"2331-8422","issn":["2331-8422"],"is_oa":true,"is_in_doaj":false,"is_core":false,"host_organization":"https://openalex.org/I205783295","host_organization_name":"Cornell University","host_organization_lineage":["https://openalex.org/I205783295"],"host_organization_lineage_names":[],"type":"repository"},"license":"cc-by","license_id":"https://openalex.org/licenses/cc-by","version":"submittedVersion","is_accepted":false,"is_published":false,"raw_source_name":null,"raw_type":"text"},"type":"preprint","indexed_in":["arxiv","datacite"],"open_access":{"is_oa":true,"oa_status":"green","oa_url":"https://arxiv.org/pdf/2406.19532","any_repository_has_fulltext":true},"authorships":[{"author_position":"first","author":{"id":"https://openalex.org/A5003538946","display_name":"Ismail Alkhouri","orcid":"https://orcid.org/0000-0002-5754-5509"},"institutions":[],"countries":[],"is_corresponding":false,"raw_author_name":"Alkhouri, Ismail","raw_affiliation_strings":[],"raw_orcid":null,"affiliations":[]},{"author_position":"middle","author":{"id":"https://openalex.org/A5099801483","display_name":"Cedric Le Denmat","orcid":null},"institutions":[],"countries":[],"is_corresponding":false,"raw_author_name":"Denmat, Cedric Le","raw_affiliation_strings":[],"raw_orcid":null,"affiliations":[]},{"author_position":"middle","author":{"id":"https://openalex.org/A5100425074","display_name":"Yingjie Li","orcid":"https://orcid.org/0000-0002-8401-0649"},"institutions":[],"countries":[],"is_corresponding":false,"raw_author_name":"Li, Yingjie","raw_affiliation_strings":[],"raw_orcid":null,"affiliations":[]},{"author_position":"middle","author":{"id":"https://openalex.org/A5029321729","display_name":"Cunxi Yu","orcid":"https://orcid.org/0000-0003-3481-307X"},"institutions":[],"countries":[],"is_corresponding":false,"raw_author_name":"Yu, Cunxi","raw_affiliation_strings":[],"raw_orcid":null,"affiliations":[]},{"author_position":"middle","author":{"id":"https://openalex.org/A5100409739","display_name":"Jia Liu","orcid":"https://orcid.org/0000-0002-9845-2720"},"institutions":[],"countries":[],"is_corresponding":false,"raw_author_name":"Liu, Jia","raw_affiliation_strings":[],"raw_orcid":null,"affiliations":[]},{"author_position":"middle","author":{"id":"https://openalex.org/A5100733180","display_name":"Rongrong Wang","orcid":"https://orcid.org/0000-0003-0615-0838"},"institutions":[],"countries":[],"is_corresponding":false,"raw_author_name":"Wang, Rongrong","raw_affiliation_strings":[],"raw_orcid":null,"affiliations":[]},{"author_position":"last","author":{"id":"https://openalex.org/A5067109059","display_name":"Alvaro Velasquez","orcid":"https://orcid.org/0000-0001-6757-105X"},"institutions":[],"countries":[],"is_corresponding":false,"raw_author_name":"Velasquez, Alvaro","raw_affiliation_strings":[],"raw_orcid":null,"affiliations":[]}],"institutions":[],"countries_distinct_count":0,"institutions_distinct_count":0,"corresponding_author_ids":[],"corresponding_institution_ids":[],"apc_list":null,"apc_paid":null,"fwci":null,"has_fulltext":true,"cited_by_count":0,"citation_normalized_percentile":null,"cited_by_percentile_year":null,"biblio":{"volume":null,"issue":null,"first_page":null,"last_page":null},"is_retracted":false,"is_paratext":false,"is_xpac":false,"primary_topic":{"id":"https://openalex.org/T10320","display_name":"Neural Networks and Applications","score":0.9965000152587891,"subfield":{"id":"https://openalex.org/subfields/1702","display_name":"Artificial Intelligence"},"field":{"id":"https://openalex.org/fields/17","display_name":"Computer Science"},"domain":{"id":"https://openalex.org/domains/3","display_name":"Physical Sciences"}},"topics":[{"id":"https://openalex.org/T10320","display_name":"Neural Networks and Applications","score":0.9965000152587891,"subfield":{"id":"https://openalex.org/subfields/1702","display_name":"Artificial Intelligence"},"field":{"id":"https://openalex.org/fields/17","display_name":"Computer Science"},"domain":{"id":"https://openalex.org/domains/3","display_name":"Physical Sciences"}},{"id":"https://openalex.org/T12676","display_name":"Machine Learning and ELM","score":0.9832000136375427,"subfield":{"id":"https://openalex.org/subfields/1702","display_name":"Artificial Intelligence"},"field":{"id":"https://openalex.org/fields/17","display_name":"Computer Science"},"domain":{"id":"https://openalex.org/domains/3","display_name":"Physical Sciences"}},{"id":"https://openalex.org/T12702","display_name":"Brain Tumor Detection and Classification","score":0.9517999887466431,"subfield":{"id":"https://openalex.org/subfields/2808","display_name":"Neurology"},"field":{"id":"https://openalex.org/fields/28","display_name":"Neuroscience"},"domain":{"id":"https://openalex.org/domains/1","display_name":"Life Sciences"}}],"keywords":[{"id":"https://openalex.org/keywords/set","display_name":"Set (abstract data type)","score":0.6629534959793091},{"id":"https://openalex.org/keywords/artificial-neural-network","display_name":"Artificial neural network","score":0.655998706817627},{"id":"https://openalex.org/keywords/quadratic-equation","display_name":"Quadratic equation","score":0.6333500146865845},{"id":"https://openalex.org/keywords/computer-science","display_name":"Computer science","score":0.48846736550331116},{"id":"https://openalex.org/keywords/mathematical-optimization","display_name":"Mathematical optimization","score":0.394179105758667},{"id":"https://openalex.org/keywords/mathematics","display_name":"Mathematics","score":0.3770468533039093},{"id":"https://openalex.org/keywords/artificial-intelligence","display_name":"Artificial intelligence","score":0.2729361653327942},{"id":"https://openalex.org/keywords/geometry","display_name":"Geometry","score":0.04788437485694885},{"id":"https://openalex.org/keywords/programming-language","display_name":"Programming language","score":0.0394006073474884}],"concepts":[{"id":"https://openalex.org/C177264268","wikidata":"https://www.wikidata.org/wiki/Q1514741","display_name":"Set (abstract data type)","level":2,"score":0.6629534959793091},{"id":"https://openalex.org/C50644808","wikidata":"https://www.wikidata.org/wiki/Q192776","display_name":"Artificial neural network","level":2,"score":0.655998706817627},{"id":"https://openalex.org/C129844170","wikidata":"https://www.wikidata.org/wiki/Q41299","display_name":"Quadratic equation","level":2,"score":0.6333500146865845},{"id":"https://openalex.org/C41008148","wikidata":"https://www.wikidata.org/wiki/Q21198","display_name":"Computer science","level":0,"score":0.48846736550331116},{"id":"https://openalex.org/C126255220","wikidata":"https://www.wikidata.org/wiki/Q141495","display_name":"Mathematical optimization","level":1,"score":0.394179105758667},{"id":"https://openalex.org/C33923547","wikidata":"https://www.wikidata.org/wiki/Q395","display_name":"Mathematics","level":0,"score":0.3770468533039093},{"id":"https://openalex.org/C154945302","wikidata":"https://www.wikidata.org/wiki/Q11660","display_name":"Artificial intelligence","level":1,"score":0.2729361653327942},{"id":"https://openalex.org/C2524010","wikidata":"https://www.wikidata.org/wiki/Q8087","display_name":"Geometry","level":1,"score":0.04788437485694885},{"id":"https://openalex.org/C199360897","wikidata":"https://www.wikidata.org/wiki/Q9143","display_name":"Programming language","level":1,"score":0.0394006073474884}],"mesh":[],"locations_count":2,"locations":[{"id":"pmh:oai:arXiv.org:2406.19532","is_oa":true,"landing_page_url":"http://arxiv.org/abs/2406.19532","pdf_url":"https://arxiv.org/pdf/2406.19532","source":{"id":"https://openalex.org/S4306400194","display_name":"arXiv (Cornell University)","issn_l":"2331-8422","issn":["2331-8422"],"is_oa":true,"is_in_doaj":false,"is_core":false,"host_organization":"https://openalex.org/I205783295","host_organization_name":"Cornell University","host_organization_lineage":["https://openalex.org/I205783295"],"host_organization_lineage_names":[],"type":"repository"},"license":"cc-by","license_id":"https://openalex.org/licenses/cc-by","version":"submittedVersion","is_accepted":false,"is_published":false,"raw_source_name":null,"raw_type":"text"},{"id":"doi:10.48550/arxiv.2406.19532","is_oa":true,"landing_page_url":"https://doi.org/10.48550/arxiv.2406.19532","pdf_url":null,"source":{"id":"https://openalex.org/S4306400194","display_name":"arXiv (Cornell University)","issn_l":"2331-8422","issn":["2331-8422"],"is_oa":true,"is_in_doaj":false,"is_core":false,"host_organization":"https://openalex.org/I205783295","host_organization_name":"Cornell University","host_organization_lineage":["https://openalex.org/I205783295"],"host_organization_lineage_names":[],"type":"repository"},"license":"cc-by","license_id":"https://openalex.org/licenses/cc-by","version":null,"is_accepted":false,"is_published":null,"raw_source_name":null,"raw_type":"Preprint"}],"best_oa_location":{"id":"pmh:oai:arXiv.org:2406.19532","is_oa":true,"landing_page_url":"http://arxiv.org/abs/2406.19532","pdf_url":"https://arxiv.org/pdf/2406.19532","source":{"id":"https://openalex.org/S4306400194","display_name":"arXiv (Cornell University)","issn_l":"2331-8422","issn":["2331-8422"],"is_oa":true,"is_in_doaj":false,"is_core":false,"host_organization":"https://openalex.org/I205783295","host_organization_name":"Cornell University","host_organization_lineage":["https://openalex.org/I205783295"],"host_organization_lineage_names":[],"type":"repository"},"license":"cc-by","license_id":"https://openalex.org/licenses/cc-by","version":"submittedVersion","is_accepted":false,"is_published":false,"raw_source_name":null,"raw_type":"text"},"sustainable_development_goals":[],"awards":[],"funders":[{"id":"https://openalex.org/F4320306076","display_name":"National Science Foundation","ror":"https://ror.org/021nxhr62"},{"id":"https://openalex.org/F4320309292","display_name":"Princeton University","ror":"https://ror.org/00hx57361"},{"id":"https://openalex.org/F4320332180","display_name":"Defense Advanced Research Projects Agency","ror":"https://ror.org/02caytj08"}],"has_content":{"pdf":true,"grobid_xml":true},"content_urls":{"pdf":"https://content.openalex.org/works/W4400222407.pdf","grobid_xml":"https://content.openalex.org/works/W4400222407.grobid-xml"},"referenced_works_count":0,"referenced_works":[],"related_works":["https://openalex.org/W4391375266","https://openalex.org/W1979597421","https://openalex.org/W2007980826","https://openalex.org/W2061531152","https://openalex.org/W3002753104","https://openalex.org/W2077600819","https://openalex.org/W2142036596","https://openalex.org/W2072657027","https://openalex.org/W2600246793","https://openalex.org/W4238204885"],"abstract_inverted_index":{"Combinatorial":[0],"Optimization":[1,126],"(CO)":[2],"addresses":[3],"many":[4],"important":[5],"problems,":[6],"including":[7],"the":[8,82,91,94,134,137,152,190,195,200,203,212],"challenging":[9],"Maximum":[10,42],"Independent":[11],"Set":[12],"(MIS)":[13],"problem.":[14],"Alongside":[15],"exact":[16,186],"and":[17,63,85,145,155,169,187],"heuristic":[18,188],"solvers,":[19,189],"differentiable":[20],"approaches":[21],"have":[22],"emerged,":[23],"often":[24],"using":[25,103],"continuous":[26],"relaxations":[27],"of":[28,93,136,181,197,205],"ReLU-based":[29],"or":[30],"quadratic":[31,52],"objectives.":[32],"Noting":[33],"that":[34,67],"an":[35,58,109],"MIS":[36,55,83,111,128,167],"in":[37,45,101,199],"a":[38,41,50,74,178],"graph":[39],"is":[40,183,209],"Clique":[43],"(MC)":[44],"its":[46],"complement,":[47],"we":[48,96],"propose":[49,97],"new":[51],"formulation":[53],"for":[54,127],"by":[56,108,161],"incorporating":[57],"MC":[59],"term,":[60],"improving":[61],"convergence":[62],"exploration.":[64],"We":[65,118],"show":[66],"every":[68],"maximal":[69],"independent":[70],"set":[71],"corresponds":[72],"to":[73,81,141,173],"local":[75],"minimizer,":[76],"derive":[77],"conditions":[78],"with":[79,194],"respect":[80],"size,":[84],"characterize":[86],"stationary":[87],"points.":[88],"To":[89],"tackle":[90],"non-convexity":[92],"objective,":[95],"optimizing":[98],"several":[99],"initializations":[100],"parallel":[102],"momentum-based":[104],"gradient":[105],"descent,":[106],"complemented":[107],"efficient":[110],"checking":[112],"criterion":[113],"derived":[114],"from":[115],"our":[116,120,149],"theory.":[117],"dub":[119],"method":[121,139,150],"as":[122],"parallelized":[123],"Clique-Informed":[124],"Quadratic":[125],"(pCQO-MIS).":[129],"Our":[130,207],"experimental":[131],"results":[132],"demonstrate":[133],"effectiveness":[135],"proposed":[138],"compared":[140],"exact,":[142],"heuristic,":[143],"sampling,":[144],"data-centric":[146,162],"approaches.":[147],"Notably,":[148],"avoids":[151],"out-of-distribution":[153],"tuning":[154],"reliance":[156],"on":[157],"(un)labeled":[158],"data":[159],"required":[160],"methods,":[163],"while":[164],"achieving":[165],"superior":[166],"sizes":[168],"competitive":[170],"runtime":[171,191],"relative":[172],"their":[174],"inference":[175],"time.":[176],"Additionally,":[177],"key":[179],"advantage":[180],"pCQO-MIS":[182],"that,":[184],"unlike":[185],"scales":[192],"only":[193],"number":[196,204],"nodes":[198],"graph,":[201],"not":[202],"edges.":[206],"code":[208],"available":[210],"at":[211],"GitHub":[213],"repository:":[214],"https://github.com/ledenmat/pCQO-mis-benchmark/tree/refactor.":[215]},"counts_by_year":[],"updated_date":"2026-08-26T07:47:46.906454","created_date":"2024-07-02T00:00:00"}