2025-11-17T05:52:13.175509

Accelerated Evolving Set Processes for Local PageRank Computation

Huang, Luo, Xiao et al.
This work proposes a novel framework based on nested evolving set processes to accelerate Personalized PageRank (PPR) computation. At each stage of the process, we employ a localized inexact proximal point iteration to solve a simplified linear system. We show that the time complexity of such localized methods is upper bounded by $\min\{\tilde{\mathcal{O}}(R^2/ε^2), \tilde{\mathcal{O}}(m)\}$ to obtain an $ε$-approximation of the PPR vector, where $m$ denotes the number of edges in the graph and $R$ is a constant defined via nested evolving set processes. Furthermore, the algorithms induced by our framework require solving only $\tilde{\mathcal{O}}(1/\sqrtα)$ such linear systems, where $α$ is the damping factor. When $1/ε^2\ll m$, this implies the existence of an algorithm that computes an $\ epsilon $-approximation of the PPR vector with an overall time complexity of $\tilde{\mathcal{O}}\left(R^2 / (\sqrtαε^2)\right)$, independent of the underlying graph size. Our result resolves an open conjecture from existing literature. Experimental results on real-world graphs validate the efficiency of our methods, demonstrating significant convergence in the early stages.
academic

স্থানীয় PageRank গণনার জন্য ত্বরান্বিত বিবর্তনশীল সেট প্রক্রিয়া

মৌলিক তথ্য

  • পেপার আইডি: 2510.08010
  • শিরোনাম: Accelerated Evolving Set Processes for Local PageRank Computation
  • লেখক: Binbin Huang, Baojian Zhou, Luo Luo, Deqing Yang, Yanghua Xiao (ফুডান বিশ্ববিদ্যালয়)
  • শ্রেণীবিভাগ: cs.LG
  • প্রকাশিত সম্মেলন: 39th Conference on Neural Information Processing Systems (NeurIPS 2025)
  • পেপার লিঙ্ক: https://arxiv.org/abs/2510.08010v2

সারসংক্ষেপ

এই পেপারটি নেস্টেড বিবর্তনশীল সেট প্রক্রিয়া (nested evolving set processes) এর উপর ভিত্তি করে ব্যক্তিগতকৃত PageRank (PPR) গণনা ত্বরান্বিত করার জন্য একটি নতুন কাঠামো প্রস্তাব করে। প্রতিটি পর্যায়ে, সরলীকৃত রৈখিক সিস্টেম সমাধানের জন্য স্থানীয়করণ করা অনির্ভুল আনুমানিক পয়েন্ট পুনরাবৃত্তি ব্যবহার করা হয়। গবেষণা দেখায় যে এই ধরনের স্থানীয়করণ পদ্ধতির সময় জটিলতার উপরের সীমা হল min⁡{O~(R2/ε2),O~(m)}\min\{\tilde{\mathcal{O}}(R^2/ε^2), \tilde{\mathcal{O}}(m)\} যা PPR ভেক্টরের ε-আনুমানিকতা পেতে, যেখানে m গ্রাফের প্রান্তের সংখ্যা এবং R নেস্টেড বিবর্তনশীল সেট প্রক্রিয়া দ্বারা সংজ্ঞায়িত একটি ধ্রুবক। কাঠামো দ্বারা প্ররোচিত অ্যালগরিদম শুধুমাত্র O~(1/α)\tilde{\mathcal{O}}(1/\sqrt{α}) এই ধরনের রৈখিক সিস্টেম সমাধান করতে হয়, যেখানে α হল ড্যাম্পিং ফ্যাক্টর। যখন 1/ε2≪m1/ε^2 \ll m, এটি মানে একটি অ্যালগরিদম বিদ্যমান যা O~(R2/(αε2))\tilde{\mathcal{O}}(R^2/(\sqrt{α}ε^2)) মোট সময় জটিলতায় PPR ভেক্টরের ε-আনুমানিকতা গণনা করতে পারে, এবং এটি অন্তর্নিহিত গ্রাফ আকারের উপর স্বাধীন।

গবেষণা পটভূমি এবং প্রেরণা

সমস্যা সংজ্ঞা

ব্যক্তিগতকৃত PageRank (PPR) ভেক্টর π ∈ ℝⁿ সংজ্ঞায়িত হয় যেমন:

(I - (1-α)(I + AD⁻¹)/2)π = αeₛ

যেখানে eₛ উৎস নোড s এর সাথে সংশ্লিষ্ট মান ভেক্টর, α ∈ (0,1) হল ড্যাম্পিং ফ্যাক্টর, এবং A এবং D যথাক্রমে অনির্দেশিত গ্রাফ G(V,E) এর সংলগ্ন ম্যাট্রিক্স এবং ডিগ্রি ম্যাট্রিক্স।

গবেষণা প্রেরণা

  1. গুরুত্ব: PPR গ্রাফ বিশ্লেষণের একটি মূল সরঞ্জাম, যা স্থানীয় ক্লাস্টারিং, বিস্তার প্রক্রিয়া মডেলিং, গ্রাফ নিউরাল নেটওয়ার্ক ইত্যাদিতে ব্যাপকভাবে প্রয়োগ করা হয়
  2. বিদ্যমান সীমাবদ্ধতা:
    • APPR এর মতো মান পদ্ধতির সময় জটিলতা O(1/(αε))
    • ত্বরান্বিত পদ্ধতি গতিবেগ পদ অবশিষ্টাংশ একঘেয়েত্ব ভাঙার চ্যালেঞ্জের সম্মুখীন
    • বিদ্যমান ত্বরান্বিত পদ্ধতি সম্পূর্ণ গ্রাফ অ্যাক্সেস করতে পারে, যার ফলে O(m/√α) সময় জটিলতা
  3. খোলা প্রশ্ন: এমন কোনো স্থানীয় ত্বরান্বিত পদ্ধতি বিদ্যমান যার সময় জটিলতা 1/α এর পরিবর্তে 1/√α এর উপর নির্ভর করে?

মূল অবদান

  1. AESP কাঠামো: ত্বরান্বিত বিবর্তনশীল সেট প্রক্রিয়া (AESP) কাঠামো প্রস্তাব করে, যা একটি দীর্ঘ প্রক্রিয়ার পরিবর্তে O~(1/α)\tilde{O}(1/\sqrt{α}) সংক্ষিপ্ত বিবর্তনশীল সেট প্রক্রিয়া ব্যবহার করে
  2. তাত্ত্বিক গ্যারান্টি: O~(vol(St)/(αγt))\tilde{O}(\text{vol}(S_t)/(\sqrt{α}γ_t)) সময় জটিলতা প্রতিষ্ঠা করে, যা বিদ্যমান সাহিত্যে ত্বরান্বিত সীমানা অনুমান মেলে
  3. স্থানীয়তা গ্যারান্টি: প্রমাণ করে যে vol(St)/γt\text{vol}(S_t)/γ_t এর উপরের সীমা হল min⁡{O(R2/ε2),2m}\min\{O(R^2/ε^2), 2m\}, যখন 1/ε2≪m1/ε^2 \ll m গ্রাফ আকারের সাথে স্বাধীন জটিলতা অর্জন করে
  4. পরীক্ষামূলক যাচাইকরণ: বড় আকারের বাস্তব গ্রাফে পদ্ধতির কার্যকারিতা যাচাই করে, প্রাথমিক পর্যায়ে উল্লেখযোগ্য ত্বরণ প্রদর্শন করে

পদ্ধতি বিস্তারিত

কাজের সংজ্ঞা

নির্ভুলতা প্যারামিটার ε দেওয়া, ε-আনুমানিক π̂ গণনা করার জন্য স্থানীয় অ্যালগরিদম ডিজাইন করুন, যা ∥D−1(π^−π)∥∞≤ε\|D^{-1}(π̂ - π)\|_∞ ≤ ε সন্তুষ্ট করে, একই সাথে সম্পূর্ণ গ্রাফ অ্যাক্সেস এড়ায়।

মূল ধারণা: নেস্টেড বিবর্তনশীল সেট প্রক্রিয়া

1. সমস্যা পুনর্গঠন

রৈখিক সিস্টেমকে দৃঢ়ভাবে উত্তল অপ্টিমাইজেশন সমস্যায় পুনর্গঠন করুন:

min f(x) = (1/2)x⊤Qx - αx⊤D^(-1/2)b

যেখানে Q = ((1+α)/2)I - ((1-α)/2)D^(-1/2)AD^(-1/2), বৈশিষ্ট্য মান λ(Q) ∈ α,1।

2. নেস্টেড ESP সংজ্ঞা

বাহ্যিক লুপ পুনরাবৃত্তি t তে, স্থানীয় সমাধানকারী M অভ্যন্তরীণ লুপ পুনরাবৃত্তি k এ সক্রিয় সেট অনুক্রম {S_t^(k)}_{k≥0} বজায় রাখে, আপডেট শুধুমাত্র সক্রিয় সেটের মধ্যে নোডে সীমাবদ্ধ।

3. AESP আপডেট নিয়ম

x^(t) = M(φ_t, y^(t-1), η, α, b, G)
y^(t) = x^(t) + β_t(x^(t) - x^(t-1))

যেখানে β_t গতিবেগ ওজন, M হল স্থানীয় অপারেটর।

স্থানীয়করণ করা অনির্ভুল আনুমানিক অপারেটর

LOCGD (স্থানীয় গ্রেডিয়েন্ট ডিসেন্ট)

z_t^(k+1) = z_t^(k) - (2∇h_t(z_t^(k)) ∘ 1_{S_t^k})/(1 + α + 2η)

সক্রিয় নোড সেট: Stk={u:∣∇uht−1/2(zt(k))∣≥εt}S_t^k = \{u : |∇_u h_t^{-1/2}(z_t^{(k)})| ≥ ε_t\}

LOCAPPR (স্থানীয় APPR)

ui∈Stku_i ∈ S_t^k এর জন্য স্থানাঙ্ক-স্তরের আপডেট:

z_t^(k_{i+1}) = z_t^(k_i) - (2∇h_t(z_t^{(k_i)}) ∘ 1_{u_i})/(1 + α + 2η)

প্রযুক্তিগত উদ্ভাবন পয়েন্ট

  1. একঘেয়েত্ব সংরক্ষণ: ধ্রুবক শর্ত সংখ্যার সাথে নিয়মিত PPR রৈখিক সিস্টেম সমাধান করে, D^{1/2}-স্কেল করা গ্রেডিয়েন্টের ℓ₁ নর্মের একঘেয়েত্ব নিশ্চিত করে
  2. স্থানীয়তা নিয়ন্ত্রণ: নেস্টেড ESP প্রক্রিয়ায় গ্রেডিয়েন্ট অনুপাতের সীমাবদ্ধতা সংজ্ঞায়িত করতে ধ্রুবক R প্রবর্তন করে
  3. ত্বরণ এবং স্থানীয়তা ভারসাম্য: শর্ত সংখ্যা 1/α এর নির্ভরতা এবং প্রতি রাউন্ড সময় জটিলতা O(R²/ε²) এর মধ্যে ভারসাম্য অর্জন করে

পরীক্ষামূলক সেটআপ

ডেটাসেট

পরীক্ষা 19টি বাস্তব বিশ্বের গ্রাফ ব্যবহার করে, ছোট থেকে অতি বড় আকারের:

  • মাঝারি আকার: com-dblp (317K নোড, 1M প্রান্ত)
  • বড় আকার: ogb-mag240m (244M নোড, 1.7B প্রান্ত), ogbn-papers100M (111M নোড, 1.6B প্রান্ত)
  • অন্যান্য: com-friendster, wiki-en21 ইত্যাদি

মূল্যায়ন মেট্রিক্স

  • ত্রুটি পরিমাপ: log⁡∥D−1(π^−π)∥∞\log \|D^{-1}(π̂-π)\|_∞
  • দক্ষতা পরিমাপ: অপারেশন সংখ্যা, চলমান সময়
  • ত্বরণ অনুপাত: বেসলাইন পদ্ধতির তুলনায় কর্মক্ষমতা উন্নতি

তুলনা পদ্ধতি

  • APPR: মান আনুমানিক ব্যক্তিগতকৃত PageRank অ্যালগরিদম
  • APPR-opt: সর্বোত্তম পদক্ষেপ আকার সহ APPR
  • LOCGD: স্থানীয় গ্রেডিয়েন্ট ডিসেন্ট
  • ASPR: ত্বরান্বিত বিরল ব্যক্তিগতকৃত PageRank
  • FISTA: দ্রুত পুনরাবৃত্ত সংকোচন থ্রেশহোল্ড অ্যালগরিদম

বাস্তবায়ন বিবরণ

  • ড্যাম্পিং ফ্যাক্টর: α = 0.01, 0.1
  • নির্ভুলতা থ্রেশহোল্ড: ε = 10⁻⁶
  • 5টি উৎস নোড র্যান্ডমভাবে নির্বাচন করে পরীক্ষা করা
  • Python বাস্তবায়ন, numba ত্বরণ ব্যবহার করে

পরীক্ষামূলক ফলাফল

প্রধান ফলাফল

বড় আকারের গ্রাফ কর্মক্ষমতা

চারটি বড় আকারের গ্রাফে (ogb-mag240m, ogbn-papers100M, com-friendster, wiki-en21):

  • AESP-LOCAPPR সেরা পারফরম্যান্স, অনলাইন স্থানাঙ্ক আপডেটের কারণে
  • প্রাথমিক ত্বরণ: AESP পদ্ধতি প্রাথমিক পর্যায়ে বেসলাইন পদ্ধতির চেয়ে দ্রুত সংমিশ্রণ অর্জন করে
  • অপারেশন হ্রাস: APPR এর তুলনায় 2-10 গুণ অপারেশন হ্রাস

α নির্ভরতা বিশ্লেষণ

যখন α ছোট হয়, AESP মান স্থানীয় পদ্ধতি উল্লেখযোগ্যভাবে ত্বরান্বিত করে:

  • α ∈ 10⁻³, 10⁻¹ পরিসরে পরীক্ষা করা
  • ত্বরণ অনুপাত α হ্রাসের সাথে বৃদ্ধি পায়, √α নির্ভরতা যাচাই করে
  • চলমান সময় এবং অপারেশন সংখ্যা উভয়ই উল্লেখযোগ্যভাবে হ্রাস পায়

প্রাথমিক কৌশল তুলনা

তিনটি প্রাথমিক কৌশলের তুলনা z_t^(0):

  1. ঠান্ডা শুরু: z_t^(0) = 0
  2. পূর্ববর্তী অনুমান: z_t^(0) = x^(t-1)
  3. গতিবেগ প্রাথমিকীকরণ: z_t^(0) = y^(t-1) (সুপারিশকৃত)

গতিবেগ প্রাথমিকীকরণ কৌশল সেরা পারফরম্যান্স করে, সবচেয়ে কম বাহ্যিক লুপ পুনরাবৃত্তি প্রয়োজন।

অপসারণ পরীক্ষা

ধ্রুবক R এর বিশ্লেষণ

  • 19টি গ্রাফে R ছোট ধ্রুবক (1.0-1.4) হিসাবে থাকে
  • R গ্রাফ আকার এবং শর্ত সংখ্যার প্রতি সংবেদনশীল নয়
  • তাত্ত্বিক বিশ্লেষণে R সীমাবদ্ধ অনুমানের যুক্তিযুক্ততা যাচাই করে

vol(S_t)/γ_t অনুপাত বিশ্লেষণ

পরীক্ষা যাচাই করে যে vol(St)/γt≤min⁡{Ct0/εt,2m}\text{vol}(S_t)/γ_t ≤ \min\{C_t^0/ε_t, 2m\} তাত্ত্বিক সীমানা।

সম্পর্কিত কাজ

PPR গণনা পদ্ধতি

  • পুনরাবৃত্তিমূলক পদ্ধতি: সংযুক্ত গ্রেডিয়েন্ট, Chebyshev পদ্ধতি, জটিলতা O(m/√α)
  • স্থানীয় পদ্ধতি: APPR (O(1/(αε))), পরিবর্তনশীল পদ্ধতি (O(1/((α+μ²)ε)))
  • ত্বরণ প্রচেষ্টা: FISTA, রৈখিক সংযোগ একঘেয়েত্ব ভাঙে, স্থানীয়তা গ্যারান্টি দিতে পারে না

বিবর্তনশীল সেট প্রক্রিয়া

  • Morris এবং Peres দ্বারা প্রস্তাবিত ধারণা, মিশ্রণ সময় বিশ্লেষণের জন্য ব্যবহৃত
  • Zhou ইত্যাদির স্থানীয়করণ করা Chebyshev পদ্ধতি, কিন্তু সংমিশ্রণ গ্যারান্টি অভাব

ত্বরান্বিত অপ্টিমাইজেশন

  • Catalyst কাঠামো: অনির্ভুল ত্বরান্বিত প্রক্সিমাল পয়েন্ট পদ্ধতি
  • এই পেপার এটি স্থানীয় পদ্ধতিতে অভিযোজিত করে, একঘেয়েত্ব সংরক্ষণ করে

উপসংহার এবং আলোচনা

প্রধান উপসংহার

  1. তাত্ত্বিক অগ্রগতি: PPR গণনার প্রথম প্রমাণযোগ্য স্থানীয় ত্বরণ অর্জন করে, সময় জটিলতা O(1/α) থেকে O(1/√α) এ উন্নত করে
  2. ব্যবহারিকতা: যখন ε ≥ 1/√m, অ্যালগরিদম জটিলতা গ্রাফ আকারের সাথে স্বাধীন
  3. সর্বজনীনতা: কাঠামো পরিবর্তনশীল ফর্ম এবং অন্যান্য সম্পর্কিত সমস্যায় প্রসারিত করা যায়

সীমাবদ্ধতা

  1. ধ্রুবক R সীমানা: গ্রাফ আকার বা ইনপুট প্যারামিটার দ্বারা R সর্বজনীনভাবে সীমাবদ্ধ করা যায় না
  2. ε² নির্ভরতা: যখন ε < 1/√m, স্থানীয় সীমানা O(m/√α) এ অবনমিত হয়
  3. তাত্ত্বিক এবং ব্যবহারিক ব্যবধান: ε_t এর রক্ষণশীল অনুমান সাব-অপ্টিমাল সীমানা হতে পারে

ভবিষ্যত দিকনির্দেশনা

  1. উন্নত সীমানা: অনুসন্ধান করুন যে অনুমান করা O(1/(√αε)) জটিলতা অর্জনযোগ্য কিনা
  2. R নির্ভরতা দূর করুন: সীমাবদ্ধতা বা স্ব-অভিযোজিত পুনরায় শুরু মাধ্যমে ধ্রুবক R দূর করুন
  3. সম্প্রসারণ প্রয়োগ: দ্বিমুখী PPR, একক-উৎস PPR অনুমান ইত্যাদি সমস্যায় কৌশল প্রয়োগ করুন

গভীর মূল্যায়ন

শক্তি

  1. উল্লেখযোগ্য তাত্ত্বিক অবদান: সাহিত্যে খোলা অনুমান সমাধান করে, কঠোর তাত্ত্বিক গ্যারান্টি প্রতিষ্ঠা করে
  2. শক্তিশালী পদ্ধতি উদ্ভাবন: Catalyst কাঠামো এবং স্থানীয় বিবর্তনশীল সেট প্রক্রিয়া চতুরভাবে একত্রিত করে
  3. ব্যাপক পরীক্ষা: 19টি বিভিন্ন আকারের গ্রাফে যাচাই করে, ছোট থেকে অতি বড় গ্রাফ
  4. স্পষ্ট লেখা: গাণিতিক অনুমান কঠোর, অ্যালগরিদম বর্ণনা বিস্তারিত

অপূর্ণতা

  1. ব্যবহারিক সীমাবদ্ধতা: যখন ε খুব ছোট সুবিধা স্পষ্ট নয়, R সীমাবদ্ধতা সমস্যা ব্যবহারিক প্রয়োগ প্রভাবিত করে
  2. বাস্তবায়ন জটিলতা: নেস্টেড কাঠামো এবং প্যারামিটার টিউনিং বাস্তবায়ন কঠিনতা বৃদ্ধি করে
  3. অসম্পূর্ণ তুলনা: সর্বশেষ ত্বরান্বিত পদ্ধতির সাথে বিস্তারিত তুলনা অভাব

প্রভাব

  1. একাডেমিক মূল্য: গ্রাফ অ্যালগরিদম ত্বরণের জন্য নতুন চিন্তাভাবনা প্রদান করে, তাত্ত্বিক তাৎপর্য বড়
  2. ব্যবহারিক মূল্য: বড় আকারের গ্রাফ বিশ্লেষণ, সুপারিশ সিস্টেম ইত্যাদিতে প্রয়োগ সম্ভাবনা
  3. পুনরুৎপাদনযোগ্যতা: কোড প্রকাশ্য, পরীক্ষামূলক সেটআপ বিস্তারিত

প্রযোজ্য দৃশ্যকল্প

  1. বড় আকারের গ্রাফ বিশ্লেষণ: বিশেষত যখন নির্ভুলতা প্রয়োজন অত্যন্ত উচ্চ নয় (ε ≥ 1/√m)
  2. রিয়েল-টাইম সুপারিশ সিস্টেম: নোড গুরুত্ব স্কোর দ্রুত গণনা প্রয়োজন
  3. গ্রাফ নিউরাল নেটওয়ার্ক: প্রাক-প্রক্রিয়াকরণ পদক্ষেপ হিসাবে নোড গুরুত্ব গণনা করতে

সংদর্ভ

এই পেপার 52টি সম্পর্কিত সংদর্ভ উদ্ধৃত করে, PPR গণনা, ত্বরান্বিত অপ্টিমাইজেশন, স্থানীয় অ্যালগরিদম ইত্যাদি একাধিক ক্ষেত্রের গুরুত্বপূর্ণ কাজ অন্তর্ভুক্ত করে, গবেষণার জন্য দৃঢ় তাত্ত্বিক ভিত্তি প্রদান করে।

সামগ্রিক মূল্যায়ন: এটি একটি উচ্চ মানের তাত্ত্বিক এবং ব্যবহারিক সমন্বয়ের পেপার, PPR গণনা ত্বরণের এই গুরুত্বপূর্ণ সমস্যায় উল্লেখযোগ্য অগ্রগতি অর্জন করেছে। যদিও কিছু তাত্ত্বিক সীমাবদ্ধতা বিদ্যমান, এর উদ্ভাবনী এবং ব্যবহারিক মূল্য এটিকে এই ক্ষেত্রের একটি গুরুত্বপূর্ণ অবদান করে তোলে।