Longlong Lin

Prof. Longlong Lin

orcid

Research Focus & Metrics

Academic Career Length

9Years (2018-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
6 May 2021 in IEEE Transactions on Systems, Man, and Cybernetics: Systems
Verified
Journal Article
Closed access
LLLonglong Lin
Longlong Lin
PYPingpeng Yuan
Pingpeng Yuan
RLRong-Hua Li
Rong-Hua Li
JWJifei Wang
Jifei Wang
LLLing Liu
Ling Liu
HJHai Jin
Hai Jin
Real-world networks, such as phone-call networks and social networks, are often not static but temporal. Mining cohesive subgraphs from static graphs is a fundamental task in network analysis and has been widely investigated in the past decades. However, the concepts of cohesive subgraphs shift from static to temporal graphs raise many important problems. For instance, how to detect stable cohesive subgraphs on temporal networks such that the nodes in the subgraph are densely and stably connected over time. To address this problem, we resort to the conventional quasi-clique and propose a new model, called maximal $\rho $ -stable ( $\delta, \gamma $ )-quasi-clique, to capture both the cohesiveness and the stability of a subgraph. We show that the problem of enumerating all maximal $\rho $ -stable ( $\delta, \gamma $ )-quasi-cliques is NP-hard. To efficiently tackle our problem, we first devise a novel temporal graph reduction algorithm to significantly reduce the temporal graph without losing any maximal $\rho $ -stable ( $\delta, \gamma $ )-quasi-clique. Then, on the reduced temporal graph, we propose an effective branch and bound enumeration algorithm, named BB&SCM , with four carefully designed pruning techniques to accomplish the enumeration process. Finally, we conduct extensive experiments on seven real-world temporal graphs, and the results demonstrate that the temporal graph reduction algorithm can safely reduce 98% nodes of the temporal graph (with millions of nodes and edges) and BB&SCM is at least two orders of magnitude faster than the baseline algorithms. Moreover, we also evaluate the effectiveness of our model against other baseline models.

10 April 2024 in Expert Systems with Applications
Verified
Journal Article
Closed access
YHYue He
Yue He
LLLonglong Lin
Longlong Lin
PYPingpeng Yuan
Pingpeng Yuan
RLRonghua Li
Ronghua Li
TJTao Jia
Tao Jia
ZWZeli Wang
Zeli Wang

30 May 2024
Verified
Conference Paper
Open access
YYYunfeng Yu
Yunfeng Yu
LLLonglong Lin
Longlong Lin
QLQiyu Liu
Qiyu Liu
ZWZeli Wang
Zeli Wang
XOXi Ou
Xi Ou
Tao JiaTao Jia
Tao Jia
Graph Neural Networks (GNNs) have achieved remarkable performance in various applications, including social media analysis, computer vision, and natural language processing. Decoupled GNNs are a ubiquitous framework because of their high efficiency. However, existing decoupled GNNs suffer from the following several defects. (1) Their studies on GNN feature propagation are isolated, with each study emphasizing a user-specified propagation matrix. (2) They still have high computation costs to achieve provable performance on massive graphs with millions of nodes and billions of edges. (3) Their feature propagation steps are uniform, which makes it difficult for them to escape the dilemmas of over-smoothing. In this paper, we propose GSD-GNN, a Generalized and Scalable Decoupled GNN framework based on the spectral graph theory, which offers the following advantages. Firstly, through minor parameter adjustments, it can degenerate into most existing Decoupled GNNs, such as APPNP, GDC, SGC, etc. Secondly, it efficiently computes an arbitrary propagation matrix with near-linear time complexity and theoretical guarantees. Thirdly, it customizes the adaptive feature propagation mechanism for each node to mitigate the over-smoothing dilemma. Finally, extensive experiments on massive graphs demonstrate that the proposed GSD-GNN indeed is effective, scalable, and flexible.

9 February 2021 in IEEE Transactions on Big Data
Verified
Journal Article
Closed access
LLLonglong Lin
Longlong Lin
PYPingpeng Yuan
Pingpeng Yuan
RLRonghua Li
Ronghua Li
HJHai Jin
Hai Jin
Temporal subgraph mining is recently ubiquitous. Identifying diversified and lasting ingredients is a fundamental problem in analyzing temporal networks. In this paper, we investigate the problem of finding diversified lasting cohesive subgraphs from temporal networks. Specifically, we first introduce a new model, called maximal lasting (k, ρ)-core, for characterizing lasting cohesive subgraphs on temporal networks so as to the nodes in the subgraph are connected densely and also the subgraph's structure remains unchanged for a period of time. To enhance the diversity of results, we then formulate a diversified lasting cohesive subgraphs problem, which finds r maximal lasting (k, ρ)-cores with maximum coverage regarding the number of vertices and timestamps. Unfortunately, we show that the optimization problem is NP-hard. To tackle this issue, we first devise a greedy algorithm named GreLC with (1-1/e) approximation ratio. However, GreLC has prohibitively high time and space complexity, resulting in poor scalability. Then, an improved DFS-based search algorithm called TopLC with 1/4 approximation ratio is proposed to lower the computational cost. Finally, empirical studies on six real-world temporal networks demonstrate that the proposed solutions perform efficiently and accurately, and our model is better than temporal cohesive subgraphs detected by existing approaches.

8 April 2022
Verified
Book Chapter
Closed access
PDF file
YZYifei Zhang
Yifei Zhang
LLLonglong Lin
Longlong Lin
PYPingpeng Yuan
Pingpeng Yuan
HJHai Jin
Hai Jin

24 August 2024
Verified
Conference Paper
Open access
LLLonglong Lin
Longlong Lin
Tao JiaTao Jia
Tao Jia
ZWZeli Wang
Zeli Wang
JZJin Zhao
Jin Zhao
RLRonghua Li
Ronghua Li
Higher-order graph clustering aims to partition the graph using frequently occurring subgraphs (i.e., motifs), instead of the lower-order edges, as the atomic clustering unit, which has been recognized as the state-of-the-art solution in ground truth community detection and knowledge discovery. Motif conductance is one of the most promising higher-order graph clustering models due to its strong interpretability. However, existing motif conductance based graph clustering algorithms are mainly limited by a seminal two-stage reweighting computing framework, needing to enumerate all motif instances to obtain an edge-weighted graph for partitioning. However, such a framework has two-fold vital defects: (1) It can only provide a quadratic bound for the motif with three vertices, and whether there is provable clustering quality for other motifs is still an open question. (2) The enumeration procedure of motif instances incurs prohibitively high costs against large motifs or large dense graphs due to combinatorial explosions. Besides, expensive spectral clustering or local graph diffusion on the edge-weighted graph also makes existing methods unable to handle massive graphs with millions of nodes. To overcome these dilemmas, we propose a Provable and Scalable Motif Conductance algorithm PSMC, which has a fixed and motif-independent approximation ratio for any motif. Specifically, PSMC first defines a new vertex metric Motif Resident based on the given motif, which can be computed locally. Then, it iteratively deletes the vertex with the smallest motif resident value very efficiently using novel dynamic update technologies. Finally, it outputs the locally optimal result during the above iterative process. To further boost efficiency, we propose several effective bounds to estimate the motif resident value of each vertex, which can greatly reduce computational costs. Empirical results on real-life and synthetic demonstrate that our proposed algorithms achieve 3.2-32 times speedup and improve the quality by at least 12 times than the state-of-the art baselines.