CN-121996019-A - System and method for solving maximum clique problem

Abstract

The application discloses a system and a method for solving a maximum clique problem. A system for solving a biggest group problem includes an array light input source, a photonic chip, an array detector, and a comparator. The array light input source includes a plurality of light input sources configured to controllably input one or more of the plurality of light input sources. The photonic chip includes a splitter configured to divide the optical power of each optical input source equally into a predetermined amount of light for the edge associated with the respective optical input source. The array detector is configured to receive the aliquoted light and to detect a sum of output powers for each element of the set of vertices of the clique to be solved. The comparator is configured to compare the sum of the detected powers for each element of the vertex set of the clique to be solved to a threshold power. The result of the comparison is used to determine whether the set of vertices associated with the particular clique solution satisfy the clique condition.

Inventors

• XU BO
• HE ZIQIANG
• ZOU PENG
• Hu Fangchen
• CHU WEI
• ZHAO YIHENG
• CAI HAIWEN

Assignees

• 张江国家实验室

Dates

Publication Date

20260508

Application Date

20241105

Claims (18)

1. 1.A system for solving a biggest group problem, comprising: An array of light input sources comprising a plurality of light input sources configured to controllably input one or more of the plurality of light input sources, wherein each light input source is associated with an edge formed between vertices to which a biggest clique problem relates, and whether light of each light input source is input is determined based on whether the corresponding vertices are connected to form an edge; A photonic chip comprising a splitter configured to, for an edge associated with each light input source, equally divide the light power of the corresponding light input source into a predetermined number of lights, the predetermined number being associated with a number of cliques to be solved, wherein the cliques to be solved comprise a set of vertices, an element of the set of vertices being determined based on a superset of two vertices of the corresponding edge; An array detector coupled with the photonic chip, the array detector configured to: Receiving the aliquoted light, and And a comparator coupled to the array detector, the comparator configured to compare the sum of the powers detected for each element of the set of vertices of the clique to be solved with a threshold power, wherein the threshold power is determined based on the optical power input by the array optical input source and the number of cliques to be solved and the number of vertices in the elements of the set of vertices of the clique to be solved, wherein a result of the comparison is used to determine whether the set of vertices associated with a particular clique solution satisfies a clique condition to form a sub-clique, and a result of the maximum clique problem solution is determined from the sub-cliques formed.
2. 2. The system of claim 1, wherein, The number of vertices of the clique to be solved is 2 or more and is less than or equal to the total number of vertices involved in the maximum clique problem.
3. 3. The system of claim 1, wherein, The array light input source comprises an array light source and a corresponding array light switch, or The array light input source comprises a controllable array light switch.
4. 4. The system of claim 1, wherein, The array of light input sources being integrated on the photonic chip, and/or The array detector is mounted at the output of the photonic chip.
5. 5. The system of claim 1, wherein, Each side of the clique to be solved is arranged in a column, and The array detector is configured to detect the power of the output light for each column and sum the power of the detected output light.
6. 6. The system of claim 5, wherein, The comparator includes a level comparator configured to compare, for each column, a sum of powers with a corresponding threshold power.
7. 7. The system of claim 1, wherein, The array detector includes a summing detector or detector face covering all light input sources associated with the edge formed between each two vertices of the maximum clique problem.
8. 8. The system of claim 1, wherein, The photonic chip includes a silicon nitride waveguide and is chip-diced using a CMOS process.
9. 9. The system of claim 1, wherein, The splitter comprises at least one of a multimode interferometer, a Y-junction, and a directional coupler.
10. 10. The system of claim 1, wherein, The splitter comprises at least one of: A multi-mode interferometer based one-in-multiple-out splitter; A splitter based on a cascaded multimode interferometer; A splitter based on a cascade of directional couplers.
11. 11. A system for solving a biggest group problem, comprising: An array of light input sources comprising a plurality of light input sources configured to controllably input one or more of the plurality of light input sources, wherein each light input source is associated with an edge formed between vertices to which a biggest clique problem relates, and whether light of each light input source is input is determined based on whether the corresponding vertices are connected to form an edge; At least two photonic chips stacked on top of each other, each photonic chip comprising a splitter, the splitter of each photonic chip configured to equally divide the optical power of a corresponding optical input source into a predetermined number of lights for an edge associated with each optical input source, the predetermined number being associated with a number of clusters to be solved, wherein the clusters to be solved comprise a set of vertices, the elements of the set of vertices being determined based on a superset of two vertices of the corresponding edge; an array detector coupled with the at least two photonic chips, the array detector configured to: receiving the aliquoted light and detecting the sum of the output powers for each element of the set of vertices of the clique to be solved, and And a comparator coupled to the array detector, the comparator configured to compare a sum of the detected powers for each element of the set of vertices of the clique to be solved with a threshold power, wherein the threshold power is determined based on the optical power input by the array optical input source and the number of cliques to be solved and the number of vertices of the clique to be solved, wherein a result of the comparison is used to determine whether the set of vertices associated with a particular clique solution is capable of satisfying a clique condition to form a sub-clique, and a result of a maximum clique problem solution is determined from each sub-clique formed.
12. 12. The system of claim 11, wherein, The photonic chip includes a silicon nitride waveguide and is chip-bumped using a CMOS process, and/or The comparator includes a level comparator configured to compare, for each column, a sum of powers with a corresponding threshold power.
13. 13. A method for solving a biggest group problem, comprising: Configuring an array of light input sources comprising a plurality of light input sources to controllably input one or more of the plurality of light input sources, wherein each light input source is associated with an edge formed between vertices to which a biggest clique problem relates, and whether light of each light input source is input is determined based on whether the corresponding vertices are connected to form an edge; equally dividing, by a splitter of the photonic chip, for an edge associated with each optical input source, an optical power of the corresponding optical input source into a predetermined number of lights, the predetermined number being associated with a number of cliques to be solved, wherein the cliques to be solved comprise a set of vertices, elements of the set of vertices being determined based on a superset of two vertices of the corresponding edge; receiving the aliquoted light by an array detector; Detecting, by the array detector, a sum of output powers for each element of the set of vertices of the clique to be solved, and The sum of the powers detected for each element of the set of vertices of the clique to be solved is compared by a comparator with a threshold power, wherein the threshold power is determined based on the optical power input by the array optical input source and the number of cliques to be solved and the number of vertices of the clique to be solved, wherein the result of the comparison is used to determine whether the set of vertices associated with a particular clique solution satisfies a clustering condition to form a sub-clique, and the result of the maximum clique problem solution is determined from the sub-cliques formed.
14. 14. The method of claim 13, wherein, The number of vertices of the clique to be solved is 2 or more and is less than or equal to the total number of vertices involved in the maximum clique problem.
15. 15. The method according to claim 13, Wherein, the The light input source comprises an array light source and a corresponding array light switch, and Configuring an array light input source comprising a plurality of light input sources to controllably input one or more of the plurality of light input sources comprises: configuring corresponding ones of the array of optical switches to open based on the connection of the corresponding vertices to form edges, or Wherein, the The optical input source comprises a controllable array optical switch, and Configuring an array light input source comprising a plurality of light input sources to controllably input one or more of the plurality of light input sources comprises: corresponding ones of the controllable-array optical switches are configured to input optical power based on the connection of the corresponding vertices to form edges.
16. 16. The method of claim 13, wherein, Each side of the clique to be solved is arranged in a column, and Detecting, by the array detector, a sum of output powers for the set of vertices associated with each clique to be solved, comprising: the power of the output light is detected for each column and summed.
17. 17. The method of claim 16, wherein, Comparing, by a comparator, the sum of the powers detected for the vertex sets of each clique to be solved to a threshold power includes: the sum of the powers is compared to a corresponding threshold power for each column.
18. 18. The method of claim 15, wherein, The photonic chip includes a silicon nitride waveguide and is chip-bumped using a CMOS process, and/or The comparator includes a level comparator configured to compare, for each column, a sum of powers with a corresponding threshold power.

Description

System and method for solving maximum clique problem Technical Field The present invention relates generally to solving a maximum clique problem, and in particular to solving a maximum clique problem with a photonic chip. Background The maximum clique problem is a classical problem in graph theory, whose goal is to find a sub-graph in an undirected graph that contains the most vertices and has edges connected between vertices that are adjacent to each other, such sub-graph being called the maximum clique. Solving the biggest group problem has very wide application in the fields of social network analysis, market analysis, scheme selection, bioinformatics, computer vision, clustering problems in machine learning, and the like. The biggest group problem is an NP-hard (NP-hard) problem, whose complexity grows exponentially with the size of the problem. Current algorithms for solving the biggest group problem include brute force searches, heuristic algorithms, and the like. The method of violent searching, which requires an exhaustive search of all the possible clusters, is time-consuming and very inefficient in the case of large scales. Heuristic algorithms such as genetic algorithms and simulated annealing algorithms, etc., which can accelerate the computation, do not guarantee that an optimal solution is obtained. At present, solving the maximum group problem is mainly initiated on an algorithm, and hardware used for solving the problem is based on a digital electric chip and comprises a CPU and a GPU. The digital electric chip is used for solving the maximum group problem, the calculation rate is limited by the clock frequency of the processing unit, and the problems of low calculation speed, large delay, high power consumption and the like exist. Faster computing solutions are needed in some low latency demand scenarios, such as computer vision. There is a need in the art for a computational solution to solve the biggest clique problem that is faster in operation speed, less in delay, and lower in power consumption. Disclosure of Invention The invention provides a calculation solution for solving the maximum group problem, which has the advantages of higher operation speed, smaller delay and lower power consumption. One aspect of the invention provides a system for solving a biggest clique problem comprising an array of optical input sources comprising a plurality of optical input sources configured to controllably input one or more of the plurality of optical input sources, wherein each optical input source is associated with an edge formed between vertices involved in the biggest clique problem and whether light of each optical input source is input to be determined based on whether the corresponding vertices are connected to form an edge, a photonic chip comprising a splitter configured to divide optical power of the corresponding optical input source into a predetermined number of light for an edge associated with each optical input source, the predetermined number being associated with a number of cliques to be solved, wherein elements of the set of vertices are determined based on a superset of two vertices of the corresponding edge, an array detector coupled to the photonic chip, the array detector being configured to receive light that is equally divided, and to solve for each vertex, a set of vertices, wherein the required for the array of vertices are determined based on a specific set of vertices, a comparison of the required cliques, the required for a threshold value of the number of coefficients is compared to a set of required cliques, wherein a comparison of required power of the array of the elements is calculated for each of the vertices, the set of the required cliques is compared to a threshold value of required for a comparison of the required for the number of cliques of elements, and the result of the maximum clique problem solving is determined according to each formed sub-clique. The system as described above, wherein the number of vertices of the clique to be solved is 2 or more and is equal to or less than the total number of vertices involved in the maximum clique problem. The system of any preceding claim, wherein the array light input source comprises an array light source and a corresponding array light switch, or the array light input source comprises a controllable array light switch. The system of any of the above claims, wherein the array light input source is integrated on the photonic chip and/or the array detector is mounted at the output of the photonic chip. A system as claimed in any one of the preceding claims, wherein each side of the clique to be solved is arranged in a column, and the array detector is configured to detect the power of the output light for each column and to sum the power of the detected output light. A system as claimed in any preceding claim, wherein the comparator comprises a level comparator configured to compare, for each column, the sum of