שיטות מומלצות להפעלת אלגוריתמים ב-Spanner Graph

במסמך הזה מתוארות שיטות מומלצות להפעלת אלגוריתמים ב-Spanner Graph. הנושאים במאמר:

שיטות מומלצות לשימוש בסכימת גרף באלגוריתמים

אם אתם משתמשים בתוויות ומאפיינים מותאמים אישית ב-Spanner Graph, מומלץ תמיד לחשוף מפתחות של אלמנטים כמאפיינים. כך תוכלו לגשת למאפייני המפתח האלה בסעיף RETURN של שאילתת האלגוריתם, ולהשתמש בהם כדי לזהות את רכיב הגרף שעבורו האלגוריתם יוצר פלט.

טיפול בפלט של אלגוריתם

בקטע הזה מפורטות המלצות לגבי מה להחזיר מהפלט של האלגוריתם, ואיפה לשמור את התוצאות שהוחזרו.

מה להחזיר

כשחתימת הפלט של האלגוריתם מכילה רכיבי גרף, Spanner Graph מאפשר להחזיר כל מאפיין של הרכיבים האלה. כדי להפחית את עלות העיבוד, מומלץ לצמצם את רשימת הנכסים שיוחזרו. לדוגמה, אפשר להחזיר רק מאפיינים שהם מפתחות של אלמנט, כי המפתחות נחוצים כדי לזהות את האלמנט.

איפה לשמור את הנתונים

ב-Spanner Graph אפשר לשמור את תוצאת השאילתה של האלגוריתם ב-Cloud Storage או בחזרה לאותו מופע של Spanner Graph שבו התחלתם את השאילתה.

העברה חזרה ל-Spanner מאפשרת לכל הפעולות ב-Spanner לגשת באופן מקורי לפלט של האלגוריתם. לדוגמה, אפשר להריץ את הפקודה WeaklyConnectedComponent, לשמור את cluster_id בחזרה לגרף. לאחר מכן, מריצים את הפקודה PageRank עבור תרשים קלט עם cluster_id ספציפי. תכונות של Spanner כמו Change Stream מעבירות פלט של אלגוריתמים חדשים למערכות במורד הזרם. אם רוצים להשתמש בתוצאות של אלגוריתם ב-Spanner, מומלץ לשמור אותן ב-Spanner. למרות ש-Spanner Graph משתמש בדרכים יעילות לאגור נתונים (batch) ולשמור את פלט האלגוריתם ב-Spanner, כל פעולות הכתיבה חייבות לעבור דרך העותק המשוכפל של המוביל. אם כבר יש לכם עומסי עבודה קריטיים שתופסים את קיבולת המנהיג, כדאי להריץ את האלגוריתמים לסירוגין כדי למנוע תחרות עם עומסי עבודה קריטיים.

אם אתם לא מתכננים להשתמש בפלט של האלגוריתם ב-Spanner או שאתם רוצים לבדוק את הפלט של האלגוריתם לפני שאתם מטמיעים אותו במקור הנתונים הראשי, כדאי לשמור את הפלט ב-Cloud Storage. לרשימת הפורמטים הנתמכים של קבצים

שיקולים לגבי מודלים של נתונים לשיפור הגרף

בקטע הזה נדון בכמה שיקולים לגבי מידול נתונים כששומרים את הפלט של האלגוריתם ב-Spanner.

מאפיינים לעומת קצוות

אלגוריתמים יכולים להפיק מגוון תובנות, כולל:

  • מדדים ברמת הצומת (לדוגמה, ציון מרכזיות). אפשר לשמור אותן כמאפיינים חדשים בצומת.
  • תובנות לגבי זוגות (לדוגמה, דמיון בין שני צמתים). אפשר לשמור אותם כקשתות חדשות בין שני הצמתים, עם ערך הפלט כמאפיין של הקשת.
  • אלגוריתמים לזיהוי קהילות מזהים קהילות לוגיות בתרשים ויכולים להקצות קהילה אחת או יותר לצומת נתון. אפשר להגדיר את חברות הקהילה כמאפיין חדש בצומת על ידי תיוג כל צומת של חבר עם המזהה של הקהילה שאליה הוא משויך. אפשר גם ליצור מודל של חברות בקהילה בתור תתי-גרפים חדשים, ולאחסן את הקהילות הלוגיות בתור סוג חדש של צמתים בגרף, עם קצוות שמקשרים אותם לצמתים של חברים. מאפיין הקהילה יכול להספיק אם רוצים לדעת לאיזו קהילה צומת שייך כשניגשים לצומת. גרף המשנה של הקהילה עשוי להתאים יותר כשרוצים לנווט לפי קהילה (לדוגמה, למצוא צמתים באותה קהילה כמו צומת התחלתי). בהתאם לאופן שבו אתם מתכננים להשתמש במידע מהקהילה, אתם יכולים לבחור באפשרות אחת או בשתי האפשרויות.

סכימה מוגדרת מראש לעומת סכימה גמישה

לפני ששומרים את הפלט של האלגוריתם בחזרה ל-Spanner, צריך להגדיר את עמודת היעד או הטבלה בסכימה באחת מהדרכים הבאות:

  • אם מקרי השימוש באלגוריתם יציבים ומוכרים, אפשר להוסיף מראש עמודות או טבלאות נוספות.
  • אם אתם מבצעים איטרציות ומתנסים בדרכים שונות לחילוץ תובנות (לדוגמה, מנסים אלגוריתמים, פרמטרים וגרפים משניים שונים של קלט), יכול להיות שתרצו דרך גמישה לשמירה של פלט מכמה ניסויים ולהבחנה ביניהם, בלי לעדכן את סכימת Spanner בכל הפעלה. במקרה כזה, אפשר לשקול לאחסן מאפיינים וקצוות חדשים שנוצרו על ידי אלגוריתמים בטבלאות צאצא גנריות.

כדי לאחסן מאפיינים וקצוות חדשים שנוצרו על ידי אלגוריתמים בטבלאות צאצא גנריות, פועלים לפי השלבים הבאים:

שלב 1: יצירת טבלאות צאצא גנריות

-- Create `AccountAlgoProperty` as a child table of `Account`, to store all
-- properties produced by algorithms for `Account`.
-- `algo_run_id`: a unique ID for a given algorithm run.
-- `int_val`: column to store integer algorithm output.
-- `float_val`: column to store float algorithm output.
CREATE TABLE AccountAlgoProperty (
 id INT64 NOT NULL,
 algo_run_id STRING(200) NOT NULL,
 int_val INT64,
 float_val FLOAT64
) PRIMARY KEY(id, algo_run_id),
 INTERLEAVE IN PARENT Account;

-- Create `AccountAlgoEdge` as a child table of `Account`, to store all
-- outgoing edges produced by algorithms for `Account`.
-- `algo_run_id`: a unique ID for a given algorithm run.
-- `to_id`: destination `Account` id.
-- `int_val`: column to store integer algorithm output.
-- `float_val`: column to store float algorithm output.
CREATE TABLE AccountAlgoEdge (
 id INT64 NOT NULL,
 algo_run_id STRING(200) NOT NULL,
 to_id INT64 NOT NULL,
 int_val INT64,
 float_val FLOAT64,
 CONSTRAINT FK_AccountId FOREIGN KEY (to_id) REFERENCES Account (id) NOT ENFORCED,
) PRIMARY KEY(id, algo_run_id, to_id),
 INTERLEAVE IN PARENT Account;

שלב 2: מאחסנים את המאפיינים והקצוות שנוצרו על ידי האלגוריתמים כשורות בטבלת הצאצא, יחד עם algo_run_id הייחודי שיצר אותם.

-- Store PageRank score as property in child table.
EXPORT DATA
 OPTIONS (format = "CLOUD_SPANNER",
          table = "AccountAlgoProperty",
          write_mode = 'upsert_ignore_all' ) AS
GRAPH FinGraph
CALL PageRank(node_labels => ['Account'], edge_labels => ['Transfers'])
RETURN node.id, "page_rank_123" AS algo_run_id, score As float_val;

-- Store ShortestPath output as edge in child table.
EXPORT DATA
 OPTIONS (format = "CLOUD_SPANNER",
          table = "AccountAlgoEdge",
          write_mode = 'upsert_ignore_all' ) AS
GRAPH FinGraph
CALL ShortestPath(
    source_nodes => ARRAY {
                      MATCH (n:Account {id: 7})
                      RETURN n
                    },
    target_nodes => ARRAY {
                      MATCH (n:Account {id: 16})
                      RETURN n
                    }
  ) YIELD source_node, target_node, path, cost
RETURN source_node.id AS id, "shortest_path_456" AS algo_run_id,
  target_node.id AS to_id, PATH_LENGTH(path) AS int_val, cost AS float_val;

שלב 3: גישה לפלט של האלגוריתם באמצעות GRAPH_TABLE

SELECT acct.id, prop.float_val AS page_rank_score
FROM GRAPH_TABLE(
  FinGraph
  MATCH (n:Account)
  RETURN n.id
) acct JOIN AccountAlgoProperty prop ON acct.id = prop.id
  AND prop.algo_run_id = 'page_rank_123';

SELECT acct.id, edge.to_id, edge.int_val AS path_len, edge.float_val AS cost
FROM GRAPH_TABLE(
  FinGraph
  MATCH (n:Account)
  RETURN n.id
) acct JOIN AccountAlgoEdge edge ON acct.id = edge.id
  AND edge.algo_run_id = 'shortest_path_456';

שלב 4: אופציונלית, יוצרים גרף לוגי עם מאפיינים וקצוות שנוצרו על ידי אלגוריתם כדי להקל על הגישה לפלט של האלגוריתם.

-- Create a view that aggregates non-null algorithm properties per node into
-- name-value pairs in JSON.
CREATE OR REPLACE VIEW AccountWithAlgoProperties SQL SECURITY INVOKER AS
SELECT
  n.id, ANY_VALUE(n.create_time) AS create_time,
  ANY_VALUE(n.is_blocked) AS is_blocked, ANY_VALUE(n.nick_name) AS nick_name,
  JSON_OBJECT(
    IF(COUNT(c.algo_run_id) = 0, [], ARRAY_AGG(c.algo_run_id)),
    IF(COUNT(c.algo_run_id) = 0, [], ARRAY_AGG(
      COALESCE(
        IF (c.int_val IS NULL, NULL, TO_JSON(c.int_val)),
        IF (c.float_val IS NULL, NULL, TO_JSON(c.float_val))
      )))) AS algo_props
FROM Account AS n LEFT JOIN AccountAlgoProperty AS c ON n.id = c.id
GROUP BY n.id;

-- Create FinGraphAugmented with algorithm generated properties and edges.
CREATE OR REPLACE PROPERTY GRAPH FinGraphAugmented
  NODE TABLES (
    AccountWithAlgoProperties AS Account
      KEY(id)
      LABEL Account PROPERTIES(
        create_time,
        id,
        is_blocked,
        nick_name,
        algo_props),
    Person
  )
  EDGE TABLES (
    PersonOwnAccount
      SOURCE KEY (id) REFERENCES Person (id)
      DESTINATION KEY (account_id) REFERENCES Account (id)
      LABEL Owns,
    AccountTransferAccount
      SOURCE KEY (id) REFERENCES Account (id)
      DESTINATION KEY (to_id) REFERENCES Account (id)
      LABEL Transfers,
    AccountAlgoEdge
      SOURCE KEY (id) REFERENCES Account (id)
      DESTINATION KEY (to_id) REFERENCES Account (id)
  );

לאחר מכן אפשר לגשת ישירות למאפייני האלגוריתם ולעבור בין הקצוות שנוצרו על ידי האלגוריתם בשאילתת גרף:

-- Retrieve PageRank score property in graph query.
GRAPH FinGraphAugmented
MATCH (a:Account)
RETURN a.id, a.algo_props.page_rank_123 AS page_rank
ORDER BY page_rank DESC
LIMIT 5;

-- Navigate through ShortestPath edge in graph query.
GRAPH FinGraphAugmented
MATCH (s:Account {id: 7})-[e:AccountAlgoEdge {algo_run_id : 'shortest_path_456'}]->(d:Account)
RETURN s.id AS src, d.id AS dst, e.int_val AS path_len, e.float_val AS cost

ציון machine_category לעומסי עבודה גדולים

ברוב עומסי העבודה, קטגוריית המכונה default מתאימה. אם גרף הקלט מכיל יותר ממיליארד צמתים ויותר מ-10 מיליארד קשתות, מומלץ לבחור במפורש באפשרות large עבור machine_category.

שימוש חוזר במשאבי מחשוב לאיטרציה מהירה

אם אתם עורכים ניסויים עם אלגוריתמים שונים או עם פרמטרים שונים של קלט במערכי נתונים קטנים כדי לבצע איטרציה מהירה, מומלץ להשתמש ב-max_idle_time. גרף Spanner גדול יותר מאפשר לכם לעשות שימוש חוזר במשאבי מחשוב שכבר הוקצו לעומסי עבודה של אלגוריתמים נוספים.max_idle_time כך מצמצמים את התקורה של הפעלת מחשוב לפי דרישה ומפחיתים את הסיכון שלא תהיה אפשרות להקצות מחשוב בגלל חוסר זמני בקיבולת. שימו לב: חיוב על חישוב אלגוריתם מתבצע גם כשהוא לא פעיל.

הבחנה בין סוגי רכיבים בפלט

אם הפלט של האלגוריתם מכיל כמה סוגים של רכיבים, כדאי לכלול את ELEMENT_DEFINITION_NAME בפלט כדי להבדיל ביניהם. לדוגמה:

EXPORT DATA OPTIONS (
  uri = "gs://bucket-name/page_rank.csv",
  format = "csv",
  overwrite = TRUE) AS
GRAPH FinGraph
CALL PageRank()
YIELD node, score
RETURN ELEMENT_DEFINITION_NAME(node) AS node_type, node.id, score;

המאמרים הבאים