11institutetext: Department of Computer Science
National Tsing Hua University

# Efficient Processing of Subsequent Densest Subgraph Query

Chia-Yang Hung and Chih-Ya Shen
<EMAIL_ADDRESS><EMAIL_ADDRESS>

###### Abstract

Dense subgraph extraction is a fundamental problem in graph analysis and data
mining, aimed at identifying cohesive and densely connected substructures
within a given graph. It plays a crucial role in various domains, including
social network analysis, biological network analysis, recommendation systems,
and community detection. However, extracting a subgraph with the highest node
similarity is a lack of exploration. To address this problem, we studied the
Member Selection Problem and extended it with a dynamic constraint variant. By
incorporating dynamic constraints, our algorithm can adapt to changing
conditions or requirements, allowing for more flexible and personalized
subgraph extraction. This approach enables the algorithm to provide tailored
solutions that meet specific needs, even in scenarios where constraints may
vary over time. We also provide the theoretical analysis to show that our
algorithm is $\frac{1}{3}$-approximation. Eventually, the experiments show
that our algorithm is effective and efficient in tackling the member selection
problem with dynamic constraints.

###### Keywords:

dense subgraph extractiondynamic constraint member selection graph analysis
approximation algorithms

##  1 Introduction

Graph-based data mining has become a prominent research focus in the field of
data science. With the need to represent data existence using graph structures
in domains such as biology, chemistry, social networks, and financial systems,
graph mining holds immense value. The task of finding or labeling specific
types of subgraph structures within a graph is a fundamental problem in
discrete mathematics and finds extensive applications in the field of graph
mining.
The utilization of graph mining is widespread across various domains. In
biology, it can be used to analyze protein-protein interaction networks or
gene regulatory networks, enabling the identification of functional modules or
disease-related pathways. In chemistry, graph mining techniques are employed
to discover molecular structures or chemical compounds with specific
properties. In social networks, graph mining aids in understanding the
dynamics of communities, identifying influential users, and detecting patterns
of interaction. In financial systems, it can help analyze complex networks of
transactions and identify fraudulent activities or systemic risks.
Among the structures analyzed by researchers, there is a problem known as the
Member Selection problem (MSP). The objective of this problem is to develop an
algorithm that can find, within polynomial time, an induced subgraph in a
given graph with the highest average similarity among its nodes. However, it
has been proven that this problem is NP-hard and inapproximable, meaning it is
computationally challenging to find an optimal solution in a reasonable amount
of time.
The NP-hardness of the subgraph selection problem implies that it belongs to a
class of computationally difficult problems for which no known efficient
algorithm exists. As a result, researchers often resort to heuristic or
approximation algorithms to tackle this problem. These algorithms aim to
provide reasonably good solutions within a reasonable amount of time, even
though they may not guarantee an optimal solution.
Indeed, approximation algorithms have been proposed that demonstrate the
ability to find approximate solutions for the MSSG problem. The algorithm
offers solutions that are reasonably close to the optimal solution. However,
in the long run, repeatedly running the same algorithm for different
requirements on the same graph may lead to unnecessary time wastage.
Therefore, it is desirable to minimize the time overhead associated with
running the algorithm for different needs on the same graph. For instance,
consider a social networking platform that aims to form interest-based
communities or discussion groups for its users. Each host has specific
preferences and constraints regarding the size and composition of the group
they want to be a part of. However, these preferences can change over time as
hosts discover new interests or undergo personal growth. Additionally, the
platform may introduce new features or algorithms to enhance the group
formation process, leading to evolving constraints and requirements. In such a
dynamic environment, the Dynamic Constraint Member Selection Problem (DCMSP)
becomes crucial. DCMSP focuses on adapting to changing size and similarity
constraints when forming these interest-based groups. By incorporating dynamic
constraint management algorithms, the platform can dynamically adjust the
group composition to match the evolving preferences and constraints of its
users.

The contributions of this paper can be summarized as follows:

  * •

The Problem Formulation: This paper introduces the Dynamic Constraint Member
Selection Problem (DCMSP), which addresses the challenges posed by diverse
requirements and complexities. DCMSP aims to tackle the ever-changing demands
and constraints in the process of member selection.

  * •

Complexity Analysis: To tackle the efficiency of dynamic need on different
situation, our algorithm has been proved that it is also a
$\frac{1}{3}$-approximation algorithm.

  * •

Experimental Evaluation: The paper conducts experiments using real datasets to
evaluate the performance of the proposed algorithm and compare the computation
time to other baselines. Through rigorous evaluation and comparison, the
algorithm demonstrates superior performance and effectiveness in addressing
the problem at hand.

##  2 Related Works

###  2.1 Dense Subgraph Extraction

In recent years, the extraction of dense subgraphs from large graphs plays a
crucial role in various application domains. There has been significant
interest in studying various complex networks such as the World Wide Web,
social networks, and biological networks. In the context of the Web graph,
dense subgraphs can indicate thematic groups or even spam link farms [11]. In
the financial domain, one application of extracting dense subgraphs includes
the identification of price value motifs. This approach has been employed
among other methods for analyzing financial data [4]. In order to confront
this challenge, Huang et al. address the problem of searching for the closest
community using a $k$-truss based community model [8]. Li et al. investigate
the extraction of a set of $k$-core subgraphs aiming to maximize the minimum
node weight [10]. In addition, a set of dense subgraph extraction problems
were integrated with various factors, such as spatial [19, 14, 15], temporal
[3], skills [18, 12], and many others [9, 7, 16, 17]. As a result, the problem
of extracting dense subgraphs has garnered substantial attention.

###  2.2 Densest Subgraph Problem and Densest k-subgraph Problem

The Densest Subgraph Problem (DSP) is a branch of the broader field of dense
subgraph extraction. In DSP, the focus is specifically on identifying the
subset of vertices that maximizes the degree density. Spefically, DSP is a
well-known formulation that seeks to identify a subset of vertices $S\subseteq
V$ that maximizes the degree density of $S$. The degree density, denoted as
$d(S)$, is defined as the ratio of the number of edges within $S$, denoted as
$e[S]$, to the cardinality of $S$, denoted as $|S|$. The objective is to find
the subset of vertices that achieves the highest degree density
$d(S)=\frac{e[S]}{|S|}$. Andrew V. Goldberg’s groundbreaking contribution was
the development of a polynomial time algorithm that utilizes a max flow
technique to identify the maximum density subgraph [6]. Charikar’s work made a
significant contribution to the advancement of fast algorithms for the Densest
Subgraph (DSP) [2]. His research introduced influential developments that have
greatly impacted the efficiency and effectiveness of algorithms designed for
solving these problems.
On the other hand, size-constrained versions of the DSP have been extensively
studied in the literature, as they offer practical utility in applications
where the size of the solution must be controlled. Variants of DSP exist that
impose specific size requirements on the output containing exactly k nodes. In
formulation, densest $k$-subgraph problem intent to find a induced subgraph
$S$ that maximizes $d(S)=\frac{e[S]}{|S|}$ subject to $|S|=k$. Although DSP
itself can be solved in polynomial time, the introduction of size constraints
makes the problem computationally challenging. U. Feige et al. developed a
polynoimal time algorithm which approximation ratio is $n^{\delta}$, where
$\delta$ is a constant approximately equal to $\frac{1}{3}$ [5]. Bhaskara et
al. have proposed another algorithm that achieves an approximation ratio of
$\mathcal{O}(n^{\frac{1}{4}})$. Their algorithm is also inspired by studying
an average case version of the problem, specifically focusing on
differentiating between random graphs and random graphs with planted dense
subgraphs. In specific, their algorithms involve a clever approach of counting
appropriately defined trees of constant size within the graph $G$. By
utilizing these counts, they are able to identify the vertices that belong to
the dense subgraph. These advancements contribute to the efficiency and
effectiveness of solving the size-constrained DSP.

##  3 Preliminaries

In this section, we first provide some background material on graphs and the
Member Selection Problem. Let one heterogeneous graph $G=(V,E,S)$, where
$V=\\{v_{1},v_{2},\cdots,v_{n}\\}$ is the set of $n$ nodes, $E\subseteq
V\times V$ is the set of edges, and $S$ represent the similarity edges between
two nodes. A weight, denoted as $w\in(0,1]$, is assigned to each similarity
edge $s\in S$. In general, given an attributed graph $G=(V,E,X)$, where
$X\in\mathbb{R}^{n\times d}$ is the attributed matrix. We can model the
$w[u,v]=w[v,u]=\sqrt{\sum_{\forall i}(1-|X_{u,i}-X_{v,i}|)^{2}}$. Squared
Euclidean Distance has been proved to be useful in grouping node according to
their attributes [1]. Next, we introduce Member Selection Problem (MSP)
proposed by shen et al [13]. MSP aims to identify an induced subgraph
$F\subseteq G$ that adheres to the following principles:

  1. 1.

Maximize the average similarity between all nodes in $F$.

  2. 2.

Ensure the group size $|F|>p$, where $p$ is the predefined size constraint.

  3. 3.

Every two nodes in $F$ has edge, i.e., $F$ is a complete graph.

  4. 4.

Ensure that every node in $F$ has a least one weight edge is larger than
similarity constraint $s$.

For the first one of these, we first define the total weight function
$W:G\rightarrow\mathbb{R}$ by $\forall F\subset G$

$W(F)=\sum_{u,v\in F}w[u,v]$

and next define the average similarity function
$\alpha:F\rightarrow\mathbb{R}$ by $\alpha(F)=\frac{W(F)}{|F|}$. And the third
principles can be formulated as $\forall v\in F,\exists u\in F$ such that
$w[u,v]=w[u,v]>s$. Member Selection problem has been proves that it is a NP-
Hard problem and inapproximable with any factor unless $P=NP$ [13].

Although MSP is inapproximable with any factor, Shen et al. still provide a
$\frac{1}{3}$-approximation solution called Support Group Member Selection
(SGSEL) when we relaxed the constraint of complete graph in $F$ [13]. SGSEL
extracts a subgraph $F$ starting from a 2-clique $C_{v}$ with reference node
$v$. Next, in the second step, SGSEL iteratively eliminates vertices within
each $C_{v}$ that have smallest incident similarity. To address the complete
requirement of the Member Selection problem, SGSEL propose a post-processing
procedure that customizes the 2-clique solution $F^{APX}$. This procedure
ensures that the selected members in $F^{APX}$ meet the desired complete
criteria, further enhancing the objective value $\alpha$ of the MSP solution.
As mention above, it has been theorical proved that SGSEL is a 3-approximation
solution on member selection problem without complete graph constraint. That
is, let $F^{SGSEL}$ be an approximation solution identity by SGSEL and
$F^{OPT}$ be the optimal solution in MSP, we have
$\alpha(F^{SGSEL})>\frac{\alpha(F^{OPT})}{3}$.

Figure 1: Example for SGSEL

Example. Consider the example in figure 1. SGSEL iteratively selects nodes as
reference node in graph. After SGSEL choosing CC as reference node and expand
its 2-clique $C_{v}=\\{A,C,E,F\\}$ as $\Gamma_{1}$. In first iteration, AA is
chosen to remove because $A$ has minimum $I_{\Gamma_{1}}(u)$, $\forall
u\in\Gamma_{1}$. Thus, $\Gamma_{2}=\\{C,E,F\\}$. In next iteration, SGSEL
remove $C$ since $I_{\Gamma_{2}}(C)=0.7$ is the smallest. This procedure
repeats until $\Gamma_{4}=\varnothing$. Then SGSEL take $\Gamma_{1}$ as
$\Gamma_{C}^{*}$ which has maximum objective value $\alpha(\Gamma_{1})=0.525$,
$\forall\Gamma_{i}$. Afterward, SGSEL choosing next reference node DD and
continue above process. Eventually, SGSEL return the solution
$F^{APX}=\\{A,C,E,F\\}$.

##  4 Problem Formulation

Due to the design of the MSP algorithm, it fails to consider the process under
changing conditions. Moreover, as the number of requirements increases, it
becomes evident that we need more flexible algorithms to effectively address
the challenges presented by different analysis scenarios. Thus, we describe
the Dynamic Constraint Member Selection Problem (DCMSP). DCMSP is focus on the
change of size or similarity constraint. Moreover, we present the Extended
Dynamic Constraint Member Selection Problem (EDCMSP). EDCMSP incorporates the
idea of divide and conquer, breaking down DCMSP into two subgraphs, to
expedite the expansion of solutions for DCMSP. In this paper, we will discuss
the part of size constraint $p$.

###  4.1 DCMSP

In order to better describe the dynamic constraints of parameter $p+\Delta p$,
it is necessary to introduce a more comprehensive and flexible framework.
Consider $G=(V,E,S)$, the objective of DCMSP is to find an induced subgraph
$F\subset G$ that follow to the following three principles:

  1. 1.

Maximize the average similarity $\alpha(F)$ between all nodes in $F$.

  2. 2.

Ensure the group size $|F|>p+\Delta p$, where $p$ is the size constraint and
$\Delta p$ is the dynamic variable.

  3. 3.

Ensure that every node in $F$ has a least one weight edge is larger than
similarity constraint $s$.

As the parameter $\Delta p$ decreases, it corresponds to a relaxation of the
overall constraints. Therefore, there is no need for further discussion
regarding this scenario.

###  4.2 EDCMSP

In EDCMSP, We can approach this problem from a differnet perspective. If we
have already solved the member selection problem in graph $G$ with size
constraint $p$ and identified an approximate solution $F$. We consider the
remaining portion of the original graph $G\setminus F$ as a newly added graph.
And next, treat the new constraints $\Delta p$ as constraints specific to this
newly added graph. In general, we can re-formulate this perspective as: Given
two disjoint heterogeneous graph $G_{1},G_{2}$ with same similarity constraint
$s$ and different size constraint $p_{1},p_{2}$, respectively. We intent to
find a induced subgraph $F^{\prime}\subseteq G_{1}\cup G_{2}$ such that  (i)
Maximize the average similarity $\alpha(F)$ between all nodes in $F^{\prime}$.
(ii) Ensure the group size $|F^{\prime}|>p_{1}+p_{2}$.  (iii) Ensure that
every node in $F$ has a least one weight edge is larger than similarity
constraint $s$.  Note that $F$ and $G\setminus F$ might have some edges, but
$G_{1}$ and $G_{2}$ not. To tackle this, we might manually add some edges
between $G_{1}$ and $G_{2}$.

##  5 Algorithm Design

Although SGSEL has been proven to be able to identify an induced subgraph that
serves as a $\frac{1}{3}$-approximation solution for the member selection
problem [13], there are certain limitations and considerations that need to be
taken into account. Here we propose the algorithm called Dynamic Constrain
member SELecition (DCSEL) aim to solve the DCMSP efficiently. DCSEL first
extract an induced subgraph $F_{1}$ by modified SGSEL, which eliminate the two
cliques expansion in SGSEL. According to DCMSP requirements, when the size
constraint $p$ increases, DCSEL will search $F_{2}$ in $G\setminus F_{1}$. And
then, DCSEL concatenates two subgraph and add some nodes which one of two
endpoints is inside $F_{1}\cup F_{2}$.
Specifically, DCSEL greedily removes nodes based on their total similarity
$W(u)$ and records the best subgraph at the current size. While the size
constraint $p$ decreasing, DCSEL check that is there exists any subgraph
$F^{\prime}$ such that $|F_{1}|>|F^{\prime}|>p$ and
$\alpha(F^{\prime})>\alpha(F_{1})$. Note that $|F_{1}|$ must larger than
$|F|$, otherwise, $F^{\prime}$ must return in first step. On the other hand,
as the size constraint $p$ gradually increases to become larger than $F_{1}$,
DCSEL will automatically search for $F_{2}$ in $G\setminus F$ and merge the
two subgraphs together. And optional, greedyily select edges which one of the
two end points is in $F_{1}\cup F_{2}$. Note we call the last procedure is
optional because we don’t want the last procedure damage our objective value
$\alpha(F_{1}\cup F_{2})$.

Algorithm 1 DCSEL

1:Graph $G=(V,E,S)$, similarity constraint $s$, and size constraint
$P=\\{p_{1},p_{2},\cdots,p_{k}\\}$

2:3-Approximation solution $F$

3:$A=\\{-1,\cdots,-1\\},B=\\{\varnothing,\cdots,\varnothing\\}\triangleleft$
A, B denoted the objective value and optimal solution corresponding to their
size.

4:$F_{1},A,B\leftarrow$ Modified SGSEL$(G,s,p_{1})$

5:for $i\leftarrow 2$ to $k$ do

6: if $p_{i}-p_{i-1}<0$ then

7: if $\exists F\in B$, $\alpha(F)>\alpha(F_{i-1})$ then

8: $F_{i}\leftarrow F$

9: else

10: $F_{i}\leftarrow F_{i-1}$

11: continue;

12: if $p_{i}<|F_{i-1}|$ then

13: $F_{i}\leftarrow F_{i-1}$

14: Continue;

15: $F_{i}\leftarrow$ Modified SGSEL$(G\setminus F_{i-1},s,p_{i}-p_{i-1})\cup
F_{i-1}$

16: while $I_{F_{i}}(u_{i})>\alpha(F_{i})$ do

17: $F_{i}\leftarrow F_{i}\cup\\{u_{i}\\}$

18:return $F_{k}$

##  6 Theoretical Analysis

In this section, we will discuss the approximation ratio of our algorithm on
EDCMSP. First, we define some notation in our proof. Next, we will discuss the
problem in three cases. Last, we will show that our algorithm gives a
$\frac{1}{3}$-approximation solution for both EDCMSP and DCMSP.

In order to facilitate the subsequent proof and better elucidate our
arguments, we need to define the following symbols:  (i) $F_{i}$is the
$\frac{1}{3}$-approximation solution of EDCMSP on the graph $G_{i}$ while
considering the size constraint $p_{i}$ and the similarity constraint $s$.
(ii) $OPT_{i}$is the optimal solution of EDCMSP on the graph $G_{i}$.  (iii)
$\mathbb{F}$is the optimal solution of EDCMSP on the graph $G_{1}\cup G_{2}$
while considering the size constraint $p_{1}+p_{2}$ and the similarity
constraint $s$.  (iv) $\mathbb{F}_{i}$refers to the set of nodes in
$\mathbb{F}$ that belong to $G_{i}$. i.e., $\mathbb{F}_{1}\subset G_{1}$ and
$\mathbb{F}_{1}\cap G_{2}=\varnothing$.  (v) $\mathbb{E}$represents the
collection of edges that have their two endpoints in different graphs.  In
other words, $\mathbb{F}$ can be decomposed into three components, namely
$\mathbb{F}_{1}$, $\mathbb{F}_{2}$, and $\mathbb{E}$. This observation
inspires us to establish individual bounds for each of these components.

Algorithm 2 Modified SGSEL

1:Graph $G=(V,E,S)$, similarity constraint $s$, and size constraint $p$

2:3-Approximation solution $F$

3:$F^{APX}\leftarrow\varnothing\triangleleft$ Initialize the approximation
solution F.

4:$F\leftarrow V$

5:$A=\\{-1,\cdots,-1\\},B=\\{\varnothing,\cdots,\varnothing\\}$

6:while $F\neq\varnothing$ do

7: $v\leftarrow\operatorname*{\arg\\!\min}_{u\in F}I_{F}(u)$ $\triangleleft$
$I_{F}(u)$ is defined as the sum of the edge weights between vertex $u$ and
all other vertices $t$ in $F$.

8: $F\leftarrow F\setminus\\{v\\}$

9: if $\alpha(F)>\alpha(F^{APX})$ then

10: $F^{APX}\leftarrow F$

11: if $\alpha(F)>A[|F|]$ then

12: $A[|F|]\leftarrow\alpha(F)$

13: $B[|F|]\leftarrow F$

14:return $F^{APX},A,B$

###### Lemma 1

Suppose $\alpha(\mathbb{F})\leq\alpha(OPT_{1})$ and
$\alpha(\mathbb{F})\leq\alpha(OPT_{2})$. Then $F_{1}\cup F_{2}$ is a
$\frac{1}{3}$-approximation solution of EDCMSP. i.e., $\alpha(F_{1}\cup
F_{2})\geq\frac{1}{3}\alpha(\mathbb{F})$.

###### Proof

This can easily prove by analysis the relationship between $F_{1}\cup F_{2}$
and $\mathbb{F}$.

$\displaystyle\alpha(F_{1}\cup F_{2})$
$\displaystyle=\frac{W(F_{1})+W(F_{2})+\Delta}{|F_{1}|+|F_{2}|}>\frac{W(F_{1})+W(F_{2})}{|F_{1}|+|F_{2}|}$
$\displaystyle>\frac{\frac{1}{3}\alpha(OPT_{1})|F_{1}|+\frac{1}{3}\alpha(OPT_{2})|F_{2}|}{|F_{1}|+|F_{2}|}\geq\frac{\frac{1}{3}\alpha(\mathbb{F})|F_{1}|+\frac{1}{3}\alpha(\mathbb{F})|F_{2}|}{|F_{1}|+|F_{2}|}=\frac{1}{3}\alpha(\mathbb{F})$

Note that $\Delta>0$ is the total edge weight whose two endpoint in two
different graphs $G_{1}$ and $G_{2}$. The third inequality is because
$W(F_{1})=\alpha(F_{1})|F_{1}|\geq\frac{1}{3}\alpha(OPT_{1})|F_{1}|$, so does
$W(F_{2})\geq\frac{1}{3}\alpha(OPT_{2})|F_{2}|$.

###### Lemma 2

Suppose we have two disjoint subgraph of graph $G$, say $A$ and $B$. If
$\alpha(A)<\alpha(B)$, then $\alpha(A)<\alpha(A\cup B)$.

###### Proof

$\displaystyle\alpha(A\cup B)$
$\displaystyle=\frac{W(A)+W(B)+\Delta_{AB}}{|A|+|B|}$
$\displaystyle>\frac{\alpha(A)|A|+\alpha(B)|B|}{|A|+|B|}$
$\displaystyle>\frac{\alpha(A)|A|+\alpha(A)|B|}{|A|+|B|}$
$\displaystyle=\alpha(A)$

Note that $\Delta_{AB}>0$ is the total edge weight whose two endpoint in two
different graphs $A$ and $B$.

###### Theorem 6.1

Given a graph $G$ with similarity constraint $s$ and size constraint $p$, and
a $\frac{1}{3}-$approximation solution $F_{1}$ given by SGSEL. Given any
Dynamic size constraint $\Delta p$, the DCSEL will return a solution with
ratio $\frac{1}{3}$.

###### Proof

First of all, if the dynamic constraint $\Delta p$ is small than $0$, it
indicates a loosening of the overall constraints. Since the trimming process
of original constraint $\\{s,p\\}$ also holds the ratio $\frac{1}{3}$.
Thus,there is no necessity for additional deliberation on this scenario.

For $\Delta p>0$, We can categorize all scenarios into three disjoint cases.

  1. 1.

$\mathbb{F}\cap G_{1}=\varnothing$, or say $\mathbb{F}\subseteq G_{2}$.

  2. 2.

$\mathbb{F}\cap G_{2}=\varnothing$, or say $\mathbb{F}\subseteq G_{1}$.

  3. 3.

$\mathbb{F}\cap G_{1}\neq\varnothing$ and $\mathbb{F}\cap
G_{2}\neq\varnothing$.

WLOG, if $\mathbb{F}\cap G_{1}=\varnothing$, then we have
$\alpha(\mathbb{F})\leq\alpha(OPT_{2})$. This is because $\mathbb{F}\subseteq
G_{2}$ and $|\mathbb{F}|>p_{2}$. Follow the definition of $OPT_{2}$,
$\alpha(\mathbb{F})$ must smaller than $\alpha(OPT_{2})$. If
$\alpha(\mathbb{F})\leq\alpha(OPT_{1})$, we have proved in lemma 1. Thus, we
can suppose $\alpha(\mathbb{F})>\alpha(OPT_{1})$. On the other hand, for all
node $u$ belong to graph $G_{1}$, we can deduce that
$I_{\mathbb{F}}(u)<\alpha(\mathbb{F})$. If not,
$\alpha(\mathbb{F}\cup\\{u\\})=\frac{W(\mathbb{F})+I_{\mathbb{F}}(u)}{|\mathbb{F}|+1}=\frac{|F|}{|F|+1}\alpha(\mathbb{F})+\frac{1}{|F|+1}I_{\mathbb{F}}(u)>\frac{|F|}{|F|+1}\alpha(\mathbb{F})+\frac{1}{|F|+1}\alpha(\mathbb{F})=\alpha(\mathbb{F})$
which imply $\mathbb{F}\cup\\{u\\}$ is better than $\mathbb{F}$
$\rightarrow\\!\leftarrow$. Thus, this suggest us can greedily choose the node
$t\in G_{2}$ by $I_{F_{2}}(t)>\alpha(F_{2})$ until satisfy the size constraint
$p_{1}+p_{2}$. Since $\mathbb{F}\subseteq G_{2}$, there must exists enough
node that can form the approximation solution.

Now, we consider the third case: $\mathbb{F}\cap G_{1}\neq\varnothing$ and
$\mathbb{F}\cap G_{2}\neq\varnothing$. Note that
$\mathbb{F}=\mathbb{F}_{1}\cup\mathbb{F}_{2}\cup\mathbb{E}$. As mention
before, we will estimate the upper bound each by each. First, without loss of
generality, we show $\alpha(\mathbb{F}_{1})<3\alpha(F_{1})$. If
$\alpha(\mathbb{F}_{1})\leq\alpha(OPT_{1})$. By the property of $F_{1}$, we
have $\alpha(\mathbb{F}_{1})\leq\alpha(OPT_{1})<3\alpha(F_{1})$. on the other
hand, we suppose $\alpha(\mathbb{F}_{1})>\alpha(OPT_{1})$. If
$\mathbb{F}_{1}\cap\alpha(OPT_{1})=\varnothing$, then
$\mathbb{F}_{1}\cup\alpha(OPT_{1})$ form a solution better than optimal
solution $\alpha(\mathbb{F}_{1})$ by lemma 2, which lead to contradiction. If
$\mathbb{F}_{1}\cap\alpha(OPT_{1})\neq\varnothing$, say $\mathbb{F}_{1}\cap
OPT_{1}=R$ and $\mathbb{F}_{1}\setminus OPT_{1}=R^{\prime}$. For any subset
$U$ of $R^{\prime}$, we can claim that
$\frac{I_{R}(U)}{|U|}=\alpha(U)<\alpha(OPT_{1})$. Otherwise, $OPT_{1}\cup U$
will form an optimal solution on $G_{1}$, which lead to contradiction. Next,
we discover that there exists a subset $V$ belong to
$OPT_{1}\setminus\mathbb{F}_{1}$ such that $I_{R}\setminus V(V)>I_{R}\setminus
V(R^{\prime})$, where $|V|=|R^{\prime}|$. If not, replacing $R^{\prime}$ with
$V$ can yield another optimal solution, which lead to contradiction. Finally,
we can use this $V$ to form a better component in EDCMSP, say
$\mathbb{F}_{1}\cup V$, which leads a contradiction. Similarily, we can say
$\alpha(\mathbb{F}_{2})<3\alpha(F_{2})$. Last of all, we are going to show
that our algorithm picking a node set, denoted by $\Delta$, is an upper bound
of $W(\mathbb{E})$. Since $\Delta$ is composed by greedily picking up the node
in those which one of the node has already in $F_{1}$, but not $F_{2}$, and
vice versa. Thus, we set a stopping criteria that can bound
$\frac{1}{3}W(\mathbb{E})$ and not decrease the average similarity. Therefore,
each component of $\mathbb{F}$ is bound by our algorithm selected subgraph. In
other words, our algorithm is a $\frac{1}{3}$-approximation algorithm.

###### Lemma 3

Given a graph $G$ with similarity constraint $s$ and size constraint $p$, and
a $\frac{1}{3}-$approximation solution $F_{1}$ given by SGSEL. If Dynamic
similarity constraint $\Delta s>0$, then DCSEL will return a solution with
ratio $\frac{1}{3}$.

###### Proof

Let $U$ be the set of nodes whose edges similarity are all lower than
$s+\Delta s$ in $G$. i.e., our search space of algorithm reduced to
$G\setminus U$. Since the increment of similarity constraint eliminate nodes
whose has lower edge similarity, thus, it doesn’t impact the optimal solution.
However, there might be some nodes are in both $U$ and $F_{1}$. If
$|F_{1}\setminus U|\geq p$, we don’t need to modify our result.
$F_{1}\setminus U$ still hold the ratio $\frac{1}{3}$ and the two constraints
of our member selection problem. On the other hand, if $|F_{1}\setminus U|<p$,
we need run our DCSEL again to generate approximation solution $F$. In this
step, the ratio is still hold, since the procedure of new $F$ is same as the
initial constraints {$|F_{1}\setminus U|,s+\Delta s$}, size constraint and
similarity constraint respectively, and then with dynamic constraint $\Delta
p=p-|F_{1}\setminus U|$.

###### Lemma 4

Given a graph $G$ with similarity constraint $s$ and size constraint $p$, and
a $\frac{1}{3}-$approximation solution $F_{1}$ given by SGSEL. If Dynamic
similarity constraint $\Delta s<0$, then DCSEL will return a solution with
ratio $\frac{1}{3}$.

###### Proof

Let $U$ be the set of nodes whose edges similarity are all higher than
$s+\Delta s$, but lower than $s$ in graph $G$. i.e., $\forall u\in U,$
$s+\Delta s<e(u)<s$. Since $U$ can be seen as a new search space of DCSEL, we
can easily run the DCSEL once, adding some nodes to $F_{1}$ from $(G\setminus
F_{1})\cup U$ to form new approximation solution $F$. The ratio is hold
because the procedure of new $F$ is same as the initial constraints $\\{p,$
$s+\Delta s\\}$.

###### Theorem 6.2

Given a graph $G$ with similarity constraint $s$ and size constraint $p$, and
a $\frac{1}{3}-$approximation solution $F_{1}$ given by SGSEL. Given any
Dynamic similarity constraint $\Delta s$, the DCSEL will return a solution
with ratio $\frac{1}{3}$.

###### Proof

The lemma 3 and lemma 4 demonstrate the all cases of similarity constraint
adjustment.

##  7 Extra Nodes of Graph Adjustment

In order to deal with the constantly changing node instances in the real-world
network, we have also discussed the scenarios involving changes to nodes on
the graph. The problem can be formulated by the following statement:

###### Theorem 7.1

Giving a graph $G$ with similarity constraint $s$ and size constraint $p$, and
a $\frac{1}{3}-$approximation solution $F_{1}$ given by SGSEL. If there exists
another graph $G^{\prime}$, then our DCSEL algorithm can find an approximation
solution with approximation ration $\frac{1}{3}$ on $G\cup G^{\prime}$.

###### Proof

Since $G^{\prime}$ can be seen as a new search space of DCSEL, we can easily
run the DCSEL, which adding some nodes to $F_{1}$ from $(G\cup
G^{\prime})\setminus F_{1}$ to form new approximation solution $F$. The ratio
is hold because the procedure of $F$ is same as the initial constraints
$\\{p,$ $s\\}$ on $G\cup G^{\prime}$.

(a) Dataset: Cora

(b) Dataset: Citeseer

(c) Dataset: Pubmed

Figure 2: Size constraint $p$ monotonic increase

(a) Dataset: Cora

(b) Dataset: Citeseer

(c) Dataset: Pubmed

Figure 3: Size constraint $p$ montonic decrease

(a) Dataset: Cora

(b) Dataset: Citeseer

(c) Dataset: Pubmed

Figure 4: Size constraint $p$ randomly selected

##  8 Experiments

In this section, we testify the effectiveness of our DCSEL algorithm, we
compare it with four baselines. Our experiment is conducted on R9-5900x, RTX
3090 Ti, $4\times 16$ GB memory, and Ubuntu 22.04.

###  8.1 Datasets

We employ three widely-adopted benchmark datasets for our experiment. Cora,
Citeseer, and Pubmed are three citation network dataset. Node represent
documents and edges represent citation links. Node features of Cora and
Citeseer are documents encoded by bag-of words feature vector, while the
features of Pubmed are TF/IDF weighted word frequency. Their statistic is
summarized in Table 1

Table 1: Dataset Statistics Dataset | #Nodes | #Edges | #Features
---|---|---|---
Cora | 2,485 | 5,069 | 1,433
Citeseer | 2,110 | 3,668 | 53,703
Pubmed | 19,717 | 44,324 | 500

###  8.2 Baseline

To demonstrate the effectiveness of our proposed approach, we compare our
DCSEL with other four methods, including SGSEL, Random, Degree, and Average.
(I) SGSEL, which was introduced in Section 3 in detail.  (II) Random. Randomly
remove nodes in each iteration and return maximum average similarity subgraph
in whole epoch.  (III) Degree. Eliminate nodes based on their average incident
similarity, i in each iteration, and then calculate the maximum average
similarity throughout the entire epoch.  (IV) Average. In each iteration,
remove nodes based on their average incident similarity,
i.e.,$\frac{I_{\Gamma_{i}}(u)}{|\mathcal{N}(u)|}$, and then calculate the
maximum average similarity over the entire epoch.

###  8.3 Result

We evaluate our method under three different size constraint $p$ changes,
including  (i) monotonic increase, in figure 2 (ii) monotonic decrease, in
figure 3 (iii) random select, in figure 4 . We first compare DCSEL with other
four baselines. We can find out that DCSEL achieve objective value as high as
SGSEL in most scenario. This is because DCSEL has same procedure as SGSEL in
beginning, thus it can extract the same induced graph. Although our proposed
DCSEL is concatenate two induced subgraph, experiment result show DCSEL can
find the approximation solution properly. In addition, our algorithm processes
dynamic constraint member selection problem efficiently. This might because
$F_{1}$ is large enough, i.e., $|G\setminus F_{1}|\ll|F_{1}|$. This
observation explain that how does DCSEL work efficiently.

## References

  * [1] Abramowitz, J.S., Franklin, M.E., Schwartz, S.A., Furr, J.M.: Symptom presentation and outcome of cognitive-behavioral therapy for obsessive-compulsive disorder. Journal of consulting and clinical psychology 71(6), 1049 (2003)
  * [2] Charikar, M.: Greedy approximation algorithms for finding dense components in a graph. In: Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization. p. 84–95. APPROX ’00, Springer-Verlag, Berlin, Heidelberg (2000)
  * [3] Chen, Y.L., Yang, D.N., Shen, C.Y., Lee, W.C., Chen, M.S.: On efficient processing of group and subsequent queries for social activity planning. IEEE Transactions on Knowledge and Data Engineering 31(12), 2364–2378 (2018)
  * [4] Du, X., Jin, R., Ding, L., Lee, V.E., Thornton, J.H.: Migration motif: A spatial - temporal pattern mining approach for financial markets. In: Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. p. 1135–1144. KDD ’09, Association for Computing Machinery, New York, NY, USA (2009). https://doi.org/10.1145/1557019.1557142, https://doi.org/10.1145/1557019.1557142
  * [5] Feige, U., Peleg, D., Kortsarz, G.: The dense k-subgraph problem. Algorithmica 29, 410–421 (2001)
  * [6] Goldberg, A.V.: Finding a maximum density subgraph (1984)
  * [7] Hsu, B.Y., Shen, C.Y., Chang, M.Y.: Wmego: Willingness maximization for ego network data extraction in online social networks. In: Proceedings of the 29th ACM International Conference on Information & Knowledge Management. pp. 515–524 (2020)
  * [8] Huang, X., Lakshmanan, L.V.S., Yu, J.X., Cheng, H.: Approximate closest community search in networks (2015)
  * [9] Huang, Y.L., Shen, C.Y., Shieh, S., Wang, H.J., Lin, C.C.: Provable secure aka scheme with reliable key delegation in umts. In: 2009 Third IEEE International Conference on Secure Software Integration and Reliability Improvement. pp. 243–252. IEEE (2009)
  * [10] Li, R.H., Qin, L., Yu, J.X., Mao, R.: Influential community search in large networks. Proc. VLDB Endow. 8(5), 509–520 (jan 2015). https://doi.org/10.14778/2735479.2735484, https://doi.org/10.14778/2735479.2735484
  * [11] Saito, H., Toyoda, M., Kitsuregawa, M., Aihara, K.: A large-scale study of link spam detection by graph algorithms. In: Proceedings of the 3rd International Workshop on Adversarial Information Retrieval on the Web. p. 45–48. AIRWeb ’07, Association for Computing Machinery, New York, NY, USA (2007). https://doi.org/10.1145/1244408.1244417, https://doi.org/10.1145/1244408.1244417
  * [12] Shen, C.Y., Huang, L.H., Yang, D.N., Shuai, H.H., Lee, W.C., Chen, M.S.: On finding socially tenuous groups for online social networks. In: Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining. pp. 415–424 (2017)
  * [13] Shen, C.Y., Shuai, H.H., Yang, D.N., Lan, Y.F., Lee, W.C., Yu, P.S., Chen, M.S.: Forming online support groups for internet and behavior related addictions. In: Proceedings of the 24th ACM International on Conference on Information and Knowledge Management. p. 163–172. CIKM ’15, Association for Computing Machinery, New York, NY, USA (2015). https://doi.org/10.1145/2806416.2806423, https://doi.org/10.1145/2806416.2806423
  * [14] Shen, C.Y., Yang, D.N., Huang, L.H., Lee, W.C., Chen, M.S.: Socio-spatial group queries for impromptu activity planning. IEEE Transactions on Knowledge and Data Engineering 28(1), 196–210 (2015)
  * [15] Shen, C.Y., Yang, D.N., Lee, W.C., Chen, M.S.: Activity organization for friend-making optimization in online social networks. IEEE Transactions on Knowledge and Data Engineering 34(1), 122–137 (2020)
  * [16] Shuai, H.H., Yang, D.N., Philip, S.Y., Shen, C.Y., Chen, M.S.: On pattern preserving graph generation. In: 2013 IEEE 13th International Conference on Data Mining. pp. 677–686. IEEE (2013)
  * [17] Yang, C.H., Shen, C.Y.: Enhancing machine learning approaches for graph optimization problems with diversifying graph augmentation. In: Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. pp. 2191–2201 (2022)
  * [18] Yang, C.H., Shuai, H.H., Shen, C.Y., Chen, M.S.: Learning to solve task-optimized group search for social internet of things. IEEE Transactions on Knowledge and Data Engineering 34(11), 5429–5445 (2021)
  * [19] Yang, D.N., Shen, C.Y., Lee, W.C., Chen, M.S.: On socio-spatial group query for location-based social networks. In: Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining. pp. 949–957 (2012)