# On Clustering Detection Based on a Quadratic Program in Hypergraphs

Authors: Qingsong Tang
Journal: Journal of Mathematics
 (2022)

---

## Abstract

A proper cluster is usually defined as maximally coherent groups from a set of objects using pairwise or more complicated similarities. In general hypergraphs, clustering problem refers to extraction of subhypergraphs with a higher internal density, for instance, maximal cliques in hypergraphs. The determination of clustering structure within hypergraphs is a significant problem in the area of data mining. Various works of detecting clusters on graphs and uniform hypergraphs have been published in the past decades. Recently, it has been shown that the maximum1,2-clique size in 1,2-hypergraphs is related to the global maxima of a certain quadratic program based on the structure of the given nonuniform hypergraphs. In this paper, we first extend this result to relate strict local maxima of this program to certain maximal cliques including 2-cliques or 1,2-cliques. We also explore the connection between edge-weighted clusters and strictly local optimum solutions of a class of polynomials resulting from nonuniform 1,2-hypergraphs.


---

## Body

## 1. Introduction

Many important phenomena depend on the structures of graphs or hypergraphs, for example, the spread of disease in a society, image segmentation problems in image analysis, or feature extraction in networks. To understand hypergraph structure, we often start with the study of the subhypergraphs with denser relations inside and sparser connections to other subhypergraphs. Thus, detecting such hypergraph clusters of closely related objects remains one of the most interesting problems in the field of bioinformatics, social society, and data mining. Clustering is a process of partitioning a set of objects into meaningful subsets so that all objects in the same group are similar and objects in different groups are dissimilar. It is a method of data exploration and a way of looking for patterns or structure in the data that are of interest. The majority of approaches to clusters available in the literature assume that objects similarities are expressed as pairwise relations in networks in terms of 2-graphs. There is also study of pairwise clustering to edge-weighted and vertex-weighted graphs (see [1–6], respectively). For uniform hypergraphs, there are various works on clustering with applications in different aspects, such as face clustering, perceptual grouping, and parametric motion segmentation, as well as image categorization using high order relations, since approximation of more complicated similarities in terms of pairwise interaction can lead to substantial loss of information (see [7–14]). In real-world cases, similarities in a group of objects may be more appropriate to be modeled in nonuniform weighted edges in general hypergraphs. As an illustration, think of a society of people with different income levels. It makes perfect sense to define similarity measures over one person and two persons that indicate how close they are. To be specific, two persons knowing each other would get pairwise weight 1 and weight 0 otherwise; this pairwise relationship can be modeled by the well-known adjacent matrix in this society; further, for a person labeled i with income bigger than certain amount, say m, we would assign this person weight 1 on a single edge i; for income less than this amount, we would assign this person weight 0 on the single edge i; this situation involving a subset in the society may be denoted by a vector B⟶. Naturally, the internal coherency of a cluster can be represented by a maximum optimization problem based on the society as follows: maxx⟶TAx⟶+Bx⟶. This optimization is the same as the graph-Lagrangian formed from a nonuniform 1,2-hypergraph that models the relationship in this society (the detailed definition is given in the next section). Therefore, it is interesting to detect different types of clusters, say 1,2-cliques or 2-cliques. Clearly, this example can be generalized to any model fitting problem, where the deviation of a set of points from the model provides a measure of their dissimilarity. The problem of data clustering using more comprehensive dissimilarity (uniform or nonuniform) is usually referred to as hypergraph clustering, since we can represent any instance of this problem by means of a hypergraph, where vertices are the objects to be clustered and the (edge-weighted) hyperedges (uniform or nonuniform) encode different order similarities.In 1965, Motzkin and Straus provided a solution to the maximum value of a class of homogeneous quadratic multilinear functions onn variable over the standard simplex of the n-dimension Euclidean space, where the homogeneous quadratic multilinear function is associated with the edge set of a graph with n vertices. Motzkin–Straus’ result established a connection between the order of a maximum complete subgraph and the graph-Lagrangian of a graph. This result also provided a new proof of a theorem by Turán who pushed the development of the study of extremal problems in graph theory. In [15], Motzkin and Straus’ result was extended to characterization of local maxima in simple graphs. For Motzkin and Straus’ type result in nonuniform hypergraphs, recently, in [16], it has been shown that the global maxima of a certain quadratic program are related to the maximum 1,2-clique size in 1,2-hypergraphs.In this paper, we extend uniform hypergraph clustering result to nonuniform hypergraphs and provide a solution to the maximum value of a class of nonhomogeneous multilinear functions inn variables over the standard simplex of the n-dimension Euclidean space. Specifically, we first extend this result to relate strict local maxima of this program to certain maximal cliques (either 2-cliques or 1,2-cliques or both). We also explore the connection between edge-weighted clusters and strictly local optimum solutions of a class of polynomials in the given hypergraphs. Nonhomogeneous multilinear functions discussed in this paper are associated with nonuniform hypergraphs.This paper is organized as follows. In Section2, we give the brief introduction to main concepts, terminology, and related results. In Section 3, we list some useful lemmas. In Section 4, we present the characterization of certain maximal cliques (either 2-cliques or 1,2-cliques or both) in terms of strictly local optimum solutions of a class of polynomials formed from unweighted 1,2-graphs. In Section 5, we discuss the parametrization graph-Lagrangian and cliques in 1,2-graphs. In Section 6, we extend the result in Section 4 to edge-weighted 1,2-graphs in some way. Conclusions are given in Section 7.


## 2. Definitions and Related Results

A hypergraphH=V,E consists of a vertex set V and an edge set E, where every edge in E is a subset of V. The set TH=F:F∈E is called the set of edgetypes of H. We also say that H is a TH-graph. For example, if TH=1,2, then we say that H is a 1,2-graph. If all edges have the same cardinality r, then H is an r-uniform hypergraph. A 2-uniform graph is called a graph. A hypergraph is nonuniform if it has at least two edge types. For any r∈TH, the rth-levelhypergraphHr is the hypergraph consisting of all edges with r vertices of H and EHr denotes the edge set of Hr. We write HnT for a hypergraph H on n vertices with TH=T. Given a subset U⊆VH, the induced subgraph denoted by HU is a hypergraph on U with the edge set F∈EH:F⊆U. An edge i1,i2,…,ir in a hypergraph is simply written as i1i2⋯ir throughout the paper.For a positive integern, let n denote the set 1,2,…,n. For a finite set V and a positive integer i, let Vi denote the family of all i-subsets of V. The complete hypergraph KnT is a hypergraph on n vertices with edge set ⋃i∈Tni. For example, Knr is the complete r-uniform hypergraph on n vertices. Knr is the nonuniform hypergraph with all possible edges of cardinality at most r. The complete graph on n vertices Kn2 is also called a clique. We also let kr represent the complete r-uniform hypergraph on vertex set k.For aT-graph H=V,E, for r∈T, we denote the r−1-neighborhood of a vertex i∈V by Eir=A∈V−ir−1:A∪i∈E. Similarly, we will denote the r−2-neighborhood of a pair of vertices i,j∈V by Eijr=B∈V−i,jr−2:B∪i,j∈E. We denote the complement of Eir by Eir¯=A∈V−ir−1:A∪i∈Vr\E. Denote Ei\jr=Eir∩Ejr¯.Definition 1.
For anr-uniform graph H with the vertex set n, edge set EH, and a vector x⟶=x1,…,xn∈Rn, we associate a homogeneous polynomial in n variables, denoted by λH,x⟶, as follows: λH,x⟶≔∑i1i2⋯ir∈EHxi1xi2…xir. Let Δ≔x⟶=x1,x2,…,xn:∑i=1nxi=1,xi≥0fori=1,2,…,n. The graph-Lagrangian of H, denoted by λH, is the maximum of the above homogeneous multilinear polynomial of degree r over the standard simplex S. Precisely,(1)λH≔maxλH,x⟶:x⟶∈Δ.
The valuexi is called the weight of the vertex i. A vector x⟶=x1,x2,…,xn∈Rn is called feasible weighting for H if and only if x⟶∈S. A vector y⟶∈S is called optimal weighting for H if and only if λH,y⟶=λH.Remark 1.
λH was called Lagrangian of H in literature [17–20]. The terminology “graph-Lagrangian” was suggested by Franco Giannessi.
The characteristic vector of a setC⊆V, denoted by x⟶C=x1C,x2C,…,xnC, is the vector in S defined as(2)xiC=1i∈CCwhere C denotes the cardinality of C and 1P is the indicator function returning 1 if property P is satisfied and 0 otherwise.
In [21], Motzkin and Straus provided the following simple expression for the graph-Lagrangian of a 2-graph.Theorem 1 (see Theorem 1 in [21] ).
IfH is a 2-graph with n vertices in which a largest clique has order t then λH=λKt2=1/21−1/t. Furthermore, the characteristic vector of a maximum clique of H is optimal weighting for H.This result provided a solution to the optimization problem of this type of quadratic functions over the standard simplex of an Euclidean space.In [16], Peng et al. generalized the concept of graph-Lagrangian to nonuniform hypergraphs as given below.Definition 2.
For a hypergraphHnT with TH=T and a vector x⟶=x1,…,xn∈Rn, define(3)λ′HnT,x⟶=∑r∈Tr!∑i1i2⋯ir∈EHrxi1xi2⋯xir.
LetΔ=x⟶=x1,x2,…,xn:∑i=1nxi=1,xi≥0fori=1,2,…,n. The Lagrangian of HnT, denoted by λ′HnT, is defined as(4)λ′HnT=maxλ′HnT,x⟶:x⟶∈Δ.
The valuexi is called the weight of vertex i. A vector y⟶∈S is called optimal weighting for H if λ′H,y⟶=λ′H.
In [22], Peng and Yao gave a generalization of Motzkin–Straus result to 1,2-graphs.Theorem 2 (see Theorem 1.4 in [22]).
IfH is a 1,2-graph with n vertices and the order of its maximum complete 1,2-subgraph is t (where t≥2), then λ′H=λ′Kt2=2−1/t. Furthermore, the characteristic vector of a maximum clique of H is optimal weighting for H.In [23, 24], Gu et al. and Tang et al. obtained more Motzkin–Straus results to some uniform hypergraphs.


## 3. Graph-Lagrangians and Cliques in1,2-Graphs: Unweighted Case

There is a 1-to-1 connection between strictly local optimum and maximal cliques (2-cliques or1,2-cliques) in 1,2-graphs.Theorem 3.
A subsetC of vertices in H is a maximum clique of a 1,2-hypergraph H if and only if its characteristic vector x⟶C is a global maximum of optimization problem (4).Proof.
One direction is immediate from Theorem2. For the other direction, suppose that x⟶C is a global maximum of optimization problem (4). From (4), λ′H,x⟶C=λ′H,x⟶U, where U is a maximum clique in H. Let C=c and S=s. From Theorem 2, λ′H,x⟶C≤2−1/c and λ′xU=2−1/u. However, λ′H,x⟶C=λ′H,x⟶U only if 2−1/u=2−1/c. This implies c=s. So C must be a clique from Theorem 2 and C is a maximum clique.Proposition 1.
LetC be a subset of k vertices of a 1,2-hypergraph H. Then C is a maximal clique of H if and only if its characteristic vector x⟶C satisfies(5)∂λ′H,x⟶∂xj==3k−2k,ifj∈C,≤3k−2k,ifj∉C.Proof.
Suppose thatC is a maximal clique. From the definition of maximal clique(6)∂λ′H,x⟶C∂xj=1+2∑ij∈E2CxiC=1+2k−1k=3k−2k,for all j∈C; and(7)∂λ′H,x⟶C∂xj=2∑ij∈E2Cxixj≤3k−2kfor all j∉C. Hence x⟶C satisfies (5).
For the other direction, ifC is not a clique, then, for some vertex j∈C, there exists a vertex i∈C satisfying i≠j and ij∉E2C or i∉E1C. Hence,(8)∂λ′H,x⟶C∂xj<1+2∑ij∈E2CxiC=3k−2k.
This contradicts∂λ′H,x⟶C/∂xj=3k−2/k for all j∈C. So C must be a clique. If C is not a maximal clique, then there must exist a clique C′⊃C. Let j∈C′∖C. Then(9)∂λ′H,x⟶C∂xj=1+2∑ij∈E2CxiC=3>3k−2k.
This contradicts∂λ′H,x⟶C/∂xj≤3k−2/k for j∉C.Lemma 1 (KKT necessary condition, [25]).
If feasible weightingx⟶=x1,x2,…,xn is a local solution of optimization problem (4), then there exists θ∈R such that, for all j∈n,(10)∂λ′H,x⟶∂xi==θ,ifj∈σx⟶,≤θ,ifj∉σx⟶.The following corollary follows from Proposition1 immediately.Corollary 1.
IfC is a maximal clique of a 1,2-hypergraph H, then xC satisfies the first-order KKT necessarily.Definition 3.
For a1,2-hypergraph H, a maximal clique C is said to be strictly maximal if, for all i∈V\C∩E1, the number of 2-edges crossing i and C is less than C−1.
Note that, forC to be a maximal clique, it suffices that the number of edges crossing i and C be no more than C−1 for all i∈V\C∩E1. However, for C to be a strictly maximal clique, this number needs to be strictly less than C−1.Lemma 2.
Consider a1,2-hypergraph H which contains two cliques C and D of equal cardinality C=D=k. Let m=C\D=D\C=m≤k. Then, for every α1,α2≥0 satisfying α1+α2=1, we have the following:(a)
IfH has exactly mm−1 edges crossing C\D and D\C, then λ′H,α1x⟶C+α1x⟶D=λ′H,x⟶C(b)
IfH has fewer than mm−1 edges crossing C\D and D\C, then λ′H,α1x⟶C+α1x⟶D<λ′H,x⟶C
The proof of this lemma is similar to the proof of Theorem 6 in [15]. So we omit the details here.Lemma 3.
Letx⟶ be a strict local maximum of optimization problem (4); then, ∀i,j∈σx⟶, there exists an edge e∈EH such that i,j⊆e.Proof.
Suppose, for a contradiction, that there existi and j in σx⟶ such that i,j⊈e for any e∈EH. We define new weighting y⟶ for H as follows. Let δ<xj be an arbitrarily small positive constant. Let yl=xl for l≠i,j, yi=xi+δ, and yj=xj−δ; then y⟶ is clearly legal weighting for H, and(11)λ′H,y⟶−λ′H,x⟶=xj∂λ′H,x⟶∂xi−∂λ′H,x⟶∂xj−xj2∂2λ′H,x⟶∂xi∂xj=0.
This contradictsx⟶ being a strict local maximum of optimization problem (4). Hence Lemma 3 holds.
Now we are ready to prove the main result of this section.Theorem 4.
LetC be a subset of k vertices of a 1,2-hypergraph H.(a)
IfE1∩C≠φ, then C is a strict maximal 1,2-clique of H if and only if x⟶C is a strict local maximum of optimization problem (4)(b)
IfE1∩C=φ, then C is a strict maximal {2}-clique of H if and only if x⟶C is a strict local maximum of optimization problem (4)Proof.
(a) Suppose thatx⟶C is a strict local maximum of optimization problem (4); then the KKT conditions (10) hold for some θ. We will show that θ=3k−2/k, where k=C. Then, by Proposition 1, C is a maximal clique. Suppose that θ≠3k−2/k for a contradiction. For every two vertices i,j in C,ij∈E2 by Lemma 3. We will show that all the vertices in C are contained in E1. Then C is a clique and θ≠3k−2/k. Assume that there exist some vertices in C not contained in E1. Since E1∩C≠φ, there must exist a vertex i∈C contained in E1. Assume that j∈C but it is not contained in E1; then(12)∂λ′H,x⟶∂xi=1+2·k−1k,∂λ′H,x⟶∂xj=2·k−1k.
This contradicts∂λ′H,x⟶/∂xi=∂λ′H,x⟶/∂xj by Lemma 1 Hence, all the vertices in C are contained in E1.
To seeC as a strictly maximal clique, suppose to the contrary that j∈E1\C adjacent to exactly k−1 vertex in C, and let i denote the only vertex in C not adjacent to j. Then set D=j∪C\i as a clique of the same cardinality as C. Because m=C\D=D\C=1, there are no edges crossing CD and D\C, since i,j are nonadjacent. From Lemma 2, for all α∈0,1, we have λ′H,x⟶C=λ′H,α1x⟶C+α1x⟶D which contradicts the hypothesis that x⟶C is a strict maximum of optimization problem (4). This proves the first part of the theorem.
For the other part, suppose thatC is a strictly maximal clique. To prove that xC is a strict local maximum of optimization problem (4), we apply the second-order sufficiency conditions for constrained optimization. First, from Corollary 1, xC satisfies the KKT conditions. Note that, in this case, the Lagrange multipliers μi’s are given by(13)μi=3k−2k−1i∈E1−∑ij∈E2xj.
It remains to be shown that the Hessian of the Lagrangian associated with the optimization in (4) is negative definite on the subspace(14)M=y⟶∈Rn,∑i=1nyi=0andyi=0,foralli∈Iwhere I=i:xic=0andμi>0. Since C is a strict maximal clique, we have(15)∑ij∈E2xj<3k−2k,for all i∉C. Now, let y⟶∈M\0; then(16)λ′H,y⟶=∑i∈E1yj+∑ij∈E2yiyj=∑i∈Cyi∑j∈Cyj−yi=−∑i∈Cyi2<0.
This completes the proof. (b) This is similar to that in (a). We omit the details here.


## 4. The Parametrization Lagrangian and Cliques in1,2-Graphs

Definition 4.
For a hypergraphHnT with HnT and a vector x⟶=x1,…,xn∈Rn, define(17)λ′HnT,x⟶=∑r∈Tr!∑i1i2⋯ir∈EHrxi1xi2…xir.
LetPS=x⟶=x1,x2,…,xn:∑i=1nxi=1,∑i=1nxi2=1/s,xi≥0fori=1,2,…,n, where s is a real number between 1,n. The parametrization Lagrangian of HnT, denoted by λs′HnT, is defined as(18)λs′HnT≔maxλ′HnT,x⟶:x⟶∈PS.
The valuexi is called the weight of vertex i. A vector y⟶∈PS is called optimal weighting for H if λs′H,y⟶=λs′H.
Let(19)Xs,C≔x⟶|x⟶∈PSandxu=0∀u∉C.
The following is easy to see.Lemma 4.
The setXs,C is nonempty if and only if 1≤s≤C. For s=C, Xs,C consists simply of the character vector of C.Theorem 5.
LetH be a 1,2-hypergraph with clique number ω. Then(a)
λs′H=2−1/s for 1≤s≤ω(b)
λs′H≤2−1/ω<2−1/s for ω≤s≤n(c)
λs′H=2−1/s if and only if s≤ω(d)
λ′H=max1≤s≤nλs′H=2−1/ω(e)
Fors≤ω, the set of global optimal solutions of (18) is given by(20)∪Xs,C|Cisaclique,s≤|(f)
The set of global optimal solutions ofλω′H is 1C/ω, where C is an (optimal) 1,2-clique of order ω. Hence, there is a one-to-one correspondence between the global optimal solutions of λω′H and the optimal cliques in H.Proof.
Proof of (a). Lets≤ω. Let x⟶ be any feasible solution of λs′H. Then(21)λs′H=∑i∈E1xi+2∑ij∈E2xixj≤1+x1+x2+⋯+xn2−∑i=1nxi2−2∑ij∈E¯2xixj≤2−1s.On the other side, letC be a clique of size s in H for some S≥s (note that s is not assumed to be integral). Since ω≥s, Xs,C is not empty. Now, for an arbitrary x∈Xs,C,(22)λs′H=∑i∈Cxi+2∑ij∈Cxixj1+∑i∈Cxi2−∑i∈Cxi22−1s.Hence,λs′H=2−1/s for 1≤s≤ω.Proof of (b). Lets>ω. Since any x⟶ that is feasible for λs′H is also feasible for λ′H, and since λ′H=2−1/ω, we have λs′H<λ′H=2−1/ω.Proof of (c). Since2−1/s is an increasing function of s, (a) and (b) together imply (c).Proof of (d). Note that the feasible region ofλ′H is the feasible region of λs′H for s in the range 1,n. Combining with (a) and (b) implies (d).Proof of (e). By equation (22), every x∈Xs,C, where C is a clique of size at least s, satisfies(23)λs′H=2−1s.On the other side, for an arbitraryx of Ls, we have(24)λs′H=2−1s−∑i∈E¯1xi−2∑ij∈E¯2xixj.Hence, ifλs′H=2−1/s, then ∑i∈E¯1xi+∑ij∈E¯2xixj=0. This happens if and only if(25)xi=0,wheneveri∈E¯1,xixj=0,wheneverij∈E¯2.So the supportσx⟶ of x⟶ forms a clique in H. Let C be this clique. Clearly, x⟶∈Xx,C. Lemma 4 implies that s≤C.Proof of (f). The result follows from (e) and Lemma4.


## 5. Maximum Vertex-Weighted Cliques in1,2-Graphs

Given a nonnegative weight vectorw⟶v, for any subset C of the vertex set, wvC denotes the sum of the weights of vertex in C. The vertex-weighted clique number ωw⟶v,H is the maximum of wvC over all cliques C of G. Note that ωe,H is the usual clique number ωH of the hypergraph. Given a positive weight vector w⟶v, define a set of matrices as follows:(26)Mw⟶v,H=B|Bii=1wvi∀i,Bij+Bji≥1wvi+1wvj∀ij∈E2¯,Bij=0∀ij∈E2.For a given a matrixB∈Mw⟶v,H, consider the following optimization problem:(27)LH,w⟶v=min−∑i∈E1xi2wvi+2x⟶TBx⟶|x⟶∈S.Theorem 6.
LetH be a 1,2-graph. Then ωw⟶v,H=1/LH,w⟶v for any positive weight vector w⟶, and B∈Mw⟶,H.In the Proof of Theorem 6, we will impose an additional condition on a solutionx⟶=x1,x2,…,xn to a global optimum x⟶ to problem (27): (∗) i:xi>0 is minimal; that is, if y⟶ is a feasible solution for H satisfying i:yi>0<i:xi>0, then LH,y⟶<LH. We need the following lemmas.Lemma 5.
Letx⟶ be a global optimum of optimization problem (27) with minimum support; then there exists an edge e∈EH such that i,j⊆e∀i,j∈σx⟶.Proof.
Letx⟶ be a global optimum of optimization problem (27) with minimum support. Let fx⟶=−∑i∈E1xi2/wvi+2x⟶TBx⟶. Suppose, for a contradiction, that there exist i and j in σx⟶ such that i,j⊈e for any e∈EH. We define a new feasible solution y⟶ to (27) as follows. Let yl=xl for l≠i,j, yi=xi+xj, and yj=xj−xj=0; then y⟶ is clearly a feasible solution (27) with smaller support compared to x⟶. By KKT necessary condition ∂fx⟶/∂xi=∂fx⟶/∂xj, and(28)fy⟶−fx⟶=xj∂fx⟶∂xi−∂fx⟶∂xj+2xj2Bii+Bjj−1i∈E11wvi−1j∈E11wvj−Bij−Bji=2xj2Bii+Bjj−1i∈E11wvi−1j∈E11wvj−Bij−Bji≤0,since Bij+Bji≥1/wvi+1/wvi≥Bii+Bjj−1i∈E11/wvi−1j∈E11/wvi. This contradicts x⟶ being a global optimum of optimization problem (27) with minimum support.Claim 1.
Eitheri∈E1 for all i∈σx⟶ or i∉E1 for all i∈σx⟶.Proof.
Suppose thati∈E1 but j∉E1 for a contradiction. By the KKT condition, ∂fx⟶/∂xi=∂fx⟶/∂xj. By Lemma 5, ∀i,j∈σx⟶,ij∈E2; therefore 0=2xj/wvi. This is a contradiction.
Now we are ready to prove Theorem6.Proof.
of Theorem 6. Letx⟶ be a global optimum of optimization problem (27) with minimum support. By Lemma 5 and Claim 1, σx⟶ induces 1,2-clique or a 2-clique of H.
Ifσx⟶ induces a 1,2-clique, then(29)fx⟶=−∑i∈E1xi2wvi+2x⟶TBx⟶=∑i∈σx⟶xi2wvi,and its minimum over the simplex is at(30)xi=ifi∈σx⟶,0,ifi∉σx⟶.for i=1,2,…,n. So the optimal value of fx⟶ is 1/wvσx⟶. For the solution to be global optimal, wvσx⟶ must be the maximum 1,2-clique in H.
Ifσx⟶ induces a 2-clique, then(31)fx⟶=−∑i∈E1xi2wvi+2x⟶TBx⟶=2∑i∈σx⟶xi2wvi,and the left is similar to the case where σx⟶ induces 1,2-clique.


## 6. Dominant Set for1,2-Graphs

LetG=V,E be an edge-weighted graph with edge weight wij>0 for ij∈E. The weighted adjacency matrix A=aijn is defined as aij=wij if ij∈E and aij=0 otherwise. The average weighted degree of i with regard to S is defined as(32)awdegSi=1S∑j∈Saij.Ifj∉S, define(33)φSi,j=aij−awdegSi.The weight ofi with regard to S is defined as(34)WSi=1,ifS=1,∑j∈SiφSij,iwSij,otherwise,WS=∑i∈SwSi.Definition 5 (see [4]).
A nonempty subset of verticesS⊆V such that WT>0 for any nonempty T⊆S is said to be dominant if(1)
WSi>0 for all i∈S(2)
WS∗ii<0 for all i∉S
Set the weighted characteristic vectorx⟶S∈△ as follows:(35)xiS=wSiWS,ifi∈S,0,otherwise.
Pavan and Pelillo connect the dominant set to the following quadratic program:(36)maximizex⟶TAx⟶subjectto∈△,and establish a correspondence between the global (local) maxima of (36) and the dominant sets of a graph.Theorem 7 (see [4]).
IfS is a dominant subset of vertices, then its weighted characteristic vector x⟶S is a strict local solution of program (36). Conversely, if x⟶∗ is a strict local solution of program (36), then its support σ=σx⟶∗ is a dominant set, provided that wσ∪ii≠0 for all i∉σ.Here we consider the quadratic program related to edge-weighted1,2-graph. Let H be a 1,2-graph on vertex set n with edge sets E1∪E2. Let u⟶≥0 be the edge weight vector of H1 and let A≥0 be the edge weight matrix of H2.Letpi=ui if i∈E1 and pi=0 if i∉E1; let qij=aij−pi if ij∈E2 and qij=−pi if ij∉E2; that is, aij=qij+pi. Consider the following quadratic program:(37)maximizefx⟶=p⟶Tx⟶+x⟶TQx⟶subjectto∈△,where p⟶=p1,…,pnT and Q=qijn. A vector x⟶∈△ satisfies the Karush-Kuhn-Tucker (KKT) conditions for problem (37), that is, the first-order necessary conditions for local optimality, if there exist n+1 real constants (Lagrange multipliers) μ1,…,μn and λ with μi≥0 for all i=1,…,n, such that(38)pi+Qx⟶i+θ+μi=0,for all i=1,…,n, ∑i=1nxi=1, and ∑i=1nxiμi=0. Note that ∑i=1nxi=1 and aij=Qij+pi. Equality (38) is equivalent to(39)Ax⟶i+θ+μi=0,for all i=1,…,n, ∑i=1nxi=1, and ∑i=1nxiμi=0. So, if we define the dominant set of H as the dominant set of H2, then, by Theorem 7, we have the following.Theorem 8.
IfS is a dominant subset of vertices, then its weighted characteristic vector x⟶S is a strict local solution of program (37). Conversely, if x⟶∗ is a strict local solution of program (37), then its support σ=σx⟶∗ is a dominant set, provided that wσ∪ii≠0 for all i∉σ.


## 7. Conclusion

In this paper, we study the connection between the local maxima of a class of quadratic program and certain maximal cliques including 2-cliques or1,2-cliques of 1,2-hypergraphs. We also explore the connection between edge-weighted clusters and strictly local optimum solutions of a class of polynomials resulting from nonuniform 1,2-hypergraphs. In the future, we will try to extend these results to general hypergraphs.



---

*Source: 4840964-2022-01-11.xml*